# Question
Title: How to define the languages of the implicit set system problems?
There are implicit versions of some set system problems or matroid problems.

A set system is a pair $(U, \mathcal{F})$, where $U$ is a universe of size $n$ and $\mathcal{F}$ is a collection of susbets of $U$. $\mathcal{F}$ may satisfy some properties (e.g. Matroid). We define $\Phi$ is a polynomial-time oralce which determines whether $S \subseteq \mathcal{F}$ given the universe $U$ and a subset $S \subseteq U$.

We formally define the implicit set system problems: Given a universe $U$, the goal is to determine whether there exists a set $X$ satisfying the property $P$.

For example of the property $P$.

1. The size of $X \in \mathcal{F}$ at least $k$.
2. $X$ hits all the elements $S \in \mathcal{F}$.

So the size of the instance is $|U| = n$.

What is the language of the implicit problem? It seems that the input contains an oracle. How can I know the complexity of this kind of problems.

I think the size of this problem can be smaller (that is $O(\log n)$), because the input can just be a natural number, right?

# Answer
> 1 votes
There are different notions of complexity used for various computational problems, not all tasks fit naturally to the standard model of decision/search problems. The "classic" analysis of complexity talks about how many resources we need to compute $f(x)$ given $x$, but this misses a lot of interesting questions we can ask. Consider communication complexity, where we want to compute $f(x,y)$ where one sides holds $x$ and the other holds $y$, while minimizing the number of bits exchanged between the parties. This requires a new definition of complexity. Same goes for query complexity, where we are given a black box access to some function $f$ and we want to know how many evaluations of $f$ are required to determine if it satisfies some property $P$.

The seemingly natural way (this of course depends on the context) to determine hardness of set system problems would be in terms of standard complexity and the number of queries to the membership oracle. As the set system is given, I don't want to involve hardness of deciding whether some set is in the system, so I'll only charge one operation for querying the membership oracle. This allows, in a sense, to isolate the hardness of evaluating the property from the hardness of the system's description.

---
Tags: formal-languages, oracles
---


title: Proving $(a + ab)^*a = a(a + ba)^*$

text:
# Question
Title: Proving $(a + ab)^*a = a(a + ba)^*$
Need to prove $(a + ab)^\*a = a(a + ba)^\*$ by using regular algebra.

Concatenation does not commute. So repeated use of commutativity will fail. I am getting confused about which identity I should use to prove this. What I can interpret is that I just need to change the side of $a$ but the $^\*$ must be kept outside. But I am not able to do this.

Any help will be appreciated.

# Answer
> 4 votes
This is an instance of the identity $(xy)^\*x = x(yx)^\*$ with $x = a$ and $y = 1 + b$: $$ (a + ab)^\* a = (a(1+b))^\*a = a((1+b)a)^\* = a(a +ba)^\* $$

# Answer
> 1 votes
Write:

$\begin{align\*} (a + a b) a &= a a + a b a \\ &= a (a + b a) \end{align\*}$

Thus:

$\begin{align\*} (a + a b)^n a &= (a + a b)^{n - 1} a (a + b a) \\ &\\;\\;\vdots \\ &= a (a + b a)^n \end{align\*}$

Note this is true whatever $n$ may be. So:

$\begin{align\*} (a + a b)^\* a &= \left( \bigcup\_{n \ge 0} (a + a b)^n \right) a \\ &= \bigcup\_{n \ge 0} (a + a b)^n a \\ &= \bigcup\_{n \ge 0} a (a + b a)^n \\ &= a \bigcup\_{n \ge 0} (a + b a)^n \\ &= a (a + b a)^\* \end{align\*}$

(Not very elegant...)

# Answer
> 0 votes
You should write $(a+ab)^\*a$ as $\bigcup\limits\_{n\geqslant 0}(a+ab)^na$ and try to factorize $(a+ab)^na$ differently from here.

---
Tags: regular-expressions
---


# Question
Title: Are the following assertions true if P != NP?
We consider the NP-complete $CLIQUE$ problem. Let furthermore $MST^\*$ be the minimum spanning tree problem. Assume that $P \ne NP$ and explain whether the following assertions hold:

1. $MST^\* \le\_{P} CLIQUE$
2. $CLIQUE \le\_{P} MST^\*$

**Definitions**:
$\le\_{P}$ ... Karp reduction
$MST^\*$ ... Given is a weighted graph $G$ and a number $k$. Does $G$ have a spanning tree with the total cost $\le k$? (problem lies in P)
$CLIQUE$ ... A clique in a graph is a subset $S$ of the nodes such that all nodes in $S$ are connected in pairs. In the $CLIQUE$ problem we are given a graph and a number $k$ as input and must decide whether there is a clique with $\vert S \vert \le k$. (problem is NP-complete)

**Question:** Can anyone give me a hint on how to solve this?

# Answer
1. Take a look at the definition of NP-complete, it might help.
2. How fast can we compute $MST^\*$? Try to use this in conjunction with the assumption you made.
> 0 votes

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


# Question
Title: Assume P != NP, are these assertions valid?
Assume $P \ne NP$, and $A$ is a problem in $P$ and $B$ is a problem which is $NP-complete$. Are the following assertions valid?

1. $A \le\_{P} B$
2. $B \le\_{P} A$

**My approach**:

* $B \le\_{P} A$ isn't valid, because if $B$ is reducible in poly-time to $A$, so $B$ has to be also in $P$. But thats not possible because $P \ne NP$.
* $A \le\_{P} B$. Is it possible to reduce a problem in $P$ to a problem in $NP$ ? If it is, then the assertion is valid.

**Question:** Is my approch correct or am I missing some important point?

# Answer
Regarding 1: yes, since $B$ is $\mathsf{NP}$-complete it must be $\mathsf{NP}$-hard, i.e., for every problem $C$ in $\mathsf{NP}$ we have $C \le\_P B$. Since $A \in \mathsf{P} \subseteq \mathsf{NP}$, we can pick $C=A$.

This is true regardless of whether $\mathsf{P}=\mathsf{NP}$. Notice, however, that we are using the fact that $B$ is $\mathsf{NP}$-complete. In general it is not possible to reduce an arbitrary problem in $\mathsf{P}$ to an arbitrary problem in $\mathsf{NP}$.

Regarding 2: no. Here your reasoning is correct, $B \le\_p A$ would imply $\mathsf{P} = \mathsf{NP}$.
> 1 votes

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


# Question
Title: How to demonstrate unambiguous CFG and CNF?
I have to show that if G is an unambiguous CFG, the transformed grammar G' in CNF is also unambiguous. But couldn't come up with something concrete. I could only visualize the case where the grammar G is ambiguous, not necessarily G' will be.

# Answer
One way to approach this question is to prove the equivalent statement:

$$G^\prime \text{ ambiguous} \implies G \text{ ambiguous}$$

This statement is called the contrapositive of the original statement.

Now you can use the definition of ambiguity of a Grammar (which happens to be in CNF in your case) and work your way to proving the ambiguity of the original grammar. What's nice about proving the contrapositive is that you can focus on a single counterexample: a member of the language that has at least two different derivations in $G\prime$ and try to show that it has at least two different derivations in $G$ instead of trying to show that for all member of $G$ it must be true that there is a unique derivation in both $G$ and $G\prime$/
> 1 votes

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


title: Accounting method - dynamic array

text:
# Question
Title: Accounting method - dynamic array
I want to compute the amortize time of a type of dynamic array (inserting such that if i have no place to insert i am multipling the array by (1+a) (a is between 0 to 1). I need to compute the time with the accounting method. The answer is that i need for each insertion a 2 + $1/a$ coins. I can see why the answer is right, problem is that i don't understand how i was supposed to get to the answer myself so what i am asking for is the way to the solution and the way to approach the question.

# Answer
> 2 votes
The accounting method relies on two arguments. The first is that in any sequence of $n$ operations, you never run out of coins. That is, however you choose to distribute the coins and pay for the operations, no sequence of operation will lead your scheme to a negative balance. The question remains of what this has to do with running time. Now the second argument comes into play, you want the running time to be bounded by the number of chips spent (without this claim, we have nothing relating the amortized running time with our chips distribution scheme). We can conclude that if you have devised a scheme satisfying those two properties, in which $C$ is the maximal amount of chips drawn in a single operation (where the maximum is taken over different types of operations), then the amortized running time is bounded by $C$.

This sheds some light on how to choose the number of chips per operation. I want to draw, for some element $x$, a number of coins that will suffice for all future operations involving $x$ (think of the insertion of $x$ as an element being born, and you attempt to compute how much money you will need from childbirth all the way to college). The tricky thing is that $x$ can be involved in an unbounded number of operations. Each extension of the array requires moving $x$, so I don't know how to determine the number of coins that will suffice to put $x$ through its entire existence. We can overcome this by having each element pay for his part in the first extension after its insertion.

Suppose that you just extended your array from size $k$ to size $\lceil(1+\alpha)k\rceil$. You would need to add an additional $\lceil(1+\alpha)k\rceil - k$ elements before the next extension, which will require $\lceil(1+\alpha)k\rceil$ operations. Let us try to construct our distribution scheme in such a way that only those new elements would pay for the next extension. Let $C$ be the number of coins requested for each insertion which allows this. It suffices that $C\cdot \left(\lceil(1+\alpha)k\rceil - k\right)\ge \lceil(1+\alpha)k\rceil$, or equivalently $C\ge\frac{\lceil(1+\alpha)k\rceil}{\lceil(1+\alpha)k\rceil - k}$. Since $\frac{\lceil(1+\alpha)k\rceil}{\lceil(1+\alpha)k\rceil - k}\le 1+\frac{k}{\lceil(1+\alpha)k\rceil - k}\le 1+\frac{k}{(1+\alpha)k-k}=1+\frac{1}{\alpha}$, it suffices to ask for $1+\frac{1}{\alpha}$ coins. Recalling that you also need a coin for the insertion itself yields the desired result of $2+\alpha^{-1}$.

---
Tags: complexity-theory, data-structures, amortized-analysis
---


title: Branch Prediction question

text:
# Question
Title: Branch Prediction question
My question relates to a video I watched on YouTube.

The pipeline is a 5-stage pipeline which include fetch, decode, ALU, Mem (data), and Write.

It mentions that nothing is fetched until we're sure what to fetch. How can that be though? Won't you need to fetch and decode an instruction first to know what to fetch?

He mentions that the ADDI instruction gets fetched, but then goes in a bubble since it's not a branch. I really do not understand what is happening here and why the CPI for each instruction are ADDI=2, ADD=2, and BNEZ=3.

Can any explain to me what's going on here? Maybe a table with cycle iteration would be helpful.

Here's the video link: Branch Prediction question

# Answer
I figured out what he means: fetch the instruction and decode it, but do not fetch the next instruction until you've determined whether it's a branch or non-branch instruction.

For the non-branch instructions, it will fetch next instruction after the decode stage. But for the branch instruction, it will require an extra cycle to determine it should stay in the loop or not.

The CPI does add up if I do follow through with what I've mentioned. I've added a picture to give you a better picture of what's happening at each cycle.
> 2 votes

# Answer
I think the answer posted is correct in the demonstration of the 7 cycles. On the other hand the processor with the perfect predictor should consume 5 cycles not 3. The reason for that is the dependency between I1 (Add r1,r1,-1) and I3 (bnez r1,loop). This dependency will halt I3 at the fectch stage until I1 passes the write-back stage (final or 5th stage in the pipeline) which causes 2 stale cycles so the speedup should be 7/5 = 1.4 here is a demonstration for my answer using a cycle by cycle pipeline
> 0 votes

---
Tags: cpu-pipelines
---


title: Proving $S=SL\implies S=\emptyset$

text:
# Question
Title: Proving $S=SL\implies S=\emptyset$
> Let $L\subseteq \Sigma^\*$ such that $\\{\epsilon\\}\not\in L$. Then for any $S\subseteq \Sigma^\*, S=SL\implies S=\emptyset$.

So we suppose $S=SL$ and $S\ne\emptyset$. Then $\exists w\in S$ such that $0\le|w|\le |v|$ for some $v\in S$. Now $|w|\ne 0$, since $|w|=0\implies\\{\epsilon\\}=w\in S=SL\implies \\{\epsilon\\}=xy$ for some $x\in S$ and $y\in L\implies x=y=\\{\epsilon\\}\in L$ which contradicts that $\\{\epsilon\\}\not\in L$.
Thus $w\ne\\{\epsilon\\}$ and $\\{\epsilon\\}\not\in S$. So we have
\begin{align} w \in S &\implies w\in SL\\ &\implies w=sl\\;\text{for some}\\; s\in S\\; \text{and}\\; l\in L\\ &\implies |w|=|s|+|l| \end{align}
Here I'm stuck now. I think if I can show that $|l|=0$, then we can arrive at a contradiction.

Your help is highly appreciated.

# Answer
You should consider (one of) the word $w$ of minimal length in $S$, and show that for this word in particular, you can reach the conclusion that $|l| = 0$.
> 1 votes

---
Tags: regular-languages, strings
---


# Question
Title: What happens if there is context switch while executing system call?
Suppose a process does system call, hence it goes to kernel mode, the registers are saved. Now the system call will be running in process' allocated kernel stack.

1. Can there be a context switch when a system call is processed?
2. Is really the system call allocated process' kernel stack?
3. If context switch is possible, this means kernel has set the timer for this. Right?
4. Are system calls part of job scheduling(separately) or this are include in job scheduling of process?

I am really messed up with this kernel stack.

# Answer
If the kernel decides to do a context switch, it's in response to some event which caused the processor to enter kernel mode. This can be either a system call or an interrupt (which can be a timer interrupt or some other interrupts).

Whether the kernel is processing an interrupt or a system call, there are good and bad times to do a context switch. The kernel does what it wants to do, and then at the end of the processing it decides which user thread to schedule next. If it decides to schedule a thread which wasn't the last scheduled thread, it then does a context switch.

During critical parts of the processing, the kernel may disable interrupts. If an interrupt happens while the kernel is already active and doesn't have interrupts disabled, what usually happens is that the kernel does what needs to be done immediately (for example, read data from a peripheral), and adds an element to a queue to remember what needs to be done later. In Linux, these are called the “top half” and “bottom half” of interrupt processing; I don't think there's a standard term even though the concept is common. For example, if a network interrupt is triggered while the kernel in the middle of communicating with a disk, the kernel reads the network packet and stores it into a queue; then, when the disk I/O is finished (or can be paused), the kernel processes the network packet, and at this point it may decide to schedule a task that has received some input from the network.

In case there's any doubt, a timer is not required for a context switch. A context switch can happen any time a system call is in progress. The connection between timers and context switches is that if user code never makes any system call, and there is no system event (user input, networking, etc.) that causes an interrupt, the only way a context switch can happen is if a timer interrupt causes the kernel to wake up. And there are operating systems that only have non-preemptive multitasking; such kernels don't set a timer interrupt, and only do a context switch during a system call.
> 3 votes

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


title: Pushdown automaton with binary stack

text:
# Question
Title: Pushdown automaton with binary stack
I have a problem where I'm asked to prove that if P is a pushdown automaton, then there exists another pushdown automaton P' with only two symbols in its stack alphabet that accepts the same language as P. I've tried to codify the stack alphabet of P in binary, using the same ammount of symbols for each representation so I know where the codification of one symbol starts and ends, but I don't know how to simulate P with P'.

# Answer
You're on a good path! Keep at it. Remember that a pushdown can have a finite-state control, and you can remember up to a finite amount of information in the finite-state control. Also, it can have $\epsilon$-transitions (so the read head doesn't consume any of the input). Those might be helpful.
> 2 votes

---
Tags: automata, context-free, pushdown-automata
---


# Question
Title: NP completeness of deciding whether a set of examples, consisting of strings and states, has a corresponding DFA?
I'm working on a textbook problem, 7.36 in Sipser 3rd edition. It claims that if we are given an integer $N$ and set of pairs $(s\_i, q\_i)$, where $s\_i$ are binary strings and $q\_i$ are states (we are unconcerned here with whether the states are accepting), then the problem of "deciding whether there exists some $N$-state DFA for which each $s\_i$ causes that DFA to end up in state $q\_i$" is NP-complete.

A much more well-known result by Gold (1978) is the same as the above, except with the alphabet being arbitrary instead of binary, and the examples being in the form $(s\_i, \mathrm{accept})$ and $(s\_j, \mathrm{reject})$ instead of having the state $q\_i$. That result is discussed in some other threads, like this, this, and this.

If I naively try to reduce from the Gold problem to the Sipser problem, I would try to replace all "accept" with a single "terminal" accept state, and same for reject, but that fails because if you wanted only a single terminal accept state to handle all accepted strings, you would need to have an **N**FA with epsilon transitions; if you try to convert that back to DFA, the single terminal states may split up into multiple, which would invalidate your examples.

I suspect Myhill-Nerode may be useful here, since the DFA states correspond to the equivalence classes of strings. I think you can rephrase the Sipser result as deciding whether some given set of strings can be partitioned into some given set of Myhill-Nerode equivalence classes.

I searched through the literature, but was not able to find the Sipser result anywhere. What is another decision problem that we can use as a polynomial-time reduction here? Alternatively, is this result derived or discussed anywhere else?

# Answer
> 0 votes
(Note: the below proof may have some issues raised in the comments. I am in the processing of addressing the issues.)

The following "end-character" method was suggested in the comment above, as well as private communication with some others. Any mistakes are my own.

We construct a polynomial-time reduction from the Gold problem (arbitrary alphabet with "accept" or "reject" in the examples) to the Sipser problem (binary alphabet with states in the examples). Since the Gold problem is NP-complete, it then follows that the Sipser problem is also NP-complete.

The Gold decision problem gives us an integer $n$ and pairs $(s\_1, x\_1), (s\_2, x\_2) \ldots (s\_k, x\_k)$ \[where each $s\_i$ is a string in some arbitrary alphabet $\Sigma$, and each $x\_i$ is either "accept" or "reject"\] and asks if there exists an $n$-state DFA $G$ that for each $i$, accepts or rejects $s\_i$ based on the value of $x\_i$.

We claim that the Gold input has such an $n$-state DFA if and only if the examples $(t\_1, y\_1) \ldots (t\_k, y\_k)$ has a corresponding $f(n)$-state DFA $H^\prime$ in the Sipser problem, where:

* $t\_i$ is some binary encoding of $s\_i$ plus a common suffix $Z$ that is unambiguously different from any of the other encoded characters in $\Sigma$.
* $y\_i = q\_{x\_i}$; that is, either $q\_\mathrm{accept}$ or $q\_\mathrm{reject}$
* $f(n)$ is a function that be computed and written down in time polynomial in $\log n$.

First, suppose the Gold DFA $G$ exists. Then, there exists a size $O(n \log \lvert \Sigma \rvert)$ DFA $H$ that recognizes the homomorphism ($\Sigma$ encoded into binary) of the language of $G$: simply take every transition in $G$ and split up into transitions corresponding to the binary encoding. Since $G$ may have more than one accept state, so does $H$ (which has the same number of accept states as $G$). Hence, modify $H$ by taking every accept state and inserting transitions corresponding to the "end of string" bitstring $Z$ to a single newly-created $q\_\mathrm{accept}$, and inserting the same transitions from non-accept states in $H$ to a single newly-created $q\_\mathrm{reject}$. The resulting DFA $H^\prime$ clearly fits the examples $(t\_i, y\_i)$, and its number of states is bounded above by some easily computed $f(n)$.

Now for the other direction, suppose some $f(n)$-state DFA $H^\prime$ exists which fits the examples $(t\_i, y\_i)$. Then, since by construction every $t\_i$ has the "end of string" bitstring $Z$ as a suffix, we simply take $H^\prime$ and for every state $q$ for which reading $Z$ would take $H^\prime$ to $q\_\mathrm{accept}$, we make $q$ an accept state. Then, we remove $q\_\mathrm{accept}$ and $q\_\mathrm{reject}$, and we have the DFA $H$. We can then construct a DFA $G$ which recognizes the same language with characters decoded from binary to alphabet $\Sigma$. This construction can easily be done by starting with the start state in $G$, trying out every encoded character in $\Sigma$ and writing down the transitions in $G$, and recursively repeating. Since $H$ is finite, this procedure is guaranteed to terminate in polynomial time.

(Note: the above solution simply quotes the Gold result, the proof of which is pretty involved. There's probably a simpler method that directly proves the Sipser result instead of using Gold as an intermediary.)

---
Tags: regular-languages, finite-automata, np-complete, polynomial-time-reductions
---


# Question
Title: How to find long trails in a multidigraph
I have a directed multigraph (a multigraph is a graph that can have more than one edge between any two nodes). In Wikipedia's terminology, this is a **directed multigraph (edges without own identity)**. I want to find its longest directed trails (a directed trail is a directed walk in which all edges are distinct). I.e., I'm looking for long walks with repeated nodes, but distinct edges.

Note that this is an NP-hard problem. Otherwise, I would have asked for the longest trails, not merely long trails.

My graph has no weights and it is weakly connected (that is, if each edge were converted to an undirected edge, that undirected graph would be connected).

I define walk/trail/path length as the number of edges in the walk.

My current program is based on traversing the graph in a DFS-like manner. If allowed to run for, e.g., half an hour, it produces trails of less than satisfactory length, and I know that longer trails should be possible in that time budget.

Note that this problem is quite similar to the problem of **finding the longest path** of a directed graph, but with each edge having a *max allowed visits number* associated with it, equal to the cardinality of the corresponding edge set in the multidigraph.

In fact, it's possible to transform my problem to the **longest path** problem by producing the line graph of my graph and then finding its longest paths. However, I'm hoping for a smarter, more efficient solution.

The reason I'm mentioning the *digraph longest path problem* is that there are certain smart solutions to that problem, but they don't seem to translate to my *multidigraph longest trail problem*, sadly. In particular, I'm thinking of Miguel Raggi's Arxiv paper, *finding long simple paths in a weighted digraph using pseudo-topological orderings*. Those and other solutions are based on finding the longest path of a DAG subgraph (or, equivalently, some feedback arc set), which seems inapplicable to my problem (unless I do the mentioned line graph transformation), but I'd be happy for somebody here to prove me wrong.

## What am I looking for, then?

Either of these two:

1. some method of finding long trails in my multidigraph, smarter than the naive approach.
2. some method of finding long paths in my multidigraph's line graph; but it should be more efficient than just looking for an arbitrary digraph's longest paths, i.e., it should take into account the fact that the graph that is being searched through is a line graph.

## Some characteristics of my graph

It's got around 500 nodes and around 20000 edges. If the multiple edges are accounted for, the graph's got around 160000 edges.

### Some characteristics of my graph's condensation

I don't know if the info on the condensation is relevant, but it might be. See the Wikipedia page for strongly connected components for definitions and examples of graph condensations.

There are less than 200 strongly connected components (equivalently, the condensation has less than 200 nodes), and the condensation's got around 220 edges. One of the SCCs consists of more than 300 original nodes, while every other SCC has only a single original node.

### Info about node in-degree and out-degree over all nodes

This too is of dubious importance, but it may be useful. The images are just thumbnails that link to the full-sized plots (made with Vega-Lite):

Note about the scatterplots: each point in the scatterplots is "transparent" so that if there's only one data point in the same point of the plot it's displayed less prominently than if there are multiple in the same position.

# Answer
Here's a suggestion for a simple greedy heuristic to apply to the big SCC. It's based on the observation that **a cycle of edges can be traversed a number of times equal to the minimum multiplicity of any edge in the cycle**, so looking for cycles in which all edges have large multiplicity may be a good strategy:

1. Order edges in the big SCC in decreasing order by multiplicity. Call this list of edges $X$. (Note: Each edge appears in $X$ just once, regardless of its multiplicity.)
2. Set $Y$ to be an empty list of edges.
3. If no edges remain in $X$, go to 7.
4. Choose the edge $e$ with highest multiplicity remaining in $X$. Remove it from $X$ and add it to $Y$.
5. Test whether $Y$ now contains a cycle (since this cycle must contain $e$, this check can be done quickly using a union/find data structure): If so, let $Z \subseteq Y$ be the edges in this cycle. Add the pair $(Z, m)$ to the set $C$, where $m$ is the minimum multiplicity of any edge in $Z$, clear out $Y$ and start over (recurse) with $X\setminus Z$.
6. Otherwise, go to 3.
7. At this point, we have a set of edge-disjoint cycles in $C$, as well as the maximum number of times each can be completely traversed. Note that if $(Z, m) \in C$, then the cycle $Z$ can be entered at any of its vertices, traversed $m$ times, and then exited at the same vertex; or entered at any vertex, traversed $m-1$ times, then (possibly after a further partial traversal) exited from *any* vertex, giving us some flexibility.
8. Find the vertex $v\_1$ that is shared by the largest number of cycles in $C$; let these cycles be $C\_1 \subseteq C$. If $C\_1 = C$ then stop here: We can start at $v\_1$ and traverse each cycle the full number of times in any order.
9. Otherwise, find the vertex $v\_2$ that is shared by the largest number of cycles in $C\setminus C\_1$ and is adjacent to $v\_1$. Repeat this for $v\_3$, etc., until $C$ is exhausted.
10. Starting at $v\_1$, for each $i$ in increasing order, and for each cycle $C\_{ij} \in C\_i$ (in no particular order), add either $m\_{ij}$ or $m\_{ij}-1$ traversals of $C\_{ij}$ to the the trail, whichever is larger and still allows us to stop at $v\_{i+1}$ in preparation to begin traversing the following set of cycles.

Since the procedure is fairly quick, it may be worthwhile to rerun it many times, choosing a different order of edges each time, and pick the best overall.
> 2 votes

---
Tags: graphs, np-hard, search-problem, search, directed-graphs
---


# Question
Title: Fast computing of a matrix power for large integer values in C++
I'm working with squared matrices that can be quite large, for instance, a `M = 50 x 50 matrix`.

My objective is to compute the power of the squared matrix `M^t` for very large `t` values (for example `t = 4000`).

I work in `R` and I have used the `R` function `matrix.power` from the `matrixcalc` R package.

I'm exploring the possibility to write a code for matrix power in C++ and then import it in R through the R package `Rcpp`.

One alternative would be to use the matrix multiplication approach (as in the `matrix.power` function in R), but looking around I have understood that there might be faster approaches to calculate a matrix power.

Do you have any experience on that? Does anyone know a library in C++ that does matrix power calculation fast and efficiently?

Consider that I'm working on a Mac0s laptop with 16 GB of RAM and 4 CPUs.

# Answer
> 3 votes
Since your matrices are small $(50 \times 50)$, you can probably just compute $M^t$ through repeated exponentiation where the exponents are powers of $2$.

Write $t$ in binary so that $t = 2^{k\_1} + 2^{k\_2} + \dots + 2^{k\_\ell}$. Then $M^t = \prod\_{i=1}^\ell M^{2^{k\_i}}$. Moreover, for $k\_i \ge 1$ you have $M^{2^{k\_i}} = \left( M^{2^{k\_i - 1}} \right)^2$, so you need at most $O(\log t)$ matrix multiplications.

Here is a pseudocode where "&" denotes "bitwise and" and "~" denotes "bitwise not":

```
Power(M, t):
  if(t & 1):        //Handle odd values of t (this saves a multiplication later)
     R = M;
     t = t & ~1;    //Clear the least significant bit of t
  else:
     R = I;

  i=1;
  B=M;                //B will always be M^i, where i is a power of 2
  while t!=0:
     i = i*2;         //Advance i to the next power of 2
     B = B*B;         //B was M^(i/2) and is now M^i

     if(t & i):       //i is of the form 2^j. Is the j-th bit of t set?
        R = R*B;      //Multiply the result with B=A^i
        t = t & ~i;   //Clear the j-th bit of t

  Return R;

```

# Answer
> 1 votes
I suggest using xtensor. You can compute the 4000-th matrix power of `M` as `xt::linalg::matrix_power(M, 4000)`.

Obviously you should be aware that powering in any language can incur in numerical issues. Even if your matrix is 1 x 1, `M^4000` could be enormous, larger than what you could store as a floating point value.

---
Tags: efficiency, matrices, linear-algebra, performance, c++
---


# Question
Title: Is a register machine built out of automata of some sort?
I am looking at register machines like the Random Access Machine. Wikipedia says:

> Random-access machine (RAM) – a counter machine with indirect addressing and, usually, an augmented instruction set. *Instructions are in the **finite state machine*** in the manner of the Harvard architecture.

Does this mean the instructions are somehow encoded as a finite automaton? Or how exactly is a register machine implemented (theoretically and practically, at a high level). Where do automata fit into the picture?

I am wondering because I realize automata are pretty limited in what they can do, and once you need to "parse" something but have access to an entire database of information at each step of the parse, and then the result of parsing is a complicated object graph, you are no longer dealing with automata (as far as I can tell). Automata are basically recognizers returning a yes or no answer, with very little access to "data" to make their transition decisions. But I like the idea of "state machine", where it transitions around state to state.

So I'm wondering what a so-called "state machine" with access to a large database to figure out how to make each transition might be called, and if this is what a register machine could/would be.

My understanding is that a complex register machine is closer to something like x86, where you have instructions and data. But it seems that you might somehow be able to encode these instructions as a state machine somehow. Is this true? What am I missing from this picture? Is a register machine compiled down to automata of some sort, or otherwise built out of automata, or if not, how is it different from automata?

# Answer
> 1 votes
I can only react to this as seen from the perspective of a theoretical computer scientist.

A *finite state* machine/automaton is, as you know, usually represented by a finite directed graph. The vertices of the graph repesent the states of the automaton, the edges are the instructions: in state $p$, upon reading symbol $a$, move to state $q$. Next to this graph is the "machine interpretation". The machine has a control unit and an input tape. That control unit is represented by the finite graph.

From these finite state machines/automata we can build more complex automata by adding external memory. For instance the *pushdown automaton*. The external memory is a single stack. The edges/instructions of the finite state repesentation are now extended with tests and instructions of the external pushdown: test what is the topmost symbol $A$, pop $A$ and push a new sequence $\alpha$.

The *register machine* likewise is obtained by choosing another external memory type. That of registers. The machine has a finite, fixed, number of registers each holding a natural number. Each register can be tested for zero, incremented and decremented. The instructions of the register machine are added to the finite state control. So we get edges/instructions of the form: in state $p$ upon reading $a$, when register $i$ is nonempty, increment it by $1$ and move to state $q$. If we allow the register machine to read $\varepsilon$, that is compute without reading input, these machines are Turing complete (even with two registers).

---
Tags: automata, reference-request, computation-models
---


title: Weird "proof" recursion

text:
# Question
Title: Weird "proof" recursion
Assume we have some statement called $\alpha$. We will define a new statement $P(\alpha):="(\alpha\text{ can be proved})\lor(\lnot\alpha \text{ can be proved})"$

I claim that $P(P(\alpha))$ is always correct (that is, we can always prove\disprove whether a statement can be proved or not).

The following is a "proof" for that:

Assume towards contradiction that $P(P(\alpha))$ is not correct. Then, there is no proof for $P(\alpha)$ and also there isn't a proof for $\lnot P(\alpha)$.

Lemma: If $\alpha$ can be proved, say using some proof $p\_\alpha$, then this $p\_\alpha$ also proves that "$\alpha$ can be proved", hence $p\_\alpha$ proves that $P(\alpha)$ is also true.

Use this lemma again and get that $P(P(\alpha))$ is true.

If $\alpha$ cannot be proved, then either that $\lnot\alpha$ can be proved or not. If it is possible to prove $\lnot \alpha$, then by the lemma we know that $P(\lnot\alpha)$ can be proved. But notice that by the definition of $P$ we have $P(\alpha)\equiv P(\lnot \alpha)$, so also $P(\alpha)$ can be proved, and once again, using the lemma we get that $P(P(\alpha))$ is true.

If its also impossible to prove $\lnot\alpha$, then by the definition of $P(\alpha)$ we have $P(\alpha)$ is false. However the "proof" up until this point proves that $P(\alpha)$ was false, since we assumed that there is no proof for $P(\alpha)$ but in every other case there was a proof. Thus, a contradiction - and hence $P(P(\alpha))$ must be true in this case as well.

## My question

1. Is this idea "correct"?
2. If it is "correct", then is it possible to formalize it? how would it look like?

# Answer
I feel like there is a kind of circularity in the last part of your argument (and I think the conclusion is wrong, there are undecidable problems which we cannot prove to be undecidable).

You are basically making a case distinction:

* if $\alpha$ can be proved or $\neg \alpha$ can be proved: Then $P(\alpha)$ can be proved and thus $P(P(\alpha))$ is true. (I agree here)
* if neither $\alpha$ nor $\neg \alpha$ can be proved: Then $\neg P(\alpha)$ can be proved and thus $P(P(\alpha))$ is true. I disagree here. The correct assumption to make this conclusion would be: "if we can prove that neither $\alpha$ nor $\neg \alpha$ can be proved".

Note that you cannot in general prove that you are in the second case. You say you can because otherwise you could prove that you are in the first case. But what you need is to be able to prove that you cannot find a proof that you are in the first case, which is a different thing.
> 4 votes

# Answer
To reason safely about provability, you need to fix some kind of formal proof system. It usually won't matter at all what system you pick (barring some basic sanity checks), but it is important that "proving" should mean the same thing everywhere in your argument.

Here, "proof" in the last paragraph suddenly jumps from referring to whatever notion of proof you started with to some informal meta-reasoning, and that is where it all goes wrong.
> 0 votes

---
Tags: logic
---


title: Language in $R \setminus \mathit{NP}$

text:
# Question
Title: Language in $R \setminus \mathit{NP}$
I am wondering whether the language $$L\_{\textrm{hanoi}} = \\{\langle k,s \rangle \mid \text{$s$ is a solution of Tower of Hanoi problem on $k$ rings}\\}$$ is in $R\setminus \mathit{NP}$.

I want to claim that there is a Turing machine that solves the problem, therefore, $L\_{\mathrm{hanoi}} \in R$, but given a solution to the problem, verifying that it is a valid solution takes $\Omega (2^k)$. However, $2^k$ could be be linear to the length of the input (number and sequence).

Is my solution valid? If not, how can I construct a language in $R \setminus \mathit{NP}$?

# Answer
We always measure the running time of a machine with respect to *input size*. For this reason, your language is in P. Given a sequence of moves, you can easily check in polynomial time that the sequence is valid.

You can construct a language in $R \setminus \mathit{NP}$ using diagonalization. This is the content of the nondeterministic time hierarchy theorem.
> 4 votes

---
Tags: turing-machines, np
---


# Question
Title: Proving satisfiability using resolution and variable elimination
I don't 100% understand this. But I have a entailment, and I want to prove whether it is satisfiable or not, and I will do this using resolution and variable elimination.

Here is the formula: $$ (x\_1 \lor x\_2 \lor x\_6) \land (\lnot x\_1 \lor x\_3 \lor x\_8) \land (\lnot x\_2 \lor \lnot x\_3 \lor x\_4) \land \\ (\lnot x\_4 \lor x\_5 \lor x\_7) \land (\lnot x\_4 \lor x\_6 \lor x\_8) \land ( x\_5 \lor \lnot x\_6) \land \\\(\lnot x\_6 \lor x\_7 \lor \lnot x\_8) \land (x\_7 \lor \lnot x\_8 \lor \lnot x\_{10}) \vDash \lnot(x\_7 \lor \lnot x\_9 \lor x\_{10}) $$ First I negate the conclusion and move it into the premises. If I can prove this to be ⊥ using Resolution, I have proven that the original entailment IS satisfiable. So this is what I want to refute by using resolutin (and variable elimination to simplify).

$$ (x\_1 \lor x\_2 \lor x\_6) \land (\lnot x\_1 \lor x\_3 \lor x\_8) \land (\lnot x\_2 \lor \lnot x\_3 \lor x\_4) \land \\ (\lnot x\_4 \lor x\_5 \lor x\_7) \land (\lnot x\_4 \lor x\_6 \lor x\_8) \land ( x\_5 \lor \lnot x\_6) \land \\\(\lnot x\_6 \lor x\_7 \lor \lnot x\_8) \land (x\_7 \lor \lnot x\_8 \lor \lnot x\_{10}) \lor (x\_7 \lor \lnot x\_9 \lor x\_{10}) $$

So I start off by eliminating all clauses with $x\_7$ since it's a pure literal, which leaves me with

$$ (x\_1 \lor x\_2 \lor x\_6) \land (\lnot x\_1 \lor x\_3 \lor x\_8) \land (\lnot x\_2 \lor \lnot x\_3 \lor x\_4) \land \\ (\lnot x\_4 \lor x\_6 \lor x\_8) \land (x\_5 \lor \lnot x\_6) $$

Here $x\_5$ is a pure literal, so that one clause can be removed.

$$ (x\_1 \lor x\_2 \lor x\_6) \land (\lnot x\_1 \lor x\_3 \lor x\_8) \land (\lnot x\_2 \lor \lnot x\_3 \lor x\_4) \land (\lnot x\_4 \lor x\_6 \lor x\_8) $$

Now $x\_6$ is a pure literal, which would leave just the two clauses

$$ (\lnot x\_1 \lor x\_3 \lor x\_8) \land (\lnot x\_2 \lor \lnot x\_3 \lor x\_4) $$

However, here $x\_8$ is a pure literal, thus leaving us with only one clause, and that clause contains pure literals. Can it really be simplified into nothing? It feels like I'm doing something wrong but I'm not sure what it is that's wrong.

If I really can simplify into nothing, would that mean that the original formula is satisfiable or not satisfiable?

Since all the clauses contain a pure literal, wouldn't that make it impossible to resolve?

# Answer
> 0 votes
If $x\_7$ is a pure literal, then this means that you can satisfy all clauses containing $x\_7$ by setting it to true. Accordingly, we set $x\_7,x\_5,x\_6,x\_8$ to true, satisfying all clauses apart from $\lnot x\_2 \lor \lnot x\_3 \lor x\_4$, which we can satisfy by setting $x\_4$ to true (for example).

If you set $x\_4,x\_5,x\_6,x\_7,x\_8$ to true, then the left-hand side of your original formula is satisfied (once you correct $x\_1 \lor x\_2$ to $x\_1 \lor x\_2 \lor x\_6$ and $\lnot x\_5 \lor \lnot x\_6$ to $x\_5 \lor \lnot x\_6$), while the right-hand side is falsified, and so the entailment is false. (In contrast to your post, there is no "formula" there which can be satisfied or not.)

---
Tags: satisfiability
---


# Question
Title: Is this variation of the traveling salesman problem NP-hard
Consider the following setting. You have $n$ cities, and there is a cost to travel from a city $i$ to a city $j$ given by $c\_{ij}\>0$ where $c\_{ij}\neq c\_{ji}$. Moreover, if you are traveling to city $i$, you are allowed to stay exactly $d\_i\>0$ days. The problem is:

Find a travel schedule, this is: a number $m$ and a sequence of different cities $i\_1,\dots,i\_m\in\\{1,\dots,n\\}$, such that the cost $\sum\_{k=1}^{m-1} c\_{i\_k,i\_{k+1}}$ is minimal and that the whole trip lasts at least $L$, this is $\sum\_{k=1}^m d\_{i\_k}\geq L$.

There are many similarities between this problem and the traveling salesman one. The key differences are the non symmetric costs $c\_{ij}\neq c\_{ji}$ and that instead of having to travel to all cities once, one just needs to travel to enough cities to make the trip last enough.

I understand that to show that this problem is NP-hard, I need to show that another NP-hard problem can be reduced to this one in polynomial time. I suspect that the original traveling salesman problem may work to do so through some clever trick I haven't found yet. Moreover, since there is plenty of literature on the traveling salesman problem, I suspect a similar problem to this may already be shown to be NP-hard.

**My question is**: Do you see how to show this problem to be NP-hard? Or, do you recognize this problem to be something standard in some piece of literature you can point me out?

# Answer
> 2 votes
I think if you choose all $d$'s to be exactly $1$ and choose $L$ to be exactly $n$ (number of cities), any solution must visit all cities, so the reduction will work out.

---
Tags: optimization, reductions, np-hard, combinatorics, traveling-salesman
---


# Question
Title: How to choose word for pumping lemma for $a^kb^{2k}a^k$?
I have to show that the language $ \mathcal {L} = \\{a ^ k b ^ {2k} a ^ k: k \geq 0 \\} $ is not a regular language. So that's what I want to use the pumping motto for. What I could do is this: let $ \ sigma = a^Nb^{2N}a^N $, where $| \sigma | = 4N \geq N $, fulfilling that $ \alpha \beta^k \gamma$. But at the moment of being able to separate $ \alpha \beta $ I am very complicated and I cannot reach the possible cases.

# Answer
Since $|\alpha \beta|\leq N$, then $\beta = a^i$, $i\>0$. You can take it from here.
> 0 votes

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


# Question
Title: Reduction from set cover problem to vertex cover problem
Although the reduction from vertex cover problem to set cover problem is quite simple, I did not find anywhere the reduction in the opposite direction. From the similarity in the type of problems, I guess this reduction should be simple too. However, despite trying for some time, I could not develop this. So, any ideas how this reduction can be done?

# Answer
Edit: Wherever it says "vertex cover", read "dominating set".

Suppose that the sets are $S\_1,\ldots,S\_n$ and the elements are $x\_1,\ldots,x\_m$. For each set $S\_i$ there will correspond a vertex $S\_i$. For each element $x\_j$ there will correspond $n$ vertices $x\_j^{(1)},\ldots,x\_j^{(n)}$. There is also an additional vertex $t$. Finally, assume wlog that the optimal solution for set cover is *not* $S\_1,\ldots,S\_n$ (this can be checked in polynomial time).

The instance of vertex cover is as follows. The vertex $t$ is connected to all of $S\_1,\ldots,S\_n$. Whenever $x\_j \in S\_i$, the vertex $S\_i$ is connected to all of $x\_j^{(1)},\ldots,x\_j^{(n)}$. If there's a set cover of size $M$, then there is a vertex cover of size $M+1$ (we need to take the extra vertex $t$ so that all set vertices are covered). I believe that the converse should hold as well.

Try to work it out yourself, and if it doesn't work out, try to fix it and let us all know how.
> 3 votes

# Answer
If you make a set of subsets out of the edges of a graph and solve the set cover problem, youll have solved the vertex cover problem. This is true for any graph. If you take a set of subsets,

1. You may not be able to make it into graph.
2. even if you did the vertex cover might not be the set cover.
> 0 votes

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


# Question
Title: Show that a circuit of size $s$ can be converted to a DeMorgan circuit computing the same function of size at most $2s$
I am trying to prove the above statement. A DeMorgan circuit is a circuit that has only $\\{ \wedge, \vee, \neg \\}$ gates, and the negation is applied only to input variables.

So, assuming we have a circuit of size $s$ that computes a function $f: \\{0,1\\}^n \rightarrow \\{0,1\\}$. The basis for this circuit is $\\{\wedge, \vee, \neg\\}$ with fan-in 2 for the OR and AND gates. I am trying to prove we can convert this circuit to a DeMorgan circuit of size at most $2s$.

Intuitively and in small examples, this claim makes sense to me but I would like to prove that more formally. I have searched in several papers but this claim is mostly mentioned but not proved. Can someone give me intuition about the proof?

The above statement was mentioned in the following paper https://eccc.weizmann.ac.il/report/2018/154/ in the second paragraph of the 1st page and continuing on the 2nd page.

# Answer
The idea is to "move backwards" all the not gate. Assume you have some circuit, for example $(\cdot,\cdot)\rightarrow AND\rightarrow NOT\rightarrow OUTPUT$

Can be converted to:

$(\cdot \rightarrow NOT,\cdot \rightarrow NOT)\rightarrow OR\rightarrow OUTPUT$

Doing this without thought can increase the circuit size exponentially. So, when you see two $NOT$ gates one after another - cancel both of them out. I guarantee you this will work, but I wont prove it to you (this is your task)
> 2 votes

---
Tags: circuits
---


# Question
Title: What is "dynamic" about dynamic programming?
One of my seniors had a job interview and he was asked why it is called dynamic. He couldn't answer and after he gave up the interviewer said that there's nothing dynamic about it, its just called like that. That is hard for me to believe.

Does it refer to the fact that the subproblems are solved during run-time and used in reaching the final goal? Like dynamic memory allocation that happens during run-time?

**\[ANSWER\]**

I should have read **this** wiki article before asking the question, sorry.

# Answer
Actually, there is nothing special in the name "dynamic programming"; the technique itself is just about smartly unwinding recursion. See this question and look at @Jeffe answer, in which is reported that Belman choose that name to be intentionally distracting.
> 11 votes

# Answer
Richard Bellman called it Dynamic Programming in the words in Bellman

> I spent the Fall quarter (of 1950) at RAND. My first task was to find a name for multistage decision processes.
>
> An interesting question is, Where did the name, dynamic programming, come from? The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word research. I'm not using the term lightly; I'm using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term research in his presence. You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, "programming". I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying. I thought, let's kill two birds with one stone. Let's take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that it's impossible to use the word dynamic in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It's impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.

Source: Eye of the Hurricane, Richard Bellman (Autobiography)
> 6 votes

# Answer
There's an interesting story here.. Bellman pioneered this paradigm. But, this was actually mathematical research. Back in his day, the then secretary of defense was paranoid of the words *Research* and *Math* (crazy guy, right!). Bellman was scared that the secretart would be furious at his work and eventually would get him into trouble. So to blur things a bit, he called it *Dynamic Programming*, however there's nothing 'dynamic' about it..
> 5 votes

# Answer
Even though there is a backstory on the naming, as stated in the other answers, the term *dynamic programming* makes total sense. *Dynamic* means that something is changing. *Programming* means keeping a table (program or schedule), as it is implied to the term *linear programming*, too.

Quoting CLRS

> “Programming” in this context refers to a tabular method, not to writing computer code.

So, dynamic programming is keeping a table (with the results of the sub-problems) that is being updated during the solution.

On that regard, the name could apply to any algorithm than mutates a table. It doesn't attribute any of the basic characteristics of the dynamic programming, which are optimal substructure and overlapping sub-problems. So, in the end you just cannot use it "in a pejorative sense".
> 2 votes

# Answer
I always intuited that it meant that algorithms using *dynamic programming* seemed to edit the problem space "*dynamically*" until the problem could be solved with a greedy algorithm.

For example, with the Checkerboard problem, the dynamic programming algorithm edits the entire board as it goes through it, and then finally, a greedy algorithm can be used (similarly, with Dijkstra's shortest-path algorithm, etc.).

I am unsure if this generalizes to every dynamic programming problem though.
> 1 votes

---
Tags: terminology, dynamic-programming
---


title: Euler polygon division algorithm

text:
# Question
Title: Euler polygon division algorithm
I am trying to enumerate and display all possible divisions of an `n`-polygon into `(n-2)` triangles (as in the following mathworld picture)

I know how to count how many divisions (Catalan numbers, `1, 2, 5, 14, 42, ...` ), but I am struggling to find a way to generate all the C(n-2) triangulations. Can anyone point to existing software implementation, or at least to an algorithm that generates these triangles?

# Answer
> 1 votes
See: Hurtado and Noy, *Graph of triangulations of a convex polygon and tree of triangulations*, Computational Geometry 13 (1999) pp179–188.

Section 3 of that paper gives a relatively straightforward method for constructing all triangulations of $n+1$-gons given all triangulations of $n$-gons.

# Answer
> 1 votes
You can use the formula to count the number of division to generate them.

Suppose you want to generate a division of a $n$-polygon whose vertices are $1, 2, …, n$. We know that there are $C\_{n-2}$ such divisions (where $C\_k$ is the $k$-th Catalan's number). What we need to do is:

* chose $2\leqslant k\leqslant n-1$ the other vertex of the triangle with edge $\\{1, n\\}$;
* chose a division of the polygon with vertices $1, 2, …, k$;
* chose a division of the polygon with vertices $k, k+1, …, n$.

Suppose you want to generate the $i$-th division of the $n$-polygon, $1\leqslant i\leqslant C\_{n-2}$. Since we know that $C\_{n-2} = \sum\limits\_{j=2}^{n-1}C\_{j-2}C\_{n-1-j}$, we have a way to chose the value of $k$: chose the minimum $k$ such that $i\leqslant \sum\limits\_{j=2}^kC\_{j-2}C\_{n-1-j}$.

We then need to chose the number $i\_1$ of the division of the polygon $1, 2, …, k$ and the number $i\_2$ of the division of the polygon $k, k+1, …, n$. Picking $i\_1 = i\mod C\_{k-2}$ and $i\_2 = \left\lfloor \frac{i}{C\_{k-2}}\right\rfloor$ will do the trick.

This gives the idea of a recursive algorithm to generate divisions. Note that the base case here is the polygon with $n=2$ (a simple edge).

---
Tags: polygons
---


# Question
Title: How can I quickly judge whether matrix A is the inverse matrix of B?
How can I quickly judge whether matrix A is the inverse matrix of B?

This is an exercise for the course I take. This question is given in the section of randomized algorithms. So I think its solution may be related to randomized algorithms.

# Answer
> 24 votes
You might be looking for something like Freivalds' algorithm. It is a randomized probabilistic algorithm that given three square matrices $A,B$ and $C$ checks if $A \times B = C$ by using random vectors. This method reduces the time complexity from $O(n^{2.3729}$) (regular matrix multiplication) to $O(n^2)$ with high probability. In your case, the matrices $A$ and $B$ would be the matrices you are given, and the matrix $C$ would be the identity matrix.

# Answer
> 8 votes
## tl;dr: You can make a rough probabilistic judgement in $O(1)$ time

Let's assume you are willing to settle on a test which differentiates "good" matrices $A,B$ from "pretty bad" $A,B$, in the following sense:

* If $A \times B = I$, the test will accept with high probability.
* If $A \times B$ is *far** from $I$ , the test will reject with high probability.
* If $A \times B$ is *close* to $I$, you don't care

If you can live with my relaxation\** , then here's your test: repeatedly compute a random cell of $AxB$ and check it against $I$. That is, repeatedly:

1. Uniformly sample a row index $i$.
2. Uniformly sample a column index $j$.
3. Compute the inner product of the $i$'th row of $A$ by the $j$'th column of $B$.
4. Ensure the result is 0 for $i \neq j$ or 1 for $i = j$.

Each repetition takes $\Theta(n)$ time, and the number of repetitions depends on your distance parameter and the desired probability of being correct, only. And it's one-sided error too :-)

You could go even further, and *estimate* the inner product instead of computing it fully, by repeatedly sampling pairs of corresponding elements in the two vectors, multiplying just the pair, and taking an average over these individual element multiplications. The expected value of a single-element-pair multiplication is in fact the overall inner product (easy exercise). This will reduce your time complexity from $\Theta(n)$ to $O(1)$ (times a function of the distance parameter and desired correctness probability), but now the test has two-sided error.

---

(\*) - This should work w.r.t. $L\_k$ norms with $k \> 0$. If you don't know what these are, see here.
(\**) - This relaxation is the object of study of the field of Property Testing.

# Answer
> 0 votes
1. Multiply row 1 of A by column 1 of B. For randomly chosen matrices, this has unit probability of proving that they're not inverses, and you're done in O(n) time.
2. Find any eigenvalue and the corresponding eigenvector of A. I think this is O(n^2) (quicker than finding all eigenvalue-eigenvector pairs). Check whether this eigenvector is also an eigenvector of B, with the inverse eigenvalue. If not, then you're done.
3. Repeat 2 with an eigenvector that's orthogonal to the one found previously. Keep going until it becomes advantageous to switch and do...
4. In the space orthogonal to all the previously found eigenvectors, do matrix multiplication.

---
Tags: algorithms, time-complexity, randomized-algorithms, matrices
---


# Question
Title: Why does CLRS refer to the disk parts as pages rather than blocks?
I recently decided to review the B-tree chapter (chapter 18, p 486 in 3ed) in Introduction Algorithms, and found that they call pages what I always referred to as blocks or clusters:

> In order to amortize the time spent waiting for mechanical movements, **disks access** not just one item but several at a time. Information is divided into a number of equal-sized **pages** of bits that appear consecutively within tracks, and each **disk** read or write is of one or more entire pages. For a typical **disk**, a **page** might be $2^{11}$ to $2^{14}$ bytes in length. Once the read/write head is positioned correctly and the **disk** has rotated to the beginning of the desired **page**, reading or writing a magnetic **disk** is entirely electronic (aside from the rotation of the disk), and the disk can quickly read or write large amounts of data.

I always thought that pages are related to the virtual memory, although including swapping with the disk access. When the talk goes into the discussion of the filesystems in general, then I thought the information is divided into blocks rather than pages. Is he talking about virtual memory here? If I restate the whole paragraph in terms of blocks, would it be still correct, except for the provided sizes of the blocks?

# Answer
> 0 votes
I think you're right to be confused by this.

If their "pages" are sectors (= disk blocks), then they're right to say that pages "appear consecutively within tracks, and each disk read or write is of one or more entire pages", but their size range for pages makes no sense. The overwhelmingly most common sector size in 2009, when this textbook was published, was $2^9$ bytes. Also, I've never heard the term "page" used for a disk sector before.

If their pages are VM pages, then the size range makes more sense. But then they're wrong to suggest that the page size is a property of the disk, and it's not true that a swapped-out VM page will generally appear consecutively in a track. Also, disk reads and writes are only in units of VM pages if they come from the paging subsystem, and you shouldn't expect B-tree nodes to be paged in general (though they can be).

If their pages are clusters (filesystem allocation units), then the size range may be reasonable, but the rest is wrong. Clusters aren't generally read or written as a whole, they are just allocated as a whole. Also, I can't think of any reason to match the B-tree node size to the cluster size unless it's a filesystem B-tree (probably a directory index) and equating them simplifies the design or implementation of the file system.

---
Tags: computer-architecture, database-theory, filesystems, b-tree
---


# Question
Title: Number of combinations without given pairs
Given a set of elements {e1, e2, ... en}, a set of pairs of these elements (each element may be present in several pairs) and a number k.

I need to count how many combinations of size k exist which not include any pair?

For example: if there only one pair {e1, e2} result in number of all combinations without elements e1 and e2. It may be counted in constant time: $$C^k\_n - C^{k-2}\_{n-2}$$

This task can be solved with the naive algorithm on python:

```
def combinations_without_pairs(elements, pairs, k):
    def iterable_len(iterable):
        return sum(1 for _ in iterable)

    def not_include_pairs(combination):
        for pair in pairs:
            if pair[0] in combination and pair[1] in combination:
                return False
        return True

    return iterable_len(filter(not_include_pairs, itertools.combinations(elements, k)))

```

But this algorithm is ineffective: it requires iterating over each element combination and each pair.

Is there any way to solve this problem with better complexity? At least reduce the impact of a big count of elements and pairs?

I want to find an algorithm with the lowest time complexity.

# Answer
> 7 votes
Don't expect an efficient algorithm. This is the problem of counting the number of independent sets in an undirected graph. This problem is #P-complete \[1,2\], so there is unlikely to be any effective algorithm that works for arbitrary graphs.

See https://cstheory.stackexchange.com/q/10700/5038 for techniques you could use.

\[1\] The complexity of counting cuts and of computing the probability that a graph is connected, J. Scott Provan and Michael O. Ball, SIAM J. Computing, 12:4.

\[2\] The complexity of counting in sparse, regular, and planar graphs, Salil P. Vadhan, SIAM J. Computing, 31:2(398--427).

---
Tags: algorithms, combinatorics
---


# Question
Title: How to show that pda accepts empty language?
I have to show that a PDA accepts empty language, but for this I have to use some algorithm, with what kind of algorithms could I demonstrate it? I've heard about the algorithm from Moore, Brzozowski or Thompson, but they are for DFA, so I don't know if it would work.

# Answer
I am not aware of any straightforward algorithms. One roundabout way I can think of is:

1. Convert the PDA to a CFG (there is a standard construction for this covered in introductory automata classes, the resulting CFG has $O(|Q|^2)$ variables where $Q$ is the size of the PDA)
2. Check if the CFG's language is empty.

We can check if the language of a CFG $G$ is empty using an iterative algorithm that marks a variable if it can derive a string:

1. Mark all terminals in $G$ (or delete them from the rules)
2. While no new variables are marked:
    1. For each rule $A \to \alpha\_1 \ldots \alpha\_k$, if $\alpha\_1, \ldots, \alpha\_k$ are all marked then mark $A$.
3. If the start variable is marked then $L(G)$ is nonempty, otherwise $L(G)$ is empty.

The algorithm above can be optimized with a worklist that skips re-visiting a same variable's rules after it's marked, and doing some processing to allow checking rules affected by the previous pass
> 2 votes

---
Tags: pushdown-automata
---


# Question
Title: How to get the expected time complexity of while loop?
How to get the expected time complexity of while loop below?

```
While infinity:
  case1: Return 0 with a probability of p(1 - p)
  case2: Return 1 with a probability of p(1 - p)
  case3: otherwise repeat this loop until return 0 or 1

```

I can understand the probability that this loop runs only one time is $2p(1 - p)$. But I cannot understand how much the expected run time of this is. Can anyone let me know it and why?

# Answer
> 1 votes
You should calculate the probability that the `while` loop runs **exactly** $k$ times, for $k\in\mathbb{N}$.

Then the expected number of loops is $\sum\limits\_{k=0}^{\infty}k\times\mathbb{P}(\text{loop runs }k\text{ times})$.

# Answer
> 1 votes
Define $q:=2p(1-p)$ the probability that the while loop halts at a certain point.

The probability the loop runs **exactly** once is $q$
The probability the loop runs **exactly** twice is $(1-q)\cdot q$
The probability the loop runs **exactly** three times is $(1-q)^2 \cdot q$

And you can see where this is going: the probability the loop runs exactly $n$ times is given by: $(1-q)^{n-1}\cdot q$ and as @Yuval Filmus suggested, this is a geometric distribution.

According to wikipedia, the expected value of such a geometric distribution is $\frac{1}{q}$, so the average complexity of your loop is: $\frac{1}{2 p (1-p)}$

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


# Question
Title: What is a good path for self-study of CS foundations/fundamentals?
I’m a self-taught software engineer who’s been working in industry for 12 years. I don’t have any formal education in CS and math was never my strong suit (although I’m willing to do the work to make it my strong suit!), but when I first started learning how to program I went through some basic courses offered by Stanford, MIT, etc.

Anyhow, I’m looking to gain a more rigorous understanding of CS, starting from the most basic, foundational pieces. I’m looking for some guidance on a good course of self-study - the order to go in, suggested resources, etc.

Given that I’m looking to understand CS fundamentals more rigorously, as I said, I’m beginning with some basic math (not my strong suit). What I’ve mapped out so far is going through the following books (and investigating prerequisites/dependent concepts for these materials on an as-needed basis):

1. Discrete Mathematics with Applications 4th edition by Susanna Epp
2. Practical Analysis of Algorithms by Dana Vrajitoru, William Knight
3. Book of Proof Richard Hammack
4. Mathematics for Computer Science by Lehman, Leighton, Meyer

I have a bit of a tendency to get down the rabbit hole and go on detours, whereby the main purpose of my study recedes into the distance as I investigate yet another area that I don’t seem to have a solid foundation in. But I’m unsure how to avoid this as some things *really do* need to be understood before other things. For example, without understanding some basic discrete maths, it will be difficult to talk about recursion, time complexity in a way that is more rigorous than my current understanding.

Perhaps I’d be better suited just starting immediately with MIT’s “Mathematics for Computer Science” course (6.042J) and only looking into things I don’t have a grasp on as needed?

Anyhow, sorry for the ramble. Would love some general guidance and direction for getting to where I’m trying to go. Thanks in advance.

# Answer
Check out this and this. I prefer the former one cause the number of subjects is relatively small, and they are the core fundamentals.
> 1 votes

# Answer
As other people have already said in the comments, the best way to learn is through a university. This is not necessarily because a book does not cover the same material but becasue you need (1) structure and (2) someone to check that what your understanding is sufficient and your solutions to problems are correct. As a software engineer, you already know that you can't just learn by reading, you have to practice.

Some recommendations:

1. Check out CS courses, perhaps at an online university with a flexible program since getting a degree is not your main goal. Also there are many univerities that offer courses for free.
2. If you don't want to enroll you can see if you can audit a course.
3. Pick a CS program of any univeristy, look at the lessons offered to CS undergrads and go to the webpages for the courses. The suggested literature is usually published there.
4. Some books that I personally found helpful:

* "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.
* "Introduction to the Theory of Computation" by Michael Sipser
* "Logic in Computer Science: Modelling and Reasoning about Systems" by M. Huth and M. Ryan
* "Introduction to Graph Theory" by Douglas Brent West
* Something about Linear Algebra and something about Statistics. I don't have any recommendations of books in english but they are they are both taught in almost all undergrad CS programs so good textbooks should be easy to find.

5. Another good list with great books on fundamental concepts related to CS is here
> 1 votes

---
Tags: algorithms, data-structures, education, books
---


# Question
Title: Changing binary counter structure such that increament and decreament methods will work in O(1) amortized
Just trying to solve the second part of a question with two parts. First part was to prove that you can't add decrement method to a standart binary counter without hurting the amortized complexity and change it to be more than O(1). This part i have done with no problems.

Solution in a nutshell - after some method you are going to be in a dead end when you have a number like this: 100...0 so when you decrease by 1 you will get 0111...1 and then when you will increase by 1 you will get again 100...0 and those decreasment and increament are cost n and you will do them m times so its not O(1) amortized.

The second part, is to tell how you can change the structure such that it will support decreament and increase methods and the amortized complexity will stay O(1). I never saw something like this and it really confusing me what they want me to do. Their solution is that anytime you want to change 0 to 1 you change it to minus 1. Problem is, i can't understand what they meant, i mean, on which stracture you are inserting this change and how does it improved the complexity (if you change to -1 you stil going to the same dead end).

# Answer
They may by suggesting that you use a binary counter with three digit values, $\\{-1,0,1\\}$, and budget a fixed additional time whenever you set a digit to $\pm1$.

To increment the counter you start at the least significant trit, and if it's $-1$ you set it to $0$ and stop, if it's $0$ you set it to $1$ and stop, and if it's $1$ you set it to $0$ and loop (using the previously budgeted time). Decrementing is the same with everything negated.
> 1 votes

---
Tags: time-complexity, amortized-analysis, binary
---


# Question
Title: What is the advantage of probability algorithm?
What is the advantage of probability algorithm? e.g. Las Vegas. I would also like to know some applications of the randomized algorithms. Are there any recommendable courses or books?

# Answer
What is advantage of probability algorithm (we usually use randomized algorithm instead of probability algorithm)? Well this is a big question, e.g. we don't know if $P = BPP$, if so then we would say that deterministic algorithm is the same as randomized algorithm. If not, i.e. $P \ne BPP$ then randomized algorithm gives us more power than deterministic algorithm. I think randomized algorithm can give us some polynomial speed up but I'm not sure if it can give us an exponential speed up over deterministic.

Note that **P** is the class of all problems that can be done by efficient algorithm (i.e. polynomial algorithm in the size of the input) while **BPP** stands for Bounded-error Probabilistic Polynomial time, i.e. it contains all problems that have a non-deterministic TM with at least 1/2 of the branches accepts and less than 1/3 of the branches rejects.

A quick example of a randomized algorithm is verifying polynomial identities, e.g. given (x+2)(x-4)(x+22)(x-43)(x+11) = x^5-2x+4. The question is: Can you verify that the right-hand side is equal to the left hand side? One way to do is to multiply all terms together which takes O(n^2) where n is the number of terms. But we can do it in O(n) time by selecting some random number and text whether they are equal or not. Yes, there is a probability of wrong answer, but with many run of the algorithm (say 100) if there is at least one counterexample, then this is enough.

There are two major textbooks in randomized algorithm which are:

* Probability and Computing - Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal
* Randomized Algorithm By Rajeev Motwani and Prabhakar Raghavan

I recommend the first since it is easier and have one or more examples in each chapters while the second is good if you are interested in randomized complexity.
> 2 votes

---
Tags: randomized-algorithms
---


# Question
Title: Is there a grammar for this language? $w^{m-1}aca^m$?
I have to form a free context grammar for this language $w^{m-1}aca^m$ where $w \in \\{a,b\\}$, so what I have been able to do is this:

$X \rightarrow SacA$
$S \rightarrow aS|bS$
$A \rightarrow aA$

But I don't know how to do it or if possible, condition the exponents as long as $ S $ is repeated $ m-1 $ times, and $ A $, $ m $ times.

# Answer
You attack it from the exact wrong side.

First, the language is the same as $\\{w^m aca a^m|w\in\\{a,b\\},m\in\mathbb{N}\\}$. For this, you apply a rule that adds $w$ on the left and $a$ on the right repeatedly, and then inserts $aca$ in the middle and is done. By using one rule that adds both on the left and the right side, you make the number of w's and a's the same.

$S \rightarrow WSa$
$S \rightarrow aca$
$W \rightarrow a|b$

That’s it.
> 1 votes

# Answer
If the question is really about $w \in \\{ a, b \\}$ (i.e., $w$ is an $a$ or a $b$), a grammar would be:

$\begin{align\*} S &\to a A a \mid b B a \\ A &\to a A a \mid a c a \\ B &\to b B a \mid a c a \end{align\*}$
> 0 votes

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


title: Meaning of Epilogue in Computing

text:
# Question
Title: Meaning of Epilogue in Computing
Wordsense.eu gives a definition of epilogue as

> 4. (*computing*) A component of a computer program that prepares the computer to return from a routine.

I’d like to know more & haven’t been able to successfully search for info. Could anyone point me to a source / share their knowledge?

# Answer
It depends on context, languages, operating systems

In many languages, Prologues and Epilogues are the parts automatically added by compilers at the beginning and end of each function, for example adjusting stack pointers or copying parameters.
> 9 votes

# Answer
The popular x86 architecture has two instructions, ENTER and LEAVE, that are designed to be used as a prolog and epilog for functions. They adjust stack pointers. In practice they are not used, see this stackoverflow question.

The same architecture also has two pairs of instructions, PUSHA/POPA and their 32-bit analogs PUSHAD/POPAD, which could also form part of prologs and epilogs. They store and restore registers, though in practice they are not used, see this stackoverflow question.

For more on this, see also this question on stackoverflow.

Prologs and epilogs (sometimes called initialization and finalization) also appear in larger units, for example executables or the operating system. See for example this question on stackoverflow for some hints.

Finally, prologs and epilogs are also popular in object oriented programming, where they are known as constructors and destructors.
> 3 votes

---
Tags: algorithms
---


# Question
Title: Turing, RAM, or Von Neumann --- which theory/model is the consensus?
I am not a formal student for CS nor have I ever been, I just want to understand something simple about your field for general knowledge, in plea.

Turing, RAM, or Von Neumann --- which theory/model is consensually accepted to describe how "generally every computer works" (among computer scientists)?

# Answer
> 4 votes
The Turing machine and the RAM machine are models of computation. The Von Neumann architecture is a very high-level computer architecture. None of these are theories describing how computers work.

Scientific theories describe reality in several different levels, among these:

* Fundamental laws of nature, such as Newton's laws.
* Emergent phenomena, such as consciousness.

There is absolutely no need for a theory describing the fundamental laws behind how computers work, the reason being that humans design computers. We get to set the rules! There might be theories that describe emergent phenomena, such as the structure of social networks.

Close to scientific theories, but not quite the same, are conceptual models such as seven layer model of networking, which attempts to make sense of complicated edifices engineered by computer professionals. They are not *theories* in the sense that they cannot be right or wrong. They could be more or less helpful at organizing reality into manageable chunks.

---

The Turing machine and the RAM machine are two examples of models of computation, which are used to *define* and to *analyze* computation. According to the Church–Turing thesis, all reasonable models of computation are equivalent in power, and this includes both of these models.

However, this point of view is very coarse. In practice, one is also interested in various notions of *efficiency*. Another issue is that Church–Turing models are best at describing symbolic computations, not as good at describing numerical computations. For this reason, in practice different models are used in different circumstances, such as:

* Turing machines were invented by Turing as an intuitive notion of computation, and caught on in the theoretical literature since they are easier to work with than other models. Turing machines are not a good model of how real computers work. They appear in undergraduate classes, are the go-to model in recursion theory, and are quite common in complexity theory.
* RAM machines are a more realistic model, which is often implicitly used to describe and analyze algorithms. They even appear in certain subareas of complexity theory, such as fine-grained complexity. However, they don't model all aspects of modern computers, such as bit manipulation and concurrency.
* Real RAM machines are used to describe idealized numerical computations. They are most commonly used in computational geometry. In some sense this is an example of hypercomputation, in that the Real RAM cannot be simulated by a Turing machine, since Turing machines can only handle finite strings (though recursion theory has fixes for that).
* Boolean circuits are a theoretical model popular in complexity theory and theoretical cryptography, and also used to study certain algorithm (under the name *bit complexity*), for example fast integer multiplication. They might be inspired by actual digital circuits, but in practice are probably a poor model for those.
* Algebraic circuits are the "Real RAM" analog of Boolean circuit. They make an appearance when studying fast matrix multiplication, as an example.
* Quantum circuits (more popular than quantum Turing machines) describe the capabilities of quantum computers. In contrast to classical models of computation (here *classical* means *non-quantum*), which tend to be polynomially related to each other (that is, given an algorithm in one running in time $T$, we can create an equivalent algorithm in another which runs in time at most $cT^c$ for some constant $c$ depending only on the models), quantum computers offer super-polynomial speed-up.

Another basic difference between some of these models is uniformity: are we describing a general algorithm (uniform) or an algorithm for a specific input length (non-uniform)? Sorting algorithms (themselves corresponding to yet another model of computation, comparison-based computation) are typically described as a single algorithm, while integer multiplication circuits are designed on a size-by-size basis.

---

Computer architectures are general principles for designing actual computers. The Von Neumann architecture is an abstraction of the principles used to design some of the early computers, and are still an inspiration today. Unfortunately I am not an expert on this area, so will leave it to others to comment on these.

# Answer
> 1 votes
It depends on the usage. For basic formal complexity theory, we usually work with Turing machines. However, RAMs and Von Neumann architectures are a better description for a real-world computer, so some may be more interested in them.

From my personal experience, TMs are the most popular in a CS degree, and in theory in general. I barely saw theoretical usages for RAM, and I never saw any Von Neumann architecture used in theory for computation, but I have seen models that describe a CPU in a specific course that covers that.

---
Tags: theory
---


# Question
Title: Are the outcomes of the maximum shifts function fixed regardless of our choice of axiomatic system?
It is known that there is a $748$-state Turing machine that halts if and only if $\mathsf{ZF}$ is inconsistent. So by Gödel's second incompleteness, $\mathsf{ZF}$ cannot find what $S(748)$ exactly is, where $S$ is the maximum shifts function (Also known as the "Frantic Frog").

I'm rather confused by this fact. As $S$ is well-defined, that should mean that regardless of what axiomatic system we use, the exact value of $S(748)$ always stays the same. We just need a stronger axiomatic system to find $S(748)$, like $\mathsf{ZFC}$, $\mathsf{ZFC+CH}$, or $\mathsf{ZFC+(V=L)}$.

If $\mathsf{ZFC}$ and $\mathsf{ZF¬C}$ entailed $S(748)$ to be different numbers, since Axiom of Choice is independent to $\mathsf{ZF}$, it would be concluded that $\mathsf{ZF}$ was inconsistent at the first place. So far, is my understanding correct?

# Answer
> 1 votes
Interesting but slightly confusing thoughts, indeed.

Let us tread water slowly and cautiously.

* Suppose $\mathsf{ZF}$ is inconsistent.
    + Suppose we continue to use $\mathsf{ZF}$. Every proposition becomes trivially true. $S(748)$ can be any number. (That 748-state Turing machine will halt. That does not mean much though, since every proposition is true.)
    + Otherwise, suppose we choose another axiom system. Which one should we use? What will happen over there? That should be the story of another question, of a very different nature possibly, although an answer to that question might well be the wanted answer of this question as well.
* Suppose $\mathsf{ZF}$ is consistent. However, we cannot prove that (within $\mathsf{ZF}$ or any enclosing axiomatic systems) even if that is true.
    + $S(748)$ is well-defined, (which can be proved). That means, whatever relatively consistent extension of $\mathsf{ZF}$ we would choose to use later, such as $\mathsf{ZFC}$ or $\mathsf{ZFC+CH}$, $S(748)$ will remain the same.
    + That 748-state Turing machine will never halt. (However, this cannot be proved.)

---

"$\mathsf{ZF}$ cannot find what $S(748)$ exactly is". Yes, in the sense that, when $\mathsf{ZF}$ is indeed consistent, we can never be sure that 748-state Turing machine will never halt.

"We just need a stronger axiomatic system to find $S(748)$, like $\mathsf{ZFC}$, $\mathsf{ZFC+CH}$, or $\mathsf{ZFC+(V=L)}$." As explained above, the problem is not about whether $\mathsf{ZF}$ is strong enough. The problem is whether $\mathsf{ZF}$ is consistent, a question that signifies a part of the intrinsic boundary of our knowledge. It could be consistent, which we could believe willingly and happily but we cannot prove. It could be inconsistent, an example of which could elude us before the end of the universe.

"If $\mathsf{ZFC}$ and $\mathsf{ZF¬C}$ entailed $S(748)$ to be different numbers, since Axiom of Choice is independent to $\mathsf{ZF}$, it would be concluded that $\mathsf{ZF}$ was inconsistent at the first place". That statement is correct.

I would like to emphasize that overwhelmingly most of mathematicians/computer scientists work with the implicit or explicit assumption that $\mathsf{ZF}$ is consistent. Once the distrous possibility of $\mathsf{ZF}$ being inconsistent is introduced into the discussion, be careful and slow to avoid confusion.

---
Tags: busy-beaver
---


# Question
Title: Is every pair of NP-Complete problems reduced in polynomial time?
As shown above, several NP-Complete problems are derived from GSAT (general satisfiability problem) by a polynomial-time reduction.

Then, my question is that is every pair of NP-Complete problems reduced in polynomial time? In other words, I think that the above graph should be represented as a complete graph by the definition of NP-Hard. Is it correct?

# Answer
Yes, Let $A,B$ be two NP-complete problems. Then, by definition,

1. $A,B\in NP$
2. Every language $L\in NP$ can be reduced to them.

Hence, since $B\in NP$, then $B\le\_p A$, and with a similar argument, $A\le\_p B$.

The graph you included shows the **only** the reductions we used to prove NP-completeness of the problems.
> 1 votes

---
Tags: np-complete
---


# Question
Title: Algorithm to convert many paths into a graph?
I have a list of billions of paths in an unknown graph, e.g.:

```
A -> B -> D -> E
A -> F -> K
A -> B -> K -> B -> D -> E

```

and I want to obtain the edge list, e.g.:

```
A -> B
A -> F
B -> D
B -> K
D -> E
F -> K
K -> B

```

This feels like a classical problem, and I would like to know if there is a classical solution.

# Answer
> 1 votes
There are very different solutions, and which one is best depends much on your specific instance:

* if $G$ is small, then just parse the input list and add each encountered edge to a set stored in central memory (if the number $n$ of vertices is small then the best solution for this is a boolean $n \times n$ matrix, otherwise a hash table makes a good job);
* if $G$ is huge, then the approach above needs too much memory; I would then just list all edges, sort them, and remove duplicates (while sorting). Something like `zcat list.gz | awk -F ' -> ' '{for (i=2;i<=NF;i++) print $(i-1),"->",$i;}' | sort -u | gzip -c > edges.gz` should make the job (maybe use the `-S` sort option).

# Answer
> 0 votes
You can find the smallest graph that is consistent with those walks from the graph as follows: start with an empty graph; for each pair of vertices that are adjacent in a list, e.g., $A \to B$, add the corresponding edge $A \to B$ to the graph. The resulting graph is one that could have led to those walks, and is the smallest such.

You can't guarantee to uniquely and correctly reconstruct the original graph. If you are unlucky, there could be some vertex in the graph that was just never visited by any walk, and then it won't appear in the reconstruction. If walks are chosen randomly and you have enough of them, the probability of this happening might be low enough that you are willing to accept this risk.

---
Tags: algorithms, graphs
---


# Question
Title: Simplify $X'(X+Y) + (Y+X.X) ( X + Y') + Z + X.Z$
I wanna know if $X'(X+Y)$ means $X'.X+Y.X'$?

Does it have an AND gate after $X'$?

**Notation:**

* $X'$ : NOT $X$
* $X + Y$: $X$ OR $Y$ (OR gate)
* $X.Y$ : $X$ AND $Y$ (AND gate)

New to boolean, can't seem to understand this question.

# Answer
I am not aware of any different conventinos so it is probably implied that your expression is $X'.(X + Y)$

By definition in Boolean Algebra, $+$ and $.$ are distributive over one another. This means that $x.(y+z)=xy+xz$ and $x+(y.z)=(x+y).(x+z)$.

Obviously what you are asking is the first case, so let's take $x.(y+z)=xy+xz$. This is not a proof, I am writing it like this to help you understand what is going on. In natural language, it says that the expression holds if $x$ and ($y$ OR $z$) is true. Or equivalently that $x$ and simultaneously at least one of $y$, $z$ is true. Or in other words, if $x$ and $y$ are true or if $x$ and $z$ are true. Or to return to the math notation $x.y + x.z$
> 0 votes

---
Tags: computation-models, boolean-algebra
---


# Question
Title: Is the concatenation of a non-regular CFL and a complement of a regular upper-set always non-regular?
Let $L\_1$ be a non-regular CFL. Let $L\_2$ be a regular language. Assume that $\left(L\_1\right)^{\*} \subseteq L\_2$. I'm looking at $L\_3 = \left( L\_1 \right) ^{\*} \circ \overline{L\_2}$. Is $L\_3$ always non-regular? I can find multiple examples of it being non-regular, yet none of it being regular.

Edit: $\overline{L\_2} \neq \emptyset$.

# Answer
Consider the language $L = \\{uv\mid u, v\in\Sigma^\*, |u|=|v|\wedge u\neq v\\}$. I claim that $L$ is context-free, it is not regular (a simple pumping lemma proof can do the trick), but $L^\*$ is regular, without being equal to $\Sigma^\*$, so that means that $L^\*\overline{L^\*}$ is regular and satisfies your conditions.

Now let's show that if we denote $L'= (\Sigma\Sigma)^\*\setminus\left(\bigcup\limits\_{a\in\Sigma}a^\*\right)\cup \\{\varepsilon\\}$ (words of even length, not composed of the same letter), then $L^\*=L'$:

* the inclusion $\subseteq$ is the easiest, since words of $L$ are of even length, and are not composed of the same letter. We added $\varepsilon$ to $L'$ by definition of the Kleene star;
* let's prove by induction that $L'\subseteq L^\*$:

+ consider $w\in L'$; if $w = \varepsilon$, then $w\in L^\*$, if $|w| = 2$, then $w\in L$ (because it contains two different letters), so $w\in L^\*$;
    + suppose the result proved for words of length up to a certain $2n\in\mathbb{N}$, and consider $w\in L'$ of length $2n+2$. If $w\in L$, then trivially, $w\in L^\*$. Otherwise, since $|w|$ is even, then $w = uu$, with $u\in\Sigma^\*$, $u$ containing different letters.

    - If $|u|$ is even, then it means that $u \in L'$
        - Otherwise, $u = u\_1u\_2…u\_{2k+1}$, and we can show that $uu = xy$ verifying $x,y\in L'$ (with either $x = u\_1…u\_{2k}$ and $y = u\_{2k+1}u$ or $x=uu\_1$ and $y = u\_2…u\_{2k+1}$).

    In all cases, we can use the induction hypothesis to show that $w\in L^\*$.
> 2 votes

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


# Question
Title: A small question about generating random variable with geometric distribution
I was reading Professor Knuth's Volume 2 (page 136) about generating a geometrically distributed random variable $N$ (with $p$ as the probability of success). Basically, the idea is to generate a uniformly distributed random variable $U$ in $\[0,1\]$. Then, we can apply a simple formula $N = \left\lceil\frac{\ln(U)}{\ln(1-p)}\right\rceil$.

Additionally, Professor Knuth mentions a special case when $p=1/2$. Then, the aforementioned formula transforms into $N = \left\lceil -\log\_2 U \right\rceil$. And then he states that N is simply "one more than the number of leading zero bits in the binary representation of $U$. I'm confused by the last statement since I tried different interpretations of this statement and nothing gives the correct result:

1. Let's interpret the statement as it is. We consider the binary representation of real number $U$. On modern machines, this is either float or double. If we take float, then we have 1 bit for sign and then 8 bits for exponent. If we consider $U=0.25$ and $U=0.5$, we will see that the first 8 bits of their corresponding binary representations are $7d$ and $7e$, respectively. Binary representation have the same number of leading zeros, although $\log\_2(1/0.25) \not= \log\_2(1/0.5)$.
2. Let's assume that Knuth means binary representation of $\left\lceil 1/U \right \rceil$. Then, $\left\lceil \log\_2 \left\lceil 1/U \right \rceil \right \rceil$ is exactly what we need. But $\left\lceil \log\_2(x) \right \rceil = 32 - \mathrm{nlz}(x-1)$ for 32-bit integer, where $\mathrm{nlz}$ is the number of leading zeros. So this is again not what is originally proposed by the author.

Maybe you understand what was meant by Professor Knuth? Could you please explain it? Thanks in advance!

# Answer
* If $1/2 \leq U \< 1$ then $\lceil -\log\_2 U \rceil = 1$.
* If $1/4 \leq U \< 1/2$ then $\lceil -\log\_2 U \rceil = 2$.
* If $1/8 \leq U \< 1/4$ then $\lceil -\log\_2 U \rceil = 3$.

And so on.

Now,

* $1/2 \le U \< 1$ if the binary expansion of $U$ starts $0.1$.
* $1/4 \le U \< 1/2$ if the binary expansion of $U$ starts $0.01$.
* $1/8 \le U \< 1/4$ if the binary expansion of $U$ starts $0.001$.
> 2 votes

---
Tags: probability-theory, bit-manipulation
---


# Question
Title: Probability that two specific elements are in uniformly random sample
Consider the sampling algorithm as described here section 2.2 specifically Algorithm 2.4.

Essentially we are given a stream of $N$ elements and wish to maintain a uniformly random sample, $S$, of size $k$. Initially we put $k$ elements into $S$ and then for each iteration, $i \in \[k+1, N\]$ we choose a random number $x \in \[1,i\]$ and if $x \leq k$ we replace the $x$'th element from $S$ with the element seen at iteration $i$.

I see answers online e.g. here that after iteration $N$ each element from the stream has probability $k/N$ to be in the sample $S$. However what is the probability that two elements $x\_l$ and $x\_j$ where $l \neq j$ are both in the sample after iteration $N$? As i understand it the event that $x\_l$ is sampled is not independent from the event that $x\_j$ is sampled since we would have fewer slots to choose from when including $x\_j$ assuming it occurs later than $x\_l$ in the stream.

# Answer
Let us study the event that $x\_a$ and $x\_b$ are both in the reservoir at the end of the algorithm, where $k \< a \< b$.

In order for this to occur four things must happen:

1. On the $a$th iteration the random number must be $\leq k$.
2. Between the $a$th and $b$th iteration $x\_a$ must not be replaced.
3. On the $b$th iteration the random number generator must be $\leq k$ but also not equal the location of $x\_a$. WLOG we say that the random number must be $\leq k-1$.
4. For the remaining iterations neither $x\_a$ or $x\_b$ must be replaced.

This gives us the equation

$$p = \frac{k}{a} \cdot \prod\_{i=a+1}^{b-1}(1 - 1/i)\cdot \frac{k-1}{b}\cdot \prod\_{i=b+1}^n(1-2/i).$$

Left as an exercise to the reader, this solves to $$p = \frac{k}{a} \cdot \frac{a}{b-1}\cdot \frac{k-1}{b}\cdot \frac{(b-1)b}{(n-1)n},$$ $$p = \frac{(k-1)k}{(n-1)n}.$$

Thus the probability that $x\_a, x\_b$ are both in the sample is independent of $a, b$ when $k \< a \< b$. The case where $k \geq a$ is once again left as an exercise.
> 1 votes

# Answer
More generally, we can show that at any given time, the current sample is a random sample of $k$ elements out of all elements seen so far. The proof is by induction on $n$, the number of elements seen so far. The base case $n = k$ is clear.

Now suppose that we know the claim for $n$. Thus after seeing $n$ elements, we have a random sample $S$ of $k$ elements out of these $n$ elements. Now we are seeing a new element $x$. With probability $k/(n+1)$, we remove a random element from $S$ and replace it with $x$.

The probability that the chosen sample is a specific subset of $k$ elements out of the first $n$ elements is thus $$ \frac{1}{\binom{n}{k}} \cdot \frac{n+1-k}{n+1} = \frac{1}{\binom{n+1}{k}}. $$ Now suppose $T$ is a subset of $k$ elements out of the first $n+1$ elements which contains the new element $x$. There are $n-(k-1)$ choices for $S$, resulting from adding an element $y$ to $T - x$. The probability that $x$ replaced $y$ rather than some other element is $1/(n+1)$, and altogether the probability that $T$ is the chosen sample is $$ \frac{n-k+1}{\binom{n}{k}} \cdot \frac{1}{n+1} = \frac{1}{\binom{n+1}{k}}. $$ (In fact, this calculation must come out to be $1/\binom{n+1}{k}$, since all sets $T$ are equiprobable; but it is still instructive to see it.)
> 1 votes

---
Tags: algorithms, randomized-algorithms, sampling, streaming-algorithm
---


# Question
Title: Closure of context-sensitive languages under inverse language substitution
We define *language substitution* for a Context-Sensitive Language (CSL) $S$ over an alphabet $\Sigma$ is a map from $\Sigma$ into CSL's, for example: $f(abc) = L\_1(a) L\_2(b) L\_3(c)$ such that (I guess) the union of all $L(s)$ for $s \in f(S)$ is defined to be $L(f(S))$ and $L(f(S))$ is known to be a CSL itself.

That is my interpretation of language substitution for CSL's. Well languages are also closed under inverse of string homomorphisms, homomorphisms $f$ being a special case of language substitution in which each $a \in \Sigma$ gets mapped to a singleton language $L\_1(a) = \\{f(a)\\}$.

So my question is simple, yet probably hard or interesting to prove. That is, are CSL's closed under inverse of language substitution? Wikipedia is silent on this topic.

Let $f$ be a language substitution taking $S$ to $f(S)$. Then $f^{-1}(S) := \bigcup f^{-1}(s)$ I'm assuming. Is that a CSL?

# Answer
> 3 votes
Fix a universal Turing machine $T$.

Let $L\_1$ be the language of all sequences of configurations $c\_1 \\# c\_2 \\# \cdots \\# c\_\ell$ which describe a valid computation of $T$, starting with an arbitrary initial configuration $c\_1 \neq \epsilon$, and ending with a halting state; we do not allow any further configurations to appear. This language is clearly context-sensitive (it can be accepted in linear space even deterministically).

Let $L\_2$ be the language of all sequences of configurations $c\_1 \\# c\_1 \\# c\_2 \\# \cdots \\# c\_\ell$ such that $c\_1 \\# c\_2 \\# \cdots \\# c\_\ell \in L\_1$ (notice the initial configuration is repeated twice). This language is also context-sensitive.

Define a function $f$ from $\Sigma$ to CSLs by $f(\sigma) = \\{ \sigma \\}$ for $\sigma \neq \\#$ and $f(\\#) = \\{ \\#w : w \in L\_1 \\}$.

Notice that $f^{-1}(L\_2)$ consists of strings $c\_1\\#$, where $c\_1$ is an initial configuration of $T$ on which $T$ eventually halts. Thus $f^{-1}(L\_2)$ is not computable.

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