# Question
Title: Can a program exist that halts only if it can prove that it doesn't halt?
Consider a program P that enumerates possible proofs in some proof system and halts only if it finds a valid proof that P does not halt. Clearly no such proof exists, or the program would eventually find it, causing a contradiction. But that argument itself appears to constitute exactly such a proof. It seems like that means that P cannot exist (for proof systems sufficiently powerful to express that argument), but I can't otherwise see why that should be the case.

# Answer
We can define a sound proof system as a computable function $\Pi$ which maps strings (proofs) to strings (statements proved), with the following property: if $\Pi(\pi) = p$, then $p$ encodes a true statement. We think of $\pi$ as a proof of $p$. (If $\pi$ is not a valid proof, then $\Pi$ outputs some fixed true statement.) We consider sound proof systems which are rich enough to prove statements about the halting of Turing machines.

Let $Q(q)$ be the program that enumerates over all strings, and halts if it ever finds a string $\pi$ such that $\Pi(\pi) = p$, where $p$ is an encoding of "The Turing machine encoded by $q$ never halts when run on $q$". Let $\[Q\]$ be an encoding of $Q$. If we run $Q$ on $\[Q\]$, then $Q$ halts iff there is a $\Pi$-proof that $Q$ doesn't halt when running on $\[Q\]$.

(Using the recursion theorem, we can transform $Q$ to a Turing machine $P$ which runs $Q$ on $\[P\]$, which is the setup in the original post.)

If there is a $\Pi$-proof that $Q$ doesn't halt when running on $\[Q\]$, then $Q$ doesn't halt when running on $\[Q\]$. We conclude that there cannot be any $\Pi$-proof that $Q$ doesn't halt when running on $\[Q\]$, because if such a $\Pi$-proof existed, then $Q$ would halt when running on $\[Q\]$. Therefore $Q$ doesn't halt when running on $\[Q\]$. However, there is no $\Pi$-proof of this fact.

This is an example of incompleteness. The proof system $\Pi$ is unable to formalize the argument above. One reason is that $\Pi$ cannot even prove its own consistency (i.e., that it does not prove a contradiction, as per Gödel's second incompleteness theorem), not to say soundness (which $\Pi$ may not even be able to express).
> 20 votes

# Answer
Your program P may halt if the proof system it is using is inconsistent, allowing it to prove a self-contradictory statement.

The fact that no (sufficiently expressive) proof system can prove its own consistency is exactly what is shown by Gödel's second incompleteness theorem (which, not coincidentally, is in many ways analogous to Turing's halting theorem).

So, in short, your program P will never halt *if* the proof system it uses is consistent. But that's not something P, or anything else using the same proof system, can prove.

Nor, for that matter, can we definitely and objectively prove that *any* sufficiently complex proof system is consistent, since the only way to do that would be using a "meta-proof" in some other, more powerful proof system whose consistency we would then also need to prove…

In fact, if the proof system used by P features the principle of explosion, which allows deducing any statement from a contradiction, then P will halt *if and only if* that proof system is inconsistent — since if it is, P will eventually find a proof that first proves a contradictory statement and then deduces "P does not halt" from it. Or at least that's what P will do if it indeed correctly enumerates and evaluates all valid proofs in the system, which is something that we again cannot prove in general without making use of some proof system subject to the incompleteness theorem.
> 9 votes

# Answer
Succinctly, your argument (that there is no such proof that P does not halt) is a proof but **not** in the same proof system that P is using to search for proofs! In fact, this very kind of computability-based argument can be used to great effect to prove the generalized incompleteness theorems, even the Rosser strengthening.
> 6 votes

---
Tags: halting-problem
---


# Question
Title: How to show that this problem is NP-hard: Find two subsets of 2 given sets such that the difference between the subset sums is $\leq v$
As input, given two finite sets of integers $X = \\{x\_1,...,x\_m\\}$, $Y = \\{y\_1,...,y\_n\\} \subseteq Z$, and a non-negative integer $v ≥ 0$. The goal is to decide if there are non-empty subsets $S ⊆ \[m\]$ and $T ⊆ \[n\]$ such that

$$ \left|\sum\_{i\in S}x\_i-\sum\_{j\in T} y\_j\right| \leq v$$

How to show this problem is NP-hard? I'm quite confused. What I got so far is to reduce from subset sum problems, since the form is set to less than v. So I need to have 2v+1 subset sum problems to verify

# Answer
The special case where $v=0$ and $Y=\\{\frac12\sum\_{i=1}^m x\_i\\}$ is the partition problem, which is NP-complete.
> 2 votes

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


# Question
Title: Is the following problem NP-hard? (or have you seen it before?)
I genuinely don't know if the following problem is NP-hard. I have never seen it mentioned online, but it's hard to even search for exact problems like this. I have been trying to find an efficient algorithm for a while and intuitively it feels very NP-complete to me, but I haven't been able to prove it. A solution would be directly applicable to my work, if it could be found.

---

**Problem:** Assume you have $N$ different tasks which each have a unique integer length $l\_n$. These tasks are arranged in a dependency tree so that each task can only be started after zero or more other tasks are completed. You also have $M$ different resources. Each task requires a given resource and each resource can only be used by one task at a time. What ordering of tasks allows for the fastest completion of the overall program (based on maximizing the amount of tasks that can be parallelized).

**Example:** In less abstract terms, imagine that each task is a step in a recipe. The resources are elements of a kitchen like an oven or mixer. If cooking one part of a meal requires a short use of the oven followed by a lot of manual work, and cooking the other part of the meal requires a long oven time, you should schedule the shorter cook first so that you can do the rest of the work for that component while the other half is in the oven.

**Another example**: Consider the dependency tree below. $a \rightarrow b$ indicates "$a$ depends on $b$". The length of a block indicates the time it takes to complete (1 or 3 in this case). There are two resources/channels: red and blue.

An example solution might look like this:

This shows that a greedy approach (like scheduling (1) and (2) simultaneously) is not sufficient -- you have to look ahead to minimize waiting for resources.

# Answer
This problem (more formally its decision version) is **NP-complete**.

NP-hardness can be shown via a reduction from the Job-Shop Scheduling Problem (JSP) with makespan objective, which is well-known to be NP hard.

In the JSP, we have $n$ jobs $J\_1, J\_2, ..., J\_n$. Within each job there is a set of operations $O\_1, O\_2, ..., O\_n$ which need to be processed in a specific order. Each operation $o$ has a specific machine $m\_o \in M$ that it needs to be processed on and only one operation in a job can be processed at a given time. (adapted from Wikipedia)

Now it is easy to see that JSP is just a special case of your proposed problem (one task per operation of JSP, dependencies only between successive operations in a job), which makes it at least NP-hard too.

Membership in NP can be shown by guessing an optimal schedule and verifying in polynomial time that it fulfills all constraints.
> 18 votes

# Answer
What you are describing is a planning and scheduling problem. Kautz and Selman pioneered the use of Boolean satisfiability and SAT solvers to attack such problems in the early 1990's. SATPLAN, STRIPS, and PDDL are good search terms for further research. There seem to be several planner implementations that take world descriptions written in STRIPS and generate a plan that minimizes plan length, ordering tasks to take advantage of time savings produced by tasks that can be executed in parallel. Given how effective SAT solvers are at attacking planning instances, I'd guess that the average-case hardness of planning problems is low, but I wouldn't be surprised if the general problem turned out to be NP-hard.
> 14 votes

# Answer
**Thanks to "user2357112 supports Monica" for pointing out issues! Now fixed.**

Let's formulate the decision problem form of this problem, which I'll call Tree Scheduling (TS):

Given a number $k$, and a rooted tree with

* tasks $t\_1, \dots, t\_n$ for vertices, each having some integer duration $l\_i$ and requiring some resource $r\_i$ from a set $S$ of resources, and
* arcs representing dependencies between tasks,

is there a schedule that satisfies all dependencies, avoids scheduling two jobs that use the same resource at overlapping times, and completes within $k$ time units?

This problem is **NP-complete** even with just two resources, by reduction from Partition (PART).

In PART, we are given a multiset of $m$ numbers $a\_1, \dots, a\_m$ having $\sum\_i a\_i = T$, and the task is to determine whether we can partition them into two multisets, each having sum $T/2$. Given an instance of PART, we construct an instance of TS with:

1. A root task $t\_r$ using resource 1, of duration 1;
2. For each $1 \le i \le m$, a task $t\_i$ using resource 1, having duration $l\_i = a\_i$ and on which $t\_r$ depends;
3. A task $t\_{after}$ using resource 2, of duration $T/2$ and on which $t\_r$ depends;
4. A task $t\_{sep}$ using resource 1, of duration 1 and on which $t\_{after}$ depends;
5. A task $t\_{before}$ using resource 2, of duration $T/2$ and on which $t\_{sep}$ depends;
6. $k=T+2$.

The idea is that an optimal solution to an instance consisting of *just* $t\_r$, $t\_{before}$, $t\_{sep}$ and $t\_{after}$ takes time $T+2$, since these tasks are on a critical path of this length. This solution has 2 "gaps" of length $T/2$ in the usage of resource 1. After adding the tasks $t\_1, \dots, t\_m$, we can still complete all tasks in $T+2$ time iff we are able to fill up each gap with exactly $T/2$ time units' worth of tasks.
> 6 votes

# Answer
It is NP-Hard as others have said, but... sometimes there is an easier way to solve it. You can do a Lagrangian relaxation to essentially remove the NP-hardness solve that problem, and then use that as an initial guess for the original problem. Pekny and Miller essentially did something like to for the Asymmetric Traveling Salesman problem. They reduced it to an assignment problem (n^3), and the used that to stich together a solution to the original problem. where they could stich together the cycles without adding cost, they had a guaranteed optimum in polynomial time - FOR FORTUITOUS DATA SETS. But having a fortuitous data set might end up being most of the time.
> 2 votes

---
Tags: algorithms, time-complexity, np-complete, np-hard
---


# Question
Title: What would you say the sub problem is in this dynamic programming challenge?
Alongside the OBJ files for each figurine, Nintendo has released the following information about each figurine f: • the filament cost (amount of filament necessary) to print f, denoted fc, in grams, as an integer • the amount that Nintendo will pay for each printed copy of f, denoted fp

Find P(N), the maximum profit which can be attained with N grams of filament by printing figurines, selling filament, or some combination thereof. Don’t forget base cases!

# Answer
Sounds a lot like homework :( what have you tried?

In any case, take the following hint: If you use the first figurine exactly $k$ times, you lost $k\cdot fc\_1$ grams of filament, but you win $k \cdot fp\_1$. Now that you have decided to use the first figurine $k$ times, how does the rest of the problem looks like?
> 0 votes

---
Tags: algorithms
---


# Question
Title: There is an $n^k$ prover if and only if $P = NP$
I am studying computational complexity using Papadimitrious's book: "Computational Complexity". I am trying to solve the final statement of Problem 8.4.9, but I am stuck and would like some hint on how to proceed.

Problem 8.4.9:

> "Let $f(n)$ be a function from integers to integers. An $f(n)$-prover is an algorithm which, given any valid expression in first-order logic that has a proof in the axiomatic system in Figure 5.4 of length $l$, will find this proof in time $f(l)$. If the expression is not valid, the algorithm may either report so, or diverge (so the undecidability of validity is not contradicted).
>
> (a) - Show that there is a $k^n$ prover, for some $k \> 1$.
>
> In a letter to John von Neumann in 1965, Kurt Gödel hypothesized that an $n^k$ prover exists, for some $k \geq 1$. For a full translation of this remarkable text, as well as for a discussion of modern-day complexity theory with many interesting historical references, see:
>
> * M.Sipser "The history and status of the P versus NP problem" *Proc. of the 24th Annual ACM Symposium on the Theory of Computing*, pp.603-618, 1992.
>
> **Problem:** Show that there is an $n^k$ prover, for some $k \> 1$, if and only if $P = NP$."

Figure 5.4 that he mentions contains the standard logical axioms for first-order logic (I can post the picture here, if you like).

I tried reading the mentioned article, and although it is very interesting from the historical point of view, it didn't help me figure out the solution. My first attempt was to use the result that a formula $\phi$ is valid if and only if its negation $\neg \phi$ is not satisfiable and try to connect this problem to $SAT$, which we know is $NP$-complete. However, using this result I obtain something about a formula NOT being satisfiable, while $SAT$ is about satisfiability.

Can anyone help me with this statement? Thanks in advance.

PS: Not closely related to what I am asking, but I think I was able to solve letter (a) by noticing that if a formula is valid, then we can apply the logic axioms (and the number of logic axioms is constant) without worrying about how we instantiate variables since a valid formula is true under all possible interpretations.

# Answer
An $n^k$ prover implies that the set $\\{\left(\varphi,1^n\right)|\text{$\varphi$ has a proof of length $\le n$}\\}$ is in $P$, since we can simply run the prover for $n^k$ steps and check whether it yields a valid proof.

It remains to show that this language is NP complete. This follows from a straightforward reduction from SAT. Given a CNF $\varphi$ over the variables $x\_1,...,x\_n$ return the pair $\left(\exists x\_1,...,x\_n: \varphi, 1^k\right)$ where $k=k(|\varphi|)$ is some upper bound on the length of the satisfiability proof for satisfiable formulas of length $|\varphi|$.
> 3 votes

---
Tags: complexity-theory, np-complete, p-vs-np, first-order-logic
---


title: ACC0 and the majority gate

text:
# Question
Title: ACC0 and the majority gate
I am missing something obvious here. Does ACC0 reach a ceiling AC0\[m\] with m being constant?

By another description, ACC0 can use any m, which can trivially test modulus gates from \[n/2,n\] over all inputs. Any modulus active in that range indicates MAJ returns true, implementable as an OR over the current range of gates.

# Answer
It does not reach a constant ceiling, but the modulo gate cannot depend on the input's length, e.g. $\bmod n/2$ gates are not allowed. You must decide on the constants while constructing the circuit, independently of the input/input size. See the definition in Arora and Barak's book, where they first define $ACC0(m\_1,...,m\_k)$ which corresponds to circuits with $\bmod m\_1,...,\bmod m\_k$ gates, and then define $ACC0$ as the union of $ACC0(m\_1,...,m\_k)$ over all integer $k$-tuples.
> 3 votes

---
Tags: complexity-theory
---


# Question
Title: Proving undecidability of a language with mapping reductions
I'm referring to questions like this one: Mapping reduction to show NeverHalt is undecidable

I understand with Turing reductions, you have to use oracle calls of the unknown language you're trying to prove is undecidable to solve a known undecidable language.

However, with mapping reductions, am I right in assuming these calls aren't needed? In addition, in the link provided, the solution pseudocode says

```
For input x:
  Simulate M for input w
    if it accepts, loop
    if it rejects accept x

```

How can you say "if it accepts"? How can you determine this, what if it loops forever and this is never found out? Why can you make such statements with a mapping reduction but not with Turing reductions? Could I make a statement like "if M halts on w, do ...". I mentioned this to my teaching assistant and he said you can't make any statements like these unless you're accessing an oracle and doing a during reduction, but I see loads of examples which seem to show otherwise. Hopefully this makes sense

# Answer
Usually, when the context of the statement "if $M$ accepts $x$" is in a loop simulating the execution of $M$ on $x$, we just mean to say that if the simulation stopped and $M$ accepted/rejected then do something, otherwise just continue simulating (the more precise way of writing this would be to say "if $M$ accepted after $t$ steps then...").

Your pseudocode doesn't do anything magical, it simply checks **at a specific point of the simulation** whether or not $M$ already accepted/rejected.
> 1 votes

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


# Question
Title: Is $A \leqslant_P B \iff A \in \mathsf{P}^B$? If not are there counter-examples?
The way I think of reducing problem $A$ to problem $B$ in polynomial time, i.e. $A \leqslant\_P B$, is that you assume an efficient solution to $B$ which is enough to solve $A$. Now, this is suspiciously similar to $A \in \mathsf{P}^B$. I'm confident that $A \leqslant\_P B \implies A \in \mathsf{P}^B$ but is the reverse implication true? If not, can you provide some counter examples?

Similarly can anything be said about the statement: $$ A \leqslant\_L B \iff A \in \mathsf{L}^B $$

Edit: Clarified $\leqslant\_P$ is polynomial reduction and fixed notation for PTIME, LOGSPACE.

# Answer
Assuming $\le\_P$ is a polynomial many-one reduction (as opposed to a Turing reduction), the statement is incorrect.

For example, for any language $L$ we have $\overline{L} \in P^L$ (and in fact, in $O(1)$ time and space as well, so this is also an example for logspace many-one reductions)

But obviously if we take $L=\mathrm{Halt}$ to be the halting problem language, we wont have that $\overline{L} \le\_P L$ since $\mathrm{Halt}\in \mathsf{RE}$ but $\overline{\mathrm{Halt}}\notin \mathsf{RE}$ and $\mathsf{RE}$ is closed under $\le\_P$.
> 3 votes

---
Tags: complexity-theory, oracles
---


# Question
Title: Color coding to get an FPT algoirthm for k disjoint triangles
The k-disjoint triangles problem is as follows:

> Input: A graph $G=(V,E)$ and an integer $k\in \mathbb{N}$
>
> Output: Are there $k$ vertex-disjoint triangles in $G$?

An FPT algorithm is presented here (starting from slide 60). The algorithm uses color-coding and relies on dynamic programming to determine if a solution is highlighted (each vertex in the solution group is colored with a distinct color). The running time of the algorithm is $O^∗((2e)^{3k})$.

I\`m trying to understand the running time of this algorithm using dynamic programming (method 2). why is it $O^∗((2e)^{3k})$?

# Answer
> 2 votes
The dynamic programming algorithm goes over all subsets of $\[3k\]$ whose size is a multiple of 3, in nondecreasing order of size. For each such non-empty subset, it goes over all $O(n^3)$ triplets of vertices, and for each one, it performs a single table look-up. Therefore the running time is $O^\*(2^{3k} n^3)$, where $O^\*$ hides $\operatorname{poly}(k)$ factors which are needed to manipulate indices.

---
Tags: algorithms, time-complexity, np, colorings, parameterized-complexity
---


# Question
Title: What subset of TMs are there where the halting problem is decidable?
Halting problem is not decidable in general, but are there interesting/useful subsets where it IS decidable? Bonus points if that subset is actually helpful.

Example:

If we know BB(x), then the halting problem for TMs with x states is decidable. The problem is BB(x) is not a computable function, as it basically requires solving the halting problem in the first place, so this doesn't help construct a general halting problem solver for arbitrary x. We do however, know BB(x) for x \< 5 (which isn't very helpful I imagine, but still...).

Still, I guess that means technically the halting problem is decidable for subsets which contain all TMs with the same finite amount of states, but we still can't construct a TM that decides it without first solving the halting problem.

Similarly, any finite subset of TMs is trivially decidable by some TM that just happens to correctly map the input TMs to truth values. Again, we can't construct this TM. Not very interesting or helpful.

# Answer
If you don't look at turing machines in particularly: Sometimes you can make an argument "if it halts at all, then it must halt within x steps" where x can be calculated, so you decide the halting problem by calculating x and performing x steps.

One particular case: A program with nested loops, where an upper limit for the number of iterations of each loop can be calculated before the loop is executed, will halt. And if you take such a program and insert identifiable "non-halting" constructs, like "for (;;) {}" in a C program, then the halting problem is decidable.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: Infinite prefix-closed context-free languages contain an infinite regular subset
The Problem:

> Say that a language is prefix-closed if all prefixes of every string in the language are also in the language. Let C be an infinite, prefix-closed, context-free language. Show that C contains an infinite regular subset.

Can we show this by using Myhill-Nerode Theorem?

# Answer
> 2 votes
Given a normal form grammer $G$ for an infinite prefix-closed $L$, examine the (almost) regular grammer $G'$ obtained by transforming rules of the form $A\rightarrow BC$ into $A\rightarrow B$. I leave it to you to show that $L(G')$ satisfies your requirements.

# Answer
> 0 votes
Another easy solutions uses the pumping-lemma for context-free languages. Let $L$ be infinite, prefix closed and context free. Then there is an $l$ such that for all $z\in L$ with length at least $l$ there is a decomposition $uvwxy=z$, s.t. $vx$ has length $\>0$, $vwx$ hat length $\leq l$ and $\forall i\geq 0: uv^iwx^iy\in L$ (actually, we don't need $l$ and just one $z$ and since $L$ is infinite, there is one).

Now take such a word $z$ and some decomposition. Then $uv^\*$ and $uvwx^\*$ are regular expression for subsets of $L$ (since $L$ is prefixed closed) and at least one of them generates an infinite language, because $x$ and $v$ cannot both be empty.

Using the Myhill-Nerode Theorem seems rather difficult: Take the language $L=\\{a^nb^m|m\leq n\\}$. While $A=\\{a\\}^\*=\\{a^n| n\geq 0\\}$ is an infinite regular subset of $L$, all the $a^i$ ($i\geq 0$) are pairwise inequivalent w.r.t. the Nerode relation of $L$. So we need an additional ingredient to show why we can collapse equivalence classes by not allowing certain suffixes (that is what taking a subset practically means for the Nerode relation).

---
Tags: formal-languages, regular-languages, automata, context-free, pushdown-automata
---


# Question
Title: Closure of context-free languages under left-half
The regular languages are known to be closed under the operation "left half": $$ \operatorname{left}(L) = \\{ x \in \Sigma^\* : xy \in L \text{ for some } y \in \Sigma^\* \text{ s.t. } |x|=|y| \\} $$ What about the context-free languages?

# Answer
> 1 votes
Let $L = \\{a^nb^na^mbba^{3m} : n,m \geq 1 \\}$, which is clearly context-free. Then $$ \operatorname{half}(L) \cap a^+b^+a^+b = \\{ a^nb^na^nb : n \geq 1\\}, $$ which is not context-free. Hence $\operatorname{half}(L)$ is not context-free.

(If $L$ is a unary context-free language then $L$ is regular, and so $\operatorname{half}(L)$ is regular.)

---
Tags: formal-languages, context-free, closure-properties
---


# Question
Title: Optimal encoding scheme for semi-rewritable memory?
Let's define a "semi-rewritable" memory device as having the following properties:

* The initial blank media is initialised with all zeroes.
* When writing to the media, individual zeroes can be turned into ones.
* Ones can not be turned back into zeroes.

Making a physical interpretation of this is easy. Consider for instance a punch card where new holes can easily be made, but old holes can not be filled.

What makes this *different* from a "write once, read many" device is that a used device can be rewritten (multiple times), at the cost of reduced capacity for each rewrite.

# Implicit assumptions I would like to make explicit:

1. The memory reader has no information about what was previously written on the device. It can therefore not be relied upon to use a mechanism such as "which symbols have been changed?" to encode data on a device rewrite. That is, the reader is stateless.
2. On the other hand, different "generations" of the device may use different encoding schemes as the available capacity shrinks.
3. The data stored can assumed to be random bits.

# Sample storage scheme, to demonstrate rewrite capability:

Information in this scheme is stored on the device as pairs of binary symbols, each pair encoding one of the three states of a ternary symbol, or \[DISCARDED\] in the case where both symbols have been written.

The first generation thus stores data at a density of $\frac{log\_2(3)}{2} \approx 0.79$ times that of simple binary encoding.

When the device is rewritten, the encoder considers each pair of binary symbols in sequence. If the existing state matches the one it desires to write, the encoder considers the data written. If on the other hand the pair doesn't match, it writes the necessary modification to that pair, or in the case where that isn't possible, writes the symbol \[DISCARDED\] and considers the next pair instead until it has successfully written the ternary symbol.

As such, every rewrite would discard $\frac{1}{2}$ of existing capacity.

For a large number of cycles, the device would in sum have stored $log\_2(3) \approx 1.58$ times the data of a simple one-time binary encoding.

(For a variation of the above, one could also encode the first generation in binary and then apply this scheme on every subsequent generation. The loss from the first generation to the second would be larger, and the total life time capacity reduced, but the initial capacity would be larger).

# Question:

1. Is it possible to have a better life-time capacity than $log\_2(3)$? I suspect the the real asymptotic capacity is 2.
2. Can a scheme do better than having $\frac{1}{2}$ capacity loss between rewrites?

# Answer
The lifetime capacity can be arbitrarily large.

One may change the weight of the ternary symbols from 1/3, 1/3, 1/3 to 1/2, 1/4, 1/4 (favouring the symbol with blank bits). This reduces the entropy of the ternary symbol from $log\_2(3)$ to $\frac{3}{2}$.
What it also does is reducing the capacity loss between generations, to a factor of $\frac{5}{3}$

Thus, instead of a lifetime capacity of:

$$\frac{log\_2(3)}{2} \cdot \sum\_{i=0}^{\infty}\left(\frac{1}{2}\right)^i = log\_2(3) \approx 1.58$$

The lifetime capacity is instead:

$$\frac{3}{4} \cdot \sum\_{i=0}^{\infty}\left(\frac{3}{5}\right)^i = \frac{15}{8}\approx 1.88$$

This can be generalised.

By weighted as $x$, $\frac{1-x}{2}$, $\frac{1-x}{2}$, the loss of capacity for each generation is a factor that can be written as:

$$generation\ loss =\frac{1}{2} - \frac{1}{x - 1}$$

And the entropy of the symbol is:

$$S = - \left(xlog(x) + (1-x)log\left(\frac{1-x}{2}\right)\right)$$

For a lifetime capacity of:

$$\frac{- \left(xlog(x) + (1-x)log\left(\frac{1-x}{2}\right)\right)}{2} \cdot \sum\_{i=0}^{\infty}\left(\frac{1}{2} - \frac{1}{x - 1}\right)^i$$

Which grows unbounded when $x$ approaches 1, however quite slowly (logarithmic). This makes the capacity per generation very low, but the sparseness of the set bits allows the memory to be reused many many times.
> 1 votes

# Answer
In pre-historic times, laser printers stored their page counts in some hardware that only let you set bits. N consecutive bits set from the start followed by a zero would mean the number N. After printing a page, you’d set another bit. You can probably encode an array of small integers to which another is added in a similar way.
> 0 votes

---
Tags: memory-hardware, encoding-scheme
---


# Question
Title: Describe a Monte Carlo algorithm for the Triangle Packing problem
Book: Parameterized Algorithms by Marek Cygan (free to download legally)

Chapter about Multivariate polynomials on Page 353 (In the book not the pdf) Question 10.19:

Describe a Monte Carlo $2^{3k}n^{O(1)}$ \- time polynomial-space algorithm for the Triangle Packing problem: given a graph $ G $ and a number $ k \in N $, decide whether $ G $ contains $ k $ disjoint triangles (subgraphs isomorphic to K3).

Hint 10.19 in Page 354: Use a similar approach as in the $2^{k}n^{O(1)}$ -time algorithm for $k$-path from this chapter (Page 333).

I tried to solve the problem using the hint, but without success unfortunately, there are solutions to the book? I would be happy to get help if it can be solved even without official solutions of the book but it is important to solve it using the hint they brought in order to use the tools learned in the same chapter.

Thanks in advance.

# Answer
> 3 votes
Although I agree with Yuval, I'll try to get you started on the connection to their longest path approach. The goal is, given a graph $G$, to define a polynomial $P\_G$ which is nonzero iff $G$ has $k$ disjoint triangles. If you could evaluate $P\_G$ on an arbitrary point in the underlying field $\mathbb{F}$ in time $2^{3k}n^{O(1)}$ then Schwartz-Zippel gives you the desired result (assuming that the degree of $P\_G$ is low enough compared to $|\mathbb{F}|)$.

Denote by $T$ the set of all length $3k$ vertex sequences $(v\_1,...,v\_{3k})$ such that for all $i$ satisfying $i=1\pmod 3$, the triplet $(v\_i,v\_{i+1},v\_{i+2})$ is a triangle in $G$. Now, it is not hard to see that if $\mathbb{F}$ has characteristic 2 then the following polynomial (over $|E|+3k|V|$ variables) is nonzero (i.e. has a nonzero coefficient) iff $G$ contains $k$ disjoint triangles:

$P\_G(\pmb{x\_e},\pmb{y\_{(v,j)}})=\sum\limits\_{(v\_1,...,v\_{3k})\in T}\sum\limits\_{l\in S\_{\[3k\]}}\prod\limits\_{i\in\[3k\]}x\_{(v\_i,v\_{i+1})}\prod\limits\_{i\in\[3k\]} y\_{i,l(i)}$

Where $S\_n$ is the symmetric group. The hard part is evaluating $P\_G$ without going over all possible sequences in $T$. The fact that we don't care about repetitions in sequences in $T$ will allow (after some considerable work in rewriting $P\_G$) efficient dynamic programming to come into play. The rest pretty much follows the proof for the longest path case (after extending the sum to functions whose range is a subset of $\[3k\]$, the dynamic programming part would look a bit different, e.g. you would probably want to shorten the sequence by three elements at a time).

# Answer
> 2 votes
Koutis gives an $O^\*(2^{3k})$ algorithm for the more general problem of $3$-set $k$-packing in his paper Faster algebraic algorithms for path and packing problems. This was improved by Björklund, Husfeldt, Kaski, and Koivisto in their work Narrow sieves for parameterized paths and packings to $O^\*(1.493^{3k})$. I don't know what is the state of the art on this problem.

---
Tags: algorithms, randomized-algorithms, monte-carlo
---


# Question
Title: a lower bound for the maximum fraction of matchings not containing an edge
I am trying to prove the following statement (from book, page 317):

> Let $G(A,B,E)$ be a bipartite graph, where $A$ and $B$ are the two disjoint sets of vertices s.t. $|A|=|B|=n$. Let the number of matchings of size $k\le n$, be $m\_k$. If $|E|\>k$ then there exists an edge $e$, such that $\frac{m\_{ne}}{m\_k} \ge \frac{1}{n}$, where $m\_{ne}$ is the number of matchings of size $k$, that do not include/contain edge $e$.

The book gives a hint to use pigeonhole principle. But I am only able to get a weaker result.
Each matching of size $k$, contributes towards a matching of size $k$ not containing an edge, for $|E|-k$ edges. Thus as there are in total $m\_k$ matchings, it can be seen as distributing $(|E|-k)m\_k$ balls in $|E|$ bins. Thus by pigeonhole principle there is a bin (an edge) with at least $\frac{(|E|-k)\cdot m\_k}{|E|}$ matchings which do not contain it. That is there is an edge $e$ such that $$m\_{ne} \ge \frac{(|E|-k)\cdot m\_k}{|E|}$$ $$\frac{m\_{ne}}{m\_k} \ge \frac{|E|-k}{|E|} \ge \frac{1}{|E|} \ge \frac{1}{n^2}$$

How can I prove that the lower bound is at least $\frac{1}{n}$ for some edge ?

# Answer
Your approach has been working well all along, only to miss the promising transformation at the last step.

Instead of $$\frac{|E|-k}{|E|} \ge \frac{1}{|E|} \ge \frac{1}{n^2},$$ we can proceed as $$\frac{|E|-k}{|E|} =1 - \frac{k}{|E|} \ge1- \frac k{k+1}=\frac1{k+1}.$$

Since $k\le n$, i.e., $\dfrac1{k+1}\ge\dfrac1{n+1}$, we are not far from the goal $\dfrac1n$.

It takes a bit more effort to reach the goal. I will leave it to you to complete.

---

---

Here is a slightly easier proof. It shows, except possibly for graphs where all edges are separated, we can increase $1/n$ to $1/2$.

Consider whether there are incident edges in $G$.

* There are incident edges. Say, edge $e\_1$ and $e\_2$ are incident. Every matching (of size $k$) can contain at most one of them. So either at least 1/2 of the matching of size $k$ does not contain $e\_1$ or at least 1/2 of the matching of size $k$ does not contain $e\_2$. Note that $$1/2\ge 1/n.$$
* There are no incident edges. Then there are at most $n$ edges. Since each matching does not contain at least one of the $|E|$ edges, we have , if $e$ is the edge that is absent from the most matchings of size $k$,$$\frac{m\_{ne}}{m\_k}\ge \frac{1}{|E|} \ge \frac{1}{n}.$$

$\checkmark$
> 1 votes

---
Tags: graphs, discrete-mathematics, matching, bipartite-graph
---


# Question
Title: What does "associative" exactly mean in "n-way set-associative cache"?
I'm trying to grasp what does *associative* actually mean in *n-way set-associative cache*. I understand n-way set-associative cache as a concept; `n` is the degree of associativity, i.e., how many cache lines a set can hold.

If I take *associative* to mean "having the tendency to connect", I get to the "sets tend to connect to...", what, memory addresses?

But I'm not sure if this is the correct understanding.

# Answer
> 4 votes
An n-way set associative cache is a cache that is chopped up in sections called sets. And each set can hold n-blocks.

A cache-address can be broken up up in 3 parts.

* the offset within the block
* the index that identifies the set
* the tag that identifies the block in the set.

When a request comes in, the index is calculated to identify the set. Then the tags of all blocks in the set are checked. And when a block with a matching tag is found, the right bytes are returned based on the offset.

A direct mapped cached is effectively a 1 way set associative cache.

So associativity doesn't mean the number of blocks the cache can hold, but the number of blocks a set within the cache can hold.

The big advantage of a n-way set associative cache compared to a direct mapped cache, is the latter can only have a single block for a set of addresses and the former can hold multiple blocks for a set of addresses.

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


title: Speed of a microprocessor

text:
# Question
Title: Speed of a microprocessor
I was just wondering why are are new generation microprocessors faster at the same clock speed as the old ones. For instance a 2.66Ghz dual core i5 is faster than the a device with clock speed of 2.66Ghz but core 2 dual.

# Answer
> 2 votes
If executing each instruction took a single clock-cycle, then your confusion would have been understandable, as a higher clock frequency would imply shorter cycle time, hence, more instructions per unit time.

However, the reality is quite different. Modern CPUs are usually pipelined, meaning that a single instruction takes multiple number or core-clocks, and that multiple instructions are executed simultaneously at the same time (each occupies different parts of the CPU pipeline). Complex instructions, such as calling a function or "jumping" to a different part of the code interfere with this pipeline and cause the CPU to temporarily halt its execution until the offensive instruction completes (known as a pipeline stall).

The picture is even more complex. Recent processors have multiple pipelines running on the same "core" (say, one clock advances pipeline 1 while the next clock advances pipeline 2). Of course, sometimes the program running on one pipeline affects (stalls) the progress of the other pipeline. This is "multithreading". Other approaches to make the CPU perform better are superscalar processing and other paralleling approaches.

As you can figure out, the number of instruction a CPU performs at any time unit is very complex to compute or even estimate, and is affected by the clock frequency, but also by the architecture of the CPU as well as by the program itself (e.g., how many "jumps" instructions it contains, or how well it parallelizes). All of these together determine the "speed" of the CPU, which is measured in the (average) number of instructions it can perform in a second, known as IPS. As said, the clock frequency is only one factor to the IPS, but in modern CPUs the specific architecture (rather than small differences in their clock frequency) dominates the IPS.

# Answer
> 2 votes
Modern x86/x64 CPUs are incredibly complicated. There can be dozens of instructions in various stages of execution flying around a CPU core at a given time. The cycle boundaries are just times when the various functional units synchronize with each other and work out what each one will be doing next.

A CPU can be made faster at the same clock rate by increasing the number of regions that can operate in parallel, increasing the amount they do per cycle, or increasing the fraction of time that they're actually in use. There can be tension between these approaches – e.g., increasing the number of execution units makes the chip larger, which increases travel-time delays, and you pay that penalty even if the code you're running doesn't have enough parallelism to use the extra units.

The gory details of how recent Intel processors differ from those of a decade ago can probably all be found in Agner Fog's optimization manuals, specifically the microarchitecture manual and instruction tables. They aren't really organized in a way to make comparing specific generations easy, but looking at the instruction tables for Wolfdale (45nm Core 2) and Ice/Tiger Lake, I see that many simple instructions have a throughput of 0.33 (i.e., three per cycle) on Wolfdale and 0.25 (four per cycle) on Ice/Tiger Lake, probably due to there being an additional execution unit that can handle them, and 128-by-64-bit integer divisions have a throughput of one per 10 cycles on Ice/Tiger Lake and one per 18-88 cycles on Wolfdale.

The microarchitecture manual says of Ice/Tiger Lake:

> The pipeline is very similar to previous designs, but the number of execution units has been increased to improve the throughput from four to five instructions per clock cycle. The number of output ports is doubled so that the processor can do two memory reads and two memory writes per clock cycle under favorable circumstances. The size of the µop cache has been increased by 50%. \[Wolfdale has no µop cache at all, though it has a small loop buffer which is a similar idea.\] The resources for out-of-order execution have been increased further. The reorder buffer has 352 entries. \[Wolfdale: 96\] The reservation station has 160 entries. \[Wolfdale: 32\]

Ice/Tiger Lake also has 256-bit and 512-bit wide SIMD instructions, while Wolfdale only has 128-bit. This only benefits code that uses the new instructions, but a lot of software tests the CPU type at run time and uses new instructions when available, so a particular executable file may run faster on newer processors for this reason.

This is far from a complete list of changes and I encourage you to read Fog's manuals if you find this sort of thing interesting.

# Answer
> 1 votes
There are many techniques that can be applied.

At a higher level you have 2 main options:

* ILP: Instruction Level Parallelism
* TLP: Thread Level Parallelism

So increase parallelism in a single instruction stream or increase parallelism due to having multiple instruction streams.

Multicore (SMP) and hyperthreading (SMT) help to increase parallelism in multiple instruction streams.

Increasing parallelism in a single instruction stream can be done using:

* pipelining
* superscalar-execution/VLIW
* SIMD instructions

What you see with the Apple M1 is that it deals very well with super scalar execution. So it has a huge out of order execution window so it can keep its execution units busy and it has many execution units. So instead of betting on higher frequencies, it bets on improved superscalar execution.

There are also other techniques that can be applied to speed up processors like increasing the size of the caches, branch prediction, prefetching, NUMA, etc.

---
Tags: computer-architecture
---


# Question
Title: Regular expression for binary representation of even numbers?
I need help writing the regular expression over the alphabet (0,1) represent the even numbers in base ten. So basically the regular expression would show represent an even number in binary. (also if you know what the FSA would look for that it would help as well)

# Answer
> 1 votes
Here are the first few even natural numbers: $$ \begin{array}{r} 0 \\ 10 \\ 100 \\ 110 \\ 1000 \end{array} $$ Here are the first few odd natural numbers: $$ \begin{array}{r} 1 \\ 11 \\ 101 \\ 111 \\ 1001 \end{array} $$ Notice any pattern? You take it from here.

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


title: Complexity of All-SAT

text:
# Question
Title: Complexity of All-SAT
All-SAT is the problem of enumerating all satisfying assignments of a boolean formula.

All-SAT is different from #SAT, where it suffices to find the number of satisfying assignments without enumerating them.

Is the computational complexity of All-SAT known, or is this an open problem?

In this CS Theory question, some solvers for All-SAT are discussed, but the papers do not seem to give complexity results.

# Answer
You can naively compute ALL-SAT in $2^npoly(n,m)$ time, where $n$ is the number of variables and $m$ is the number of clauses. You clearly need $\Omega(2^n)$ time in the worst case just to write down the assignments (in the case of a tautology). If the strong exponential time hypothesis (SETH) holds, then this is not much harder than SAT itself, so under SETH the complexity of SAT, ALL-SAT, #SAT is the same (up to polynomial factors).

Moreover, without SETH you can claim that given access to a $\\#SAT$ oracle, you can output all satisfying assignments in time $k(\varphi)poly(n,m)$ where $k(\varphi)$ is the number of satisfying assignments for $\varphi$ (just see if the number of satisfying assignments changes when substituting $1$ or $0$ to some variable $x\_i$). This also shows that in some sense ALL-SAT is not much harder than $\\#SAT$.
> 4 votes

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


# Question
Title: Show that $(\log(n))^\alpha = O(n^\beta)$
I am trying to show that $\forall \beta \gt0, \log(n^\alpha) = O(n^\beta)$, however I cannot use the limit definition, as demonstrated in similar questions on the forum.

First I show that $\log(n^\alpha) = O(n)$, using the following method:

$\log(n^\alpha) = \alpha \cdot \log(n) \leq \alpha \cdot n$ Thus for $c=\alpha^\alpha, n\_0=0$, we have $(\log(n))^\alpha \leq c \cdot n$ which implies $\log(n^\alpha) = O(n)$

Now I will show $\forall \beta \gt0, \log(n^\alpha) = O(n^\beta)$, we have two cases

$\beta \ge 1$: Since $\forall n \ge1, n\leq n^\beta$, then from the above result, for $c=\alpha^\alpha, n\_0 = 1$, we have $\log(n^\alpha) \le c \cdot n^\beta$ which implies $\log(n^\alpha) = O(n^\beta)$

$0 \lt \beta \lt 1$: I can't seem to find a series of inequalities, as shown above, that prove $\log(n^\alpha) =O(n^\beta)$ in this case

# Answer
> 3 votes
You can use the following identities: $$ (\ln n)^a \le n^\beta \iff \ln (\ln n)^a \le \ln n^\beta \iff a \ln \ln n \le \beta \ln n. $$

This is trivial if $\alpha \le 0$, so we consider the case $\alpha \> 0$.

For simplicity substitute $t= \ln \ln n$ and $\gamma = \frac{\alpha}{\beta}$. Notice that $\gamma \ge 0$. We obtain: $ \gamma t \le e^t \iff \gamma t - e^t \le 0 $

To show that $\alpha t \le \beta e^t$ for sufficiently large $t$, we take the derivative of $h(t) = \gamma t - e^t$: $$ h'(t) =\gamma - e^t. $$

This shows that for $t \ge \ln \gamma$, $h(t)$ is monotonically non-increasing. Moreover, for $t=\ln \gamma$ we already have $h(t) \le 0$, indeed $h(\ln \gamma) =\ln \gamma-\gamma \le 0$ since the logarithm is a monotonically increasing function.

Hence, in the definition of big-Oh with $n\_0$ and $c$, we can pick $n\_0 = \ln \gamma = \ln \frac{\alpha}{\beta}$ and $c=1$.

---
Tags: time-complexity, asymptotics
---


# Question
Title: What are the #P-hard version of Latin square and sudoku?
I know that filling partial latin square and solving sudoku are NP-hard. But what are the counting versions of these two problems?

# Answer
The counting problems corresponding to your two decision problems are:

* Given a partially filled Latin square, in how many ways can it be completed to a Latin square?
* Given a partially filled Sudoku puzzle, in how many ways can it be completed to a Sudoku solution?
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Cost to convert one integer array into another
This question is distilled from an interview question.

Given two arrays $a$ and $b$ containing $n$ integers each, change each integer in array $a$ into the corresponding integer in array $b$ by increasing or decreasing a single digit by $1$. What is the optimum algorithm?

The number of digits in $a\[i\]$ are the same as $b\[i\]$ and the length of arrays $a$ and $b$ are also the same.

An example, $a = \[123, 456\]$, $b= \[124, 307\]$. Then the minimum cost to convert array $a$ into array $b$ is 8.

I know of a naive solution to this question which of course is to count the number of increments to each digit but I'm wondering if there is a more efficient binary operation that can be used.

# Answer
Let $\ell\_{i}$ denote the number of digits in $a\[i\]$. Then the complexity of the naive algorithm as suggested by you is $O(\ell)$, where $\ell = \sum\_{i = 1}^{n} \ell\_{i}$.

Moreover, the algorithm must visit every digit at least once. For the sake of contradiction, suppose the algorithm did not visit some digit in the array. Then an **adversary** can modify the unvisited digit to a different digit. This will prove that your algorithm's output is incorrect. Therefore, any correct algorithm must require at least $\Omega(\ell)$ comparisons. Thus, you can not expect better than $\Theta(\ell)$ complexity for this problem.
> 1 votes

---
Tags: algorithms, time-complexity
---


# Question
Title: What does a non-deterministic guess "look like"?
I have been trying to understand the solution to the following problem:

*"Show that if $L\_2$ and $L\_3$ are Turing recognisable, then so is $L\_2L\_3 = \\{w\_1w\_2 : w\_1 \in L\_2,w\_2\in L\_3\\}$:*

which essentially says to use non-determinism to guess a partition $w$ (say $w=xy$) and run the Turing machines $L\_1$ and $L\_2$ on $x$ and $y$ respectively.

I'm trying to get my head around what this non-deterministic guess "looks like", i.e. what we would say if we were to describe this implementation in more detail.

My thought is if the input string is of length $n$, then the second string $y$ could start at any of the $n$ positions, or be empty, so there are $n+1$ possible partitions. Does this mean we ultimately need to split into $2(n + 1)$ parallel/non-deterministic clones? And how do we manage this splitting in terms of transitions? We obviously don't know the length of the input ahead of time, so we can't immediately have $2(n+1)$ transitions from the start state? Would we scan the input string left to right, spawning two additional parallel threads for each character encountered, or something?

I see this "non-deterministically guess" phrase a lot in example solutions, but I feel like I'm missing a bit of intuition as to why this actually works. Any thoughts would be much appreciated.

# Answer
Nondeterministic guess is a non formal term we use for two (or more) possible transitions from the same configuration. When talking about a non deterministic finite automata, if a state $q$ has two different transitions for the character $a$, and I want to show that it accepts a certain word $w$, then I treat the junction at $q$ where $a$ is read as the location where the "guess" happens. By "guessing correctly" I refer to the transition that will lead to the eventual acceptance of $w$ (whereas I don't care what would have happened if I took the other transition, the "wrong" guess).

One implementation of guessing a partition of $w$ to $w\_1w\_2$ would be to have two transitions from the initial state for each character read by the machine head. One transition goes to the state $q$, where $q$ refers to $w\_1$ as whatever lies to the left of the current position of the head and $w\_2$ as the rest. The other transition stays at the initial state and keeps moving right until it meets blank. Although it's important to realize how to implement such a "guess", it is arguably more important to develop the intuition around the power of nondeterminism and understanding the such a nondeterministic partition can be done (without going through the tedious details and elaborating on the transition function).

For your problem non determinism doesn't really make things much easier, as you could simply execute both machines on every possible partition (of which there are $n$ where $n$ is the input's length) in parallel via dovetailing.
> 3 votes

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


# Question
Title: Prove that given 2 regular expressions represent the same language
Is it possible to use regular expression identities to prove or disprove that the `RE1=0*(0+1)*0*` and `RE2=(0+1)*` represent the same language?

# Answer
> 0 votes
Yes:

Clearly, $L(RE\_2)=\Sigma^\*$ ($\Sigma=\\{0,1\\}$ in this case), and obviously $L(RE\_1)\subseteq \Sigma^\*=L(RE\_2)$ (since $RE\_1$ contains only letters from $\Sigma$)

Now, we also have $L(RE\_2)\subseteq L(RE\_1)$, since concatenating with a language that contains $\epsilon$ is guaranteed to only expand the language. That is, for any $L$, and and $L'$ such that $\epsilon \in L'$, its clear why $L\subseteq LL'$. In this case, $L=L((0+1)^\*)$ and $L'=L(0^\*)$. Apply this twice from both sides and you will get that $L(RE\_2)\subseteq L(RE\_1)$.

Therefore $L(RE\_1)\subseteq L(RE\_2)\subseteq L(RE\_1)$ and thus $L(RE\_1)=L(RE\_2)$

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Running an application that needs 6 threads on dual core processor
If a dual core processor have 4 threads, then what will happen if i run an application which uses more than 4 threads?

And just to make sure i'm understanding what are threads in a cpu, when an application uses more than one "task" on its main process a single core will switch back and forth between the threads to give the illusion that it is running them in parallel, is that right?

# Answer
If there are $2$ cores and $4$ threads, two threads will be assigned to each core. Similarly, if there are $6$ threads, three threads will be assigned to each core. For example, suppose $6$ threads are $T\_1,T\_2,T\_3,T\_4,T\_5,T\_6$. Then, say $T\_1,T\_2,T\_3$ are assigned to core $1$ and $T\_4,T\_5,T\_6$ are assigned to core $2$.

As you are saying, $T\_1,T\_2,T\_3$ will switch back and forth on core $1$ to give an illusion of parallel. However, note that $T\_1$ and $T\_4$ are indeed running in parallel on different cores.
> 1 votes

---
Tags: cpu, threads
---


title: Shuffling Bits For Uniform Distribution

text:
# Question
Title: Shuffling Bits For Uniform Distribution
I am writing a hashing algorithm to be used in the key-value data store. That is for each key the location of the data is determined. The structure of the data store is given a key, a value needs to be retrieved OR given a key and value we determine a location to store the value. We want the keys to be designed/modified such that the whole storage space is uniformly used. In my application, if they're too many collisions, we would be forced to evict certain data items. The input is a key and the output of the mechanism sought is a "better key" that reduces the collision.

I assume that the key would not have more than 64 bits. For uniform distribution in the data store, I want key bits to be shuffled appropriately so that all the data do not collide in the same slot of the data store.

The approach I am thinking of is to have a predefined padding table, from where we take the rest of the bits and shuffle the whole thing to produce a new key. For Example, for a smaller key value that can be accommodated in a byte, we pad the rest of seven bytes (for 8-byte word). In the case of a 2-byte long key, we have another pad of 6 bytes and so on. I am not sure if this is an efficient way to do the job, but exploring should worth it.

If this is a good way, want to understand from you, how can I create such a table? What bits should be filled in it etc? Will be glad if there any pointers.

The idea of padding bits is to create a uniform distribution. For Example, if the key is a very small number 0xab (say) then the padding bits could be 0x12345cdeadbeef00 such that we could OR the two things to form 0x12345cdeadbeefab. Now we shuffle the whole thing such that the resultant key is uniformly distributed in the storage space.

# Answer
> 1 votes
It sounds like you might be trying to re-invent double-hashing. I recommend reading up on standard strategies for hash tables, including open addressing, closed addressing, cuckoo hashing, 2-choice hashing, and so on.

---
Tags: hash, bit-manipulation
---


# Question
Title: Compare Hidden Markov Model's sample with ground truth data
I have a time-serie and I fit different HMMs on it, each with a different number of hidden states. Now after sampling from the models , I'd like to compare the results with the ground truth data and find the model that gets closer to the real world data in the original time-serie.

For now I simply compared visually the distribution of the values generated by the HMMs and the distribution of values in the time-serie, but I'd like to compute a number indicating which model generates better samples.

# Answer
> 2 votes
Compute the likelihood of the observed data, for each model. Then higher the likelihood, the better the fit. The likelihood is just the probability that the model assigns to the observed data, which for HMMs can be computed using dynamic programming.

Be prepared that the more complex the model, the higher the likelihood will be, but that doesn't necessarily mean the model is "better" -- you run the risk of overfitting. Larger HMMs may fit the training data better, but if the HMM is too large, it might perform poorly on new data because of overfitting.

---
Tags: machine-learning, hidden-markov-models, time-series-analysis
---


# Question
Title: Proof that pseudorandom generators implies one-way function
I'm reading proof on Wikipedia that the existence of pseudorandom generators implies the existence of one-way functions.

My understanding is that *pseudorandom generators* are defined as

> A function $G\_l:\\{0,1\\}^l\to\\{0,1\\}^m$ is a pseudorandom generator if all of the following hold:
>
> a. $l\<m$
>
> b. $G\_l\in\mathbf P$
>
> c. For any polynomially-sized circuit $C$, $$ \left|\Pr\_{x\sim\text{Unif}\\{0,1\\}^l}\[C(x)=1\]-\Pr\_{x\sim\text{Unif}(D)}\[C(x)=1\]\right|\<\text{poly}(n), $$ where $D$ is the image of $G\_l$.

and that *one-way functions* are defined as:

> A function $f:\\{0,1\\}^n\to\\{0,1\\}^n$ is a one-way function if all of the following hold:
>
> 1. $f$ is invertible
> 2. $f\in\mathbf P$
> 3. For any polynomially-sized circuit $C$,
>
> $$ \Pr\[f(C(f(x))=f(x)\]\<\text{poly}(n). $$

**Question 1:** Looking at definitions for *one-way functions* above, I assume that the notation $f:\\{0,1\\}^n\to\\{0,1\\}^n$ refers to a *family* of functions $\mathcal F=\\{f\_n\\}\_{n\in\mathbf N}$, where each $f\_n$ is an invertible function $\\{0,1\\}^n\to\\{0,1\\}^n$. (And analogously for the defintion of pseudorandom generators.) **Is this assumption correct?**

The proof that pseudorandom generators implies one-way functions given on the Wikipedia page starts off with:

> Consider a pseudorandom generator $G\_l:\\{0,1\\}^l\to\\{0,1\\}^{2l}$. Let's create the following one-way function $f:\\{0,1\\}^n\to\\{0,1\\}^n$ that uses the first half of the output of $G\_l$ as its output. Formally, $$ f(x,y)\to G\_l(x) $$

**Question 2:** What exactly is this saying? It looks like $|x|+|y|=n$, so I'll assume for now that $|x|=l=n/2$, in which case $G\_l(x)$ outputs a string of length $2l=n$. But if $G$ ignores $y$, how can $f$ be injective?

Thanks!

# Answer
One-way functions need not be invertible. A one-way function which is invertible is known as a *one-way permutation*.

Here is the definition of one-way function from Goldreich's primer:

> A function $f\colon \\{0,1\\}^\* \to \\{0,1\\}^\*$ is *one-way* if it can be computed in polynomial time, and is hard to invert: for every polynomial time algorithm $A$, $$ \Pr\_{x \in \\{0,1\\}^n}\[f(A(f(x),1^n))) = x\] \text{ is negligible}. $$

(A function $\epsilon(n)$ is negligible if $\epsilon(n) = O(1/n^k)$ for all $k$.)

As you can see, there is no promise that $|f(x)| = |x|$; it could be that $f(x)$ is longer than $x$, or even shorter than $x$ (which is why we feed $A$ the auxiliary input $1^n$, an arbitrary string of length $n$).
> 1 votes

---
Tags: complexity-theory, pseudo-random-generators, one-way-functions
---


# Question
Title: Is there a formal way of defining a Zeno Machine?
The idea of a Zeno machine is pretty interesting to me, but I can't seem to find a formal definition for how a Zeno machine would work. I can find a couple of definitions around but they are all about the same (I suspect that everyone is cribbing off of each other) and lack any real formalism. A fairly representative definition is this one from the relevant wikipedium

> More formally, a Zeno machine is a Turing machine that takes $2^{-n}$ units of time to perform its $n$-th step; thus, the first step takes $0.5$ units of time, the second takes $0.25$, the third $0.125$ and so on, so that after one unit of time, a countably infinite (i.e. $\aleph\_0$) number of steps will have been performed.

This definitions is a little weird.

The biggest reason this definition is lacking is that the description doesn't really tell us anything about the state of the machine at any time $t \geq 1$.

Now if we look at an example of some psuedo-code for an accelerated Turing machine we have a bit of a conflict. Here is a sample slightly modified from C. Calude, L. Staiger. *A Note On Accelerated Turing Machines*

> ```
> begin program
>   write 0 on the first position of the output tape
>   set i = 1
>   begin loop
>     simulate the first i steps of T on w
>     if T(w) has halted,
>     then
>       write 1 on the first position of the output tape
>     set i = i + 1
>   end loop
> end program
>
> ```

Now this sample is intended to solve the halting problem on a Turing Machine. And according to the authors:

> By inspecting the first position of the output tape we need one unit of time to run the above machine in order to decide whether $T(w)$ stops or not

Now here we are relying on some notion of the state of the machine at time $t=1$, which is out of the scope of our definition.

Now the intuitive patch here is to say that the state at time $t=1$ is just the limit of the states as time approaches $1$.\[1\] But there are some problems with this the most important being that not all sequences will converge. Take for example the following pseudo-code:

> ```
> begin program
>   set i = 1
>   begin loop
>     write i on the first position of the output tape
>     if i is 1,
>     then
>       set i = 0
>     else
>       set i = 1
>   end loop
> end program
>
> ```

The sequence of states here cannot converge (regardless of how we choose our metric) and thus this naïve patch does not completely fix the problem.

Is there a way of defining a Zeno machine that is formal and complete?

---

\[1\] : In fact while I was putting this question together I found this paper which pretty much outright states this definition.

# Answer
> 3 votes
Hamkins' survey *Infinite time Turing machines*, linked by Yuval Filmus, formally defines a computational model (Infinite time Turing machine) that meets the requirements of a Zeno machine.

The definition of ITTMs does not use the time based framing; instead it is an extension of classical binary **TM**s to be defined at transfinite ordinals. A classical **TM** has a start status (empty tape, etc.) and a function to get the successive status; a **ITTM** just adds the status of the machine at limit ordinals.

Rather than taking the *limit* of the cells in the tape, as suggested and refuted in the question, we take the *limit supremum*. Formally for

$$ T(\lambda)\_k = \limsup\_{n\rightarrow \lambda} T(n)\_k $$

where $\lambda$ is a limit ordinal, $k$ is the index of some cell, and $T$ is the function that gives the tape at some numbered step.

The $\limsup$ ensures that it will always be defined for any sequence (since the alphabet is bounded). If the normal limit does not converge for some cell then (for a binary alphabet) the cell at time $\lambda$ will be $1$, since in order for it to not converge it must be $1$ at an infinite number of steps.

The state and the location of the read head are resolved much more simply. Just as there is a start state, there is also a limit state. At times corresponding to limit ordinals the machine is in the limit state, and the read head is set to the beginning of the tape.

---

The linked paper does not even mention "Zeno machine" (although it mentions Zeno) and **ITTM**s may not be the only formal model of a Zeno machine possible (beyond trivial modifications). However it is *a* model of computation that allows a Turing machine to perform an infinite number of operations and then continue calculations, so if you are looking for a formal way to talk about Zeno Machines **ITTM**s work just fine.

---
Tags: turing-machines, computability, hypercomputation
---


title: Dijkstra's algorithm vs A*

text:
# Question
Title: Dijkstra's algorithm vs A*
The A\* algorithm terminates when the f (distance + heuristic) is less than the f values for all of the nodes that haven't been visited. Dijkstra's algorithm produces the shortest path to every node from a starting point (not just the end node - the goal).

Is it possible to modify Dijkstra's algorithm so that when the distance to the end node is shorter than the distances to all of the unvisited nodes in the priority queue, we terminate the algorithm?

# Answer
> 6 votes
Yes, that is a common variant. In fact, Dijkstra himself included this early termination in his algorithm (see **problem 2**). So in that sense it's not really a modification, it's how Dijkstra himself described the algorithm to begin with. As Wikipedia puts it:

> Dijkstra's original algorithm found the shortest path between two given nodes,\[6\] but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

(\[6\] is the same paper I linked to)

However, in my perception, the original version is the more popular one.

To make the exit condition a bit more precise, the algorithm can terminate when a goal node is taken out of the frontier. That can also happen if a goal node is tied for the lowest cost with other nodes. The same applies to A\*. I intentionally use "a goal", because Dijkstra's algorithm also works with multiple goals or with a predicate that is evaluated to determine whether a node is a goal node.

By the way a recurring *incorrect* variant of Dijkstra's algorithm is to test whether a node is the goal when it is *first reached* and then terminate, but this fails to take into account that as long as a node is still in the frontier, it may be possible to find a shortcut to it.

---
Tags: algorithms, dijkstras-algorithm
---


# Question
Title: How do we pick and switch hash functions from a universal family?
When we have a universal family of hash functions, it gives us a few useful mathematical guarantees. But, if we pick a specific function from the family and use it all the time it's effectively like the family doesn't exists and we only have this one function.

Therefore, the only logical thing seems to be switching a hash function every once in a while (picking a new function from our family). If indeed this is what we should do, how often should we switch functions? How should this time period be selected and is there an optimal time period for different tasks?

Also, suppose we have two hash functions $h\_1, h\_2$, and then store values in an array according to $h\_1$. After a while, we switch our has function to be $h\_2$. Do we have to re-hash all of our values according to $h\_2$? This seems rather wasteful

# Answer
> 2 votes
You need to decide what sort of resilience you are expecting from your hash function. While it is true that once picked, your hash function does not change (and in a sense "the rest of the family doesn't exist") but you're ignoring the crucial part of picking the function at random.

Suppose that $\mathcal{H}\subseteq U^{\[m\]}$ is a universal family, $h$ is chosen uniformly at random from $\mathcal{H}$, and is subsequently used to hash elements from $U$ into $m$ cells via chaining. This guarantees that regardless of what is the current content of the table, if the load factor is $\alpha=n/m$, then for every $x\in U$ (note the worst case analysis, as opposed to the average case analysis in the simple uniform hashing case) the expected search/insertion time for $x$ is $O(\alpha)$, where the expectation is taken over the initial choice of $h$ (this is the only place where randomness occurs). This remains true regardless of how many operations were done since the initialization, the random choice of $h$ guarantees low expected search time for all inputs.

Switching might come to mind if you are looking for robustness against certain types of adversaries. If the entire problem was handling a user giving you inputs and hashing them to a table, then everything's fine. This changes if you are looking at the problem of an adversarial user with more access, say e.g. that he might learn the hash value of some elements (which happens in real world attacks based on response time analysis). In that case, the adversarial user might be able to recover $h$ and then send you tailored inputs that will cause high search time. This relied on the adversary having a richer interface than just being able to send arbitrary values (which alone, as we saw above, can't cause problems). Now you're entering the world of cryptographically secure hash functions, and here some switching mechanism might be of use. This requires an entirely different formalization, and to say something interesting about parameters such as switching intervals we need to be clear about what sort of robustness we want to achieve.

---
Tags: data-structures, hash-tables, hashing
---


# Question
Title: Are decidable set/languages EQUIVALENT to type 1 grammars (non-contracting)?
Suppose a Turing Machine (TM\_G) that generates natural numbers following \< or, equivalently, it generates words in lexicographical order.

Then, that language/set is decidable. Because it is trivial to devise a (halting) TM\_R, using TM\_G, that recognize/accepts the words/numbers of that language/set.

It is also clear (really?), that there must be a non-contracting grammar for the language of TM\_G.

Now, let's suppose a we have a TM\_G' that generates a decidable language not in lexicographical order. Because the language is decidable, there must exist a TM\_R' that completely recognizes it. Now, it is not clear how to build TM\_R' using TM\_G' (probably this is a unsolvable problem (is it?). At least, it is easy how to have a semi-deciding TM\_R' based on TM\_G').

In any case, by assumption, TM\_R' (the halting/complete recognizer) does exist. Then, we can use TM\_R' to build a TM\_G'' which generates the language in lexicographical order. Hence (really?), there exists a non-contracting grammar for the language.

In sum, **is the class of decidable languages equivalent to non-contracting grammars?**

In other words, **are there a decidable language that cannot be generated by a non-contracting grammar (type 1)?**

Expressed in terms of Turing Machines: \**is the power of all halting TM equivalent to the power of all linear bounded automata (a restricted type of TM equivalent to type-1 grammars).? \**

# Answer
> 1 votes
Languages which can be described by a type 1 grammar are known as context-sensitive. This class of languages is known to coincide with $\mathsf{NSPACE}(O(n))$, the class of languages which can be accepted by a nondeterministic Turing machine using linear space.

The space hierarchy theorem gives an example of a computable language which is not context-sensitive: the language of all pairs $\langle M, 1^n \rangle$ where $M$ is a nondeterministic Turing machine that halts, on the empty input, while using at most $n^2$ space.

# Answer
> 4 votes
Yuval's answer is absolutely right, but note that there's a more general principle in play here as well: **diagonalization**. Any time we have a class of decidable languages for which we have a "decidable syntactic description" (I'm being vague about this for a moment), we can diagonalize out of this class to get a decidable language not in the class. Basically, we whip up a notion of "$n$th language in the class" and then consider the new language which contains word $1...1$ ($n$ times) iff the $n$th language in the class does *not* contain that word (or something similar); granting the complexity assumption on the starting class, this results in a decidable language.

*(In snappier computability-theoretic terminology: if $f(x,y)$ is a total computable function then there is a total computable $g(z)$ such that for each $x$ there is some $y$ with $f(x,y)\not=g(y)$.)*

Classes like type $1$ grammars are defined by simple syntactic conditions, and so can be diagonalized out of. Of course this does not necessarily result in a **natural** example of a decidable language not in the starting class, but it does prove that that class misses many decidable languages.

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


# Question
Title: How do you "time" the measure of binary streams?
This is just something I've been wondering just out of curiosity. I apologize if this doesn't fall under the category of this forum, and if so feel free to divert me :)

Whenever a computer does anything, it always handles a sequence of bits. My question is: how does it *actually* measure what bit goes in what place? I'm curious of the electric current that gets sent into the transistors, and how these are actually placed correctly in the binary stream. I understand the concept of the transistors and how a threshold voltage determines whether or not a bit is 0 or 1, but how are these bits actually placed in sequence?

Say if we have a binary sequence of 00010010001. How does whatever component handling this stream know how "long" it has to wait with no current before it places a 0-bit, and then moves on? According to my understanding, for the first three 0-bits, there will be no current going into the transistors. But does it have to "wait" for a set amount of time before it determines that a single bit is 0? I'm generally just confused as to how a computer knows the difference between a single 0-bit, and (for example) 10 different 0-bits. When does a computer know to set another bit?. Appreciate any feedback! :)

# Answer
To most components we can attach an internal clock, that is made sure to "tick" at a rate with intervals bigger than the time needed for the current to pass through the circuit. Then, each "tick" the components look at their input and evaluate the output.

This is what defines "when" and "what" a component sees, which (also) allows it to differentiate even between a single 0 and series of 0's.
> 1 votes

---
Tags: cpu
---


# Question
Title: mapping function to map the index of Lower triangular matrix
If I have a Lower triangular matrix of order n and I want to store non-null elements of this matrix in 1D array from first row to last row and within a row from left to right. What could be the mapping function to map the index of Lower triangular matrix Aij in 1D.

# Answer
> 1 votes
Index of $A\_{i,j}$ in $1$-$D$ will be $\frac{i(i-1)}{2} + j$ assuming $1$ based indexing.

---
Tags: data-structures, arrays, matrices
---


# Question
Title: k-polynomial time approximation algorithm for set cover (k = max size of subsets)
**Problem Definition:** Given a universe set $U = \\{1, 2, \dots, n\\}$ and a collection of $m$ subsets $S\_1, S\_2, \dots S\_m \subseteq U$, find the minimum collection of subsets that cover $U$.

I am specifically trying to find a $k$ polynomial time approximation algorithm for set cover where $k$ is the largest size of the subsets. In other words, $k = \max\_{i=1}^m|S\_i|$

I have the following ILP and relaxed LP programs as shown at the end of page 1 and start of page 2 from these lecture notes of Luca Trevisan.

I know that the factor of the polynomial time approximation algorithm depends on the rounding factor necessary in the LP. In the case for weighted set cover, the rounding factor would depend on $m$, the number of subsets.

I have determined a lower bound on the number of subsets based on the defined $k$ to be as follows: $\lceil \frac{n}{k} \rceil \leq m$.

I don't know how to use this (or if this is the correct relationship) to show something along the lines of $A(I) \leq \alpha OPT(I)$ where $A(I)$ is the approximation algorithm solution, $OPT(I)$ is the optimal solution, and $\alpha$ is related to $k$.

How would you go about solving this problem?

# Answer
> 1 votes
Let $A = \\{ i : x\_i \geq 1/k \\}$. By construction, $|A| \leq k \sum\_i x\_i \leq k \mathrm{OPT}$. The set $A$ is a set cover, since if $S\_j = \\{i\_1,\ldots,i\_\ell\\}$ (where $\ell \leq k$) then $x\_{i\_1} + \cdots + x\_{i\_\ell} \geq 1$, and so $\max(x\_{i\_1},\ldots,x\_{i\_\ell}) \geq 1/\ell \geq 1/k$.

---
Tags: algorithms, approximation, linear-programming
---


# Question
Title: Is every decidable language recognizable by a Turing Machine space-bounded by some f(|w|)?
The negative answer to decidable = non-contracting grammar? suggests the following question:

> Is there a decidable language that can be recognized *only* by a space unrestricted Turing Machine (i.e. with infinite tape but in finite time)?

This is, are there words, w, in a decidable language for which cannot be determined a bound f(|w|)?

# Answer
Consider a Turing machine which reads its input and then immediately stops. This Turing machine always halts on every input, but the running time is unbounded: the machine runs for $n$ steps on an input of length $n$.

In fact, most halting Turing machines have unbounded running time: if the running time of a Turing machine is bounded by $T$, then the language it decides can only depend on the first $T$ symbols of the input.

If a Turing machine always halts on any input, then there is a function $f(n)$ such that the Turing machine always halts within $f(n)$ steps on an input of length $n$. You can take as $f(n)$ the maximal time it takes the Turing machine to halt on an input of length $n$. Since there are only finitely many words of length $n$ (recall that the input alphabet is fixed), this is well-defined.

Furthermore, if a Turing machine always halts on any input, the function $f(n)$ defined in the preceding paragraph is always computable. You can compute it by simulating the machine on all possible inputs of length $n$.

Space works exactly the same way.
> 1 votes

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


# Question
Title: Proving Irregularity of $L = \{ a^mb^nb^n \mid nm \ge 3 \} $
I'm trying to prove the irregularity of the following language:

$$L = \\{ a^mb^nb^n \mid nm \ge 3 \\} $$

I tried to demonstrate that it doesn't verifies the Pumping Lemma but for all words I tried it seems to accept all of them.

Any hints or suggestions?

# Answer
> 3 votes
It is regular since $a^\*(bb)^\* \setminus L$ is regular:

$a^\*(bb)^\*\setminus L = a^\* \cup (bb)^\* \cup \\{a^mb^{2n}|1\leq mn \< 3\\}$

The last language of the union is finite thus regular.

# Answer
> 2 votes
Your language is regular. Indeed, the condition $nm \geq 3$ is equivalent to ($n = 1$ and $m \geq 3$) or ($n \geq 3$ and $m = 1$) or ($n \geq 2$ and $m \geq 2$). It is described by the regular expression $$ a (bb)^3(bb)^\* + a^3a^\*bb + a^2a^\*(bb)^2(bb)^\*. $$

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: How to perform AND on binary "recursive repeating sequences"?
Suppose, we have a two binary sequences, encoded as "recursive repeating sequences" (I don't know exactly how to name them). Each sequence can contain other sequences and has number related to how many times this sequence is repeated, or can contain a bit either 0 or 1. Following image describes it visually:

On this image repetition is denoted by lower index number nearby ending bracket. The bits need to be expanded are denoted by regular size font.

Each sequence can produce binary sequence (sequence of bits), when we expand it.

The questions are:

1. Can we create a algorithm, that performs AND on two recursive repeating sequences, without expanding both of them? (The algorithm should produce third recursive repeating sequence, such when we expand it, it is AND on both expanded input sequences).
2. If the answer for first question is true, how such algorithm will look (for example in pseudo code) ?

Note: In practice, the numbers responsible for repetition may be very large, so expansion of whole sequence is not practical in terms of computation - but if algorithm will need to do it partially, it may be accepted.

# Answer
> 1 votes
Let $A,B$ be the two recursive repeating sequences, where $|A| = |B|$. If $|A| = |B| = 1$ then there is nothing to do. Otherwise, either $A$ is of the form $A\_1A\_2$ or of the form $(A')\_k$, where $k \> 1$. In the second case, we can write $A = A' (A')\_{k-1}$, which is also of the form $A\_1A\_2$. Thus it suffices to explain how to compute $A\_1 A\_2 \land B$ (here $\land$ means AND). We will show that we can find two recursive repeating sequences $B\_1B\_2$ such that $B=B\_1B\_2$ and $|A\_1|=|B\_1|$, $|A\_2|=|B\_2|$. We can then compute $A \land B = (A\_1 \land B\_1) (A\_2 \land B\_2)$.

Given a recursive repeating sequence $B$ and a number $\ell$, we have to break $B$ into $B\_1B\_2$, where $|B\_1| = \ell$. We consider two cases:

1. $B = C\_1 C\_2 \dots C\_r$. We can find $t$ such that $|C\_1 C\_2 \dots C\_t| \leq \ell \< |C\_1 C\_2 \dots C\_t| + |C\_{t+1}|$. If $|C\_1 C\_2 \dots C\_t| = \ell$ then we can take $B\_1 = C\_1 C\_2 \dots C\_t$ and $B\_2 = C\_{t+1} \dots C\_r$. Otherwise, we break $C\_{t+1}$ into two parts $D\_1D\_2$, where $|D\_1| = \ell - |C\_1 C\_2 \dots C\_t|$, and take $B\_1 = C\_1 C\_2 \dots C\_t D\_1$ and $B\_2 = D\_2 C\_{t+2} \dots C\_r$.
2. $B = (C)\_r$. We treat this as an explicit description of the preceding case, where $C\_1 = \cdots = C\_r = C$. We use division with remainder to find $t$ efficiently. In the easy case we take $B\_1 = (C)\_t$ and $B\_2 = (C)\_{r-t}$, and in the complicated case we take $B\_1 = (C)\_t D\_1$ and $B\_2 = D\_2 (C)\_{r-t-1}$.

---
Tags: recursion, boolean-algebra, binary, subsequences
---


# Question
Title: Polynomial time optimization problems belong to which complexity class?
I know that $\mathsf{P}$ class is only defined for decision problems. Therefore, a problem like "Does there exist an $(s,t)$ path of length $k$ in the graph $G$?" is in $\mathsf{P}$. One can first find the shortest path from $s$ to $t$ in polynomial time and check if it is smaller than $k$ or not.

Now, consider the optimization version of this problem that we popularly call the *shortest path problem:* "Find a shortest $(s,t)$ path in the graph $G$". Since this is not a decision problem, is it wrong to say that "*shortest path problem* is in $\mathsf{P}$"? If so, in which complexity class does it belong to?

# Answer
> 5 votes
Take a look at the FP complexity class.

Technically speaking, it *is* wrong. However, usually people don't make a huge difference between the two. Its usually clear from the context whether the problem is a decision or a search problem, hence its clear whether it should be in $P$ or $FP$.

So, writing that "Finding the shortest $(s,t)$ path in the graph $G$, is a $P$ problem" would actually mean: "Finding the shortest $(s,t)$ path in the graph $G$, is an $FP$ problem" (since the context is clear)

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


# Question
Title: Using pumping lemma to prove that $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $ is irregular
Given the following language:

$L = \\{ a^ib^j \mid \lvert i - j \rvert \le 2 \\} $

I am trying to prove that it is not regular. On the one hand my intuition tells me that the language is non-regular as there is no way of tracking $a^{i's}$ and $b^{j's}$.

However, when I try to prove that it is irregular using the pumping lemma I have trouble finding which word I should use to arrive at a contradiction.

Any suggestions?

# Answer
> 1 votes
You can use the word $a^pb^p$, where $p$ is the constant promised by the pumping lemma.

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Create a CFG for $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $
I'm trying to find a CFG for the following language:

$L = \\{ a^ib^j \mid \lvert i - j \rvert \le 2 \\} $

What I thought about unsuccessfully is the following:

$S \rightarrow SASBS \mid SBSAS \mid \epsilon$

$A \rightarrow a \mid aa \mid aaa $

$B \rightarrow b \mid bb \mid bbb $

Which has the following problems:

***(1) It does not take into account words that do not have a's or b's***

***(2) It is possible to add a greater number of a's or b's than the allowed distance, for example aaabaaab is a word generated by that CFG***

I've been thinking about it for a long time and it seems like a dead end because it seems that making CFG's is more of an art than anything else, I would greatly appreciate any help

# Answer
You can write your language as a union of simpler languages: $$ \\{ a^{i+2} b^i : i \geq 0 \\} \cup \\{ a^{i+1} b^i : i \geq 0 \\} \cup \\{ a^i b^i : i \geq 0 \\} \cup \\{ a^i b^{i+1} : i \geq 0 \\} \cup \\{ a^i b^{i+2} : i \geq 0 \\} $$
> 2 votes

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


title: Group testing puzzle

text:
# Question
Title: Group testing puzzle
> I have a cake with $n$ layers in total. I know that $k$ are vanilla, and at least $n-k$ are not. I dislike all flavors other than vanilla, so I decide to only eat those layers.
>
> I can't tell which layer is which flavor, but I can smell the vanilla. For any $m$ with $1\le m\le n$, I can test the top $m$ layers of the cake by removing them from the cake and taking them to another room. There, I can smell whether any of those layers are vanilla. Then I can replace those $m$ layers in their proper position on top of the cake.
>
> Once I've performed enough tests to determine if a layer is vanilla, I eat it right out from the middle of the cake, leaving the $n-1$ layers intact. I need to be certain what I eat is vanilla. Then I can return to doing more tests to find the next vanilla layer.
>
> How can I write an algorithm that takes in $n$ and $k$, and outputs the number of tests required to identify (and therefore eat) all of the vanilla layers?

In my opinion, the only way we can do this is by checking every single layer individually... I don't see how taking multiple layers at a time would ever work.

Let vanilla = 1 and other flavors = 0.

Let's say we have a cake 011: and we take 3 at a time, and find there is vanilla, then we anyways need to check every layer.

Let's say we have 0000001 and we take 3 layers, then yes, we can move on to the next 3. But why don't we take 4 or 5? Or 7? if we take 7 though, we'd be back at the first issue.

I think we have to do this individually (it would take $n$ tests) because trying to shorten it simply does not give us enough information. Any clarification would be helpful as this does seem too simple to me!

# Answer
Try to think in terms of binary search:

Start by checking half the cake. Then, if you didn't smell vanilla, you can be sure the first half does not contain vanilla, hence we don't need to check them anymore - hence we save time. **This was only intuiton** to why it might be possible to do better than $O(n)$, not the actual solution for it.

But something important to note is that any algorithm better than $O(n)$ **must** depend on $k$. Its not hard to show a lower bound of $\Omega(k)$
> 2 votes

---
Tags: dynamic-programming
---


# Question
Title: Shortest path given correct order of colours?
I have a directed graph $G=(V,E)$ where each vertex is a 4-D coordinate $v: (x, y, z, c)$ representing spatial coordinates $x, y, z \in \mathbb{R}$ and the non-physical parameter colour $c \in (c\_{1}, c\_{2},... c\_{n})$. The edge weights $\omega\_{v\_{a} \to v\_{b}}: f(x, y, z)$ are purely a function of three of the four dimensions, as this is a *physical* problem.

Trouble is, I wish to find the shortest path given a specific sequence of colors (eg. $c\_{2}, c\_{5}, c\_{1}, c\_{1}, c\_{3}, c\_{4}$). It's difficult to incorporate this into the weight function as it is non-physical. Are there well-established path traversal algorithms that find the shortest path through coloured vertices, given the starting vertex, ending vertex, and the sequence it needs to pass through? I wonder if there is already a family of algorithms that describe this problem?

I've considered something like a Hidden Markov Model that abstracts vertices of colours into hidden states, but I am not sure how to prevent one state from being visited again (whereas in a directed acyclic graph I can prevent revisiting the same vertex).

# Answer
Use a product construction, to construct a new graph whose vertices are given $(x,y,z,k)$, where $k$ counts the index into the sequence of colors (i.e., we are currently at $k$th vertex in that sequence). Then, find the shortest path in this new graph using any standard shortest-path algorithm. If all weights are non-negative, you can use Dijkstra's algorithm on this graph; otherwise you can use Bellman-Ford on this graph.

See How hard is finding the shortest path in a graph matching a given regular language?. Your problem is a special case of the problem solved there. (Possibly also useful: Product construction for given two finite automata .)

Specifically, here is how the product construction works in your setting. Let $(c\_1,c\_2,\dots,c\_q)$ be the desired sequence of colors. Then, for each $k=1,2,\dots,q-1$, you'll have an edge $(x,y,z,k) \to (x,y,z,k+1)$ in the new graph if there is an edge $(x,y,z,c\_k) \to (x,y,z,c\_{k+1})$ in the original graph; the weight of the edge is copied over from the corresponding edge in the original graph. Now, find the shortest path from $(x\_0,y\_0,z\_0,1)$ to $(x\_1,y\_1,z\_1,q)$ in the new graph, where $(x\_0,y\_0,z\_0,c\_1)$ is the starting vertex in the original graph and $(x\_1,y\_1,z\_1,c\_q)$ is the ending vertex in the original graph.
> 3 votes

---
Tags: algorithms, shortest-path, graph-traversal, traveling-salesman, hidden-markov-models
---


# Question
Title: PDA for $\{a^ib^jc^k \mid (i+j) \bmod 3 = 0, k = i + j\}$
> Construct a pushdown automaton that accepts $$\\{a^ib^jc^k \mid (i+j)\bmod 3 = 0, k = i + j\\}$$

# Answer
> 0 votes
Let $L = \\{a^ib^jc^k \mid k = i+j\\}$ and let $R = \\{ a^ib^jc^k \mid i+j \bmod 3 = 0\\}$. The language $L$ is context-free, and presumably you know how to construct a PDA that accepts it. The language $R$ is regular, and presumably you know how to construct a DFA that accepts it. Combine both to obtain a PDA for your language.

---
Tags: pushdown-automata
---


# Question
Title: PDA for the language { $a^i b^j c^k \mid i,j,k \geq0, 7j = 5i + 6k$ }
I have seen this similar question but I can't seem to apply the same technique for the equation $7j = 5i + 6k$

# Answer
> 0 votes
Implement using the stack an accumulator that counts the quantity $$ 5\\#\_a(w) - 7\\#\_b(w) + 6\\#\_c(w), $$ where $w$ is the word read so far, and $\\#\_\sigma(w)$ is the number of $\sigma$ in $w$. This value can be represented, for example, as the empty stack if the accumulator is zero, as $n$ many $+$s if the value is $n$, and as $m$ many $-$s if the value is $m$.

---
Tags: automata, pushdown-automata
---


# Question
Title: Upper bound on the number of subgraphs in a tree
Is there an upper bound of the number of induced subgraphs in a tree (i.e., connected acyclic undirected graph)? The bound can be expressed in terms of vertices, edges, etc.

For example, consider the following graph $G$ represented as edge list: $\\{(S,T),(T,G),(T,B),(B,H),(H,Q)\\}$. The number of connected subgraph (i.e., tree) is (represented by the set of vertices): $\\{S\\}$, $\\{T\\}$, $\\{G\\}$, $\\{B\\}$, $\\{S,T\\}$, $\\{T,G\\}$, $\\{T,B\\}$, $\\{S,T,G\\}$, $\\{B,T,G\\}$,$\\{S,T,B\\}$, $\\{S,T,G,B\\}$, $\\{T,G,B,H\\}$,$\\{T,B,H,Q\\}$, $\\{S,T,B,H\\}$,$\\{S,T,B,H,G\\}$,$\\{T,G,B,H,Q\\}$,$\\{S,T,B,H,Q\\}$, and $\\{S,T,B,H,G,Q\\}$.

I find two seemingly relevant answer that can directly answer my questions  and  but I'm not sure.

# Answer
> 2 votes
Let us prove by induction that any tree on $n$ vertices has at least $2^{n-1} - n$ induced disconnected subgraphs.

When $n = 1$, this is clear since $2^{n-1} - n = 0$. Now suppose $n \> 1$, and let $T$ be a tree on $n$ vertices. Choose an arbitrary leaf $v$, let $T'$ be the tree obtained by removing $v$, and suppose that $v$ is connected to $u \in T'$. By induction, $T'$ has at least $2^{n-2} - (n-1)$ induced disconnected subgraphs. Each of these correspond to two induced disconnected subgraphs of $T$, one including $v$ and one not including $v$. Moreover, for any $w \in T'$ different from $u$, the subgraph induced by $\\{v,w\\}$ is disconnected, and does not arise from an induced disconnected subgraph of $T'$ (since the subgraph of $T'$ induced by $\\{w\\}$ is connected). In total, we get this many induced disconnected subgraphs of $T$: $$ 2(2^{n-2} - (n-1)) + (n-2) = 2^{n-1} - 2(n-1) + (n-2) = 2^{n-1} - n. \quad \square $$

This is tight, as the example of a star shows. If the center of the star is $x$ and the other vertices are $y\_1,\ldots,y\_{n-1}$, then the subgraph induced by any subset of $\\{y\_1,\ldots,y\_{n-1}\\}$ of size at least 2 is disconnected. There are $2^{n-1} - (n-1) - 1 = 2^{n-1} - n$ of these.

---
Tags: graphs, trees, combinatorics
---


title: Prove x . y' . z' is y' . z'

text:
# Question
Title: Prove x . y' . z' is y' . z'
Please, how can I prove that x . y' . z' simplifies to y' . z'?

I have tried without success. Below is the context of my question; I am taking a course on Coursera

# Answer
> 3 votes
Clearly, $x\cdot y'\cdot z'≠ y'\cdot z'$ as it depends on the truth value of $x.$

However, in your specific case, the expression is $(\lnot x\land \lnot z)\lor (x\land \lnot y\land\lnot z).$

Note that if $x$ is false, then the $\lnot x$ literal in the left clause (i.e. $\lnot x\land \lnot z$) will become true, and if it's false then the one in the right clause will be true. So only in this case, it's safe to just "remove" it in the right clause as its truth value specifically in the right clause will not affect the overall outcome. This is because there is a $\lnot z$ in both the clauses. More generally, this is a simple law in Boolean algebra: $$a\cdot b +a\cdot b' = a\cdot (b+b') = a$$

So in this case, it's a slightly more complicated version of $(\lnot x\land \lnot z)\lor (x\land\lnot z)$ which is just $\lnot z.$ Hence it is independent of the value of $x.$

Note, for better understanding, that the 2 clauses are separated with a logical OR ($\lor$) operation, so for the whole expression to be true, either or both of the clauses need to be true.

P.S. - My apologies for the inconsistency in notation. Hope it's okay :)

---
Tags: boolean-algebra
---


# Question
Title: Polynomially Equivalent Pairs of Minimization-Maximization Problems in Weighted Graphs
I am studying computational complexity using Papadimitrious's book: "Computational Complexity". I am trying to solve Problem 9.5.14, about polynomially equivalent minimization-maximization problems in weighted graphs:

> Consider the following pairs of minimization-maximization problems in weighted graphs:
>
> (a) - MINIMUM SPANNING TREE and MAXIMUM SPANNING TREE (we seek the heaviest connecting tree).
>
> (b) - SHORTEST PATH (recall Problem 1.4.15) and LONGEST PATH (we seek the longest path with no repeating nodes; this is sometimes called the TAXICAB RIPOFF problem).
>
> (c) - MIN CUT between $s$ and $t$, and MAX CUT between $s$ and $t$.
>
> (d) - MAX WEIGHT COMPLETE MATCHING (in a bipartite graph with edge weights), and MIN WEIGHT COMPLETE MATCHING.
>
> (e) - TSP, and the version in which the longest tour must be found.
>
> Which of these pairs are polynomially equivalent and which are not? Why?

Let's denote an edge $e \in E$ that connects vertex $u$ and $v$ and has weight $w\_e$ as $e = (u, v, w\_e)$. Let $M = max(|w\_e|) + 1$. I was able to solve some of them by using the following reduction: given a graph $G = (V, E)$ construct the graph $G' = (V, E')$ where you construct the set $E'$ as follows: for each edge $e = (u, v, w\_e) \in E$ add the edge $e' = (u, v, M - w\_e)$ to $E'$. For some of the mentioned problems, the minimization version in graph $G$ is equivalent to the maximization version in graph $G'$.

I was able to solve itens (a), (d) and (e) using this trick. I am not sure if this trick applies to (c), and I think it does not work for (b).

Can anyone tell me if my attempt at itens (a), (d) and (e) are correct? Also, how do I solve itens (b) and (c)? Thanks in advance.

# Answer
> 1 votes
For item (b), the reduction does not work. To understand why, imagine a graph with all edges having the same weight. Then, the reduction has no effect: $G = G'$. Finding the shortest path from $u$ to $v$ consists in finding the path with fewer intermediate nodes, while finding the longest path, consists in finding the path with the highest number of intermediate nodes. The problems are not polynomially equivalent because the shortest path is in $P$ while longest path is in $NP$ (see here).

For item (c), the optimization problem for MAX CUT is NP-hard while for MIN CUT is polynomial. However, when you consider the version of these problems that allows both positive and negative weights they can be trivially converted to each other by flipping the sign in all weights.

---
Tags: complexity-theory, graphs, weighted-graphs, polynomial-time-reductions
---