# Question
Title: Can I solve pumping lemma for context free language proofs using examples?
Say I need to prove that

$L=${$a^n b^n c^n; n\geq 1$} is not context free language

I take n=3. w=aaabbbccc

Here |w|=9.

we know by pumping lemma-:

|vxy| $\leq$n so vxy=abb

|vy| $\geq$1 so vy=ab

Hence I suppose-: u=aa v=a x=b y=b z=bccc

So

$u v^i x y^i z$ =aaaabbbbccc

Hence it is not in L so L is not regular.

But this looks funny to me to be approved in exam. Will it be approved in exam in your opinion? I know it is broad question but there must be CS teachers in cs.stackexchange to know about this? The other proof of this is too hard for me to understand. So I have resorted to this.

# Answer
> 1 votes
That's an incorrect proof. There are two reasons.

You say that you need to prove that $L$ is a context-free language. The pumping lemma cannot help you with that, since it can only be used to prove that $L$ is not regular (which doesn't imply that $L$ is context free) or that $L$ is not context-free (in its variant for context-free languages).

Assuming instead that you wanted to prove that $L$ is not a regular language, it is not correct to just pick "an example" word.

The pumping lemma statement is as follows:

**Pumping lemma:** if $L$ is regular, then there **exists** some positive integer $p$, such that **for every** word $w$ with $|w|\ge p$, there **exists** a way to write $w$ as $xyz$ with $|xy| \le p$ and $y \ge 1$, such that **for every** integer $i \ge 0$, $xy^iz \in L$.

If you want to show that $L$ is not regular, then you need to prove that the pumping lemma does not hold for $L$. In other words you need to show that the following holds:

**Negation of Pumping Lemma:** **for all** positive integers $p$, there **exists** a word $w$ with $|w|\ge p$ such that, **for every** possible choice of $x,y,z$ with $w=xyz$, $|xy| \le p$, and $|y| \ge 1$, there **exists** an integer $i \ge 0$, such that $xy^iz \not\in L$.

This means that you cannot choose a fixed length of $|w|$. Moreover, you cannot choose the decomposition of $w$ into $x$, $y$, and $z$, but you need to consider all possible decompositions (that satisfy the constraints of the statement above).

Here is a proof that your specific $L$ is not regular by showing that "Negation of Pumping Lemma" holds.

Given **any** value of $p$ (recall that our proof must hold for all $p \> 0$), we choose $w=a^p b^p c^p$ and we notice that $|w| = 3p \ge p$. We are allowed choose $w$ since we only need to show that a suitable word $w$ **exists**.

We now consider **all possible** ways of writing $w$ as $xyz$ with $|xy|\le p$ and $|y| \ge 1$. Notice that $xy$ must contains only $a$s, therefore $x$ must be of the form $a^j$ for some $j \ge 0$, $y$ must be of the form $a^h$ for some $h \ge 1$, $j+h \le p$, and $z$ is of the form $a^{p-j-h}b^p c^p$.

Next, we pick a value for $i$ (a single value suffices since we only need to show that a suitable value **exists**). In particular we choose $i=0$.

We need to verify that $x y^i z \not\in L$. This is true since: $$ x y^i z = a^j (a^h)^i a^{p-j-h}b^p c^p = a^{p-h}b^p c^p, $$ and $h \ge 1$.

This shows that "Negation of Pumping Lemma" holds for $L$, i.e., that the Pumping Lemma fails for $L$. As a consequence $L$ cannot be regular. This concludes the proof.

# Answer
> 1 votes
There are very many flaws in this proof attempt, and I would not give marks for this.

First of all: $L$ is NOT context-free and the pumping lemma for context-free languages can only be used to prove that a language is NOT context-free. Similar to the better-known pumping lemma for regular languages, there are non-context free languages that have the pumping properties required by the lemma.

Second: the pumping properties rely on the assumption that there exists a finite pumping length $p$, and that only strings containing $p$ or more symbols are subject to the requirements of the lemma. Therefore, you can't use the string $aaabbbccc$, because it's possible $p \> 9$ for all possible pumping lengths $p$ of $L$ in which case we wouldn't expect the conditions to hold anyway. You can use any $s \in L$ with $|s| \geq p$, for instance $a^pb^pc^p$.

Third: after you have fixed the string for observation, eg. $s = a^pb^pc^p$ as above you must present the $uvxyz$ division under the conditions given is impossible to satisfy. You have to show that *every* choice of $uvxyz$ fails at least one of the lemma's conditions. The choice of $s$ here matters a lot: as the "center part" of the string is bounded in length – more formally, $|vxy| \leq p$, you know that $v$ and $y$ contain no $a$ symbols, no $c$ symbols, or neither symbol, which gets you the expected result of $L$ being non-context free.

Try again with these notes in mind, and I think you will have an easier time.

---
Tags: context-free, pumping-lemma
---


# Question
Title: Why is copy speed periodic? (or seems to be)
When copying ~80Gb data from one USB 3.2 stick to another, i noticed that the GUI of the transfer speed had clear periodicity. Out of curiosity, what could be the reason for this? No other active programs were running that, to my awareness, should put a periodic load on the system.

# Answer
> 11 votes
Here's a possibility: Every transfer copies one megabyte and takes 0.4 seconds. The display is updated every second. The counter for "data transferred" is updated when a transfer is complete.

So 50% of the time the display is updated after 2 transfers with 2.0 megabyte completed, and 50% of the time it is updated after 3 transfers with 3.0 megabyte completed. That explains the "periodic" behaviour quite nicely.

In your case, your USB stick might be quite slow, so my numbers are actually realistic. In case of a hard drive: Hard drives have caches. So your computer can write say 100MB per second to the hard drive, but actually only 80MB get written and 20MB fill up the cache. Until the cache is full, and then your hard drive doesn't accept new data until say 100MB of the cache are written to the actual hard drive. That will look to your computer as if write speed wasn't constant.

But since you posted on CS, it's now your duty to explain exactly what happened :-) For example, you could write a program that logs reading and writing with the exact times when they happen.

# Answer
> 4 votes
The transfer is DMA so it isn't really the other programs which create periodicity. It is more like bus-mastering and the speed with which the device answers the read and write commands. I assume you are on Windows desktop with an x86-64 CPU. On these desktops an xHCI is used to transfer data. I actually wrote a partial xHCI driver which I have not finished yet.

I can tell the xHCI supports MSI-X. The xHCI thus can trigger interrupts directly to the local APIC of one specific CPU core. The currently running program on the core is interrupted and the TSS is used to switch the stacks if there was a ring 3 to ring 0 transition. Otherwise, the interrupts are simply nested on the same stack. The interrupts are short lived because they don't do the main work. They simply do some work to add the interrupt to the queue of programs that the OS will then switch on using the scheduler. The data Transfer Event TRB is probably also read by the driver and it pushes the data of the TRB to some other place. This is called Bottom-Half Interrupt Processing. The TRB informs software of the size of the transfer (for more info see When are a controller's registers loaded and ready to inform an I/O Operation?).

The periodicity can be created by file switching. One file can be "programmed" to be read/written to a USB stick to a specific address at once whatever the file's size) but you cannot tell the xHCI to just write to a device with five different addresses and tell it to read the files from 5 different addresses. There is some processing involved by software on file switch that can create periodicity in the transfer.

The scatter gather operations can create periodicity because the virtual memory is contiguous but not physical memory. The physical memory is separated in chunks of 4KB so the buffer allocated to your program (the built-in file explorer) may be bigger than a page and be scathered around RAM. To avoid that you can use one buffer of 4KB but that makes the operation slower because you need to schedule the operation several times to read into the buffer. Instead, file explorer probably makes the buffer much bigger and let the OS do the scather gather by putting several TDs on the Transfer Ring of the endpoint for that device. The TDs contain TRBs and specify physical addresses so the OS must make sure that the transfer doesn't overwrite parts of the address space of another process. It must also pin the pages to physical memory instead of swap because DMA transfers are writing directly to it. If the OS swaps the page-frame to the hard-disk and give the page-frame to another process, the DMA engine is writing to another process's address space. This is very dangerous and could be a potential vulnerability. There have been some vulnerabilites known in the past so this is actually something that can happen in a recent OS (because it happened in recent years but I don't know if there are current vulnerabilities).

A lot of other things can create periodicity. It is a very complex operation which involves bringing the data to RAM and then sending the data back to the other device.

Also, I didn't read the xHCI spec for the bulk transfer part. Bulk transfers seem to be the way to transfer data from a mass storage device to RAM or vice-versa. Maybe start to read the spec and you'll have all the info you need. The spec is linked on my answer that I linked above.

---
Tags: operating-systems
---


# Question
Title: For 3CNF unsatisfiable boolean formulas, does it take exponential time to transform them into disjunctive form？
From the link Solving SAT by converting to disjunctive normal form, I learnt that the algorithm to transform any boolean formula to disjunctive form takes exponential time in worst case.

But I have a question that for unsatisfiable boolean formulas, does it also take exponential time to transform them into disjunctive form?

More specifically, for 3CNF unsatisfiable boolean formulas, does it take exponential time to transform them into disjunctive form？

# Answer
> For 3CNF unsatisfiable boolean formulas, does it take exponential time to transform them into disjunctive form？

For *unsatisfiable* formulas, the answer is trivially no -- in fact it takes constant time. Output any disjunctive unsatisfiable formula, like $(p \land \lnot p)$.

It is possible to fix your question so that it's not trivially answered, but that does require some more effort. We could ask: is there an algorithm that takes as input a 3CNF boolean formula, and outputs a disjunctive normal form, such that for unsatisfiable inputs, the algorithm takes sub-exponential time (but it is allowed to take exponential or longer time on the satisfiable inputs)? To this question, D.W.'s answer applies.
> 1 votes

# Answer
We don't know. If P=NP, then no, it doesn't take exponential time. If P$\ne$NP, then it cannot be done in polynomial time (but we don't know whether it requires exponential time). If the Exponential Time Hypothesis holds, it requires exponential time.
> 0 votes

# Answer
The procedure in your reference still holds for unsatisfiable instances; it's just that each clause produced by that procedure will have a pair of opposite literals $... \land a \land \neg a$.

The minimized disjunctive normal form of an unsatisfiable problem (the set after removing subsumptions and contradictions) is the set $\emptyset$ with no clauses. As the interpretation of DNF is that each clause be disjoined, you end up with an empty disjunction, which is vacuously false.

To be clear, it is possible to convert the formula to DNF in polynomial time an an approach akin to the Tseitin trasnformation, but the quantification of the Tseitin variables would have to be universal instead of existential, so it would no longer be a SAT problem.
> 0 votes

---
Tags: complexity-theory, time-complexity, satisfiability, computation-models, 3-sat
---


title: P vs NP Clarification

text:
# Question
Title: P vs NP Clarification
A problem is solvable in polynomial by a deterministic turing machine, and no solution exists which benefits from parallelism.

Will it be P or P-Complete or NP or NP-Complete?

# Answer
> 2 votes
Assuming that we are talking about a decision problem, it is in $\mathsf{P}$ since it is solvable in polynomial **time** by a deterministic Turing machine.

Whether the problem is $\mathsf{P}$-complete depends on which type of reduction you are considering.

The problem is in $\mathsf{NP}$ since $\mathsf{P} \subseteq \mathsf{NP}$. We don't know whether such a problem is $\mathsf{NP}$-Complete, in fact this is a major open question in computer science.

# Answer
> 2 votes
A decision problem is in NP if you can find the answer (and prove it's correct) in polynomial time if the answer is YES, and you are given a suitable hint. It's in P if you can find the answer in polynomial time. Obviously any problem in P is in NP, because you can solve it in polynomial time, whether the answer is YES or NO, and you can just ignore any hint.

It's unlikely to be NP-complete. Actually, it is widely believed that problems in P are NEVER NP-complete or NP-hard. Finding a prove for that is very, very, very hard.

---
Tags: complexity-theory
---


# Question
Title: Regular Expressions - What is difference between a+ and a⁺
I'm very confused as to if a+ and a⁺ mean the same thing or are completely different.

# Answer
> 5 votes
Usually that is a matter of taste. If I am nathematically motivated then I write $a^\*$ like some single argument postfix operations in mathematics. If I keep close to applications, I would type $a\*$ because typing superscripts in input for programs seems silly.

Same for $a^+$.

Be aware that in the context of regular expressions plus $+$ might have another meaning. It might be the same as "choice" or "union". Thus people can write $a+b$, $a\cup b$, or $a\mid b$ depending on their choice for that binary operator.

# Answer
> -1 votes
a\* means that "a" must occur zero or more times.
a+ means that "a" most occur one or more times.

In other words, a\* allows an empty string, while a+ doesn't (unless a itself allows an empty string).

To write it: If your editor allows it easily, $a^\*$ and $a^+$ are preferable, because they are correct. On this site: Dollar, a, caret, star, dollar for $a^\*$. Exponent in curly braces like { 15 } if it is more than a single character, like $a^{15}$ and not $a^15$.

PS. Oh well. I read your question as a+ vs a\*. Maybe $a^+$ is not such a good idea. Or I need new glasses :-(

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


# Question
Title: Efficient intersection detection between disks with identical radius
I have a set of $N$ points randomly positionned on a rectangular space (btw with either absorbing, reflecting or wrapping boundaries), and I need to obtain the distances between every 2 points whose distance is at most $2\\,r$.

This is akin to consider every point as a disk with radius $r$ and only consider distances between centers of intersecting disks. I know that people doing collision detection are very much into optimizing the detection of intersecting shapes, but it seems that I can make hypotheses that they cannot make in general, and that would maybe help me not to test every 2 points together:

* There is no motion, only the set of static disks.
* All shapes are disks.
* All disks have the same radius $r$.
* I have a *hint* that the average distance between 2 neighbouring points is much smaller than $r$, so it will be frequent that numerous disks overlap together.

Are there clever ways to prune among the $\left(\begin{array}{c}N \\ 2\end{array}\right)$ pairs of points and (at best) only calculate distance between points whose disks are intersecting.. or likely to intersect together?

# Answer
Use any standard data structure / algorithm for nearest neighbor search. In particular, you are interested in the fixed-radius nearest neighbor problem, for which there are many algorithms.
> 1 votes

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


# Question
Title: Explicit form of Hofstadters bluediag in floop
In " Gödel, Escher, Bach" Hofstadter introduces the programming languages Bloop and Floop. Relevant here is mostly that Floop is Turing complete, while Bloop differs from Floop in one aspect: all loops must be bounded. So only for-loops, no while-loops.

Hofstadter shows that not all computable functions are computable by a Bloop program (so that Bloop is apparently really weaker than floop) by exhibiting a function called BLUEDIAG that is not computable by a bloop program. While the function itself is quite explicit, the proof (reproduced below) of *why* this is not programmable in Bloop somehow seems to never use any other property of Bloop except that there are only countably infinitely many Bloop programs. In particular it is not clear to me *where in the proof it is used that loops must be bounded*. To make this point clearer, my question is this:

> If I would explicitly code a program to compute the BLUEDIAG function in Floop, where would I use an unbounded loop?

I will show where I got stuck in my own attempt. First a summary of the proof. (If my notation differs from Hofstadter's it is because I am translating back to English from a translated version of the book)

BLUEPROGRAMS is a list of all Bloop programs that take one integer input and have one integer output for each input. The programs on the list are sorted by length and within that alphabetically so that there is no ambiguity about the order.

BLUEPROGRAMS{N} denotes the Nth entry on this list.

BLUEPROGRAMS{N}\[M\] denotes the output of the program BLUEPROGRAMS{N} when fed the input M.

The function BLUEDIAG is defined by BLUEDIAG\[N\] = BLUEPROGRAMS{N}\[N\] + 1.

Now if BLUEDIAG *were* computable by a Bloop program then this program should appear somewhere on the list BLUEPROGRAMS, say at position $X$. We then get the strange situation that BLUEPROGRAMS{X}\[X\] = BLUEDIAG\[X\] = BLUEPROGRAMS{X}\[X\] + 1, where the first equality represents the assumption that BLUEPROGRAMS{X} calculates BLUEDIAG and the second comes from the definition of BLUEDIAG. Since no number Y satisfies Y = Y + 1 the number BLUEPROGRAMS{X}\[X\] cannot exist, hence the program BLUEPROGRAMS{X} does not exist.

So far so good. As far as proofs go this is really easy, but at the price of obfuscating what about all this is special to Bloop.

Now for the quest of making a program that computes BLUEDIAG. My plan of attack is to make three programs.

Program 1 takes as input a natural number and as output the code of the Nth blueprogram.

Program 2 takes as in put the code of a blueprogram B and a number M and outputs the same number this program B would produce when given the input M

Program 3 takes as input a number K and outputs the number K + 1.

I convinced myself that program 1 can be written in Bloop: we can show that the Nth blue program has no more than N + 100 characters, so we can just loop through the huge but bounded list of gibberish strings of at most N + 100 characters and count how many of those are bloop programs.

I also convinced myself that program 3 is in bloop.

So this isolates the problem of needing unbounded loops to program 2.

But here I get stuck. When I try to write a program that simulates a different program whose code it is given as input I don't see how to do it - not with unbounded loops and also not without it. It seems to require the program to 'break free' from its domain of well defined software and start talking to the hardware in some sort of meta-language: 'stop treating this in the way I treat it (as a string) but view it in the same way you view me'. I'm not sure how floop (or any language really) would have this power, let alone how unbounded loops come into play.

Any help is appreciated!

# Answer
Great question!

You are wondering how "to write a program that simulates a different program whose code it is given as input".

That kind of program can be roughly understand as "an interpreter of a language." For example, the Python interpreter, i.e., python.exe (together with supporting libraries ) can read a Python program and execute it. Note that python.exe is written in machine code (roughly speaking), instead of in Python.

If the source code is also written in the same language, that kind of program will be called "a universal machine" of that language. The most famous universal machine is the universal Turing machine, which can read the textual representation of another Turing machine and simulates what it does.

As the above examples indicate, it may not be an easy task to write an interpreter or program a universal machine, conceptually or practically. That explains why you "don't see how to do it". Had you taken a course on assembly languages or compilers, you would have known how to do it. Basically, your code should read the input program as text, translate/compile it into "executable code" and then (or at the same time) execute the code. The "executable code" will define/allocate variables that record the current running state as it runs, as well as variables that track the next statement to execute.

---

Program 2, if written in Bloop, would be a "universal machine" of BlooP. You are right to assert that, in fact, there is no universal machine of Bloop.

Since FlooP is Turing complete, it is possible to write program 2 in FlooP. (Turing completeness means roughly the statement "what is machine-computable is FlooP-computable" in the book.)

---

You are wondering how unbounded loops come into play, which enables FlooP to "have this power".

This is, in fact, not easy to answer. Most computable functions, especially the "ordinary" ones, that are studied in mathematics can be computed by a BlooP program. It is difficult to devise or prove a computable function that cannot be computed by a BlooP program. In fact, instead of "at the price of obfuscating what about all this is special to Bloop", the proof given in the book tells clearly what is special to Bloop, i.e., there are countably-enumerable many programs written in Bloop and "addition by 1" is allowed in a Bloop program. It is only unfortunate/fortunate that to beginners, that characterization may not appear intuitive or familiar at all.
> 2 votes

# Answer
Program 2 can be a FlooP interpreter.

When started in a state in which the source code of a FlooP program is in internal memory, it will execute it.

It can do this by keeping its internal memory subdivided into three parts:

1. The FlooP program's source code (represented as a sequence of numbers according to some representation you have chosen, e.g. ASCII, or a more concise bytecode representation).
2. A sequence of numbers representing the current point of execution within that program (e.g., if ASCII is used, there might be an index into the sequence of ASCII characters, but for each loop we're in, we want to store the start of the loop to jump back to after an iteration has finished, and for each bounded loop we're in, we also need to count the number of iterations executed thus far).
3. The contents of the variables of the FlooP program being executed (`OUTPUT` and `CELL(i)` for each `i`)

Part 1 is fixed, but 2 and 3 are variable in size and they can grow arbitrarily large (depending on the program being interpreted). This is not a blocking issue, e.g. they can be interleaved.

The FlooP program implementing the interpreter will alternate between scanning statements in the source code (within memory area #1) and executing them (on memory area #3). For each type of statement, a function can be defined to execute that statement; for control structures, more than one function may be required. The interpreter will scan the source code, find a statement or control structure, and invoke the functions defined to execute them.

I'm not filling in the functions, but I hope this will suffice to convince you that it's doable.

(Doesn't Hofstadter explain this? I do not have a copy handy.)
> 2 votes

# Answer
I think the crux of the problem is this: Consider an arbitrary BlooP program. It may contain no loops. It may contain one or more loops in sequence, where the body of each loop has no loops. It may contain one or more loops with sub-loops. It may contain loops within loops within loops. ... It may contain an arbitrary number of nested loops.

Now consider a program which interprets an arbitrary BlooP program. It may need to interpret an arbitrary number of nested loops. I do not believe this can be done with a program that itself uses only bounded loops -where those loops were written before the interpreter ever saw a BlooP program-. There would always be a degree of nesting not interpretable.
> 1 votes

---
Tags: computability, loops
---


# Question
Title: Collision between a bi-infinite linear sequence of 2D integer lattice points and any of a fixed set of such sequences
Given:

* a finite collection $V$ of bi-infinite linear sequences of two-dimensional integer lattice points, each sequence ${V\_i}$ given by $\cdots,\vec{{V\_i}\_{-1}},\vec{{V\_i}\_0},\vec{{V\_i}\_1},\cdots$ where $\vec{{V\_i}\_j} = \vec{{V\_i}\_0} + j \times \vec{d\_i}$ for $j \in \mathbb{Z}$. (A natural way to represent a sequence like this would be with the pair $(\vec{{V\_i}\_0}, \vec{d\_i})$, with $\vec{{V\_i}\_0}$ chosen arbitrarily among the elements of ${V\_i}$)
* a single sequence $Q$ of the same type as an element of $V$ and similarly represented
* it is known that any two sequences in $V \cup \\{Q\\}$ share at most one point
* it is known that there are no "vertical", "horizontal" or constant sequences: the difference between successive elements in each sequence is always nonzero in both dimensions

I am interested in deciding whether any element of $V$ shares a point with $Q$. Allowing reasonable one-time precomputation for fixed $V$, is there an algorithm that decides this in less than linear time with respect to the size of $V$, for varying $Q$?

In other words, can we do pessimistically better than checking every element of $V$ for collision with $Q$?

I don't actually need to find the element of $V$ that shares a term with $Q$. I only need to know if such an element exists.

# Answer
> 0 votes
I think I figured it out, here's an outline of the idea:

#### Precomputation:

1. Choose a point $O^\prime$ that doesn't lie on any of the lines containing sequences in $V$; the origin is as good a choice as any, provided none of said lines go through the origin. $O^\prime$ does not need to have integer coordinates, so a random real point in the unit square is nearly sure to be good.
2. For each sequence $S$ in $V$, find the point closest to $O^\prime$ on the line through $S$ and add that point to a quadtree, together with a pointer to $S$.

#### Query

1. Consider the set $C$ of circles through $O^\prime$ and centered at midpoints between $O^\prime$ and each point in $Q$. Those can be alternatively defined as circles through 3 points, two of which are common to all the circles: $O^\prime$, the point closest to $O^\prime$ on the line containing $Q$, and an element of $Q$ (this is in fact the *textbook construction* of the point on a line closest to another point not on the line). Note that $C$ is still defined even if the line through $Q$ contains $O^\prime$, hence no extra restriction here.
2. I won't go into needless details, but it is $O(1)$ to check whether a point lies on one of those circles, and it is also $O(1)$ to decide whether a quadtree node overlaps any or none of those circles (i.e. whether it fits entirely in a crescent between two nearest circles).
3. Employing observations from point 2, traverse the quadtree, descending into nonempty nodes whose bounding rectangles intersect with some circles in $C$, and enumerating points that lie exactly on the circles. Output elements of $V$ associated with those points and additionally satisfying the full collision test with $Q$. Since this traversal will skip nodes that fit entirely between the circles of $C$, one hopes for a performance gain here.

Will add pics later.

---
Tags: computational-geometry, decision-problem, number-theory
---


# Question
Title: Uses of of the one-variable fragment of first-order logic aka S5
I'm looking at decidable fragments of first-order logic. It seems that FO(1), i.e. the one-variable fragment of first-order logic is equivalent to the modal logic S5. However, I cannot find a reference (everybody references a German article of 1933 which I cannot understand).

So I'm trying to understand what can be done with FO(1). It seems to me that it the same as the monadic fragment, i.e. where you only have monadic predicates and no binary relations, am I right? Can you tell me any interesting thing that can be expressed using no binary relations?

For example, I cannot find any meaningful sentence with a quantifier alternation since any nested quantifier would hide the outmost quantified variable.

So is there any interest in FO(1)/S5 by itself?

# Answer
Certainly there're meaningful research went to one-variable fragment of some specific first-order logics, though surprisingly in general they're undecidable even without any binary relations in this fragment.

From a recent paper "The One-Variable Fragment of Corsi Logic" by Caicedo1 et al, the one-variable fragment of the first-order logic of linear intuitionistic Kripke models turns out to be decidable:

> In this paper, we investigate the one-variable fragment of the first-order logic of linear intuitionistic Kripke models, axiomatized by Corsi in \[7\] as the extension of first-order intuitionistic logic with the prelinearity axiom schema (α → β) ∨ (β → α), and referred to here as Corsi logic. In particular, we prove that the modal counterpart of this one-variable fragment is the many-valued modal logic S5(G), with propositional connectives interpreted using the standard semantics of Gödel logic and $\square$ and $\Diamond$ interpreted as infima and suprema relative to \[0, 1\]-valued accessibility relations.

> The logic S5(G) lacks the finite model property with respect to its standard Kripke semantics, but is complete with respect to a variety of monadic Heyting algebras that has this property (see \[2\]) and is hence decidable. We provide here an alternative decidability proof that also establishes co-NP-completeness.

Another one-variable fragment of the first-order logic of branching time temporal logic had been studied by Hodkinson et al in their somewhat old paper "Decidable and undecidable fragments of first-order branching temporal logics":

> On the one hand, we show that the one-variable fragments of logics like first-order CTL\*—such as the product of propositional CTL\* with simple propositional modal logic S5, or even the one-variable bundled first-order temporal logic with sole temporal operator ‘some time in the future’—are undecidable. On the other hand, it is proved that by restricting applications of first-order quantifiers to state (i.e., path-independent) formulas, and applications of temporal operators and path quantifiers to formulas with at most one free variable, we can obtain decidable fragments.

So definitely there's interest in FO(1) fragments of certain first order logics.
> 2 votes

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


# Question
Title: Eulerian Path and Circuit Algorithm - How does it work?
I have found several versions of algorithms the find a Eulerian path/circuit in a graph, but I'm having trouble understanding why they work. For example http://www.graph-magics.com/articles/euler.php gives a clear description of the steps, but I can't see how those steps work, and certainly don't imagine I could have come up with the algorithm myself.

What insights/intuition would be needed to be able to develop this algorithm for oneself?

From my reading, it seems the basic idea is to find multiple circuits and somehow "splice" them together. However, the details are very murky in my mind and I'd like to understand in detail, including why and when you can do this etc.

Does the algorithm given in the link have a name? Is it based on DFS? Is it a version of Fleury’S Algorithm? If not how does it differ? (It seems Fleury's Algorithm makes decisions which the one in the article doesn't, but I may well be mistaken.)

It may well be that there are multiple algorithms for this problem, in which case it would be good to know which the one in the article is, and what the alternatives are.

It would also be very helpful to have some pseudocode for the algorithm in the article, based off an adjacency list, if anyone is willing to provide one.

# Answer
> 1 votes
The algorithm you linked is (or is closely related to) **Hierholzer's algorithm**. While Fleury's algorithm stops to make sure no one is left out of the path (the "making decisions" part that you mentioned), Hierholzer's algorithm zooms around collecting edges until it runs out of options, then goes back and adds missing cycles back into its path retroactively.

I'm not entirely clear how Hierholzer did this originally, but I agree with you that the version linked is using a *depth first search* approach to the problem, then backing up to the last "choice" to pick up the missing cycles. (This is why I'm not sure if it is Hierholzer's algorithm, or just related.)

In your link, it provides a "sample execution" which is far more detailed than any pseudo-code I would be able to provide you, but this site (geeksforgeeks) has C++ and Python code for Hierholzer's algorithm.

---
Tags: graphs, intuition, eulerian-paths
---


# Question
Title: Why are there here at most $ \vartriangle \cdot E $ paths?
I ran across this proof from the following paper: Finding and Counting Given Length Cycles

But I do not understand the third line.

> There are at most $ \vartriangle \cdot E $ such paths and they can be found in $O(\vartriangle \cdot E)$ time.

Why is that?

# Answer
> 2 votes
There are at most $E \cdot \Delta$ paths whose middle vertex has low degree. Indeed, any such path is composed of an edge $x\to y$, where $y$ has degree at most $\Delta$, and an edge $y \to z$. There are at most $E$ choices for $x\to y$, and since $y$ has degree at most $\Delta$, at most $\Delta$ choices for $y\to z$. This also shows how to find all these paths in time $O(E\cdot\Delta)$: just go over all directed edges $x\to y$, and whenever $y$ has low degree, go over all edges $y\to z$.

If a triangle $abc$ is not found this way, this means that there is no way to arrange its vertices so that the middle vertex has low degree. Some possible orderings are $abc,bca,cab$, showing that if *any* of the three vertices has low degree, then it is possible to arrange its vertices so that the middle vertex has low degree. Hence if $abc$ is not found in this way, all of its vertices must have high degree.

---
Tags: algorithms, graphs
---


# Question
Title: What is the analysis that a heap's optimal branching factor is between 2 and 5?
I'm reading the book Advanced Algorithms and Data Structures. It makes the claim that the optimal branching factor $D$ for a heap satisfies $2 \le D \le 5$, and that it is most likely $3$ or $4$ depending on the data being stored.

There is no citation in that book, so I tried to find one. On Wikipedia's D-ary Heap page I find two references cited for this claim. The 2nd one citation is the book Data Structures and Algorithm Analysis in C++ which contains no citations but makes the same assertions as Advanced Algorithms.

The first wikipedia citation is a 1983 book Data Structures and Network Algorithms by Robert Tarjan that simply states:

> An analysis of the constant factor involved in the timing of the heap operations suggests that the choice $D = 3 \text{ or } 4$ dominates the choice $D = 2$ in all circumstances, although this requires experimental confirmation.

Is there a paper with this analysis or did anybody verify this claim experimentally?

# Answer
You would really need the exact algorithm used, and the exact implementation, and the exact time for comparing two items and for moving an item from one place in the heap to another.

The critical operation is inserting an item into the heap. With $D=4$ instead of $D=2$, the height of the heap is halved, so half as many items move up. But at each level, one out of four instead of one out of two items must be moved up, so it’s more comparisons. So it is mostly the ratio of cost of comparisons vs cost of moves that counts.

You might look at cache effects: It is often faster to access several consecutive items than accessing the same number of items in several locations (if D items fit into one cache line, that is often just one memory access, so a larger D has an advantage). So measuring is needed, and you will have to try this for different heap sizes. And the ratio between cost of moving items and cost of comparing items will vary a lot. I think the optimal D will depend on the machine, on the heap size, and on the type of data in the heap.
> 1 votes

---
Tags: reference-request, heaps, priority-queues
---


# Question
Title: Why can't I use a polynomial-time reduction for proving P-completeness?
According to the Wikipedia page on P-complete,

> a decision problem is P-complete (complete for the complexity class P) if it is in P and every problem in P can be reduced to it by an appropriate reduction. \[...\] Generically, reductions weaker than polynomial-time reductions are used, since all languages in P are P-Complete under polynomial-time reductions.

I am not sure I can understand it. May you please elaborate on why I cannot use a polynomial-time reduction for proving P-completeness?

# Answer
> 5 votes
$P$-completeness is defined in terms of reductions stronger than polynomial reductions. For example, the notion of log-space reductions is such a "stronger" (more restrictive) reduction.

Notice that all languages in $P$ are poly-reducible to each other, by definition. So defining $P$-completeness in terms of poly-reductions would just be useless - so indeed a different notion of reduction has to be used.

This means that showing a poly-time reduction isn't enough to prove that a language is $P$-complete.

# Answer
> 1 votes
A more constructive demonstration: for any complexity class $X$ (not just for $P$), any problem $P\_X$ in $X$ can be *solved* by an $X$-algorithm (that's the definition).

If it can be solved by an $X$-algorithm, it's simple to extend that algorithm to output one of two different values depending on whether the solution is yes or no - unless your complexity class is so extremely restrictive that outputting a constant string is too hard for it - which $P$ is not.

Now choose any other problem $Q\_Y$ in *any* complexity class $Y$ which has at least one instance whose answer is "yes" and at least one instance whose answer is "no".

Now extend your algorithm for $P\_X$ so that if the answer is "yes" it outputs a known (hard-coded) instance of $Q\_Y$ whose answer is "yes" and if the answer is "no" it outputs a known (hard-coded) instance of $Q\_Y$ whose answer is "no".

You have now constructed an algorithm which reduces $P\_X$ to $Q\_Y$. And this applies for every $P\_X$ and every non-trivial $Q\_Y$, in most complexity classes $X$ and all complexity classes $Y$. You could reduce nearly anything to nearly anything this way.

---

And here's an actual instance of that. Here's an $NP$-algorithm that reduces SAT to the problem of determining whether an integer is less than five. The reduction algorithm works like this:

1. Solve the satisfiability problem instance (in $NP$ time).
2. If the instance is satisfiable, output 4.
3. If the instance is unsatisfiable, output 6.

Seems silly, right? That's why we don't define it that way.

---
Tags: complexity-theory, turing-machines, reductions
---


# Question
Title: When you convert epsilon NFA to NFA, how do you decide the final states of resultant NFA?
The question is-:

THIS is the transition table for NFA-:

Final result as shown in youtube video.

https://www.youtube.com/watch?v=GjLiXk0imi0&list=PLENQMW\_c1dimRCKF3bjUqHaH8dvJkapSw&index=49

**My question-:** What are the final states of this nfa?

I think q0, q1 and q2 all are final states. Because $\in$ closure of q0,q1 gives q2. And q2 is the final state itself. So q2 U (q1 U q0) is the final state.

Another youtuber solves the same problem but gets different answer-: (exactly what I am telling and tbh this makes more sense than the first one)

Source-: https://www.youtube.com/watch?v=ce0xAcABOYw

Then this neso academy video does the same (as I said).

https://www.youtube.com/watch?v=WSGcmaHNBFM

# Answer
> 1 votes
In short your assumption: "I think q0, q1 and q2 all are final states." is true.

Suppose your $\epsilon-\text{NFA}$ is called $M\_1$ and its equivalent $\text{NFA}$ is called $M\_2$. every state in $M\_1$ that can see at least one final state by only getting input $\epsilon$, will be a final state in $\text{NFA}$.

I think the reason will be quite obvious if you would consider $q\_1$ in your own example of $\epsilon-\text{NFA}$.
A final state, $q2$, is in its $\epsilon^{\*}$, i.e, being in state $q\_1$ (after starting from the initial state and getting the input $w$) can end in $q\_2$ and the given input will be accepted by $M\_1$.
So in $M\_2$ the state $q\_1$ is a final state too (as long as $q\_0$ with the same proof).

# Answer
> 0 votes
In the powerset construction $2^{\mathcal{A}}$ of an automaton $\mathcal{A}$, the final states of $2^{\mathcal{A}}$ are the sets that contain a final state of $\mathcal{A}$.

This also works when removing $\varepsilon$-transitions.

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


title: CFG for L={a^i b^j c^i; i,j > 0}

text:
# Question
Title: CFG for L={a^i b^j c^i; i,j > 0}
I worked a bit on this and got this-:

```
S->ABC
A->aA/a
B->bB/b
C->cC/c

```

The obvious problem here is I am unable to count number of a's and c's which should be equal. How do I create a cfg that can count a and c's and make them equal? Please guide.

If this was $a^i b^i c^j$ I could make a cfg.

# Answer
> 2 votes
So I worked a bit. And I think I got the answer. Feel free to correct me.

```
S -> aSc | aXc
X -> bX | b

```

It works a bit, e.g.: `aaaabcccc` gets derivation done. Similarly it works for `aabbbcc` as well.

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


title: Circuits for Modular Arithmetic

text:
# Question
Title: Circuits for Modular Arithmetic
I've read this which describes how to do do integer arithmetic in circuits. The one thing that it does not describe is how to do these operations with a modulus. How can modular arithmetic be done in circuits? Can someone point me to a resource or describe the modular step here?

# Answer
In general, everything that you can describe in pseudocode, you can convert into a circuit. So if you can do modular arithmetic by hand, then a circuit can do it. More to the point, here are some concrete ideas for doing modular arithmetic, where the modulus is $m$:

1. Addition: You already know how to add two numbers. Assuming both numbers were in $\\{0,\ldots,m-1\\}$, the answer lies in $\\{0,\ldots,2m-2\\}$, so it is enough to check whether the results is at least $m$, and if so, subtract $m$.
2. Subtraction: This is similar to addition. The idea is that $-a = m-a$.
3. Multiplication: Here the basic idea is to compute the result $ab$, divide by $m$, and keep the remainder. You can (possibly) optimize this by doing modular reductions along the way.
4. Division: This is more complicated, and is probably better implemented in microcode or software. Suppose we want to compute $a/b$. If $m$ is prime then we can assume that $b \neq 0$. We compute the modular reciprocal $b^{-1}$ of $b$ using the extended Euclidean algorithm, and then multiply $a$ by $b^{-1}$. If $m$ is composite then the situation is slightly more complicated since $b$ doesn't always have an inverse. In that case we first compute the GCD $g = (a,b)$, and $a' = a/g$, $b' = b/g$. There is a quotient $a/b$ only if $(b',m) = 1$, in which case we can proceed as before.
5. Powering: This is again quite complicated, and better implemented in microcode or software. Here the idea is to use the repeated squaring algorithm, reducing modulo $m$ at every step.
6. Discrete logarithm: Given $g$ and $g^a$, find $a$. This is complicated enough that it probably isn't implemented in hardware.
> 1 votes

# Answer
Yes, you should study the field of "residue numbers". This is a field in computer science and electrical engineering that has all sorts of fascinating circuits that deal with modular arithmetic. You can find circuits that deal with arithmetic that also includes an arbitrary, non-binary (power of two) modulus.
> 0 votes

---
Tags: circuits, modular-arithmetic
---


# Question
Title: 8085 microprocessor connection of CPU data bus with RAM data bus
What would happen if the CPU data-bus bit 2 is connected to the RAM data-bit 5 and CPU data-bus bit 5 is connected to RAM data bit 2? Assume the rest of the connections are all right – explain.

# Answer
Not much. Bits 2 and 5 will get swapped over when the CPU reads memory but also when it writes memory, so it cancels out. It will only make a difference if some other hardware device is also accessing the RAM and *not* swapping over those bits.
> 1 votes

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


# Question
Title: The relation of W[1]-hard and Para-NP-hard
Is it possible that a problem is both W\[1\]-hard and Para-NP-hard?

# Answer
Yes, that is possible.

Take a parameterized problem $P\_1$ that is W\[1\]-hard and a parameterized problem $P\_2$ that is para-NP hard. Now consider the problem $P\_3:=\\{(0w,k)\mid (w,k)\in P\_1\\}\cup\\{(1w,k)\mid (w,k)\in P\_2\\}$. A reduction from $P\_1$ to $P\_3$ works by just prepending a $0$ to the first part of the input. It runs in polynomial time. It does not change the parameter. The output is in $P\_3$ if and only if the input is in $P\_1$. Hence, it is a parameterized reduction from $P\_1$ to $P\_3$. As $P\_1$ is W\[1\]-hard, so is $P\_3$. In the same way we can prove that $P\_3$ is para-NP-hard.

The above is a quite general approach to "being hard for two classes". In the present case, we can argue much simpler: W\[1\] is a subset of para-NP, so each para-NP-hard problem (e.g. graph colouring, parameterized by the number of colours) is also W\[1\]-hard.

The point is that "hard for a class" is open ended: It is preserved by making a problem even harder. This may not be what you had in mind. So let's consider a different question: Is it possible that a problem is both W\[1\]-complete and para-NP-complete (meaning that both classes coincide)? There, the answer is unknown. For all we know, W\[1\] may coincide with one of FPT or para-NP, with both, or with none. Settling the question is closely tied to P-vs-NP.
> 1 votes

---
Tags: parameterized-complexity
---


# Question
Title: Are bits (0/1) named "characters" anywhere in the literature?
I know that each character ("in the macro level") is comprised of at least two bits ("in the micro level").

But are these bits of this "micro, electrical-logical level" have been considered "characters" by themselves anywhere in the literature and would it make any sense to define them as such?

# Answer
> 1 votes
In principle, a name is just a means for communication. You can use any terms and definitions you want as long as you and your audience both agree on the meaning of them and as long as it doesn't cause confusion.

In practice, no, bits are not characters. The word "character" has an accepted definition and most people would probably find it confusing if you used the word "character" to refer to a single bit.

---
Tags: terminology
---


# Question
Title: I can't visualize what happens when we pump v and y in pumping lemma for $a^n b^n c^n$
If you need some context-: https://www.andrew.cmu.edu/user/ko/pdfs/lecture-11.pdf around page 7.

Case 1-: Say vxy contains ab

So when I pump v and y, what will get pumped? And how the result would be. I can understand the case for when vxy is all a's, all b's or all c's.

Case 2-: Say vxy contains bc

When I pump v and y, what happens? Help me visualize this.

**My try-:**

I will take case 1.

take i=2 then

We let

$u=a^{n-k} $

$v=a^k $

x=$\in$

y=$b^l$ k+l\<=n

z=$b^{n-l} c^n$

Now I find $u v^2 x y^2 z$=? whwich gives $a^{n+k} b^{n+l} c^n$ which is obviously not in L. Am I right here?

# Answer
> 0 votes
I answer for the case 1, the case 2 is similar.

Since $vxy\in a^\*b^\*$, and $vy\neq \varepsilon$, that means that $v$ and/or $y$ contains at least one $a$ or at least one $b$, and no $c$. That means that $uxz$ (pumping can also mean considering $uv^0xy^0z$) contains strictly more $c$'s than either $a$'s or $b$'s (or both), so $uxz\notin \\{a^nb^nc^n\mid n\in\mathbb{N}\\}$.

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


title: What determines bus speed?

text:
# Question
Title: What determines bus speed?
I would like to know what determines bus speed in a CPU. I know about bus width, that all makes sense, but since electrical pulses travel at light speed I don't understand why bus speed is measured rather than just light speed. What on the bus means the signals aren't sent at light speed?

Thanks in advance.

# Answer
> 1 votes
"Bus speed" isn't the right technical term, since it is ambiguous. The speed of electric signal depends on the speed of the electromagnetic wave in that medium, and is not necessarily equal to the speed of light in vacuum.

The maximum *information data rate*, reported in Bits/Second, is the rate at which data can be transferred without loss of information. This rate depends on the noise level present in the channel/bus, and is given by Shannon's formula.

---
Tags: computer-architecture, cpu
---


# Question
Title: Given the hypercube Q3 of 8 vertices, what is x + 10y where x is the minimum vertex cover set size and y is the maximum independent set size?
Sorry for the shoddy formatting in the title, here's something clearer:

Given the hypercube Q3 of 8 vertices, what is x + 10y where x is the minimum vertex cover set size and y is the maximum independent set size?

I know that a hypercube Qd is just a graph with 2d vertices consisting of binary strings of length d, and that two vertices are adjacent whenever they differ in exactly one bit, but I'm struggling to put it together conceptually.

# Answer
> 1 votes
This is an easy exercise. Here is a hint.

Notice that Q3 has 12 edges and that all vertices of Q3 have degree 3. Can you find a lower bound on the size of a vertex cover using the above information?

Once you have such a lower bound, can you find a vertex cover that matches it?

Finally, how is the size of a minimum vertex cover related to the size of a maximum independent set? Recall that, given a set of vertices $S$, $S$ is a vertex cover if **at least one** of the endpoints of each edge belongs to $S$, while $S$ is an independent set if **at most one** of the endpoints of each edge belongs to $S$.

---
Tags: graphs
---


title: Can the diagonal language be empty?

text:
# Question
Title: Can the diagonal language be empty?
We defined the diagonal language as follows in the lecture: \begin{align\*} L\_{\text{diag}}=\left\\{w \in \left\\{0, 1\right\\} ^{\*}\mid w=w\_{i} \text{ for some }i \in \mathbb{N} \text{ and }M\_{i} \text{ does not accept }w\_{i}\right\\} .\end{align\*} Here, $w\_i$ is the $i$-th word in canonical order and $M\_i$ is the $i$th Turing machine, canonically ordered by their encodings in binary. No I asked myself the question whether this language could be empty, e.g. if every $M\_i$ would accept the word $w\_i$. Could this happen, depending on how we define the encoding of a Turing machine?

# Answer
Here is a simple direct proof that $L\_{\text{diag}}$ is not empty.

Let $N$ be a Turing machine that does not accept any word. For example, a Turing machine that just loops forever. Suppose $N$ is encoded as the $j$-th machine. Then $L\_{\text{diag}}$ contains the word $w\_j$. Hence $L$ is not empty.
> 10 votes

# Answer
Since the diagonal language is not computable but the empty language is computable, that means that those languages are different.
> 3 votes

# Answer
Others have already suggested the simplest and most elegant ways to prove that the diagonal language is not empty.

Indeed, we can proceed by contradiction, and argue that if the diagonal language were empty, it would be recursive, but we know it is not. Or, more constructively, if we take any TM that recognizes the empty language, then it does not accept any word including the word that encodes the TM, hence such word is in the diagonal language.

I only want to add that (arguably) more "satisfying" examples can be crafted, at the cost of additional complexity (and reduced elegance). One way to do so is to resort to the Rogers's fixed-point theorem. Briefly put, that theorem allows to craft TMs that internally have access to their own word-encoding . For instance, we can have a TM $M$ defined as follows:

> On input $w$, proceed as follows. First, compute $w\_M$ as the encoding of the TM $M$ (the one which we are executing right now). Then, compare $w$ to $w\_M$ and accept if and only if they are different.

It is not obvious that such an $M$ exists, since its description above refers to itself, but Rogers's fixed-point theorem ensures that's the case, so we can pretend the one above is a valid definition for $M$.

By construction, $M$ accepts any word except for its own ($w\_M$), so it clearly belongs to the diagonal language.
> 2 votes

---
Tags: formal-languages, regular-languages, diagonalization
---


# Question
Title: How do I create a finite state automata for addition in ternary system?
I've been scratching my head with this one for a few hours now, but am feeling to stupid to comprehend how it is to be done. I can't understand the way even the state table should be built for this one. From where should I start?

# Answer
I think the best way to do it is to begin with an addition in binary. Since you didn't give any indication on the formatting of the input, I will make my own choices here.

Suppose the input alphabet is $\Sigma = \\{0,1\\}^2 = \\{(0,0), (0,1), (1, 0), (1,1)\\}$. An input is of the form $(a\_0,b\_0)(a\_1,b\_1)…(a\_{n-1},b\_{n-1})$, meaning we want to add $x = (a\_0a\_1…a\_{n-1})\_2$ and $y = (b\_0b\_1…b\_{n-1})\_2$, where $(…)\_2$ represents the reverse binary encoding (meaning $x = \sum\limits\_{i=0}^{n-1}a\_i2^i$, for example $13 = (1011)\_2$).

I will create a Mealy Machine computing $x+y\mod 2^n$. The idea is to use two states, depending on the need of a carry or not.

Here, a transition $a|\alpha$ means that when reading $a$, I write $\alpha$ on the output.

$q\_0$ represents the state without carry, and $q\_1$ represents the state with a carry. A carry appears from $q\_0$ when adding two $1$ bits. If that's the case, the state will become $q\_1$. The carry will disappear only when adding two $0$ bits.

Now what you need to do is getting inspired by this machine and try to do the same in ternary, with input alphabet $\Sigma = \\{0,1,2\\}^2$.
> 1 votes

---
Tags: finite-automata
---


# Question
Title: Prove every number in double precision 32-bit floating-point format can be represented in 64-bit format
**Theorem:** Prove every number in double precision 32-bit floating-point format can be represented in double precision 64-bit floating point-format.

*64-bit format:*

**Attempt:** Let $ b = b\_0 ,...,b\_{31} $ be a binary string of 32 bits. Define a binary string of 64-bits $ a = a\_0,...,a\_{63} $ as follows:
$ a\_0 = b\_0 $, $ ~~~~ a\_1 = b\_1,...,a\_8 = b\_8 $, $~~~~ a\_9=a\_{10} = a\_{11} = 0 $, $~~~ a\_{12} = b\_9 ,...,a\_{34} = b\_{31}~ $, $~~~ a\_{35} = a\_{36} = ... = a\_{63} $. Note that the binary string $ a $ as a float in 64-bits has the same sign and fraction of binary string $ b $ as a float in 32-bits, since: $ a\_0 = b\_0 $ ( signs are the same ), $ \forall 1 \leq i \leq 8. a\_i = b\_i .$ and $ \sum\_{k=1}^{52} a\_{k+11} \cdot 2^{-k} = \sum\_{k=1}^{23} a\_{k+11} \cdot 2^{-k} = \sum\_{k=1}^{23} b\_{k+8} \cdot 2^{-k} $ ( fractions are the same ). We'll show that they both the same exponents, \[ missing arguments \].

I got stuck in showing that both $ a $ and $ b $ have the same exponent, but it might not be true from my construction of $ a $ since If I take the following 32-bit float:
we see that $ sign = 0 , fraction = 1 \cdot 2^{-2} = \frac{1}{4}$ , $ exp = (01111100)\_2 = (124)\_{10} $ so this floating point number represents $ (-1)^0 \cdot 2^{124-127} \cdot ( 1 + \frac{1}{4} ) = 0.15625 $. But according to my construction of $ a $ I get that $ exp =( 01111100000 )\_2 $ which is $( 992)\_{10} $, so I get that $ a $ represents $ (-1)^0 \cdot 2^{992 - 1023} \cdot ( 1 + \frac{1}{4} )$ which is a totally different number . hence I was stuck in proving the theorem. Can you please help? how would you prove the above theorem?

# Answer
> 2 votes
Ignoring denormalized numbers, infinities and the like, floating point formats can store numbers of the form $$ \pm \left(1 + \frac{x}{2^N}\right) \times 2^y, $$ where $0 \leq x \< 2^N-1$ and $-M \leq y \< M$; here $x,y$ are both integers, and $N,M$ are the parameters of the format. It's not hard to check that if you increase $N$ or $M$ then you can still represent all numbers that you used to be able to represent. This is what happens in your case.

---
Tags: floating-point, binary, number-formats
---


# Question
Title: Can a non-regular language have a regular grammar?
Basically the title. I am supposed to find a regular grammar for the language that produces palindromes. This is all I have right now:

```
S -> 1 | 0 | ε

```

Since it should be a regular grammar, I can't write 0S0 or 1S1. But then I don't know how I should even continue with this...

# Answer
> 2 votes
A regular grammar generates a regular language – the existence of a regular grammar for the language of palindromes would imply the language to be regular. However, it isn't, hence a regular grammar for it cannot exist.

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


title: Online Taylor series calculator

text:
# Question
Title: Online Taylor series calculator
When I compute the the eigenvalues of the matrix $$\begin{bmatrix}x^3& 2 + x^3& 3 - 2 x^3\\ 2 + x^3& 4 - 5 x^3& 5 + 3 x^3\\ 3 - 2 x^3& 5 + 3 x^3& x^3\end{bmatrix}$$ using WolframAlpha, I get the following first eigenvalue (copied from WolframAlpha):

```
λ_1 = 1/3 (4 - 3 x^3) + 1/3 (-432 x^9 - 1449 x^6 + 810 x^3 + 3 sqrt(3) sqrt(-10664 x^18 + 34200 x^15 - 38845 x^12 - 162020 x^9 - 241908 x^6 + 30520 x^3 - 38808) + 1072)^(1/3) - (-78 x^6 - 18 x^3 - 130)/(3 (-432 x^9 - 1449 x^6 + 810 x^3 + 3 sqrt(3) sqrt(-10664 x^18 + 34200 x^15 - 38845 x^12 - 162020 x^9 - 241908 x^6 + 30520 x^3 - 38808) + 1072)^(1/3))

```

I want to see the first few terms of the Taylor expansion around x=0 of that expression, however, it seems WolframAlpha cannot handle it. I have been looking for an online Taylor series calculator that can do this but it seems the expression is too hard to crack.

**Question:** Can anyone share with me a website where I can compute the first few terms (until $x^3$) of the desired Tylor expansion about $x=0$? I do not know how to use programs like Matlab to do this. Do you have any recommendations?

In case it is of any help, here is the expression: $$ \frac{1}{3} (4 - 3 x^3) + \frac{1}{3} (-432 x^9 - 1449 x^6 + 810 x^3 + 3 \sqrt{3} \sqrt{-10664 x^{18} + 34200 x^{15} - 38845 x^{12} - 162020 x^9 - 241908 x^6 + 30520 x^3 - 38808} + 1072)^{1/3} - \frac{(-78 x^6 - 18 x^3 - 130)}{(3 (-432 x^9 - 1449 x^6 + 810 x^3 + 3 \sqrt{3} \sqrt{-10664 x^{18} + 34200 x^{15} - 38845 x^{12} - 162020 x^9 - 241908 x^6 + 30520 x^3 - 38808} + 1072)^{1/3})}$$

# Answer
> 2 votes
SageMath can compute Taylor series. It is free software that can be downloaded for free, or it can be used online via CoCalc.

The following code will calculate Taylor series for all three eigenvalues:

```
M = matrix([[x^3, 2+x^3, 3-2*x^3], [2+x^3, 4-5*x^3, 5+3*x^3], [3-2*x^3, 5+3*x^3, x^3]])
[taylor(lam,x,0,3) for lam in M.eigenvalues()]

```

The resulting expressions don't seem too useful. In particular, although the eigenvalues are real, the equations involve complex numbers (possibly an example of casus irreducibilis).

---
Tags: reference-request
---


# Question
Title: Number of signatures of each type in a fixed column set of the Hadamard matrix
Consider a $2^n \times 2^n$ Walsh-Hadamard matrix (via Sylvester's construction). Fix a set $S \subset \[2^n\]$ of $k\leq 2^{n-1}$ columns.

Consider the rows in the $2^n \times k$ submatrix $H'$ that's obtained by dropping all columns not in $S$. Then we have $2^n$ many $k$-long row vectors. Consider the equivalence relation defined by multiplication by $-1$: $u \sim v$ iff. $u = \pm v$. There are $2^{k}/2 = 2^{k-1}$ equivalence classes this way. Is it true that the number of rows of $H'$ in each equivalence class is the same?

# Answer
The $2^n \times 2^n$ Walsh-Hadamard matrix is given explicitly by $$ M(u,v) = (-1)^{\langle u,v \rangle}, $$ where $u,v \in \\{0,1\\}^n$, and the inner product is given by $$ \langle u,v \rangle = \sum\_{i=1}^n u\_i v\_i. $$ To simplify matters, we will assume henceforth that all computations are modulo 2.

If we restrict to columns $v\_1,\ldots,v\_k$, then we see a row $\beta\_1,\ldots,\beta\_k$ whenever $$ \langle u, v\_i \rangle = \beta\_i, \quad i \in \[k\]. $$ We can think of this as a linear system in $u\_1,\ldots,u\_n \in \mathbb{F}\_2$. If the system has rank $r$, then there are either no solutions, or $2^{n-r}$ solutions.

In your case, you are identifying rows of the forms $\beta\_1,\ldots,\beta\_k$ and $\beta\_1+1,\ldots,\beta\_k+1$. A row is of one of these forms whenever $$ \langle u, v\_i + v\_k \rangle = \beta\_i, \quad i \in \[k-1\]. $$ Again, this system either has no solutions, or $2^{n-r}$ solutions, where $r$ is the rank.

What this means is that every equivalence class of rows which appears at all, appears the same number of times.

In general, not all $2^{k-1}$ will appear. Indeed, there are only $2^n$ many rows, so if $k \> n+1$ then this will certainly not be the case.

Another example is $n = 3$ and $S = \\{0,\ldots,7\\}$. Here only $4$ out of the $8$ possible equivalence classes appear, each of them appearing twice:

$$ \begin{bmatrix} 1&1&1&1\\ 1&-1&1&-1\\ 1&1&-1&-1\\ 1&-1&-1&1\\ 1&1&1&1\\ 1&-1&1&-1\\ 1&1&-1&-1\\ 1&-1&-1&1 \end{bmatrix} $$
> 2 votes

---
Tags: coding-theory, error-correcting-codes
---


# Question
Title: Given a set of partial preorders, return one not covered by any in the set
Let $S$ be a set of partial preorders over a set $U$ ($\le$ is a preorder/quasiorder if $\forall x,y,z\in U$, $x\le x$ and $x \le y \land y \le z \implies x \le z$). We say that a partial preorder *represents* a total preorder if the former is contained in the latter \[1\]. We say that a set of partial preorders *covers* a total preorder if there exists some partial preorder in the set which represents the total preorder. We say that a set of partial preorders over $U$ is *complete* if it covers all possible total preorders over $U$.

Examples ($U=\\{a,b,c\\}$):

* $a\<b$ represents $a\<b\<c$, $a\<c\<b$, $c\<a\<b$, $a\<b≤c$, etc.
* $\\{a\<b,a\<c\\}$ covers $a\<b\<c$, $a\<c\<b$, $a\<c≤b$, etc.
* $\\{a\<b,a=b,a\>b\\}$ is complete over $U$.

---

The goal is to find if there is a total preorder which is not covered by a set of partial preorders (i.e. the set is not complete), and if so, return a partial order whose total orders it represents are not covered by the set. If the set is complete return $\text{None}$.

So my question is: is there an efficient way to represent a set of preorders such that I can query the following: "give me a partial preorder such that none of the total preorders it represents are covered by $S$, or if no such preorder exists return $\text{None}$"?

Examples ($U = \\{a,b,c\\}$):

* $S = \\{a\<b\\}$, answer = $b\<a$ (or $a=b$ or $b\<c$ or $b\<c\<a$ or etc)
* $S = \\{a\<b\<c\\}$, answer = $b\<a$ (or $a\<c\<b$ or etc)
* $S = \\{a\<b,b\<a,a=b\\}$, answer = $\textit{None}$

A naive approach would be to simply enumerate all possible total preorders over $U$, and when adding a preorder to the set we mark all total preorders which contain it as `true`, and when querying return any total preorder which is yet `false`, or *None* of no such order exists. The problem is that there are this many total preorders over a $U$ with $n$ elements \[2\]!

How can I represent this set of preorders such that this query operation is faster? A trie? Something else? I searched a few books but found nothing on this subject. Really just a place to read about this would be great :)

\[1\]: "$A$ contains $B$" being equivalent to "$a\mathrel{B}b \implies x\mathrel{A}y$". Sometimes written "$B$ extends $A$". \[2\]: And also that this returns total preorders, but ideally if the set is e.g. $\\{a\<b\\}$ the algorithm would return e.g. $b\<a$, and not a total order.

# Answer
Let $\phi$ be a CNF on $n$ variables $x\_1,\ldots,x\_n$. We construct a set of partial preorders over $V = \\{a\_1,b\_1,\ldots,a\_n,b\_n\\}$ as follows:

* For any $y,z \in V$ such that $y \neq z$, the partial preorder $y = z$.
* For each $i \< n$, the four partial preorders \begin{align} a\_i &\> a\_{i+1} & b\_i &\> a\_{i+1} \\ a\_i &\> b\_{i+1} & b\_i &\> b\_{i+1} \end{align}
* We translate each clause of $\phi$ into a partial preorder; instead of defining this formally, we give two representative examples: \begin{align} x\_1 \lor x\_5 \lor x\_8 &\Longrightarrow a\_1 \< b\_1 \< a\_5 \< b\_5 \< a\_8 \< b\_8 \\ x\_2 \lor \lnot x\_4 &\Longrightarrow a\_2 \< b\_2 \< b\_4 \< a\_4 \end{align}

Which total preorders are *not* covered by this list? In view of the first two items, any such total preorder must be a total order which refines $$ (a\_1,b\_1) \< (a\_2,b\_2) \< \cdots \< (a\_n,b\_n) $$ Conversely, any such total preorder will not be covered by any of the partial preorders appearing in the first two items.

We can convert any such total preorder into a truth assignment: if $a\_i \< b\_i$ then $x\_i$ is false, and if $a\_i \> b\_i$ then $x\_i$ is true. A total preorder representing the truth assignment $\sigma$ is covered by the partial preorder corresponding to a clause $C$ iff $\sigma$ falsifies $C$. Hence the given set of partial preorders doesn't cover a total preorder iff the total preorder corresponds to a satisfying assignment of $\phi$.

This shows that the decision version of your problem (does there exist a total preorder not covered by any partial preorder in $S$) is NP-hard, and so NP-complete (it is easily shown to be in NP).
> 1 votes

---
Tags: algorithms, data-structures, order-theory
---


# Question
Title: How can you have an upper and lower bound on the worst-case complexity of an algorithm?
Yesterday I started reading "An Introduction To The Analysis of Algorithms" by Sedgewick/Flajolet. For me it was not clear what he meant with "theory of algorithms" and the "scientific approach". I googled a bit and found someone who had the same question:

Sedgewick analysis of algorithm, difference between theory of algorithm and scientific approach

Until then I thought that I had a good understanding of what worst-case complexity of an algorithm is and how it relates to $O()$ but I think that I was a bit wrong.

In the upper thread someone commented: *"(BTW O(), Ω(), Θ() as used in CLRS are about upper, lower and tight bounds all on the worst-case running time, they are not about worst-case, best-case, average-case.)"*

And then I was confused. Let split this up in worst-case analysis of a problem and worst-case analysis of a specific algorithm.

**Worst-case analysis of a problem**

When you have a problem B you want to solve, than it is absolutely understandable that you can have an upper and lower bound on the worst-case complexity since there are numerous algorithms for problem B which all can have different worst-case complexities.

In this case one could say:

The worst-case complexity of problem B lies in O(f(n)) if there is an algorithm for problem B whose worst-case runtine complexity lies in O(f(n)).

The worst-case complexity of a problem B lies in Ω(f(n)) if there can't be (yeah this has to be rigorously proved) an algorithm for the problem B whose worst case complexity lies not! in Ω(f(n)).

A good example is the proof in CLRS that the worst-case complexity of sorting(via comparing) lies in Θ(n log(n)).

So now to the worst-case complexity of an algorithm.

**Worst-case analysis of an algorithm**

Lets say we have an algorithm A for some problem and want to find out something about the worst-case complexity of A. For the upper bound I just have to find out for which problem instances the algorithm A has to do the most steps or the most "work".

So here is my problem: What should the lower bound on the worst-case complexity of an algorithm A be?

There is only one way which for me could explain that. If every algorithm yields several different implementations than one could really define a lower bound on the "best" worst-case complexity on all possible implementations of this algorithm A.

If everything what I wrote here is right for the most part than I have to say, that a lot! of books deal extremely sloppy with the relation between the asymptotic analysis and the best-,average and worst-case runtime.

# Answer
Just because an algorithm has a worst case, doesn’t mean you can find it out.

You may find a set of cases that seem quite bad to you, but can all be solved in O(n^2). But you can’t prove that *every* instance can be solved in O(n^2). So the lower bound for worst case is O(n^2). On the other hand maybe you can prove that *every* instance can be solved in O(n^3). But you don’t actually have a set of instances that take that long. The worst you have is your set of O(n^2) instances. So you have an upper bound for the worst case, which is O(n^3). The actual worst case is somewhere in between.
> 1 votes

# Answer
There is no real difference between the definition of upper and lower bounds.

You say

> For the upper bound I just have to find out for which problem instances the algorithm A has to do the most steps or the most "work"

Well, that is the same thing with the lower bound, but instead of saying "this particular worst instance of size $n$ takes at **most** $f(n)$ time to compute", you will say "this particular worst instance of size $n$ takes at **least** $g(n)$ time to compute".

Obviously, since we are talking about the **same** worst instance, the computing time will be the same, so it would be more pertinent to give a **tight** bound instead of a lower or an upper. However, it is not always as easy to find a lower bound than an upper bound (and vice versa).

For example, considering the quicksort algorithm, the worst-case occurs when the array is already sorted. Since a partition is needed, it is easy to see that the worst-case is $\Omega(n)$. Since there is at most $n$ calls to the partition function, we can say that the worst-case is $\mathcal{O}(n^2)$. However, it needs a bit more of analysis to conclude that the worst-case is $\Theta(n^2)$.
> 0 votes

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Product of polynomial with negligible function is negligible
I want to prove that for every positive polynomial $p(n)$ and any negligible function $negl(n)$ the product $negl(n)p(n)$ is also negligible.

This is what I tried so far:

$\forall n\>n\_0:negl(n)\<1/k(n),k=$any positive polynomial. $\Rightarrow p(n)negl(n)\<p(n)1/z(n) $ With $z(n)=p(n)k(n)$ $\Rightarrow p(n)negl(n)\<p(n)1/z(n)=p(n)\frac{1}{p(n)k(n)}=1/k(n)$

Question : I am not sure if I am allowed to substitute $z(n)$ with the product of $p(n)$ and $k(n)$.

# Answer
You are allowed, but you have to make sure to keep it formal.

The property of $negl$ guarantees you that $\exists n\_0 : \forall n\>n\_0: negl(n)\<\frac{1}{p(n)k(n)}$ for some polynomial $k(n)$.

Now, for any $n\>n\_0$, you know that this holds and thus $p(n)negl(n)\<p(n)\frac{1}{p(n)k(n)}=\frac{1}{k(n)}$ if $p(n)$ is positive (it will be for all $n\>n\_1$ for some $n\_1$).

Thus, for all $n\>\max\\{n\_0,n\_1\\}$, we know that $p(n)negl(n)\<\frac{1}{k(n)}$ and by definition we get that $p(n)negl(n)$ is also negligible.
> 0 votes

# Answer
We have $negl(n)$ as a negligible function, then by definition, it is smaller than the inverse of any polynomial, for all sufficiently large $n$. In particular, given any polynomial $q(n)$, $negl(n)$ is smaller than $1/(p(n) \cdot q(n))$

$$negl(n) \<1/(p(n) \cdot q(n)) $$ Now, we have

$$negl(n)p(n) \< q(n).$$

---

Limit definition also easy to use;

$f\_1(n)$ is negligible than for every polynomial $q(n)$ we have;

$$\lim\_{n \rightarrow \infty} q(n) f\_1(n) =0$$

Now, we need to show that for every $q(n)$, $negl(n)p(n)$ is negligible;

$$\lim\_{n \rightarrow \infty} q(n) negl(n)p(n)= 0$$

This is true; since $negl(n)$ is negligible implies for every polynomial;

$$\lim\_{n \rightarrow \infty} \[q(n) p(n)\] negl(n) =0,$$ where $q(n) p(n)$ is a polynomial.
> 0 votes

---
Tags: cryptography
---


title: Linear programming infeasible problems

text:
# Question
Title: Linear programming infeasible problems
A part of ORCA local avoidance collision is calculating a linear program with an incremental approach - adding the constraints one by one. If the problem is determined to be infeasible, the constraints $g\_i(x) \leq 0$ are relaxed, and we could instead solve the problem of

$\min\_{x,d} d$

$g\_i(x) -d \leq 0, \forall i$

However, I don't really understand the approach to how this is done here (which corresponds to the above mentioned problem when $x$ is two dimensional), in the function linearProgram3, line 518:

https://github.com/snape/RVO2/blob/main/src/Agent.cpp

The method there seems to directly convert the 3d problem to a 2d one, using the lines where $d$ is the same for both lines. A quick summary of my understanding of what happens:

Suppose we have three oriented lines that form a triangle and assume the "normals" (suppose they are pointing in the direction of feasibility, not outside of it) point outside and so the problem is infeasible. The algorithm would see that once it adds the constraint of $l\_3$, the problem is infeasible, and use a different approach. It does the following: For $l\_1$ and $l\_2$ we create lines $\tilde{l\_1}, \tilde{l\_2}$ where $\tilde{l\_1}$ passes through the intersection point of $l\_1$ and $l\_3$, and it bisects the angle between $l\_1$ and $l\_3$. Similarly for $l\_2$. Then,

$\min\_{x,d} d$, where $\tilde{g(l\_1)}(x) \leq 0$, $\tilde{g(l\_2)}(x) \leq 0$

is solved. In the inequality above, $\tilde{g(l\_1)}(x)$ corresponds to the constraint of $x$ being on the "correct" side of $\tilde{l\_1}$.

I can intuitively see that this approach will work, but I'm not able to justify it formally. Would someone please explain why it will work, or perhaps refer me to a text that would explain this technique?

# Answer
> 1 votes
Disclaimer: I think I've just figured this out a couple of minutes ago, so some details may be fuzzy.

The formal theory is in *Computational Geometry: Algorithms and Applications* (2008 de Berg et al.), in the Linear Programming chapter.

Just as in 2D linear programming where we know the optimal incremental solution must lie somewhere on the newly-added line segment, in 3D linear programming, we know the optimal incremental solution must lie on the newly-added plane.

RVO2 defines the constraint plane of a given ORCA line to extend into the Z-axis with a slight tilt, and the infeasible problem we're looking at is just at some slice on an XY-plane.

Now, consider the intersection of two ORCA planes, slightly tilted on the Z-axis -- their intersection is a slightly skewed line, which can be projected onto the XY-plane. This is the bisecting line that RVO2 defines.(1)

Remember that the lines of intersection are parametric; geometrically, we can view these t-parameters as the Z-axis component, i.e. where we should decide to take a new "slice" of the original system of constraints.

When we solve for LP1 in LP3, we are finding the \[tl, tr\] interval of these bisecting lines -- that is, we are finding the "bounding planes" in the Z-axis between which the optimal solution should be found.

Note that RVO2.LP3 calls LP2 with an optimal velocity pointing into the feasible region of the iterative constraint -- we know the current system is infeasible, so we want to move as directly as possible into a feasible state.

Also note that in LP1, we drop the calculation to find a point closest to the (bisecting) constraint when `dirOpt = True` -- this is because the linear problem has changed when we project the 3D problem into 2D space. We are no longer looking for minimal perturbation in 2D space, but looking for a shared feasible point among all projected constraints. We have left the minimal perturbation requirement to LP3.

I'm attempting to re-implement ORCA at the moment, at https://github.com/downflux/go-orca. Hopefully I will have more comments to the effect of this post soon.

1. N.B.: The XY-slice that LP3 feeds into LP2 is not technically aligned with the constraint plane itself, but is a 2D planar projection into 2D ambient space -- this nicely avoids attempting to deal with 3D lines and makes reasoning a bit easier.

---
Tags: linear-programming
---


# Question
Title: Getting three numbers from set that combined gives n
I have run into a little problem that I have been pondering about, and can't figure out a good solution for. Let's say that I have a set of numbers like this one:

```
[1, 2, 3, 4, 6, 9, 8, 12, 5, 10, 15, 18, 7, 14, 21, 16, 24, 27, 20, 30, 11, 22,25, 33, 36, 13, 26, 39, 28, 42, 45, 32, 48, 50]

```

I then get a number `n`, which might be "90", and then I need to output three numbers from the set that add up to n. so for n = 90 that could be 50, 39 and 1.

But do I most effeciently compute this, but also be able to compute whether such three numbers a producible?

I first thought that I could just do a naive greedy approach where I would just pick the biggest number that is at least two smaller than n, and then combine it with whatever values needed to fill in the gap.

This approach however might fail in a case where the set is `[22,7,8,10]` and `n=25` where my naive approach would pick 22 as the first number, and then not be able to use the other numbers to fill it out. It also is not able to identfy the case where it is impossible to get n with three numbers from your set, without trying all combinations.

I then thought a bit about making a dynamic programming solution. But I can't figure out whether i'm overcomplicating the problem, or how this dp solution should look.

Does someone have some good tips?

# Answer
Quite simple in O(m^2). Sort items in ascending order x1 to x-mal. Repeat for k = m, m-1, …, 3 as long as xk + x(k-1) + x(k-2) \>= n.

For each k set I=1, j=k-1. As long as i +1\< j and xi + xj +xk \> n increase i by 1. As long as j-1 \> i and xi + xj + xk \> n decrease j by 1. If the sum matches we found the solution. Repeat as long as i \< j-1, then take the next k.
> 1 votes

# Answer
Let k’ = k or k’ = k-1. Given is an array of n integers and an integer m. We can find (k+k’) array elements that add up to m in O(n^k) time and O(n^k’) space:

Create a hash table containing all sums of k’ different array elements, together with a list of those elements.

For each sum s of k different items, lookup n-s in the hash table. If found and the array elements are different we have a solution.
> 0 votes

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


# Question
Title: Lower bound Soritng with identical elements
Suppose given an array $A\[1..n\]$ that contains $k$ distinct element, why the lower bound for sorting of this instance is $\Omega(n\log k)$?

I think according the decision tree the lower bound is $$log \frac{n!}{(n-k)!}.$$ But I can't achive $\Omega(n\log k)$.

# Answer
> 2 votes
Suppose that the number of array entries with each distinct element are $j\_1, j\_2, \ldots, j\_k$. Note that $\sum\_i j\_i = n$.

Then the number of possible permutations of this array is:

$$\frac{n!}{j\_1! j\_2! \cdots j\_k!}$$

We would like to find what distribution of keys will give us the largest number of permutations.

Glossing over quite a lot of rigour, the number of permutations is maximised in this case:

$$j\_1 = \frac{n}{k}, \ldots, j\_k = \frac{n}{k}$$

The number of permutations of this array is:

$$\frac{n!}{\left(\frac{n}{k}\right)!^k}$$

And so the minimum number of comparisons required to build a decision tree is:

$$\begin{eqnarray\*}\log \frac{n!}{\left(\frac{n}{k}\right)!^k} & \approx & n \log n - k \frac{n}{k} \log \frac{n}{k} \\ & = & n \log k\end{eqnarray\*}$$

By the way, the more general result is that the minimum number of comparisons required to sort an array of $n$ elements is $nH$ where $H$ is the zero-order entropy of the key distribution.

---
Tags: algorithms
---


# Question
Title: A hash function for a 2D hash table with a scattering property?
I have an $n\times n$ matrix, and want to find a bijective function $h:\[n^2\] \to \[n\]\times \[n\]$ that can act as a hash function to map the numbers 1 through $n^2$ to row/column indices in my matrix. The additional property I'm looking for is that any two close input values should map to matrix indices that are far apart (in, say, the L1 norm). Thus, for a reasonably small set of integers $\\{k,k+1,k+2,\ldots,k+d\\} \subset \[n^2\]$, we should have that $\\{h(k), h(k+1), h(k+2), \ldots, h(k+d)\\}$ are a scattered set of matrix indices, none of which are close to each other.

I know that in the one dimensional version of this problem, where we have a length $n$ array instead of a matrix, we can get this scattering property using Fibonacci hashing: $$h(k) = \left\lfloor n \left(k\varphi \pmod{1}\right)\right\rfloor,$$

where $\varphi$ is the golden ratio, $\varphi=\tfrac{\sqrt5-1}{2}$. This is according to Knuth (The Art of Computer Programming Vol 3, 2nd edition, p. 514).

Might there be a way to extend Fibonacci hashing to a function with a similarly nice scattering property in two dimensions?

# Answer
> 2 votes
A random bijective function should satisfy this property with high probability for any specific set of indices. So, I suggest you use a random bijection on $\[n^2\]$.

If $n$ is very large, you can compute this random bijection efficiently using format-preserving encryption, or by using a Feistel network with arithmetic modulo $n$ instead of XOR (treat the cipher as working on $\[n\]^2$; then each block has a left half and a right half; and do at least 6 rounds of Feistel encryption using a pseudorandom function as the F function).

Another option is to construct a bijective function $\[n\]^2 \to \[n\]^2$ by separately applying Fibonacci hashing (or some similar one-dimensional solution) separately to the row index and the column index. That ensures that two close inputs will lead to two outputs that are distant. It won't be optimal but it might be good enough, if you prioritize guarantees and simplicity.

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


# Question
Title: Partition a set of n integers into m subsets in a way that the maximum subset sum is minimized
Let's say we have a set of `n` integers. I'm trying to find a way to partition this set into `m` subsets (empty subsets are not allowed), so that the maximum subset-sum gets minimized. for example, let's say we have the following set and `m = 2`:

`{11, 5, 11, 5, 10}`

the optimal partitioning will be as follows:

`{5, 5, 11}, {10, 11}`

where the maximum of subset-sums is 21 (no other partition reaches a smaller maximum subset-sum).

The brute force approach will generate all such partitions and find the minimum max sum among them. But is there a better approach to solve this? I was thinking of a backtracking algorithm but I have no idea where to start. I'm only interested in the minimum maximum sum among all partitions and not the partition itself.

# Answer
The problem can be shown to be weakly NP-hard by noticing that it is a generalization of *partition*. In particular, when $m=2$ the input set of integers is a yes instance of *partition* if and only if the measure of an optimal solution of your problem equals half the sum of the integers.

The problem can also be shown to be strongly NP-hard by noticing that it is a generalization of *3-partition* in the special case in which all the integers in the input set $S$ are positive and strictly between $\frac{1}{4}\sum\_{s \in S} s$ and $\frac{1}{2}\sum\_{s \in S} s$. In particular, we can assume that $|S|$ is a multiple of $3$. When $m=|S|/3$ the optimal solution to your problem has measure $\frac{3}{|S|}\sum\_{s \in S} s$ if and only if the *3-partition* instance is a yes instance.
> 2 votes

---
Tags: algorithms, sets, partitions, backtracking
---


# Question
Title: What is the sensitivity of gradient clipping in Differentially Private SGD?
As far as I understand, the Gaussian Mechanism uses the sensitivity of the input function to determine the right amount of noise. In DP-SGD, said input function is taking the gradient and clipping it to some norm *C*. Then the Gaussian Mechanism is used with *C* as the noise-determining parameter. this should mean the sensitivity of gradient clipping is *C*, i.e. the maximum distance that two clipped gradients obtained from neighboring data sets can have is *C*. But the gradient computation can yield arbitrarily different vectors from neighboring inputs, and the maximum (L2-)distance two arbitrary vectors of (L2-)norm 1 can have is 2! What am I not seeing?

# Answer
> 1 votes
The notion of *sensitivity* is relative to the definition of *adjacency*. Sensitivity is the maximum of the absolute distance $|f(d) − f(d)|$ where $d$ and $d'$ are *adjacent* inputs. Adjacency may be defined in slightly different ways. In Abadi et al. 2016 it is defined as:

> we say that two of these sets are adjacent if they differ in a single entry, that is, if one image-label pair is present in one set and absent in the other

It is also the definition used in Dwork and Roth 2014 (Definition 2.3).

But it is true that some authors define adjacency of $D$ and $D'$ by the fact it is sufficient to change one observation in $D$ to get $D'$. Which can be confusing.

In the case of DP-SGD (Abadi et al. 2016), this means that among all possible observations in your universe you add one (one gradient appears) or remove one (one gradient disappears), so 2 outputs from adjacent datasets will differ by $C$ at most (not $2C$).

---
Tags: differential-privacy
---


# Question
Title: Is this language $X = \{x:xxx\in L\}$ regular?
I came across this question in my Theory of Computation class recently:

> Consider a regular language $L$, and define $X = \\{x:xxx\in L\\}$. Is this language regular?

I believe that it is regular, and that the procedure required to construct an NFA for it is not particularly different from constructing one for $W=\\{x:xx\in L\\}$ (at the very least, the one I will now attempt to do).

---

This is mostly a hunch, but I was thinking something like this:

Consider an NFA $A = (Q, \Sigma, \delta, s, F)$ that accepts $L$. Let's try to see what kind of words will pass through $A$ twice before being accepted. It's quite easy to see that the ones for which this works are those words which follow a path

$$s\rightarrow^{x}q\rightarrow^x f$$

Where $s$ is the start state, $f$ is an accept state and $q$ is some state in the middle (which we don't know about). Just to keep things simple, we make sure that there is only one start state and final state; we can do that, in any case, by adding $\epsilon$ arrows.

Pick some $q\in Q$. Doesn't matter which.

Now let's form a new NFA $A'$ whose states are $Q\times Q$, and put $(s,q)$ as the only start state, and $(q,f)$ as the only accept state. The transition function will be

$$\delta'((a,b),x) = (\delta(a,x),\delta(b,x))$$

The only elements that will be accepted here are those for which there's a run from $s\rightarrow q$ and $q\rightarrow f$.

Now we have no way of knowing whether the 'midway point' of $xx$ while going through $A$ is indeed the state $q$. However, because of nondeterminism, we don't need to guess - we can make one copy of this for each state $q$. Then my hypothesis is that the accepted words of the union of all these NFAs are those which are doubly accepted by $A$.

---

Caveats: I'm quite certain that my constructed NFA will accept $W$, but my problem is that I believe that it will likely accept other inputs as well. Secondly, I'm sure that this solution generalizes to the original problem as well, but I'm having a hard time giving an explicit construction.

1. Does this work?
2. Does this also give a construction for $X$? If so, what is it explicitly?

# Answer
> 4 votes
1. Yes. What you are constructing is the product automaton recognizing the language $L\_{s,q}\cap L\_{q,f}$, where for $q, q' \in Q$, $L\_{q,q'}$ is the language of words leading from state $q$ to state $q'$. Formally: $$L\_{q,q'} = \\{u\in \Sigma^\*\mid q'\in \delta^\*(q, u)\\}$$ It is well known that $L\_{q,q'}$ is a regular language (just consider the initial state $q$ and the final state $q'$ with the same transitions in $A$).
2. The same idea can be used: $X = \bigcup\limits\_{q,q'\in Q} L\_{s,q}\cap L\_{q,q'}\cap L\_{q',f}$.

---
Tags: automata, nondeterminism
---


title: Computable Functions

text:
# Question
Title: Computable Functions
I'm learning about computable functions. Our definition for computable function is as follows:

> Informally, a computable function is a function f : A → B such that there is a mechanical procedure for computing the result f(a) ∈ B for every a ∈ A.

they go on to give the following non-example:

> A function that takes an input p (which I assume to be a program), and checks if p is a syntactically valid Python program without any user interaction that terminates and returns 1 if this is true, 0 otherwise.

I was just trying to understand why this is not computable. I know when I write a program with incorrect syntax that I get an error when I try to run it, so I am assuming that it is possible to check whether a program is syntactically correct, but I have a hunch that the terminating part has to do with the halting problem. Is this simply just an obscured halting problem?

# Answer
> 1 votes
Yes, "that terminates" is the halting problem, not really in disguise but also not pointed out as problematic.

# Answer
> -3 votes
If $f:\Sigma^\* \to \Sigma^\*$ is function, and $\exists$ a Turing machine which on the input $w\in\Sigma^\*$ writes $f(w)$, $\forall w\in\Sigma^\*$, then we call $f$ as computable function. What is a computable function?

To generalize the above notion of **computable function** as much as possible anything that applies an algorithm to an input deriving an output is a computable function even when applied by the human being "computers" of the film: "Hidden Figures".

> A function that takes an input p (which I assume to be a program), and checks if p is a syntactically valid Python program without any user interaction that terminates and returns 1 if this is true, 0 otherwise.

The above function is computable for some inputs. Within the terms of the art of computer science a function is not computable unless it derives an output for all inputs in its domain.

**The above function can be transformed into an instance of the halting problem, thus is construed as not computable in this case.**

---
Tags: computability
---


# Question
Title: What is the difference between these 2 dfas for binary strings ending with 00?
The first one is from unreputed youtuber whereas second one is from reputed university called adiuni course of theory of computation.

Now I know what that second figure means, it means it also accepts $\in$ as initial state=final state, but

1. how I don't know that. This dfa should accept all binary divisble by 4. But how is nothing(it is not zero mind that) divisible by 4?
2. Why I don't know that. I am making a dfa for binary numbers divisible by 4 and adiuni professor told that binary numbers that end with 00 are divisble by 4. So I googled about dfa ending with 00 and got this. I am personally more comfortable at first figure as it is more inituitive to me.

How is $\in$ divisible by 4? What does that even mean?

# Answer
> 1 votes
The first DFA is correct, and the second is incorrect. When we say a string *ends in 00* we imply that it must have at least two characters. So, it can't be the empty string, and it also can't be the single 0 string.

> This dfa should accept all binary divisble by 4. But how is nothing(it is not zero mind that) divisible by 4?

I agree, and this is a good way of thinking about it. However, note that we aren't writing a DFA for the set of binary numbers divisible by 4 (that would include 0), but rather for the set of binary sequences which end in two zeros. So it is slightly different.

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


# Question
Title: epsilon-NFA to DFA conversion - What will be the final states and do we need to create empty state in DFA?
Source of this question and problem:

https://www.javatpoint.com/automata-conversion-from-nfa-with-null-to-dfa

This is the question:

So in this figure there are my 1 confusion-:

1. Don't we need a empty set like this-:

Source: https://www.youtube.com/watch?v=dmvJp5EgOek&list=PLENQMW\_c1dimRCKF3bjUqHaH8dvJkapSw&index=48

Since this is DFA we need to show all transitions, isn't it?

# Answer
> 1 votes
You are correct! As you say, in a DFA you need to show all transitions. So, you have to include the empty set state (sometimes called a "sink" state or "dead" state).

Actually this is just the short answer -- the long answer is that *some* authors have defined DFAs so that they don't need to include all transitions, but that definition is not common anymore in modern textbooks. So, the source of the first DFA you showed is probably using that (older) definition.

---
Tags: finite-automata, nondeterminism
---


# Question
Title: How are pointers interpreted differently to variables in a control flow graph (CFG)?
I have been working with control flow graphs and believe I understand how they function when describing dependencies between variables. For example, given the operations:

```
a = b + c;
b = c + d;
c = d + e;

```

The control flow graph would appear:

```
a = b + c; ==> b = c + d; ==> c = d + e;

```

Since there is a write after read dependency involving b and c in the second and third operations respectively.

How would this change if instead of variables pointers were represented in the graph?

```
*a = *b + *c;
*b = *c + *d;
*c = *d + *e;

```

# Answer
> 1 votes
Great question! Typically, pointer dereferences are treated no differently than any other operation, like addition and multiplication. So the control flow graph would be:

```
*a = *b + *c; ==> *b = *c + *d; ==> *c = *d + *e;

```

Sometimes, when building a CFG it is useful to break up a complex expression into its individual steps. In that case, we would get something like this:

```
b' = *b
==> c' = *c
==> a' = b' + c'
==> *a = a'
==> c' = *c
==> d' = *d
==> b' = c' + d'
==> *b = b'
==> d' = *d
==> e' = *e
==> *c = c'

```

As an interesting side note, it may seem like this last CFG can be simplified: we have `c' = *c` twice, and `*c` does not change in the meantime, so we should remove the second `c' = *c` line, right? Actually no, because it is possible that the operation `*a = a'` modifies `*c`, in the case that `a` and `c` are pointers to the same location in memory.

---
Tags: formal-methods, software-verification, c++
---


title: Lower bound for shortest problem

text:
# Question
Title: Lower bound for shortest problem
Suppose given a weighted directed graph $G=(V,E)$. We want, for each $v\in V$ find a path $P$ from other vertices to $v$ such that weight of $P$ is minimzed.

I can solve this by running Johnson's algorithm on $G$ and doing a linear traverse of matrix to find out for each $v$ minimum weight shortest path from other to $v$ in $O(n^3)$. But my problem is are there any lower bound that show us we can't do better in $\Omega(n^3)$?

# Answer
> 1 votes
If you want a simple path: You cannot solve this in $O(n^3)$ time (unless $P=NP$).

If you allow the path to be non-simple: No. Read about all-pairs shortest paths.

---
Tags: algorithms
---


# Question
Title: What happens to a Turing Machine if it enters final state but the input is not yet read completely?
In the image, the language of the TM is defined on (a, b, c, d) and there is no transition on final state, but strings consisting of d are also part of the language.

In all TM problems I have seen until now, all transitions not defined are considered to go to the rejecting state (qrej.).

So in this TM also any transition on {a, b, c or d} from the final state should go to rejecting state and L(M) should be the string `{abc}`. But the solution states that the machine accepts the regular language `abc(a+b+c+d)*`.

According to me the answer should be options (a) and (c) but the answer is (a) and (d). Please explain how this acceptance of TM works and also how transition of final state are considered when it is not defined explicitly.

# Answer
When the Turing Machine enters an accepting state, it immediately halts and accepts. This is somewhat contrasting to many other automata that have to exhaust their input strings; the TM doesn't have to. Therefore the TM accepts all strings beginning with $abc$, while $G$ generates all strings beginning with $abc$ containing no $d$.
> 2 votes

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


# Question
Title: Python: Assigning values to 2D-array elements
I created a 2x2 2D-array of 0's as follows:

```
sizes=[[0]*2]*2

sizes
[[0, 0], [0, 0]]

```

I want to change the second element of the first row to 1. I do this as follows:

```
sizes[0][1]=1

```

Unfortunately, the second element of the *second* row also changes to 1.

```
sizes
[[0, 1], [0, 1]]

```

Why does this happen?

# Answer
> 1 votes
This happens because of how you created the array.

I won't get into too much detail, but if you are familiar with the concept of "pointers", then an array is just a pointer - copying it will copy the pointer, so changing at one "clone" will change the other. Here you have copied your array twice.

To fix this, consider writing it in this form instead: `[[0, 0] for _ in range(2)]` which will create two brand-new lists and combine them - instead of copying the same one twice.

---
Tags: python
---