# Question
Title: How Many Times Would The Assembler Load and Store i
So, this is a snippet of a C code:

```
for (i = 0; i < 20; i++) {
    a[i] = rand() & 0xFF;
    printf("a[%d]: %d\n", i, a[i]);
}

```

Now, imagine "i" is a local variable stored in the stack. How many times would "i" be called from the stack for each iteration? Is it:

> A. Once at the beginning of the loop

or

> B. Three times: once at the beginning, once for assigning the value of a\[i\] and once for the printf function (I assume that they are all stored back to the stack immediately after they are used in this case)

I think it is A but I fear I am thinking about it in terms of what would be optimal and not what the assembler may actually do.

# Answer
> 0 votes
**This answer uses ARMv8 AArch64 Assembly (ARM64)**

```
.LC0:
        .string "a[%d]: %d\n"
square:
        stp     x29, x30, [sp, -128]!
        mov     x29, sp
        str     w0, [sp, 28]
        mov     w0, 1         (A)
        str     w0, [sp, 124] (B)
        b       .L2
.L3:
        bl      rand
        and     w2, w0, 255
        ldrsw   x0, [sp, 124]  (a)
        lsl     x0, x0, 2
        add     x1, sp, 40
        str     w2, [x1, x0]
        ldrsw   x0, [sp, 124] <b>
        lsl     x0, x0, 2
        add     x1, sp, 40
        ldr     w0, [x1, x0]
        mov     w2, w0
        ldr     w1, [sp, 124] <c>
        adrp    x0, .LC0
        add     x0, x0, :lo12:.LC0
        bl      printf
        ldr     w0, [sp, 124] (d)
        add     w0, w0, 1
        str     w0, [sp, 124]
.L2:
        ldr     w0, [sp, 124]
        cmp     w0, 4
        ble     .L3
        ldr     w0, [sp, 28]
        mul     w0, w0, w0
        ldp     x29, x30, [sp], 128
        ret

```

The correct answer here is B. In the compiled code above, it is obvious that (A) and (B) is where the value "i" is moved into a register. If you take note of the address where it is stored \[sp, 124\], you will see that it is loaded in 3 scenarios (although one of the scenarios requires it to be loaded twice - \<b\> and \<c\>).

The first scenario in which it was loaded was when the program initialized a\[i\] (a). The second scenario was when it was called twice for the `printf()` function and the third time was when it was called to be incremented as part of the loop.

It is also worthy to note that the compiler actually only adds a store instruction for a loaded value if it has been changed (I did not know that).

It may be a bit hard to see because it is not color-coded here but you can use this tool called Compiler Explorer that color codes each line so you know exactly what is happening (you can select other Assembly Languages to generate and display).

Finally, a huge thanks to @Knogger for telling me about the Compiler Explorer. Huge help!

# Answer
> 2 votes
What exactly do you mean by “load” and “store”? Accessing memory?

An optimising compiler will assign i to a register. Compilers for modern CPUs with many registers will expect that some set of registers are either not modified or restored by the callee, so i within a register will survive the calls to rand and printf in a register.

So i will not be loaded or stored at all. The register that i is allocated to is saved at the start and restored at the end of the function, assuming an optimising compiler. And a non-optimising compiler doesn’t matter.

# Answer
> 1 votes
To illustrate gnasher729’s answer, here is how the snippet is compiled by gcc. As you can see, the value of `i` is kept in register `rbx` and never written to memory (no space is even allocated to it on the stack). The only memory stores are to `a[i]` (which I made a global variable; I’m not sure that was the intent in the incomplete C code, but whatever. If it is made local, the comiler optimizes it away completely as its values are never used again.):

```
LC0:
        .string "a[%d]: %d\n"
        .text
        .p2align 4
        .globl  f
        .type   f, @function
f:
.LFB39:
        .cfi_startproc
        endbr64
        pushq   %r12
        .cfi_def_cfa_offset 16
        .cfi_offset 12, -16
        leaq    a(%rip), %r12
        pushq   %rbp
        .cfi_def_cfa_offset 24
        .cfi_offset 6, -24
        leaq    .LC0(%rip), %rbp
        pushq   %rbx
        .cfi_def_cfa_offset 32
        .cfi_offset 3, -32
        xorl    %ebx, %ebx
        .p2align 4,,10
        .p2align 3
.L2:
        call    rand@PLT
        movl    %ebx, %edx
        movq    %rbp, %rsi
        movl    $1, %edi
        movzbl  %al, %ecx
        xorl    %eax, %eax
        movl    %ecx, (%r12,%rbx,4)
        addq    $1, %rbx
        call    __printf_chk@PLT
        cmpq    $20, %rbx
        jne     .L2
        popq    %rbx
        .cfi_def_cfa_offset 24
        popq    %rbp
        .cfi_def_cfa_offset 16
        popq    %r12
        .cfi_def_cfa_offset 8
        ret
        .cfi_endproc

```

---
Tags: assembly
---


# Question
Title: How to prove every context-free language over a unary alphabet is regular?
How can I show that every context-free language over a unary alphabet is regular?

# Answer
> 5 votes
The following proof follows Pighizzini, Shallit and Wang, Unary Context-Free Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds.

Let $L$ be a unary context-free language. Assume for simplicity that $\epsilon \notin L$, and consider a grammar $G = \langle V,\\{a\\},P,S \rangle$ for $L$ in Chomsky normal form. Denote $h = |V|$.

In the sequel, whenever we say *parse tree*, we mean *parse tree in $G$*.

Let $\Pi$ be the collection of all triples $(U,i,j)$ such that $U$ is a parse tree rooted at some nonterminal $A$ which represents a derivation of the sentential form $a^i A a^j$, where $0 \< i+j \< 2^h$.

Let $(U,i,j) \in \Pi$, and let $A$ be the label of the root of $U$. Given a parse tree $S$ containing a node $v$ labeled $A$, we can "pump" $S$ by $U$ by replacing $v$ with a copy of $U$, attaching the children of $v$ to the leaf of $U$ labeled $A$.

**Lemma.** If $\ell \> 2^{h-1}$ and $a^\ell \in L$ and $T$ is a parse tree for $a^\ell$, then there exists a triple $(U,i,j) \in \Pi$ and a parse tree $S$ for $a^{\ell-i-j}$ such that $T$ is obtained from $S$ by pumping by $U$.

**Proof.** Since $\ell \> 2^{h-1}$, $T$ must have depth at least $h+1$ (recall that the last level corresponds to productions of the form $A \to a$), and so a path of length $h+1$ edges. This path contains $h+1$ nonterminals, one of which must repeat. Consider such a repetition within the last $h+1$ nonterminals of the path. The repetition corresponds to a triple $(U,i,j) \in \Pi$ (note $i+j \< 2^h$ since we chose a repetition within the last $h+1$ nonterminals, and $i+j \> 0$ since the grammar is in Chomsky normal form). By "pumping out" this derivation, we obtain the parse tree $S$ for $a^{\ell-i-j}$. $\quad\square$

**Corollary.** Every parse tree in $L$ can be obtained in the following way:

* Start with a parse tree for some $a^\ell$, where $\ell \leq 2^{h-1}$.
* Repeatedly pump by $U$ for some $(U,i,j) \in \Pi$.

Using this, we can construct an NFA for $L$:

* Guess a parse tree for some $a^\ell$, where $\ell \leq 2^{h-1}$, and read the word $a^\ell$.
* Set $X$ to be the set of nonterminals appearing in the parse tree.
* Perform the following operation an arbitrary number of times:
    1. Guess $(U,i,j) \in \Pi$ such that the label of the root of $U$ appears in $X$.
    2. Read $a^{i+j}$.
    3. Add all nonterminals in $U$ to $X$.

This shows that $L$ is regular.

Parikh's theorem can be proved in the same way.

# Answer
> 3 votes
You could use the more general fact (due to Parikh) that the commutative image of a context-free language of $A^\*$ is a rational subset of $\mathbb{N}^{|A|}$. For a unary alphabet, this gives your statement.

# Answer
> 0 votes
This follows easily from Parikh's theorem, but there is also a relatively short proof using the pumping lemma (which is easier to prove than Parikh's theorem).

# Answer
> -1 votes
This was my first attempt at it:

First let $L$ be our context free language. Using the pumping lemma for context free grammars: the pumping constant is $p$ and $m \ge p$.

We have a string $s = 1^m = uvwxy$, and we say $a\_m = |uwy|$ and $b\_m = |vx|$ such that $s = 1^{a\_m}1^{b\_m}$ where $1 \le b\_m \le p$

Because our language was context free, we can say this about a string. Now let us define two more languages:

$$Mod = \\{m \in \mathbb{N} | 1^m \in L\\}$$

$$ L' = \\{x \in L| |x| \< p\\}$$

Now we can construct out language $L$ from of finite union of regular languages, meaning it is regular:

$$ L = L' \cup \bigcup\_{m \in Mod} 1^{a\_m}1^{b\_m} = L' \cup \bigcup\_{m \in Mod} 1^{a\_m}(1^{b\_m})^\* $$

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


# Question
Title: How to Solve the Recurrence Relation $T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2$ in terms of $\Theta$?
The provided recurrence relation is as follows:

$$ T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2 $$

The goal is to express the solution in terms of the asymptotic notation $\Theta$. Unfortunately, the Master's Theorem and Akra-Bazzi methods do not apply directly to this recurrence. Drawing a recursion tree would be quite challenging due to the square root term. Also I know about induction to prove the bounds, but I need a good guess that I'm not able to find it.

Any helps are appreciated!

# Answer
It’s asymptotically the same as the simple recurrence $$T'(n)=8T'(n/4)+n^2,$$ which solves to $T'(n)\sim2n^2$ by any of the common methods (where as usual, I write $f(n)\sim g(n)$ for $\lim\_{n\to\infty}f(n)/g(n)=1$).

On the one hand, $T'(n)\sim2n^2$ provides an upper bound on $T$. If you want to only estimate the recurrence up to $\Theta$, you are done: $n^2\le T(n)\le T'(n)=O(n^2)$ gives $$T(n)=\Theta(n^2).$$ For a more precise estimate, let us unwind the recurrence: $$\begin{align\*} T(n)&=n\_0^2+8n\_1^2+8^2n\_2^2+\cdots,\\ n\_0&=n,\\ n\_{i+1}&=(n\_i-\sqrt{n\_i})/4. \end{align\*}$$ You can prove by induction on $i$ that for any constant $i\ge0$, $$n\_i\sim4^{-i}n.$$ It follows that for any constant $k$, the sum of the first $k$ terms of $T(n)$ is $${}\sim(2-2^{1-k})n^2.$$ Thus, for any constant $\epsilon\>0$, $T(n)\ge(2-\epsilon)n^2$ for sufficiently large $n$ (depending on $\epsilon$), that is, $$T(n)\sim2n^2.$$ More precisely, one can show that both $T(n)$ and $T'(n)$ are $2n^2+O(n^{3/2})$ (where the hidden constant depends on the initial conditions).
> 1 votes

# Answer
$(n - \sqrt n) / 4$ is slightly smaller than n/4, for example \>= $n \cdot (3/16)$ if n \>= 16. So you get a lower limit if you take $8T(n \cdot (3/16)) + n^2$

If n \>= 64, then $n - \sqrt n \>= n \cdot (7/8)$, and the larger n is, the closer that factor is to 1. You take $8T(n \cdot (7/32)) + n^2$ as a lower bound if n \>= 64, and so on as n grows. Combine the results, and you get the same results as for $8T(n / 4) + n^2$.

This is big-O. For small n, $n - \sqrt n$ is substantially smaller than n, so there will be a very small constant factor. You can define T(0) = c, and use $T(\lfloor (n - \sqrt n) / 4 \rfloor) + n^2$ for n \>= 1 and calculate the first 1000 values to see this.
> 0 votes

---
Tags: time-complexity, asymptotics, recurrence-relation, recursion
---


# Question
Title: Proving that the scramble of a regular language is context-free
> For strings $w$ and $t$, if they have the same length and comprise the same characters (namely, they are two permutations of these characters), then $w\sim t$. For a string $w$, define an operator $\operatorname {SCRAMBLE}$ such that $$\operatorname {SCRAMBLE}(w):=\\{t\mid t\sim w\\}, $$ and for a language $A$, $$\operatorname {SCRAMBLE}(A):=\\{t\mid t\sim w, \exists w\in A\\}.$$ Prove that: given an alphabet $\Sigma:=\\{0,1\\}$, for any regular language $L$, $\operatorname {SCRAMBLE}(L)$ is a context-free language.

I have tried to use the pumping lemma of regular language to show that it satisfies the pumping lemma of context-free language after the $\operatorname {SCRAMBLE}$ operation, but I failed to find the pumping substring of $\operatorname {SCRAMBLE}(L)$. I have also tried PDA construction but to no avail. Can anyone help me with it? Any answer or hint will be appreciated. Thanks in advance.

# Answer
> 9 votes
First, two remarks. When $L = (01)^\*$, we have $\newcommand{\scramble}{\mathrm{SCRAMBLE}}\scramble(L) \cap 0^\*1^\* = \\{ 0^n 1^n : n \geq 0 \\}$, and this shows that we can't expect $\scramble(L)$ to be regular.

Second, when $L=(012)^\*$, we have $\scramble(L) \cap 0^\*1^\*2^\* = \\{ 0^n 1^n 2^n : n \geq 0 \\}$. This shows that it's important that the alphabet have only two symbols.

Now for the proof. It is actually enough to assume that $L$ is context-free (and not necessarily regular). For a word $w$, let $p(w) = (\\#\_0(w),\\#\_1(w))$, and define $P(L) = \\{ p(w) : w \in L \\}$. Parikh's theorem states that $P(L)$ is a *semilinear* set, that is, a finite union of sets of the form $$ x + \sum\_{i=1}^m \mathbb{N} y\_i, $$ where $x,y\_1,\ldots,y\_m \in \mathbb{N}^2$. It is thus enough to show that for every linear set $S$, the language $L(S)$ of words $w$ such that $p(w)$ belongs to $S$ is context-free.

A pushdown automaton accepting $L(S)$ proceeds as follows. We will assume for simplicity that $x = (0,0)$; for general $x = (x\_0,x\_1)$, the PDA will ignore the first $x\_0$ zeroes and $x\_1$ ones, but will only accept if these actually appear.

When the PDA starts running, it guesses a mode $i \in \\{1,\ldots,m\\}$. When it reads $0$, it pushes it to the stack. Meanwhile, it keeps track of the number of $1$s it has read. Once it has read $(y\_i)\_1$ of them, it removes $(y\_i)\_0$ zeroes from the stack (pushing, if necessary, "negative" $0$s which will get cancelled later with actual $0$s). Then it guesses another mode $i \in \\{1,\ldots,m\\}$ (possibly the same one).

Upon reaching the end of input, the automaton verifies that it hasn't read any $1$s in its current phase, and that the stack is empty. This completes the construction. We leave it to the reader to prove that it actually works.

# Answer
> 4 votes
We can prove this without using Parikh's theorem. Assume that a language $L$ over the two-letter alphabet $\\{0,1\\}$ is given by a finite-state machine. For the language $\mathrm{SCRAMBLE}(L)$ we construct an automaton with one register capable of holding any integer (positive or negative). The states are the same as in the finite-state machine. Transitions that read $1$s are simply copied to the automaton. Transitions that read $0$s are replaced by transitions that decrease the register. In addition, at each state we add a loop transition that reads a $0$ from the input tape and increases the register. This one-register automaton accepts the language $\mathrm{SCRAMBLE}(L)$ if we require the register to contain zero at the end. Indeed, let $w \in L$ and $t \in \mathrm{SCRAMBLE}(w)$. In order to accept the word $t$, our non-deterministic automaton guesses the word $w$ and follows the same sequence of states as the original finite-state machine that reads $w$. During this process the integer register keeps track of surplus $0$s seen in the word $t$ (this number can be negative).

Finally, we convert this automaton with one integer register to an ordinary pushdown automaton with two stack symbols, one of them used for representing positive values of the register, the other one for negative values. These two stack symbols are $A$ and $B$; they play the same role as the stack symbols "zero" and "negative zero" in Yuval Filmus's answer. We require the stack to be empty at the end. It can be shown that this pushdown automaton recognizes the language $\mathrm{SCRAMBLE}(L)$.

A direct formal construction follows. Here we skip the intermediate step with the one-register automaton and go straight to the final PDA. We are going to use the definition of a PDA without initial stack symbol and with the following acceptance mode: an input string is accepted at a configuration if the complete input string has been read, the stack is empty, and the PDA is in one of its accepting states.

Suppose $L$ is recognized by a non-deterministic finite automaton, which is a tuple $M=(Q,\Sigma,\delta,q\_0,F)$, where $Q$ is a finite set, $\Sigma = \\{0,1\\}$, $\delta$ is a function from $Q \times \Sigma$ to $\mathcal{P}(Q)$, $q\_0 \in Q$, and $F \subseteq Q$. If we follow the above construction, then for $\mathrm{SCRAMBLE}(L)$ we obtain the PDA $M'=(Q,\Sigma,\Gamma,\delta',q\_0,F)$, where $\Gamma = \\{A,B\\}$ and \begin{align\*} \delta'={}&\\{(p,\epsilon,\epsilon,q,\epsilon) \mid q \in \delta(p,\epsilon)\\}\\ &\cup\\{(p,1,\epsilon,q,\epsilon) \mid q \in \delta(p,1)\\}\\ &\cup\\{(p,\epsilon,A,q,\epsilon) \mid q \in \delta(p,0)\\}\\ &\cup\\{(p,\epsilon,\epsilon,q,B) \mid q \in \delta(p,0)\\}\\ &\cup\\{(p,0,B,p,\epsilon) \mid p \in Q\\}\\ &\cup\\{(p,0,\epsilon,p,A) \mid p \in Q\\}. \end{align\*} We define a function $\mathrm{unary}:\mathbb{Z}\to\Gamma^\*$ by putting $\mathrm{unary}(n)=A^n$ for non-negative $n$ and $\mathrm{unary}(n)=B^{-n}$ for negative $n$. For example, $\mathrm{unary}(2)=AA$ and $\mathrm{unary}(-2)=BB$. One can prove that if $|w|\_1=|t|\_1$ and $(q\_0,w)\vdash\_M^\*(q,\epsilon)$, then $(q\_0,t,\epsilon)\vdash\_{M'}^\*(q,\epsilon,\mathrm{unary}(|t|\_0-|w|\_0))$. (We use induction on the number of steps plus $|t|\_0$.) Thus, if $M$ accepts $w$, $|w|\_1=|t|\_1$, and $|w|\_0=|t|\_0$, then $M'$ accepts $t$.

On the other hand, by induction on the number of steps one can prove that if $(q\_0,t,\epsilon)\vdash\_{M'}^\*(q,\epsilon,\gamma)$, then there exists a word $w$ such that $|w|\_1=|t|\_1$, $|t|\_0-|w|\_0 = |\gamma|\_A-|\gamma|\_B$, and $(q\_0,w)\vdash\_M^\*(q,\epsilon)$. Thus, if $M'$ accepts $t$, then $M$ accepts $w$ for some $w$ satisfying $|w|\_1=|t|\_1$ and $|w|\_0=|t|\_0$.

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


# Question
Title: Is $L = \{ \langle G,k\rangle \mid G $ has a simple cycle at length $k \}$ in P or in NP
$ L = \\{ \<G,k\> |\ G \ has \ a \ simple \ cycle \ at \ length \ k \\} $

I think this language is in NP but my friend thinks this language is in P.

NP proof: if a graph has a simple cycle of a specific length can be verified quickly if we are given the cycle as a certificate.We can check in polynomial time that the given cycle is simple (doesn't repeat vertices except the first and last to make a cycle) and that it has exactly k + 1 edges.

$ R\_L = {\<G,k \>,\<C\>} $

where C is a cycle of k size in the graph,{qstart,q2....qend} V verifier will:

1. take qstart, and follow the next q until reaching qend, if qend and qstart are different then reject. if the cycle has different number of nodes then k, regect. if that is not a simple cycle ( going over the same node twice), then regect
2. accept

so $ \<G,k \> \in L $ then S is a simple cycle and the verifier will accept. and if $ \<G,k \> \notin L $ then S is not a simple cycle, or the size is not k then will reject.

my friend proof in P: there exists a polynomial deterministic in the size of the input: for each \<G,k\>:

1. run a DFS for each vertex: a. check for a cycle of size k if not exactly k then reject (when running DFS reaching to the same vertex) if there is a simple cycle of size k then accept. b. if all reject then reject.

time complexity $ O((V+E) \cdot V) $ the turning machine is deterministic. and: $ \<G,k\> \in L $ there exist a cycle size k , the machine will recognize it and return true.

$ \<G,k\> \notin L $ the machine will not find a cycle of size k and will reject

does my friend approach is correct and the language is in P?

# Answer
> 2 votes
Your understanding of how to demonstrate that a language belongs to NP is correct. If a language L consists of instances where each instance is a graph G and an integer k, and L is defined as the set of all instances \<G,k\> where G contains a simple cycle of length k, then yes, the verification process you've described can indeed be performed in polynomial time given a certificate (in this case, the cycle itself). This establishes that L is in NP.

Regarding your friend's argument for L being in P, the critical point is whether there exists an efficient polynomial-time algorithm to find a simple cycle of length k in a graph. The approach suggested by your friend involves running Depth-First Search (DFS) from each vertex to look for a cycle of exactly length k. However, there are some nuances that need to be addressed to evaluate the correctness and efficiency of this approach.

### Correctness

The idea of using DFS to find cycles is a standard approach in graph algorithms. DFS can indeed be used to find cycles in a graph, but finding a cycle of a specific length efficiently is more challenging. The complexity of finding a cycle of exactly length k using DFS from each vertex isn't as straightforward as O((V+E)⋅V) without more specifics on how these cycles of exactly length k are being identified during the DFS process.

### Efficiency

The claim of O((V+E)⋅V) time complexity for finding a cycle of exactly length k seems overly optimistic without further explanation. The process of checking every possible path of length k from each vertex doesn't straightforwardly translate to a polynomial-time operation for arbitrary k. As k grows, the number of potential paths to explore grows exponentially.

For small fixed values of k, it's possible to argue a polynomial-time complexity, but for arbitrary k, the problem of finding a simple cycle of exactly length k is more aligned with known hard problems. Specifically, the problem of finding a simple cycle of length k is NP-complete for general graphs, as it can be reduced from the Hamiltonian cycle problem, which is well-known to be NP-complete.

### Conclusion

The approach your friend suggested would need more detail to be evaluated as a correct polynomial-time algorithm for the problem. While DFS is a powerful tool in graph theory, using it to find cycles of a specific length efficiently for arbitrary k is not trivially in P as suggested. The primary challenge is that, without additional constraints or techniques, the search space for cycles of length k can become prohibitively large, leading to exponential time complexity in the worst case.

In summary, your assertion that the problem is in NP is correct, as verifying a solution is polynomially bounded.

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


# Question
Title: Table driven parser vs Recursive Descent parser
I am currently writing an LL(1) parser. At several places (Engineering a Compiler book, Dragon book, or this discussion), I have seen two ways to go about this, either with a table driven parser (using FIRST, FOLLOW sets) which is basically a large 2D array that predicts which rule should be called or the recursive descent method.

I wanted to know if using a table driven parser would be (is?) feasible since even for a relatively small grammar, the parsing table would get very large since the parsing table I saw just for this grammar that parses (incomplete) expressions is a 5x6 array. here

```
E --> TE'
E' --> +TE' | ε
T --> FT'
T' --> *FT' | ε
F --> id | (E)

```

# Answer
> 1 votes
100 x 100 entries wouldn’t be considered large. And in each row of the table, you can store only entries for members of the follow set, which reduces the table size massively. So 1,000 x 1,000 entries with 50 entries in the follow set on average you need only 50,000 entries which is quite trivial. And a recursive descent parser would have to handle the exact same number of cases.

---
Tags: compilers, parsers
---


# Question
Title: Are there context-free languages whose both intersection and complement of intersection are non-context-free?
It is well known that context-free languages are not closed under intersection or complement. But what about context-free languages $L\_1$ and $L\_2$, such that $L\_1 \cap L\_2$ as well as $\left( L\_1 \cap L\_2 \right)^C$ are not context-free languages.

I can think of many examples of two context-free languages whose intersection is non-context-free, but I can't come up with an example with complement of intersection being also non-context-free (e.g. popular counterexample for closure under intersection, where $L\_1 = \\{ a^n b^n c^m \mid n, m \geq 0 \\}$ and $L\_2 = \\{ a^m b^n c^n \mid n, m \geq 0 \\}$ with $L\_1 \cap L\_2 = \\{ a^n b^n c^n \mid n \geq 0 \\}$ discussed here: Why are CFLs not closed under intersection? and here: Prove complement a^nb^nc^n is contextfree).

I suspect there are not such languages $L\_1$ and $L\_2$, but I'm far from being sure. The only thing I'm certain of is that at least one of languages $L\_1^C$ and $L\_2^C$ would have to be non-context-free (otherwise, as a result of closure under union, language $L\_1^C \cup L\_2^C = \left( L\_1 \cap L\_2 \right)^C$ would be context-free).

# Answer
Here is a recipe to construct such a language, using examples we know. Start with a context-free language $K\_0$ such that its complement $K\_0^C$ is not context free. Also consider two context-free languages $K\_1$ and $K\_2$ such that their intersection $K\_1\cap K\_2$ is not context-free.

Note that for any language $K = a{\cdot} K\_a \cup b{\cdot}K\_b$, we have $K^C = a{\cdot} K^C\_a \cup b{\cdot}K^C\_b \cup \\{\varepsilon \\}$, which intuitively means that we can separate complements using the first symbol of the strings.

Using this observation, consider $L\_1 = a{\cdot}K\_0 \cup b{\cdot}K\_1$, and likewise $L\_2 = a{\cdot}K\_0 \cup b{\cdot}K\_2$.

First, $L\_1\cap L\_2$ is not context-free, because $(L\_1\cap L\_2) \cap b{\cdot}\Sigma^\* =b\cdot(K\_1\cap K\_2)$ is not context-free.

Similarly $(L\_1\cap L\_2)^C$ is not context-free because $(L\_1\cap L\_2)^C\cap a{\cdot}\Sigma^\* = a{\cdot}K^C\_0$.

Perhaps someone else will find an elegant direct example.
> 2 votes

# Answer
We can build a specific example over the alphabet $\\{a,b,c\\}$ as follows. Let $L\_1 = \\{ a^k b^m c^j \mid j \< m \lor k \< m \\}$ and $L\_2 = \\{ a^k b^m c^j \mid k \< 2m \\}$. Obviously, $L\_1 \cap L\_2 = \\{ a^k b^m c^j \mid ( j \< m \land k \< 2m ) \lor k \< m \\}$. We are going to prove that both $L\_1 \cap L\_2$ and $(L\_1 \cap L\_2)^C$ are non-context-free. The following proof consists in two straightforward applications of the pumping lemma (using intersection with a simple regular language where necessary).

Suppose to the contrary that $L\_1 \cap L\_2$ is context-free. The pumping lemma yields a number $p$. We consider the word $a^{2p+1} b^{p+1} c^p$, which is in $L\_1 \cap L\_2$. The pumping lemma gives a partition $uvwxy = a^{2p+1} b^{p+1} c^p$. If neither $v$ nor $x$ contains $b$, then we put $n=2$ and note that $uvvwxxy \notin L\_1 \cap L\_2$. Otherwise we put $n=0$ and consider the word $uwy$. If neither $v$ nor $x$ contains $a$, then $uwy$ contains $2p+1$ letters $a$, which is too many compared to the reduced number of letters $b$. Suppose that $v$ or $x$ contains $a$. Then neither of them contains $c$, because the letters $c$ are too far from the letters $a$. Let $uwy = a^k b^m c^j$. We see that $k = 2p + 1 - |vx|\_a$, $m = p + 1 - |vx|\_b$, $j = p$. Thus, $j = p \geq m$. On the other hand, $k \geq p + 1 \geq m$. Thus, $uwy \notin L\_1 \cap L\_2$. In all cases we have obtained a contradiction, and so $L\_1 \cap L\_2$ is not context-free.

Now suppose to the contrary that $(L\_1 \cap L\_2)^C$ is context-free. Consider the language $L = (L\_1 \cap L\_2)^C \cap \\{ a^k b^m c^j \mid k \geq 0,\ m \geq 0,\ j \geq 0 \\}$. The intersection of a context-free language with a regular language is always context-free. Applying the pumping lemma for context-free languages to $L$, we obtain a number $p$. We consider the word $a^p b^p c^p$, which is in $L$. The pumping lemma gives a partition $uvwxy = a^p b^p c^p$. If neither $v$ nor $x$ contains $b$, then we put $n=0$ and see that $uwy \in L\_1 \cap L\_2$, whence $uwy \notin L$. Otherwise we put $n=2$ and consider the word $uvvwxxy$. If neither $v$ nor $x$ contains $a$, then $uvvwxxy$ contains $p$ letters $a$ and more that $p$ letters $b$, which yields $uvvwxxy \in L\_1 \cap L\_2$, whence $uvvwxxy \notin L$. Suppose that $v$ or $x$ contains $a$. Then neither of them contains $c$, because the letters $c$ are too far from the letters $a$. Let $uvvwxxy = a^k b^m c^j$. We see that $k = p + |vx|\_a$, $m = p + |vx|\_b$, $j = p$. Thus, $j = p \< m$. On the other hand, $k \leq 2p \< 2m$. Thus, $uvvwxxy \in L\_1 \cap L\_2$, whence $uvvwxxy \notin L$. In all cases we have obtained a contradiction, and so $(L\_1 \cap L\_2)^C$ is not context-free.
> 2 votes

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


title: Model checking algorithms

text:
# Question
Title: Model checking algorithms
Given a knowledge base and a proposition alpha we can check if our knowledge base entails alpha using a model checking algorithm that functions as such : we generate a set of all the possible models ,and if for each model where our knowledge base is true alpha is also true we can conclude that our knowledge base entails alpha. What would happen if our knowledge base contains contradictry propositions ?

# Answer
If your knowledge base contains contradictory propositions, then everything can be derived from that. See, e.g., https://en.wikipedia.org/wiki/Principle\_of\_explosion.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Convert ternary constraint into set of binary
I have the following ternary constraint that needs to be converted into a set of binary constraints in order to be used for a constraints solving problem:

```
A = max(b,c)+1

```

How can I do this?

I am allowed to introduce a new variable X to do this.

# Answer
You can't. You add the constraints `A <= b+1` and `A <= c+1` but there is no set of binary constraints that are equivalent to your original constraint. This is true even if you're allowed to add additional variables.
> -1 votes

---
Tags: constraint-satisfaction
---


# Question
Title: Is $O(n^{f(n)})$ superexponential if $f(n)$ is a polynomial function such that $f(n) > n$ as $n$ approaches $\infty$?
I know that exponential time complexity is $ O(k^n) $, where $k$ is some constant and $n$ is the input size, and that subexponential time is anything slower than that, $o(k^n)$ . If we define superexponential time complexity as anything faster than exponential time, $\omega(k^n)$, and given $O(n^{f(n)})$, where $f(n)$ is a polynomial function such that $f(n) \> n$ as $n$ approaches $\infty$, would that be superexponential time complexity?

I guess what I'm more generally asking is, in $ O(k^n) $, does $n$ need to be just the input size $n$ or can it be $f(n)$ for time complexity to still be considered exponential?

I presume it would since I know that in algorithms such as the quadratic sieve whose time complexity is $O(exp(f(n)))$, where $f(n)$ \< $n$ as $n$ approaches $\infty$, the time complexity is subexponential.

# Answer
Exponential time is often described as complexity in $\mathcal{O}(2^{p(n)})$ for a polynomial function $p$ rather than $\mathcal{O}(k^n)$. See here for some references.

What you describe is the complexity of the class $\mathsf{E}$.

Nevertheless, using your definitions, if $f$ is a polynomial function greater than $n$, then $n^{f(n)}$ is indeed superpolynomial.

Since $f(n) \> n$ at infinity, that means that $f(n) = an^d + g(n)$, with $d\geqslant 1$ and $g(n) =o(n^d)$.

Therefore, for any $k\in \mathbb{N}$: $$\frac{n^{f(n)}}{k^n} = \frac{2^{f(n)\log n}}{2^{n\log k}} = 2^{f(n)\log n - n\log k}\underset{n\rightarrow +\infty}{\longrightarrow}+\infty$$

This is because for $n$ big enough, $f(n)\log n - n\log k \> n(\log n - \log k)$ and $k$ is a constant.

That means that $n^{f(n)}\notin \mathcal{O}(k^n)$.
> 2 votes

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


# Question
Title: Find 1s in almost all 0 array using comparisons only
So, we are given a 100 long array, with 97 0s and 3 1s of which we do not know the locations. We must find them using only a compare function, which I managed to write (in Python):

```
def compare(i, j):
    comparisons.append((i, j))
    if data[i] == data[j]:
        return 0
    else:
        return 1 if data[i] > data[j] else -1

```

Using this function, we must find all three 1s with using at most 73 comparisons. We must output the compared pairs as a tuple as well as the coordinates of the three 1s.

Now, I tried writing a code with the following logic:

And I thought that maybe because two 1s will use 2 instead of 3 comparisons, it might come down do 73. This was not only long to code (I am studying mathematics, not CS), but I wrote to my prof, and he said this wouldn't work, and that I should try dynamic programming. I'm a bit lost, as I've never solved a coding program that is this limiting, so I have an other idea, which is to do a first parse of the array, going in pairs, so comparing (data\[0\], data),(data\[2\], data\[3\]),.... This way, no matter how the 1s are placed, I ought to find at least one of them. I would also store all of the results of these comparisons, and then cross-check them with a set of new comparisons, namely (data,data\[2\]),(data\[5\],data\[6\]),...

Any help is appreciated, specific code would be most useful, so I can understand how such a method would work.

Edit: I almost have it now thanks to @orlp, but I don't see why I still get 75 comparisons:

```
comparisons = []

def compare(i, j):
 comparisons.append((i, j))
 if data[i] == data[j]:
   return 0
 else:
   return 1 if data[i] > data[j] else -1

def find_ones(data):
 found_ones = []

 for i in range(0, len(data), 2):
   if compare(i, i + 1) != 0:
     found_ones.append(i if data[i] == 1 else i + 1)
     if len(found_ones) == 3:
       return comparisons, found_ones[0], found_ones[1], found_ones[2]

 remaining_pairs = [i for i in range(0, len(data), 2) if i not in found_ones]
 for i in range(0, len(remaining_pairs) - 1, 2):
   if compare(remaining_pairs[i], remaining_pairs[i + 1]) != 0:
     found_ones.extend([remaining_pairs[i], remaining_pairs[i + 1]])
     break

 if len(found_ones) == 1:
   found_ones.extend(remaining_pairs[-2:])

 return comparisons, found_ones[0], found_ones[1], found_ones[2]

def get_input_data():
 position_1 = int(input("Enter position of first '1' (0-99): "))
 position_2 = int(input("Enter position of second '1' (0-99): "))
 position_3 = int(input("Enter position of third '1' (0-99): "))

 data = [0] * 100
 data[position_1] = data[position_2] = data[position_3] = 1
 return data

data = get_input_data()
comparisons, a, b, c = find_ones(data.copy())

print("Comparisons:")
for pair in comparisons:
 print(pair)

print("\nPositions of '1's:")
print(a, b, c)

print("\nNumber of comparisons:", len(comparisons))

```

I included the optimizations at the end, didn't I? Don't do the last comparison, if only one 1 has been found the first time around, and the second time don't do the last comparison, because by then we know them to be 1s.

Edit 2: I fixed, some of the issues in the first half, but I just do not see why it isn't down to 73 steps. Also now, it is returning false values. What am I doing wrong?

```
comparisons = []

def compare(i, j):
    comparisons.append((i, j))
    if data[i] == data[j]:
        return 0
    else:
        return 1 if data[i] > data[j] else -1

def find_ones(data):
    found_ones = []

    # Step 1: Initial pairing and comparisons
    for i in range(0, len(data)-2, 2):
        if compare(i, i + 1) != 0:  # One of them is a '1'
            found_ones.append(i if data[i] == 1 else i + 1)
            if len(found_ones) == 3:  # Found all three '1's
                return comparisons, found_ones[0], found_ones[1], found_ones[2]

      # Check if we need to compare the final pair
    if len(found_ones) == 2:
        result = compare(len(data) - 2, len(data) - 1)
        if result == 1:   # '1' is at index len(data) - 2
          found_ones.append(len(data) - 2)
        elif result == -1:  # '1' is at index len(data) - 1
          found_ones.append(len(data) - 1)

    if len(found_ones) == 3:  # Found all three '1's
                return comparisons, found_ones[0], found_ones[1], found_ones[2]

    # Step 2: Find the pair with the remaining two '1's
    remaining_pairs = [i for i in range(0, len(data), 2) if i not in found_ones]
    for i in range(0, len(remaining_pairs) - 1, 2):
        if compare(remaining_pairs[i], remaining_pairs[i + 1]) != 0:  # Found the (1, 1) pair
            found_ones.extend([remaining_pairs[i], remaining_pairs[i + 1]])
            break

    # Step 3: If necessary, deduce the last pair
    if len(found_ones) == 1:
        found_ones.extend(remaining_pairs[-2:])  # The remaining pair must be (1, 1)

    return comparisons, found_ones[0], found_ones[1], found_ones[2]

# Example usage
def get_input_data():
    # Replace this with your preferred input method (e.g., user input)
    position_1 = int(input("Enter position of first '1' (0-99): "))
    position_2 = int(input("Enter position of second '1' (0-99): "))
    position_3 = int(input("Enter position of third '1' (0-99): "))

    data = [0] * 100
    data[position_1] = data[position_2] = data[position_3] = 1
    return data

data = get_input_data()
comparisons, a, b, c = find_ones(data.copy())  # Use copy to avoid modifying original

print("Comparisons:")
for pair in comparisons:
    print(pair)

print("\nPositions of '1's:")
print(a, b, c)

print("\nNumber of comparisons:", len(comparisons))

```

Edit 3:

```
comparisons = []

def compare(i, j):
  comparisons.append((i, j))
  if data[i] == data[j]:
    return 0
  else:
    return 1 if data[i] > data[j] else -1

def find_ones(data):
  found_ones = []
  excluded_indices = set()  # Track indices already found

  # Step 1: Initial pairing and comparisons
  for i in range(0, len(data) - 2, 2):
    result = compare(i, i + 1)
    if result == 1:
     found_ones.append(i)
     excluded_indices.update({i, i + 1})  # Update excluded indices
    elif result == -1:
     found_ones.append(i + 1)
     excluded_indices.update({i, i - 1})  # Update excluded indices

    if len(found_ones) == 3:
        return comparisons, found_ones[0], found_ones[1], found_ones[2]

   # Check if we need to compare the final pair
  if len(found_ones) == 2 and (len(data) - 2) not in excluded_indices and (len(data) - 1) not in excluded_indices:
    result = compare(len(data) - 2, len(data) - 1)
    if result == 1:
     found_ones.append(len(data) - 2)
     excluded_indices.update({len(data) - 2, len(data) - 1})  # Update excluded indices
    elif result == -1:
     found_ones.append(len(data) - 1)
     excluded_indices.update({len(data) - 2, len(data) - 1})  # Update excluded indices

  if len(found_ones) == 3:
        return comparisons, found_ones[0], found_ones[1], found_ones[2]

  # Step 2: Find the pair with the remaining two '1's
  remaining_pairs = [i for i in range(0, len(data), 2) if i not in excluded_indices]
  for i in range(0, len(remaining_pairs) - 1, 2):
    if compare(remaining_pairs[i], remaining_pairs[i + 1]) != 0:
      found_ones.extend([remaining_pairs[i], remaining_pairs[i + 1]])
      break

  # Step 3: If necessary, deduce the last pair
  if len(found_ones) == 1:
    found_ones.extend(remaining_pairs[-2:])

  return comparisons, found_ones[0], found_ones[1], found_ones[2]

# Example usage
def get_input_data():
    position_1 = int(input("Enter position of first '1' (0-99): "))
    position_2 = int(input("Enter position of second '1' (0-99): "))
    position_3 = int(input("Enter position of third '1' (0-99): "))

    data = [0] * 100
    data[position_1] = data[position_2] = data[position_3] = 1
    return data

data = get_input_data()
comparisons, a, b, c = find_ones(data)
print("Comparisons:")
for pair in comparisons:
    print(pair)

print("\nPositions of '1's:")
print(a, b, c)

print("\nNumber of comparisons:", len(comparisons))

```

Edit 4: Okay, I believe I fixed the wrong excluding of the indexes, I now see how in both cases it must be i and i + 1. I still don't see how the logic in step 3 is wrong, but I did try to fix it in step 2. If we are in step 2 we still have an even number of elements, all of which hae previously been compared in pairs. Let's say we are here: (0,0)(1,1), where the parentheses mark the compared pairs from the first parse. The i-th element is the first zero of a pair (or the first 1 of a pair), so we compare it with the element that is 2 away from it, meaning the first element of the other pair. In this case we get remaining\_pairs(i)\<remaining\_pairs(i+2), so we add i+2 and i+3 as being 1s. If it was the other way around, then we add i and i+1. It is still slightly off though, what is wrong?

```
comparisons = []

def compare(i, j):
  comparisons.append((i, j))
  if data[i] == data[j]:
    return 0
  else:
    return 1 if data[i] > data[j] else -1

def find_ones(data):
  found_ones = []
  excluded_indices = set()  # Track indices already found

  # Step 1: Initial pairing and comparisons
  for i in range(0, len(data) - 2, 2):
    result = compare(i, i + 1)
    if result == 1:
     found_ones.append(i)
     excluded_indices.update({i, i + 1})  # Update excluded indices
    elif result == -1:
     found_ones.append(i + 1)
     excluded_indices.update({i, i + 1})  # Update excluded indices

    if len(found_ones) == 3:
        return comparisons, found_ones[0], found_ones[1], found_ones[2]

   # Check if we need to compare the final pair
  if len(found_ones) == 2 and (len(data) - 2) not in excluded_indices and (len(data) - 1) not in excluded_indices:
    result = compare(len(data) - 2, len(data) - 1)
    if result == 1:
     found_ones.append(len(data) - 2)
     excluded_indices.update({len(data) - 2, len(data) - 1})  # Update excluded indices
    elif result == -1:
     found_ones.append(len(data) - 1)
     excluded_indices.update({len(data) - 2, len(data) - 1})  # Update excluded indices

  if len(found_ones) == 3:
        return comparisons, found_ones[0], found_ones[1], found_ones[2]

  # Step 2: Find the pair with the remaining two '1's
  remaining_pairs = [i for i in range(0, len(data), 2) if i not in excluded_indices]
  for i in range(0, len(remaining_pairs) - 1, 2):
    result=compare(remaining_pairs[i], remaining_pairs[i + 2])
    if result == 1:
      found_ones.extend([remaining_pairs[i], remaining_pairs[i + 1]])
      break
    elif result == -1:
      found_ones.extend([remaining_pairs[i+2], remaining_pairs[i + 3]])
      break

  # Step 3: If necessary, deduce the last pair
  if len(found_ones) == 1:
    found_ones.extend(remaining_pairs[-2:])

  return comparisons, found_ones[0], found_ones[1], found_ones[2]

def get_input_data():
    position_1 = int(input("Enter position of first '1' (0-99): "))
    position_2 = int(input("Enter position of second '1' (0-99): "))
    position_3 = int(input("Enter position of third '1' (0-99): "))

    data = [0] * 100
    data[position_1] = data[position_2] = data[position_3] = 1
    return data

data = get_input_data()
comparisons, a, b, c = find_ones(data)
print("Comparisons:")
for pair in comparisons:
    print(pair)

print("\nPositions of '1's:")
print(a, b, c)

print("\nNumber of comparisons:", len(comparisons))

```

Edit 5: Do I have it?

comparisons = []

def compare(i, j):
  comparisons.append((i, j))
  if data[i] == data[j]:
    return 0
  else:
    return 1 if data[i] > data[j] else -1

def find_ones(data):
  found_ones = []
  excluded_indices = set()  # Track indices already found

  # Step 1: Initial pairing and comparisons
  for i in range(0, len(data) - 2, 2):
    result = compare(i, i + 1)
    if result == 1:
     found_ones.append(i)
     excluded_indices.update({i, i + 1})  # Update excluded indices
    elif result == -1:
     found_ones.append(i + 1)
     excluded_indices.update({i, i + 1})  # Update excluded indices

    if len(found_ones) == 3:
        return comparisons, found_ones[0], found_ones[1], found_ones[2]

   # Check if we need to compare the final pair
  if len(found_ones) == 2 and (len(data) - 2) not in excluded_indices and (len(data) - 1) not in excluded_indices:
    result = compare(len(data) - 2, len(data) - 1)
    if result == 1:
     found_ones.append(len(data) - 2)
     excluded_indices.update({len(data) - 2, len(data) - 1})  # Update excluded indices
    elif result == -1:
     found_ones.append(len(data) - 1)
     excluded_indices.update({len(data) - 2, len(data) - 1})  # Update excluded indices

  if len(found_ones) == 3:
        return comparisons, found_ones[0], found_ones[1], found_ones[2]

  # Step 2: Find the pair with the remaining two '1's
  remaining_pairs = [i for i in range(0, len(data)) if i not in excluded_indices]
  for i in range(0, len(remaining_pairs) - 2, 4):
    result=compare(remaining_pairs[i], remaining_pairs[i + 2])
    if result == 1:
      found_ones.extend([remaining_pairs[i], remaining_pairs[i + 1]])
      break
    elif result == -1:
      found_ones.extend([remaining_pairs[i+2], remaining_pairs[i + 3]])
      break

  # Step 3: If necessary, deduce the last pair
  if len(found_ones) == 1:
    found_ones.extend(remaining_pairs[-2:])

  return comparisons, found_ones[0], found_ones[1], found_ones[2]

def get_input_data():
    position_1 = int(input("Enter position of first '1' (0-99): "))
    position_2 = int(input("Enter position of second '1' (0-99): "))
    position_3 = int(input("Enter position of third '1' (0-99): "))

    data = [0] * 100
    data[position_1] = data[position_2] = data[position_3] = 1
    return data

data = get_input_data()
comparisons, a, b, c = find_ones(data)
print("Comparisons:")
for pair in comparisons:
    print(pair)

print("\nPositions of '1's:")
print(a, b, c)

print("\nNumber of comparisons:", len(comparisons))
```

# Answer
Start by splitting the 100 elements in 50 pairs of two, and use a comparison on each pair. If a comparison returns -1 or 1, then you've found one of the elements which is 1 (and the other one must be a 0).

Now there are two cases after these 50 comparisons: either we've found all three 1's, or we've found one 1, because the remaining two were part of the same pair. In the latter case we must find the pair which contains the last two 1's.

In this case there will be 49 pairs left (we can exclude the (0, 1) pair we identified earlier) one of which is the (1, 1) pair. We can find it by pairing the pairs, and doing one comparison each (for a total of 24 comparisons, leaving one pair out). This will identify which pair is the one with (1, 1), or if not, we know it must be the last pair.

This gives a total of 74 comparions. In fact, we could have saved one more comparison in the first step by stopping after 49 comparisons. If we have found two 1's in those first 49 comparisons we do one more to find the last 1 and we are done, and if we've found only one 1 it's useless to perform the comparison on the last pair, as it could only be (0, 0) or (1, 1), giving us no information.
> 13 votes

# Answer
Your current code has the following issues:

> `for i in range(0, len(data), 2):`

This is where you need to put the optimization to (conditionally) avoid comparing the final pair. You have two options for how to do that optimization:

* Subtract 2 from the endpoint of the range, and then check after the loop for whether comparing the final pair is necessary.
* Or check inside the loop whether the current pair is the final pair and whether comparing the final pair is necessary. If it's the final pair and comparing it is not needed, then skip the `compare` call.

Choose one or the other of those solutions, not both.

> `found_ones.append(i if data[i] == 1 else i + 1)`

Checking the value of `data[i]` in this line breaks the problem requirement of only checking data values in the `compare` function. You need to instead check whether the returned result from `compare` is 1 or -1 to determine which element in the pair is the 1. In doing this, you will also need to avoid making duplicate `compare` calls. One way to avoid the duplicate call is to use a `match` statement. Another is to save the result value to a variable so you can check that variable for the value multiple times without re-invoking the function call.

> `remaining_pairs = [i for i in range(0, len(data), 2) if i not in found_ones]`

This does not reliably filter out the pair that you found a 1 in. It filters the indexes of the first element in each pair, and fails to filter out the found pair if the found 1 is the second element in its pair.

> `if compare(remaining_pairs[i], remaining_pairs[i + 1]) != 0:`

This neglects to check which of the two pairs is a pair of 1s and which is a pair of 0s. Do this by checking whether the return value is 1 or -1, and again make sure to avoid duplicate `compare` calls as I noted earlier.

> `found_ones.extend([remaining_pairs[i], remaining_pairs[i + 1]])`

This adds the first element of each of the pairs. It should instead be adding **both** elements of **one** of the pairs. Make sure to use the result of the `compare` call to determine which pair to add.

> `found_ones.extend(remaining_pairs[-2:])`

Same problem as the previous one. This adds the first element of each of the last two pairs. It should instead be adding both elements of the last pair.

Edit responding to your comment and "Edit 2":

> I tried to implement some of your advice, and I do not see how I am wrong. I corrected the inappropriate use of something other than my compare function, but I can't get the logic right with the optimizations.

You fixed the inappropriate check of `data[i]` in your new post-loop check of the final pair, but it's still there in the first loop itself.

Now, going through your code responses to the issues in order:

1. Conditional `compare` of the final pair for the first loop: You solved this correctly.
2. Checking the return value of `compare` instead of directly checking `data[i]`: You only partially finished this. You got it right for the final pair, but you need to also apply the same fix inside the first loop.
3. Fixing the buggy filtering of `remaining_pairs`: You missed this completely, and it will sometimes cause incorrect results until you fix it. As an example to show the issue, consider the data set `[0, 0, 0, 1, 0, 0, ..., 1, 1]`. After the first loop, `found_ones` will be `[3]`. The filter you use to fill `remaining_pairs` will check if 2 is in `found_ones`, find it is not, and will include 2 in the resulting value of `remaining_pairs`. This is a bug because the 2 index is the other element of the pair that the 1 was found in and should therefore be excluded from `remaining_pairs`.
4. Checking the return value of `compare` to find which pair has the remaining two 1s: You missed this completely. Some inputs will get wrong results until this is fixed.
5. Fixing which index values to add after finding the last two 1s in the second loop: You missed this completely. Some inputs will get wrong results until this is fixed. For example, consider the data set `[0, 0, 1, 1, 0, 0, ..., 0, 1]`. The current code will report that it found 1s at positions 0 and 2 (and 99 but that's irrelevant to this issue), but the correct result is that those first two 1s are at positions 2 and 3.
6. Fixing which index values to add after finding that the last two 1s are the last pair: You missed this completely. Inputs where the last two data values are 1s will get wrong results until this is fixed.

Responding to "Edit 3":

1. `excluded_indices` is a good addition, but one of the `update` calls on it is wrong. The correct indices to exclude when you find a 1 in the first loop are always `{i, i + 1}`, because that is the pair that you compared regardless of which part of the pair is the 1.
2. This one technically isn't *wrong*, as in it won't cause your code to produce incorrect results, but checking `excluded_indices` in the condition for comparing the final pair is pointless. The indices of the final pair cannot possibly be in `excluded_indices` at that point in the code, because the final pair hasn't been checked yet.
3. You still haven't fixed issues 4, 5, and 6 from my previous edit. Those are for the sections of code that you labeled as step 2 and step 3.
> 2 votes

---
Tags: algorithms, dynamic-programming, python, comparison, dynamic-algorithms
---


# Question
Title: regular expression for $\{w\in \{a,b\}^*\mid |w|_a \mod 2 = 0\}\setminus \Sigma^*aab\Sigma^*$
The question asks to write down a regular expression $r$ indicating the language of all the words above $\Sigma = \\{a, b\\}$ , in which the number of $a$ is even and there is no sub-word $aab$ in them.

I am aware of the fact that there is an algorithm that converts a finite automaton into a regular expression.

I want to know if there is a systematic way of working that does not use this algorithm and will give an appropriate regular expression.

I have written $r = b^\*(aa)^\* + (b^\*ab^+ab)^\*(aa)^\*$

This is an incorrect answer.

I tried to fix it, but I feel like I'm just adding expressions and can't understand how to work on the problem thoroughly.

# Answer
> 4 votes
The only systematic ways to find regular expression I know of are using automata. As D.W. mentionned in his comment, I am not sure why you are rejecting this method.

A non-systematic approach for this language could be as follow.

The language of words without $aab$ as substring can be represented with the regular expression $(ab\mid b)^\*a^\*$.

To ensure that a word has an even number of $a$'s, we must consider two cases:

* either the longest suffix of $a$'s is of even length, so there must be an even number of substring $ab$. This corresponds to $(abb^\*ab\mid b)^\*(aa)^\*$
* or the longest suffix of $a$'s is of odd length, so there must be an odd number of substring $ab$. This corresponds to $(abb^\*ab\mid b)^\*abb^\*a(aa)^\*$.

Combining the two regular expressions, we get: $$(abb^\*ab\mid b)^\*(\varepsilon\mid abb^\*a)(aa)^\*$$

# Answer
> 1 votes
Hint: Here is an automaton for this language

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


# Question
Title: Proving why decreasing an edge weight in a graph may change it's MST by one edge
I'm working on understanding graphs and graph algorithms.

The problem is from: https://courses.engr.illinois.edu/cs374/fa2020/labs/sol/lab\_12\_b\_sol.pdf (Q 1.D)

> Describe an efficient algorithm to update the minimum spanning tree $T$ of a weighted undirected graph G when the weight of one edge $e \notin T$ is decreased.

I understand the solution and it makes sense to me intuitively that we add in that edge e to T, so $T'=T+e$ then that would make a cycle which we would just go through all the edges in the cycle and remove the one with the highest weight. This is clearly right because it's the only weight that was changed so the other choices we made about other vertices not in the cycle remain unchanged, adding e and removing the other max weight edge would then give a MST intuitively.

**What I don't understand is how would I prove this algorithm still results in an MST rigorously?**

I feel like since it seems obvious to me, I'm not seeing the rigorous way of explaining it. I only have the hand-wavy 'it's right because it's *obviously* right' explanation above which I realize is not an actual proof at all.

# Answer
> 2 votes
Let $T$ be the original spanning tree, and let $uv$ be the modified edge. Let $xy$ be a heaviest edge on the unique $u$-$v$-path in $T$.

Remove $xy$ from $T$ to obtain $T'$, two disconnected trees consisting of connected components $A$ and $B$. Clearly, $A$ and $B$ are minimum spanning trees of their respective sets of vertices. By the cut property, a minimum weight edge with one endpoint in $A$ and one endpoint in $B$ will be in an MST.

Hence, if $uv$ is now of a lower weight than $xy$ we add $uv$ otherwise we keep $T$ as it was.

# Answer
> -1 votes
Think of the vertices of $G$ to be partitioned into two sets : $V\_1$ and $V\_2$, where $V\_1$ consists of the vertices in the cycle and $V\_2$ are the remaining vertices. Now In the graph, $G\setminus V\_1$, the MST is what you had before, nothing has changed since $G\setminus V\_1$ has not changed. In $G\setminus V\_2$, you found the MST by the cycle argument.

Now MST of the two graphs combined, consists of the union of the MST of them and a single edge connecting these two MSTs. Convince yourself, that this hasn't changed and that should complete the proof.

---
Tags: algorithms, graphs, proof-techniques, graph-traversal, minimum-spanning-tree
---


# Question
Title: Is my understanding of Eta reduction correct?
In my script I have the following term:

> x =\> y =\> both (x) (y)
>
> This is reduced to
> both

My interpretation is that this function (the whole term) takes two arguments and returns a function and two variables, but these aren't used by the function thus we can remove them? Is this interpretation correct?

# Answer
> 3 votes
> returns a function and two variables

No, it returns the result of applying the function to these two arguments. This result of course uses the arguments.

Instead, consider this. I don't know what function `both` is, but let's say it works on numbers. if you calculate e.g. `(x => y => both x y) 1 2`, it will be:

```
(x => y => both x y) 1 2 ==
(y => both 1 y) 2 ==
both 1 2

```

And if you replace `1` and `2` by anything else, you'll still get the same result if you apply both `x => y => both x y` and `both` to the same arguments.

So `x => y => both x y` and `both` are two different expressions which represent the same function and you can simplify the first to the second.

---
Tags: lambda-calculus
---


title: Find a negative cycle linearly?

text:
# Question
Title: Find a negative cycle linearly?
In a directed graph, if you find scc (strongly connected components), then for each negative edge, if its 2 vertices are in the same scc and that scc has size \> 1, then there is a negative cycle with that edge, and is easy to find it with a simple dfs. Is this approach correct?

# Answer
No it's not true. Consider a graph with two nodes, A and B, with an edge A-\>B with length 1 and an edge B-\>A with length -1.

The edge B-\>A is a negative edge and its vertices are in the same SCC and that SCC has size \> 1. That edge is not part of a negative cycle.
> 1 votes

---
Tags: graphs
---


title: Can the Y-combinator really terminate?

text:
# Question
Title: Can the Y-combinator really terminate?
My understanding of the Y-combinator is that it never terminates (`Yg = g(Yg)`). Its termination is only decided **externally** to the $\lambda$ specification when it has reached a fixed point (`g(x)=x`) because based on its $\lambda$ expression there is no exit from the infinite loop even when the fixed point is reached.

Am I wrong?

# Answer
Terms containing the Y combinator can be *weakly normalizing*: they can terminate for a certain order of evaluation, i.e. for a certain evaluation strategy. No term containing the Y combinator applied to another term can be *strongly normalizing*, i.e. no term containing Y applied to another term terminates for all evaluation strategies, since the infinite reduction chain $Y \\, M \to\_\beta^\* M \\, (Y \\, M) \to\_\beta^\* M \\, (M \\, (Y \\, M)) \to\_\beta^\* \ldots$ is possible.

There are terms $M$ such that $Y \\, M$ has no normal form, i.e. such that there is no reduction strategy that reduces $Y \\, M$ to a value. For example $Y (\lambda x. x) \to\_\beta^\* (\lambda x.x) (Y (\lambda x.x)) \to\_\beta Y (\lambda x. x)$ is a recursive functions that just spins (`let x = x`). (The lack of another reduction chain that terminates is left as an exercise for the reader.)

Under call-by-value (only ever reducing $M \\, N$ when $M$ and $N$ are values), $Y \\, M$ only converges if $M$ does not use its argument, i.e. if $Y \\, M$ is not “really” recursive. Under call-by-name (always reducing the outermost redex first), $Y \\, M$ converges if the recursive function that it defines terminates.
> 6 votes

# Answer
Actually, I was curious about all the $Y$-combinator-related questions, so I decided to put up my old (optimal) combinator evaluator Combo.

I'll use this as a reference implementation for the question on hand and make brief mention of the alternatives.

Here's where I get. The relevant expression is $Y = W S (C B D)$, where: $$ W = λxλy(x y y),\quad S = λxλyλz(x z (y z)),\\ C = λxλyλz(x z y),\quad B = λxλyλz(x (y z)), $$ as usual, which "Combo" accepts as primitive combinators, and also $$D = λx(x x),$$ which "Combo" also treats as a primitive combinator.

If you define $Y$ and run it, by feeding "Combo" the expression $$Y = W\ S\ (C\ B\ D), Y$$ it will terminate with $S (C B D) (C B D)$, which it writes as $\\\_0 = C B D, S \\\_0 \\\_0$ (because "Combo" never writes the same subexpression twice, in any expression, except for names).

If you run it with the η-rule (using the "-e" command-line option), it will complain that the reduction is non-terminating. Its implementation of the η-rule is equivalent to running $Y$ on a dummy argument, say $f$, with the η-rule on $Y f$, if necessary, and then abstracting out the $f$ after it finishes ... except it will never finish, because $Y f$ evaluates to $f (Y f)$. So, it blocks the reduction.

In and of itself, $Y f$ does not terminate.

On the other hand, if $f$ is defined as some other combinator expression, then it may terminate. For instance, if you run "Combo" on $$Y = W\ S\ (C\ B\ D),\ Y\ (K\ x),$$ where $K = λxλy x$ then it will produce $x$ as a result. Not all combinator reduction strategies will terminate on $Y$ combinator expressions - not even on this. Some may try to expand $Y (K x)$ into $K x (Y (K x))$ and then keep expanding the $Y (K x)$ sub-terms, without bothering to chop it off with the $K$. Since "Combo" is optimal, it will chop off the subterm.

As an aside, "Combo" accepts (and pre-compiles) lambda expressions. So, you can also define $Y = λf((λx f (x x))(λx f (x x)))$, and run $Y$, by giving "Combo" the expression $$Y = \setminus f(g = \setminus x\ f\ (x\ x),\ g\ g), Y.$$ It will yield the same result as $W S (C B D)$ \- as listed above.

You can see the progress of evaluation with the "-s" command-line option; but note that it only shows the evaluation of the subexpression it is working on, at each step, not of the whole expression, and an expression like $C C C C C C ...$ will reduce in one step to $C C C$, independent of the number of $C$'s beyond the first three (because it never evaluates any sub-expression more than once).
> 0 votes

---
Tags: lambda-calculus
---


# Question
Title: Why $2n−1$ comparisons are sometimes necessary to correctly merge two sorted sequences
How we can prove that $2n−1$ comparisons are sometimes necessary to correctly merge two sorted sequences of $n$ elements each into one sorted sequence? I tried to prove it with binary decision tree, but it was not working.

# Answer
> 1 votes
Let the sequences be $A\_{1..n}$ and $B\_{1..n}$, merging takes $2n - 1$ comparisons if $A\_1 \< B\_1 \< A\_2 \< B\_2 \< A\_3 \< B\_3 \< \cdots \< A\_n \< B\_n$.

It compares $A\_1$ with $B\_1$, $A\_2$ with $B\_1$, $A\_2$ with $B\_2$, $A\_3$ with $B\_2$, $A\_3$ with $B\_3$, to $A\_n$ with $B\_n$.

It is identical to $A\_1$ with $B\_1$, $B\_1$ with $A\_2$, $A\_2$ with $B\_2$, $B\_2$ with $A\_3$, $A\_3$ with $B\_3$, to $A\_n$ with $B\_n$.

It requires each $A\_i$ and $B\_j$ comparison above be made to distinguish $A\_i \< B\_j$ and $A\_i \> B\_j$.

It resembles the original condition, so there are $2n$ elements linked by $2n - 1$ inequalities.

---
Tags: data-structures
---


# Question
Title: Size of the certificate as a property of the problem
Suppose I have a decision problem $\mathcal{L}\subseteq\Sigma^\*$ and a verifier $V$ that recognizes $\mathcal{L}$, i.e. $L(V)=\mathcal{L}$. Let's arbitrarily choose some certificate $c(w)$ for $w \in \mathcal{L}$ such that $V$ accepts $(w,c)$. Let's consider the functions that bound the size of the certificate $|c(w)|$ based on the size of the input $|w|$. If $\mathcal{L} \in \mathsf{NP}$ then for some appropriate $V$ the function that bounds the size must be polynomial (supposing that we only include to the verifier only the information/bits that the verifier will use). Also if for some verifier the function that bounds the length is logarithmic and the verifier runs in polynomial time then $\mathcal{L}\in\mathsf{P}$. This got me thinking that maybe looking at the shortest witnesses of a specific problem could help us figure out its complexity.

For example if the shortest certificate of a problem (i.e. the smallest class of function that bounds the certificate of a verifier for that problem) is strictly bigger than polynomial then that problem cannot be in $\mathsf{P}$. Obviously I don't really care about analyzing the bounding functions, I would guess that this is close to impossible in almost every case. But still these sort of arguments seem interesting to me.

Is this whole direction useful at all? Is there some well known theory that analyzes this perspective? I was about to start playing around with these ideas but I figured I should ask here first so I can save myself some time.

# Answer
I would say you have made a good case that it is at least a little bit interesting, because imposing different bounds on the length of the witness, combined with different bounds on the running time of the verifier, yields different complexity classes.

A few nitpicky remarks:

1. The length of witnesses depends on both the problem and the specific verifier chosen. So it doesn't make sense to talk about "the shortest witnesses for a problem", as the shortest witness also depends on which verifier you have chosen.
2. There is no shortest witness. You can always make the witness one bit shorter if you are willing to double the computation time of the verifier (it can try both possibilities for the missing bit).
> 4 votes

---
Tags: complexity-theory
---


# Question
Title: Locating a sequence of 2D points in a set of polygons with holes
Using the CGAL library, I am working on a 2D layout graph which contains an array of 2D polygons with holes. The aim is to generate random points (based on some conditions) and only keep the points inside the area of 2D polygons but not in their holes. The function I use for this is `CGAL::bounded_side_2`. Please see the CGAL documentation here.

Performing this for each point is very costly as I have more than 50,000 points. Is there a way to perform this operation in a parallel manner or speed up using some data structure?

# Answer
If I understand what you're trying to achieve, this problem is solved by using a point-in-polygon test for each of the 50,000 points. This should be efficient, even if performed on only a single machine. To deal with polygon-shaped holes, check if the point is contained in the containing polygon and not in the hole; each can be checked with a separate point-in-polygon test.

How to do it with the CGAL library is an implementation matter that is best addressed in a CGAL support forum or on Stack Exchange.
> 0 votes

# Answer
This question should be asked on the SO... But anyway:

1. Create a CGAL 2D Arrangement from your set of polygons with holes.
2. Mark faces of this arrangement, which you consider unwanted, by the `false` boolean value.
3. Call the function `CGAL::locate` on this arrangement and your array of random points, and keep the points, which got into faces with the mark `true`.

There are other functions in this CGAL package as well, so you can choose an algorithm, which works best for you.
> 0 votes

---
Tags: graphs, computational-geometry, polygons
---


# Question
Title: Can you identify this assignment problem and efficient solutions or estimates?
## Problem Statement

My wife's business runs a summer camp for 68 students. The students are divided into cabins:

* 27 students in 3 groups of 7 and one group of 6 belong in one set of 4 cabins;
* 41 students in 5 groups of 7 and one group of 6 belong in the other set of 6 cabins. Which set of cabins a student belongs in is fixed, but not which cabin.

The students are also divided into discussion groups. There is a maximum of 10 discussion groups with 6 or 7 students per group. (It is possible there will not be all 68 students in attendance.) No discussion group assignments are fixed, and discussion groups can (and should) be different from cabin assignments.

The business also has a dossier of variables about each student. Let's call these variables $A$, $B$, $C$, etc. There are at least 4 major variables in addition to cabin assignment ($cabin$).

The goal of the problem is to find assignments of students.

* For cabins, each cabin should have a roughly equal distribution among the values of major variables (excepting $cabin$, which is fixed).
* For discussion groups, each group should have a roughly equal distribution among the values of major variables and $cabin$.

As an example, if each cabin in the first set has roughly equal proportions of the values of each of the variables $A$, $B$, and $C$, then this is satisfactory.

Of course, the variables form a hierarchy: it is more important to balance $A$ then $B$ or $C$, $B$ dominates $C$, etc.

An example with 4 students and 2 variables (among one set of cabins and):

| student | $A$ | $B$ |
| --- | --- | --- |
| Alice | 1 | 2 |
| Bob | 1 | 1 |
| Charlie | 2 | 2 |
| David | 2 | 1 |

Then pairing Alice with David and Bob with Charlie, each cabin would have 50% $A=1$ and 50% $A=2$ (idem. for $B$). Discussion groups would need to consider the $cabin$ variable, and realistically the distribution is unlikely to be a perfect split.

## Questions

1. Is this a known type of assignment problem? A review of problems linked on https://en.wikipedia.org/wiki/Assignment\_problem and https://en.wikipedia.org/wiki/Combinatorial\_optimization didn't produce any insights for me. (Is it a known type of *other* problem?)
2. Are there known efficient exact solutions or heuristics (which provide a "good" assignment but not necessarily the "best")? The business isn't interested in something exact anyway, so I'm more than happy to accept efficient-enough heuristics that provide a reasonable starting point (one which humans could still iterate on if desired). I would also accept a negative result that proves even reasonable heuristics are impossible in reasonable time. Solutions with implementations or architectures are preferred, but I can implement a formalized algorithm.

## Attempts at a Naïve Method

When I tried to work out the size of the problem for a naïve "generate all assignments, score them by the business's evaluation rules, and take the best" I calculated something like this:

* for the first set of cabins, we can first choose 7 of the 27, then 7 of the remaining 21, etc.;
* for the second set, we can first choose 7 of the 41, then 7 of the remaining 34, etc.

This yields (for discussion groups) $$ {68 \choose 7} {61 \choose 7} {54 \choose 7} {47 \choose 7} {40 \choose 7} {33 \choose 7} {26 \choose 7} {19 \choose 7} {12 \choose 6} {6 \choose 6} \approx 1.1490756 \times 10^{61} $$ which seems astronomically infeasible (and also factorial in terms of growth).

For cabins, it's mildly better (and the business admits that, when doing this by hand, it's significantly easier to do cabins first): $$ {27 \choose 7} {20 \choose 7} {13 \choose 7} {6 \choose 6} {41 \choose 7} {34 \choose 7} {27 \choose 7} {20 \choose 7} {13 \choose 6} {6 \choose 6} \approx 1.6877279 10^{42} $$ This still seems too large to be computationally feasible without a more principle algorithm.

P.S. Have I calculated the problem size correctly?

# Answer
> 1 votes
A standard approach that is very general is to formulate this as an instance of integer linear programming, and apply an off-the-shelf ILP solver. The field of operations research deals with a lot of combinatorial optimization problems, such as arise in scheduling and logistics, and ILP solvers are one standard tool for this (there are other tools as well).

Solving ILP is NP-hard in the worst case, so it's not always feasible to solve for large problems, but for the kind of problem you mention, I expect it will be very flexible and will be sufficient for your needs.

In some special cases, where the constraints/requirements have a particular structure, we can solve this with specialized algorithms, such as maximum bipartite matching, algorithms for the assignment problem, network flow, etc. Those algorithms have the benefit of scaling very well to large problem sizes. But they are not flexible: they can only accommodate very specific types of constraints and restrictions. So if they don't apply, you can fall back to the "big hammer" of ILP solvers, SAT solvers, and/or off-the-shelf optimization algorithms.

---
Tags: approximation, assignment-problem
---


# Question
Title: why didn't ASCII/utf-8 used 00000000 to represent char 0 or rather any other character
I mean why value of 0 value in binary is not used by ascii encoding , it would have been used to represent char 0 or anything else why they used it to represent NULL

# Answer
In the modern digital era, character code 0 could have been any useful thing, such as "0" or "A". The use of character code 0 as "null," has a long history, as far back as Murray codes back in 1901. This had a particular advantage on punched tape, where a fresh tape with no punches in it read as all 0's. Distinguishing between "0" and no character proved very valuable. Instead, ASCII prepended all of the binary coded decimal characters for 0-9 with 011 and reserved the first 32 symbols for control characters like null.
> 2 votes

# Answer
NULL is the name of the character. SOH is the name of the ASCII character with code 1. It’s just a name.
> 0 votes

---
Tags: binary
---


title: The Atlas system word addresses

text:
# Question
Title: The Atlas system word addresses
I'm reading about the Atlas operating system and I came across this:

> The Atlas system used a British computer with 48-bit words. Addresses were 24 bits but were encoded in decimal, which allowed 1 million words to be addressed.

Why is it 1 million here if it's encoded in decimal?

# Answer
It looks like by "encoded in decimal" what they mean is binary coded decimal (BCD), which is a format which uses 4 bits to encode the numbers 0-9. Obviously this wastes a little, as those 4 bits could also encode 10-15, but that is sacrificed to make a 1:1 mapping between groups of bits and digits of a number in base 10

24-bits divided by 4 bits per base 10 digit yields 6 base 10 digits. 6 digits is enough to count from 0 to 999,999, hence a million adddresses.
> 1 votes

---
Tags: computer-architecture, memory-hardware
---


# Question
Title: Unique Tree using Inorder & Postorder traversals
This question appeared in my data structures examination :

You are given that GDCBFAHEJ is an in-order traversal and GCDBHJAEF is a post-order traversal. Either build the unique tree for which these are traversals or argue that they are traversals of different trees.

Why are we unable to build a unique tree, despite of having a in-order & post-order traversal? Please explain.

# Answer
> 0 votes
Given the in-order and the post-order, there is indeed a unique corresponding binary tree.

Since $F$ is the last node in the post-order, it is the root of the tree.

In the in-order, the root of the tree separates the in-order of the left tree (hence GDCB) and the in-order of the right tree (AHEJ).

That means that the left tree is of size 4. In the post-order, the first 4 nodes must represent the post-order of the left tree (GCDB). Similarly, the post-order of the right tree is HJAE.

Using the same method recursively, we get that the left tree is:

```
    B
   /
  D
 / \
G   C

```

But the problem is that when using the method on a tree with AHEJ as in-order and HJAE as post-order, we get that the root must be E, but then it decompose the in-order as AH (in-order of left tree), E (root) and J (in-order of right-tree). Can you see how it is a contradiction with the post-order?

---
Tags: data-structures, trees
---


# Question
Title: how to polynomially check if a given boolean formula is unsatisfiable
Since SAT is np-complete, there is a polynomial algorithm to check if a given solution for any particular formula is correct. Just substitute the values and solve. But what if one claims that the given formula is unsatisfiable, is there a polynomial way to check if the claim is true... Am i missing something ?

# Answer
NP only requires you to have a polynomial size proof for "yes" instances.

co-NP is the class of problems that requires polynomial size proofs for "no" instances.

SAT is in NP, but is not known to be in co-NP. Whether NP = co-NP is an open problem (and proving that SAT is in co-NP would resolve this problem in the affirmative).

So to answer the question in your title, how to polynomially check if a given boolean formula is unsatisfiable: no one knows whether that could be done in general.
> 1 votes

# Answer
We don't know for sure, but most people expect the answer is "no". In particular, assuming NP != co-NP (as is a commonly held conjecture), the answer is "no".

Checking that a formula is satisfiable (and exhibiting a proof that it is) is a NP-complete problem. Checking that a formula is unsatisfiable (and exhibiting a proof that it is not satisfiable) is a co-NP-complete problem.
> 1 votes

---
Tags: satisfiability, p-vs-np
---


# Question
Title: Does the Linz Ĥ applied to ⟨Ĥ⟩ correctly transition to its final reject state?
```
// Linz Turing machine H --- H applied to ⟨H⟩
H.q0 ⟨H⟩ ⟨H⟩ ⊢* H.qy   // H applied to ⟨H⟩ halts
H.q0 ⟨H⟩ ⟨H⟩ ⊢* H.qn   // H applied to ⟨H⟩ does not halt
Do you halt on your own Turing Machine description ?

```

Of the infinite set of implementations of H every one that transitions to H.qy derives an answer consistent with the behavior of H.

**When we append an infinite loop to the H.qy state we derive Ȟ**

```
Ȟ.q0 ⟨Ȟ⟩ ⟨Ȟ⟩ ⊢* Ȟ.qy ∞ // Ȟ applied to ⟨Ȟ⟩ halts
Ȟ.q0 ⟨Ȟ⟩ ⟨Ȟ⟩ ⊢* Ȟ.qn   // Ȟ applied to ⟨Ȟ⟩ does not halt
Do you halt on your own Turing Machine description ?

```

Of the infinite set of implementations of Ȟ none of them derives an answer consistent with the behavior of Ȟ.

This is because the question:
**Do you halt on your own Turing Machine description ?**
is self-contradictory thus incorrect question for Ȟ.

Yes/no questions intentionally defined to have no correct yes/no answer are incorrect questions. The inability to correctly answer an incorrect question places no actual limit on anyone or anything.

**Two PhD computer science professors agree with this view:**

E C R Hehner. **Objective and Subjective Specifications** WST Workshop on Termination, Oxford. 2018 July 18. See https://www.cs.toronto.edu/~hehner/OSS.pdf

Bill Stoddart. **The Halting Paradox** 20 December 2017 https://arxiv.org/abs/1906.05340 arXiv:1906.05340 \[cs.LO\]

# Prior question

**Applying a Simulating Halt Decider to the Linz Halting Problem Proof**

A simulating (at least partial) halt decider correctly predicts whether or not its correctly simulated input can possibly reach its own final state and halt. It does this by correctly recognizing several non-halting behavior patterns in a finite number of steps of correct simulation. Inputs that do terminate are simply simulated until they complete.

The Linz text indicates that Ĥ is defined on the basis of prepending and appending states to the original Linz H, (assumed halt decider) thus is named embedded\_H.

(q0) is prepended to H to copy the ⟨Ĥ⟩ input of Ĥ. The transition from (qa) to (qb) is the conventional infinite loop appended to the (qy) accept state of embedded\_H. ⊢\* indicates an arbitrary number of moves.

The Linz term “move” means a state transition and its corresponding tape head action {move\_left, move\_right, read, write}. Ĥ is applied to its own machine description ⟨Ĥ⟩.

Ĥ.q0 ⟨Ĥ⟩ ⊢\* embedded\_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢\* Ĥ.qy ∞
Ĥ.q0 ⟨Ĥ⟩ ⊢\* embedded\_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢\* Ĥ.qn

When Ĥ is applied to ⟨Ĥ⟩
(q0) The input ⟨Ĥ⟩ is copied then transitions to (qx)
(qx) embedded\_H is applied to ⟨Ĥ⟩ ⟨Ĥ⟩ (input and copy)
which simulates ⟨Ĥ⟩ applied to ⟨Ĥ⟩ which begins at its own (q0) to repeat the process.

This process continues to repeat until embedded\_H recognizes the repeating pattern and aborts its simulation of ⟨Ĥ⟩ ⟨Ĥ⟩. embedded\_H can see the same repeating pattern that we see.

**computation that halts…** “the Turing machine will halt whenever it enters a final state” (Linz:1990:234)

# Every "rebuttal" simply ignores this key fact

**⟨Ĥ⟩ ⟨Ĥ⟩ correctly simulated by embedded\_H cannot possibly reach its own simulated final state of ⟨Ĥ.qn⟩ and halt in any finite number of steps of correct simulation.**

**Linz, Peter 1990.** An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company. (317-320)

# Answer
> 0 votes
**Refutation of the Peter Linz Halting Problem proof**

The following shows how Linz H ⟨Ĥ⟩ ⟨Ĥ⟩ gets the right answer because Linz Ĥ.H ⟨Ĥ⟩ ⟨Ĥ⟩ gets the wrong answer

H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢\* H.qy // Ĥ applied to ⟨Ĥ⟩ halts
H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢\* H.qn // Ĥ applied to ⟨Ĥ⟩ does not halt

**Criterion Measure**
H is assumed to be a simulating termination analyzer that aborts the simulation of any input that would cause its own non-termination and returns NO. Otherwise H always returns YES.

Ĥ.q0 ⟨Ĥ⟩ ⊢\* Ĥ.Hq0 ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢\* Ĥ.Hqy ∞ // Ĥ applied to ⟨Ĥ⟩ halts
Ĥ.q0 ⟨Ĥ⟩ ⊢\* Ĥ.Hq0 ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢\* Ĥ.Hqn // Ĥ applied to ⟨Ĥ⟩ does not halt

Execution trace of Ĥ applied to ⟨Ĥ⟩
(a) Ĥ.q0 The input ⟨Ĥ⟩ is copied then transitions to Ĥ.H
(b) Ĥ.H applied ⟨Ĥ⟩ ⟨Ĥ⟩ (input and copy) simulates ⟨Ĥ⟩ applied to ⟨Ĥ⟩
(c) which begins at its own simulated ⟨Ĥ.q0⟩ to repeat the process
**Same execution trace even when infinite loop is removed**

It is true that Ĥ.H ⟨Ĥ⟩ ⟨Ĥ⟩ must transition to Ĥ.Hqn to prevent its own infinite execution. It is true that this makes Ĥ ⟨Ĥ⟩ halt. This entails that H ⟨Ĥ⟩ ⟨Ĥ⟩ would be correct to transition to H.qy.

When Ĥ.H ⟨Ĥ⟩ ⟨Ĥ⟩ and H ⟨Ĥ⟩ ⟨Ĥ⟩ correctly apply the above criteria then Ĥ.H ⟨Ĥ⟩ ⟨Ĥ⟩ would transition to Ĥ.Hqn and H ⟨Ĥ⟩ ⟨Ĥ⟩ would transition to H.qy

**No one has refuted any of the above reasoning**

# Answer
> 8 votes
This is an answer to an attempt at understanding a previous version of the question, and is no longer relevant to the latest question.

---

Your question is: What happens when you use a simulating halt decider and (...)?

The answer is: You can't. The question has a faulty premise. A simulating halt decider does not exist, so there is no meaningful answer to the question.

---

I'll highlight your definition. You propose the following definition:

> A simulating (at least partial) halt decider H is a UTM that has been adapted to decide whether or not its input halts. It does this by simulating its input and examining the behavior of this simulated input.

(I presume this should be interpreted as saying that, to count as a simulating halt decider, the UTM must always correctly decide whether or not its input halts, for all possible inputs.)

The problem is: there does not exist any UTM that successfully acts as a simulating halt decider on all inputs.

You can add all the conditions and requirements you want to a definition. The definition remains valid. But there is no guarantee that there exists any object that meets the conditions of the definition. That has to be separately verified.

It sounds like you think that there does exist such a UTM that would qualify as a simulating halt decider. However, your intuition is faulty. I know it's easy to identify some patterns that, if they arise during execution, allow us to determine whether the input will halt. However, those patterns will never be comprehensive. No matter how many patterns you write down, there will always be some inputs that aren't handled by any of those patterns.

Those of us who have studied complexity theory already know this, because there is a theorem that proves it. High-level statements such as "Certain patterns of behavior such as infinite loops and infinite recursion can be recognized." is not likely to be effective at persuading anyone to the contrary, because we know there are also other kinds of behavior that won't be recognized; yet such language is too vague and imprecise to allow us to give you specific examples to help you see that fact concretely.

---

If you'd like to pump your intuition, you can find some examples of programs where no one knows whether they halt or not: What are the simplest examples of programs that we do not know whether they terminate?, What are very short programs with unknown halting status?. If you study them, perhaps it will give you a better sense why these programs might fail to halt (they might run forever) without ever entering any loop, or even matching "pattern" that you can write down. (More specifically, for any pattern or list of patterns you have in mind, there might be some input that fails to halt but doesn't match any of those patterns.)

---

If you want an analogy, I find your assertions to come off (to me) as similar to the following made-up conversation:

Polly: Let's define an "awesome circle" to be a circle whose radius $r$ and circumference $C$ satisfy the relationship $C=8r+1$. What would happen if we replaced the 4 tires on my car with objects that have an "awesome circle" shape?

Conan: You can't. No such object exists. The question is meaningless.

Polly: Sure, but assume $H$ is an awesome circle, and I put it on my car. What happens?

Conan: You can't. $H$ doesn't exist. The assumption is false.

Polly: But my $H$ is defined to be awesome. An awesome circle is one that has been adapted so that $C=8r+1$.

Conan: You can't. You can't adapt a circle that way.

Polly: I have superior knowledge of round shapes. Anyone with my experience with round shapes would see immediately how to adapt a circle in that way.

I hope you can see how this exchange is a bit absurd and Conan would tire of it quickly and not have any interest in continuing the conversation. Of course, if Conan knows some mathematics, then he immediately knows that all circles satisfy the relationship $C=2\pi r$; since there is no solution to the system of equations $C=2 \pi r$, $C=8r+1$ with $r \ge 0$, any mathematician would immediately know that no "awesome circle" can exist, so there is not much point in continuing such a conversation.

This is how your attempts to address this topic come off to me. Your assertions remind me of Polly's assertions (Polly's awesome circle = your simulating halt decider; Conan = any computer scientist who has studied decidability). Hopefully this helps you better understand the reactions you are getting and use it to help you focus your future studies.

# Answer
> 4 votes
In response to an earlier version:

You have misunderstood their proof, which is not very well presented (imho); but you also seem to have cut off the end, where they establish the contradiction.

They do not state anywhere that $M$ is simulated, at all.

$\hat H$ simulates $H'$ and $H'$ simulates $H$. Now, $H$ is *assumed* -- towards a contradiction -- to be *decider*. which means it always terminates after finitely many steps. No assumption is made on how it solves the halting problem -- which is the point, of course, because only so can be disprove *all* candidates for $H$ by leading the assumption to a contradiction!

So we simulate $H$ which always terminates -- no infinitely nested simulation is happening.

Your intuition is not wrong, though, even though you seem to be missing the corner cases: you'd *need* something like "infinitely nested simulation" to solve the halting problem -- something that doesn't work. Because it's impossible.

---

> When we hypothesize that the halt decider embedded in Ĥ is simply a Universal Turing Machine (UTM) does this define a computation that never halts when Ĥ is applied to its own Turing machine description?

There are infinitely many UTMs. Without further assumptions, we just don't know what any arbitrary one of those does on its own encoding.

# Answer
> -1 votes
When a simulating halt decider correctly simulates N steps of its input it derives the exact same N steps that a pure UTM would derive because it is itself a UTM with extra features.

Because of this we can know that the first N steps of ⟨Ĥ⟩ simulated by embedded\_H are the actual behavior that ⟨Ĥ⟩ presents to embedded\_H for these same N steps.

**computation that halts…** “the Turing machine will halt whenever it enters a final state” (Linz:1990:234)

**Ĥ.q0 ⟨Ĥ⟩ ⊢\* embedded\_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢\* Ĥ.qy ∞**
**Ĥ.q0 ⟨Ĥ⟩ ⊢\* embedded\_H ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢\* Ĥ.qn**

**When Ĥ is applied to ⟨Ĥ⟩**
(Ĥ.q0) The input ⟨Ĥ⟩ is copied then transitions to embedded\_H
embedded\_H is applied to ⟨Ĥ⟩ ⟨Ĥ⟩ (input and copy)
which simulates ⟨Ĥ⟩ applied to ⟨Ĥ⟩
**which begins at its own simulated ⟨Ĥ.q0⟩ to repeat the process.**

When we see (after the above N steps) that ⟨Ĥ⟩ correctly simulated by embedded\_H cannot possibly reach its simulated final state of ⟨Ĥ.qn⟩ in any finite number of steps of correct simulation then we have conclusive proof that ⟨Ĥ⟩ presents non-halting behavior to embedded\_H.

Therefore when embedded\_H aborts the simulation of its input and transitions to its own final state of Ĥ.qn it is merely reporting this verified fact.

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


title: Constrained Maximum Flow Minimum Cost

text:
# Question
Title: Constrained Maximum Flow Minimum Cost
Let $G=(V, E)$ be a directed network with a set $V$ of vertices and a set $E$ of edges. Two vertices are distinguished, $s,t$ which are the source and sink respectively. Each edge $(i, j)$ has an associated cost $c\_{ij} \in \mathbb{Z}$ and a capacity $u\_{ij} \in \mathbb{N}$. The objective is to achieve a flow of value $K$ from $s$ to $t$ and minimize the cost. The flow through each edge must be integral, is conserved at each vertex (except at $s$ and $t$) and doesn't exceed edge capacities. In addition, the total cost of the flow must also satisfy $\Sigma\_{(i, j) \in E} c\_{ij}x\_{ij} \ge D$ where $x\_{ij}$ is the flow through edge $(i, j)$ and $D \in \mathbb{Z}$.

Is this problem solvable in polynomial time or even in pseudo-polynomial time? If not, is there a constant factor approximation for the cost for general networks with a flow of value $K$?

I was able to find a paper describing a similar problem but with an upper-bound for the cost: A Capacity Scaling Algorithm for the Constrained Maximum Flow Problem, Ravindra K. Ahuja, James B. Orlin, Networks, 25(2), 1995.

# Answer
The problem appears to be NP-hard, by a reduction from subset sum.

In particular, suppose we are given integers $a\_1,\dots,a\_n$ and target $D$. Create a graph with two vertices, $s,t$. Add edges $s \to t$, where the $i$th edge has capacity 1, cost $a\_i$, then add another edge $s \to t$ with capacity $n$ and cost $0$. Set $K=n$. Finally, find the minimum possible cost of all flows whose cost is $\ge D$ and value is $K$. If the minimum possible cost is $D$, then you know there is a subset of $a\_1,\dots,a\_n$ that sums to $D$; otherwise no such subset exists.

There could still be a pseudo-polynomial time algorithm, FPTAS, or constant-factor approximation.
> 1 votes

---
Tags: complexity-theory, np-hard, network-flow
---


title: Reduction from $ALL$ to $DECIDE$

text:
# Question
Title: Reduction from $ALL$ to $DECIDE$
Let $DECIDE=${$\<M\> :\ M\ halts\ on \ all \ inputs$} and I wish to show its unrecognizable using a reduction from $ALL=${$\<M\> :L(M)=\Sigma ^\* $}

using a deterministic turing machine $R$ which runs in polynomial time: $\<M\>\in ALL \rightarrow \_R R(\<M\>)=M'\in DECIDE$

```
R(<M>):
   M'(x):
      run M on x, if M accepts, halt on x
      if M rejects x, loop

```

where my proof would be something of:

if $\<M\>\in ALL$ than $M$ accepts all inputs, therefor $M'$ would halt on all inputs, so $\<M'\>\in DECIDE$

if $\<M\>\notin ALL$ than there exists $x\in \Sigma^\*$ that $M$ either rejects on loops on, if $M$ rejects $x$, $M'$ will enter a loop, if $M$ loops over $x$, we'll never get to the "if M accepts x" part at all, so $x$ wont be halted on, either way, $\<M'\>\notin DECIDE$

however something here seems off to me, I have this feeling that I cant tell $M'$ to just 'loop' whenever I want to.

thanks in advance

# Answer
> 0 votes
As codeing\_monkey noted, there's nothing wrong with telling it to loop. It's also possible to give a more explicit definition of $R$ (without using the universal TM) if you're not convinced.

Define for a TM $M = (Q, \Sigma, \Gamma, \delta, q\_0, q\_a, q\_r)$

$$R(\langle M \rangle) = \langle M' \rangle$$

where $M' = (Q \cup \\{q\_{loop}\\}, \Sigma, \Gamma, \sigma, q\_0, q\_a, q\_r)$ with $q\_{loop} \notin Q$ and $$\sigma(q, a) = \begin{cases} (q\_{loop}, \\\_, \texttt{R}) & \text{if } q = q\_{loop}, \\ (q\_{loop}, \\\_, \texttt{R}) & \text{if } \delta(q, a) = q\_r, \\ \delta(q, a) & \text{else} \end{cases}$$

for all $q \in Q \cup \\{q\_{loop}\\}$, $a \in \Gamma$. Then it's easy to see that

$$M \text{ accepts } x \iff M' \text{ accepts } x$$

and

$$M \text{ rejects } x \iff M' \text{ loops in } q\_{loop}.$$

---
Tags: reductions, decidability
---


# Question
Title: What is the proper way to calculate dimensions of count min sketch
I read almost everything I can find for count min sketch. Also look at most of the videos in Youtube, but did not found answer of a simple question -

What is the proper way to calculate dimensions of count min sketch

In both ChatGPT and Bing AI, if you ask how big a count min sketch needs to be in order to be able to "hold" counts for 1M elements with error 1%, bot gives you something small like:

Bing: 272 columns and 5 rows ChatGPT: 200 columns and 40,000 (!!!) rows

40,000 rows is definitely overkill, but I columns has to be more as well.

If we hash 1M different items in 272, 200 or even 40K "pigeon holes" we will have more than one "pigeon" in each hole. In fact holes will be very crowded and pigeons won't able to live.

If I check the bloom filter calculator here, https://hur.st/bloomfilter/?n=1000000&p=0.01&m=&k=

if I have 1 hash function, optimal width is 100x the items (99,499,163) and optimal solution is with 7 hash functions and 10x width (9,585,059).

I can imagine I can store 1'000 items in 1'000 slots (note no hash function can do that), but 200 columns sounds ridiculous.

What I am missing?

# Answer
In order to correctly compute the sketch dimensions, you need first to decide the error $\epsilon$ and the probability of failure $\delta$. This is because Count-min sketch, denoting with $\boldsymbol{s}$ the vector corresponding to the stream of items, and with $w$ and $d$ respectively the number of buckets (columns) and rows, provides the following guarantees:

if $w=\left\lceil\frac{e}{\varepsilon}\right\rceil$ and $d=\left\lceil\ln \frac{1}{\delta}\right\rceil$, an estimate $\hat{a}\_i$ is such that $a\_i \leq \hat{a}\_i$ and $\hat{a}\_i \leq a\_i+\varepsilon\\|\boldsymbol{s}\\|\_1$ with probability at least 1 - $\delta$.

Note that the length of the stream is not relevant, and, indeed, the sketch dimensions are independent from the length of the stream.

In your case, you fixed $\epsilon = 0.01$ (i.e., $1\\%$). Fixing $\delta = 0.04$ the guarantees hold with probability at least $1 - 0.04 = 0.96$. The corresponding dimensions are $w=\left\lceil\frac{e}{\varepsilon}\right\rceil = 272$ and $d=\left\lceil\ln \frac{1}{\delta}\right\rceil = 4$.

Fixing $\delta = 0.01$ (for a stronger guarantee holding with probability at least $1-0.01=0.99$) you get $d=\left\lceil\ln \frac{1}{\delta}\right\rceil = 5$.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Resolution exponential lower bound... alternative proofs?
I am reading the Resolution proof system exponential lower bound via Haken's bottleneck method for the Pigeonhole Principle as presented in Arora and Barak's *Computational Complexity: A Modern Approach*, Chapter 15. However, I don't like how the proof is presented in the book and I am having some difficulties following it.

Does somebody know of alternative sources where this same proof is presented? I know there are different techniques to show exponential lower bounds for Resolution, but I want something based on the Pigeonhole Principle. It's just that the phrasing in this book is truly confusing.

# Answer
> 4 votes
If you don't like the presentation of Arora and Barak, you can always take a look at Haken's original paper.

The modern approach to Resolution lower bounds is, however, via Resolution width, as worked out in a classical paper of Ben-Sasson and Wigderson. You can also find expositions in various lecture notes, for example by Jakob Nordström.

# Answer
> 1 votes
I would recommend "Proofs as Games" by Pavel Pudlak. I find the prover-adversary model quite useful for building intuition. For example, soundness and completeness of resolution are trivial (Prover just queries all variables). It has been used, for example, in "Planar tautologies are hard for resolution" by Dantchev and Riis.

Although resolution width unified many previous lower bounds, it does not capture all of them. In particular, it cannot show lower bounds on formulas that start with a wide clause. "Random restriction" is the more general approach.

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