title: Hierarchical Paging memory requirements

text:
# Question
Title: Hierarchical Paging memory requirements
OS Book written by Galvin et all states that *if page size is 4KB and size of virtual space is 32 bits then 2^(32-12) page entries would be required which is too huge to store in memory!!*

Therefore it recommends to break it down by paging the inner page table as well. Now my question is how does that reduce memory requirements? Shouldn't inner page table and outer page table both be in memory and just the computational requirements reduce because inner page table can now be indexed quickly with the help of outer page table??

# Answer
Have you read Wikipedia's article on page tables?

There are two ways that a multi-level page table saves memory. First, you don't need to create parts of the page table for memory that isn't being used by the process: you only create the subtables for the parts of the virtual address space that are in use. Second, if you want to really live by the seat of your pants, you can use your virtual memory system to swap parts of the page table out of physical memory.
> 1 votes

# Answer
For an example take a scenario like this .

```
[2].                   [7]
[3].                   [8]
[4].                   [9]
[5].                   [10]

Inner              Second page table’
Page table’

```

So we can have 4 different addresses which starts with 2. (Ex:2,7/2,8/2,9/2,10). So like that there are 4 entries in the inner page table. So altogether there are 16 entries. But in the address space there are only 8. If we did not use multiple pages there would be 16. So this method reduces memory requirement.
> 0 votes

---
Tags: operating-systems, paging
---


# Question
Title: How to construct a max heap that preserves insertion order for duplicate elements?
I have a priority queue (using a max heap) that preserves insertion order for duplicate priorities, such that equal priorities fall back to FIFO behaviour. I'm doing this by creating a node with the value, the priority, and an 'insertion stamp' that is basically an incrementing number on the structure. I'd like to remove the need for this stamp, but I'm not sure if it's possible.

How might this work?

# Answer
> 3 votes
That's a perfectly reasonable approach. Use (priority, insertion timestamp) as the priority value for your heap, with comparisons using lexicographic order (compare by priority, breaking ties by insertion timestamp). That's all simple and easy to implement, and has no downsides that I can see.

Alternative, you can have one node in the priority queue per priority, with a pointer to a queue of items with that priority. That also works and is easy to implement.

---
Tags: data-structures, heaps
---


title: A TSP to HamCycle Reduction

text:
# Question
Title: A TSP to HamCycle Reduction
I'm referring to the decision version of both $TSP$ and $HamCycle$. The first is, given a graph $G=(V,E)$, a weight function $w:E\rightarrow \mathbb R^+$ and an integer $k$, is there a simple cycle with weight $\leq k$ which passes, once, through every vertex? (The weight of the cycle is the sum of the weights of the edges). The second problem is finding a Hamiltoninan Cycle (a cycle that passes through every vertex only once).

I know both are $NPC$. I am interested in finding reduction between both these problems. The first reduction $HamCycle \leq TSP$ is quite easy: for every edge in the original graph you give a weight $0$ and for every pair of vertices who did not have an edge you give a weight of $1$. Then you ask whether the agent can travel with sum of path $\leq 0$. The correctness of this follows pretty quickly.

However, my question if for the reduction the other way around: $TSP\leq HamCycle$. I could not come up with an idea for such. I am aware that since both are $NPC$ there exists a reduction through Cook-Levin Theorem and $SAT$, but I am wondering if there is a direct reduction $TSP\leq HamCycle$?

# Answer
By *direct reduction*, do you then mean a reduction that does not *leave the graph-world and go back again*? (that might be a very vague formulation, sorry). I do not think such a reduction exists. Of cause proving that it does not exist is not a simple matter, but at least I have not been able to find or think of one myself. But here's a couple of thoughts about why such a direct reduction is unlikely:

*TSP* is run on a fully connected graph with $n$ nodes and $n^2$ edges while *HamCycle* is run on a graph with $n$ nodes and $m \< n^2$ edges (otherwise it would be trivial). A solution to *TSP* must pass all nodes and contain no cycles and therefore must contain exactly $n$ edges. We could run *HamCycle* each on all possible paths of length $n$, starting from the one with the lowest edge-sum and continuing until we reach one that contains a Hamiltonian Cycle, but as there are ${{n^2}\choose{n}} = O(n^{2n})$ such possible paths, this would mean running *HamCycle* an exponential number of times. I can not see how you can avoid this.

You have most likely thought about this already, so this is mostly to say that you are not the only one who are not able to come up with such a reduction and I suspect that this may be because a reduction either has to be quite complicated or has to *leave the graph-world* somehow and go back again. Of cause there might exists a reduction that does *leave the graph-world* but is still simpler than going all the way through *SAT*, but I do not know of any such reduction.

I'm quite interested to see if anyone has a better answer to this.
> 2 votes

---
Tags: complexity-theory, np-complete, reductions, np-hard, decision-problem
---


# Question
Title: Why is the consensus number for test-and-set, 2?
According to Wikipedia,

> The test-and-set operation can solve the wait-free consensus problem for no more than two concurrent processes.

Why can't it solve the problem for more than two processes?

# Answer
Just to make sure we are on the same page, first let us consider these three definitions:

*Definition.* Test-and-set is a read-modify-write instruction on some binary register (let's just say that 0 and 1 are possible values) where a thread obtains the old value and writes 1.

*Definition.* Consensus is reached between $n$ threads iff all $n$ threads decide on the same value (the consistency requirement) and all threads decide on a value that was actually proposed by one of the threads (the validity requirement).

*Defintion.* A consensus protocol is wait-free iff every method call finishes in a finite number of steps.

Now follow two proof sketches.

**Claim 1.** The consensus number of test-and-set is at least 2. *Proof.* Suppose that we have two threads 0 and 1 that need to reach consensus. We could do this by letting each thread follow the consensus protocol below:

1. Write your proposed value to $A\[t\]$, where $t$ is the thread id and $A$ is an array of size 2.
2. Perform the test-and-set instruction on some register $R$, with $R$ initialised to 0.
3. If the return value is 0, you were first: return $A\[t\]$. Otherwise, you were second: return $A\[|t-1|\]$.

You can verify yourself that consensus and wait-freeness are satisfied. $\square$

(For the next proof, I will nest some proofs and definitions because I think it will make it easier to follow.)

**Claim 2.** The consensus number of test-and-set is at most 2. *Proof.* By contradiction. Suppose we have three threads $A$, $B$ and $C$ that wish to decide on values $a$, $b$ and $c$, respectively, and that we have some valid wait-free consensus protocol that is implemented using test-and-set (and atomic reads and writes).

We can visualise the consensus process as a directed tree, where:

* The root is the state where none of the threads have 'made a move';
* The left child of a node represents the state that results after a move by $A$, the middle child represents the state that results after a move by $B$, and the right child represents the state that results after a move by $C$;
* A leaf node represents a state in which all threads have finished. Associated with a leaf node is a value $a$, $b$, or $c$, where the value depends on which value was decided on for that particular execution.

*Definition.* Let a state be *multivalent* if the outcome of the consensus process is not yet determined. In other words, not all possible interleavings of the remaining moves lead to the same result. Let a state be *univalent* when the outcome of the consensus process *is* determined.

**The root is multivalent.** *Proof.* If only one thread $X$ is active and the other threads lie dormant forever, then $X$ will finish in a finite number of steps (guaranteed by the wait-freeness assumption) and it will decide $x$ (for it has only access to this value and its decision will satisfy the consensus validity requirement). So for our situation, $a$, $b$ and $c$ are all possible outcomes. $\square$

*Definition.* Let a critical state be a state which is multivalent, with the additional property that a move by $A$ will determine $a$, and a move by $B$ will determine $b$.

**There exists a critical state.** *Proof.* From above we know that we start in a multivalent state. Let $C$ make no move at all. As long as either $A$ or $B$ does not force the tree into a univalent state, let it make a move. Wait-freeness guarantees that the tree is finite, so at some point a critical state must be encountered. $\square$

Now consider a scenario where we are in a critical state. There are *at least* two possibilities:

1) $A$ makes its move (thereby determining $a$) and halts. $B$ then makes its move and halts. Next $C$ runs until it finishes, eventually deciding $a$.

2) $B$ makes its move (thereby determining $b$) and halts. Next $C$ runs until it finishes, eventually deciding $b$. $A$ does not make a move.

Since atomic reads and writes have consensus number 1, $A$ and $B$'s moves had to be test-and-set instructions on the same register (if the registers are different, then $C$ would not be able to tell the order in which $A$ and $B$'s moves happened). From $C$'s perspective, then, scenarios 1 and 2 are indistinguishable, so we must have that $C$ decides both $a$ and $b$. This is impossible. $\square$

That the test-and-set instruction has consensus number 2 follows from both Claims 1 and 2.
> 19 votes

# Answer
The wikipedia article does have a reference that answers you question, but perhaps you don't want to read that 26 page paper. I'll give a simplified version of the (quite technical) proof, showing that test-and-set can not solve binary consensus for 3 processes. This kind of argument is widely used in proving consensus numbers.

Let's suppose we have a consensus algorithm using TAS registers for 3 processes.

At any point in time, each process will have a move (instruction) ready to be executed. Which of the the three instructions will be executed is non-deterministic.

Suppose that we are in a bivalent state (a state in which both a 0 or a 1 decision is still possible) and whichever process moves next, the subsequent state will be univalent. Such a state must eventually be reached because of the wait-free condition.

Suppose (w.l.g.) that if process 1 moves, the state will be 0-valent, and that if process 2 moves, the state will be 1-valent. Both moves must be a TAS operation (or at least: some kind of write) on the same register, since if they were TAS operations on distinct registers we could not tell whether process 1 moved first or process 2 moved first.

Let's consider these two possible executions:

* Process 1 moves first, then process 2 moves, then process 3 runs alone
* Process 2 moves first, then process 3 runs alone

From the viewpoint of process 3, these states are indistinguishable since it just sees the value written by process 2. However, in the first case it should give 0 as output, and in the second 1 as output. Clearly, this is a contradiction.

Processes 1 and 2 can decide among themselves which moved first (because they can see what value was in the register before their write) but a third spectator process can not.
> 7 votes

# Answer
Another way to prove that test-and-set cannot be used to solve 3-processors consensus is to show that test-and-set can be implemented using 2-processors consensus. Then, assuming that test-and-set can solve 3-processors consensus leads to a contradiction: Suppose that test-and-set can solve 3-processors consensus; then by replacing test-and-set by its implementation using 2-processors consensus one obtains an implementation of 3-processors consensus using 2-processors consensus, which is impossible. Thus test-and-set cannot solve 3-processors consensus.

To implement test-and-set for n-processors using 2-processors consensus, let processors determine a winner of the test-and-set using a tournament in which each match is implemented using 2-processors consensus (in a match, the processors propose their identifier and the consensus result tells them who wins).
> 1 votes

# Answer
In practical sense a less strict consensus definition might be enough (here I call it light-consensus):

**Definition**. Light-Consensus is reached between n threads iff (a) each thread either decides on the same value or the value is unknown for it, (b) at least one thread knows the value and (c) this value was actually proposed by one of the threads.

Hence this consensus in its lighter sense permits that some thread does not know the consensus, the value that is decided.

**Corollary**: In this lighter sense test-and-set has infinite light-consensus number.

**Claim**: This lighter sense is practical. For instance in order to select the thread to enter the critical section it is not necessary to create consensus in the strict sense. That is to say: each thread has to know whether it has been selected or not, however if it is not selected than it won't have to know which was selected. In other words, for mutual exclusion strict-consensus is not necessary, light is enough.
> 0 votes

---
Tags: concurrency, consensus
---


# Question
Title: Solving the emptiness problem for a CFG in Chomsky normal form (linear)
Given a CFG in Chomsky normal form, is there an algorithm that solves the emptiness problem in linear runtime? I thought about using depth search here, but I think it's a little bit above linear runtime.

# Answer
> 8 votes
Yup, it can be done. For each nonterminal $A$, introduce a boolean variable $x\_A$, with the intent that if $x\_A$ is true, that means $L(A)$ is non-empty. Then you can convert each production into a corresponding Horn clause:

* $A \to BC$ becomes $(x\_B \land x\_C) \implies x\_A$
* $A \to a$ becomes $x\_A$
* $S \to \varepsilon$ becomes $x\_S$

Let $\varphi$ denote the conjunction of these Horn clauses. Find the minimal satisfying assignment for $\varphi$; that can be done in linear time. If this assignment makes $x\_S$ true, then the language is non-empty, otherwise it is empty.

---

Alternatively, if you prefer a more direct algorithm, here is a standard one that you might see in textbooks.

Start out with all nonterminals unmarked. If you see a rule $A \to a$, mark $A$. If you see a rule $S \to \varepsilon$, mark $S$. Whenever you mark a nonterminal, check all rules of the form $A \to BC$ where it appears on the right-hand side; if both $B$ and $C$ are marked, mark $A$. Repeat until convergence. At that point, all marked nonterminals correspond to nonterminals that generate a non-empty language, so the language is non-empty iff $S$ is marked.

This also runs in linear time. It takes a little more work to see why, but it's true. In particular, each nonterminal can only be marked once, and each rule of the form $A \to BC$ will only be checked at most twice (once when $B$ is marked, once when $C$ is marked), so the amount of work you do is $O(1)$ per nonterminal plus $O(1)$ per rule, which is linear in the size of the grammar. It does require suitable data structures that map from each nonterminal to a list of all rules containing it on the right-hand side, but that can be built in advance in linear time as well.

---
Tags: context-free
---


# Question
Title: How to make smart contracts work in a small network?
Suppose we have a small computer network, there are 30 random people who have provided their computers to perform any computational tasks on them. Let's call these 30 computers nodes. We can access any of these 30 nodes arbitrarily, but by the condition of the problem, we do not know whether the node is honest. That is, we can not guarantee that the node will execute exactly the f (x) that we send to it, or that the node will certainly give us the correct answer.

Also, we have, by condition, A and B that want to conclude a smart contract with each other. A smart contract is a code (usually a small one, 15-25 lines long), whose body will certainly execute when a certain condition is set in the code.

In our case, the smart contract says that if event E1 occurs, B will pay A from its account, and if event E2 occurs, then A will pay B (how exactly will the payment in details not be discussed, it will occur within this network, using conventional cryptocurrency algorithms in the classic blockchain, for example).

The problem is that neither A nor B can guarantee if they entrust the execution of the smart contract code to a random node from our network that it will be executed correctly. One node can execute the received code in reverse or not execute at all. **So which cryptographic algorithm A and B can use to ensure (statistically) the correct execution of the concluded smart contract?** As already mentioned, they can use the services of any of the 30 nodes as you like.

I thought about dividing the smart contract into small parts and dividing them one by one into each of the 30 nodes, but how would this help if some dishonest nodes still execute their code incorrectly? We can easily find a dishonest node and exclude it, but a smart contract must be executed correctly the first time - that is, certainly, and not after the selection of honest nodes. When one of the nodes behaves incorrectly, the entire smart contract will already be executed incorrectly.

# Answer
> 2 votes
One approach is to use a system like Ethereum, Truebit, or their successors. In Ethereum, every node checks that the smart contract was executed correctly. In Truebit, there is a sophisticated way to assign the contract to untrusted nodes and check that they executed it correctly.

Another approach is to use trusted hardware, like SGX.

There are probably other options as well.

I suggest reading up on those systems. There's lots written on them.

---
Tags: computer-networks, cryptography
---


# Question
Title: Fastest way to check data against an envelope
If I have two arrays containing max and min points which make up an envelope. It's quick to test if any point in a given data array goes outside of that envelope using:

```
 for (int i = 0; i < envMax.size(); i++)
    {
        if ((data[i] < envMin[i]) || (data[i] > envMax[i]))
        {
            return false;
        }
    }
    return true;

```

However, my data array can be large and I have to load the max and min envelope data from a file for each new data array which needs testing (just the way the system works). So it might be quicker to just use a smaller number of points for the envelope and interpolate. But whats the quickest way of doing this with a reduced number of points. I can do (sudo code):

```
for each data point
find min and max envelope point before and after data point
calculate equation of line between two points
put in data "x" value
check resultant y value.

```

Alternatively I can just generate N max and min envelope points (where N is = length(data)) (same thing really)...

But this seems computational exhausting. I can't believe I am the first person to want to do this so is there an accepted (fastest) method / algorithm type?

EDIT:

The problem is essentially this: Check that the blue line is within the green lines. But doing it when the number of points describing the green lines is much less than the number of points describing the blue line.

# Answer
From the short description you give, I infer that you consider that fetching the envelope data from disk is a bottleneck.

Even assuming that the envelope values change with every dataset (so that there is no reuse), you figure seems to show that there are as many data points as there are envelope points. So if you completely avoided the fetching of the envelope, you could at best hope for a threefold improvement, and virtually no improvement in case there is reuse.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Non-trivial bin-packing instance with 5 objects
Bin packing problem is a problem, where one has to find the minimum number of bins of size $v$ required to store $n$ objects of sizes $s\_1, \ldots, s\_n$. Object sizes are never greater than $v$.

For example, if $v = 10$ and the objects sizes are $2, 5, 4, 7, 1, 3, 8$, we can store objects with 3 bins: \[8, 2\], \[7, 3\], \[5, 4, 1\], but not with 2 bins or less, as this would leave some items unpacked. Therefore 3 is the minimum number of bins required.

The best-fit-decreasing heuristic is a packing strategy, which aims to produce a packing close to optimal. It first sorts all the items in descending order. Then it iterates over all items, and for each item attempts to find an existing bin, which can both fit the item and whose spare capacity is closest to the size of the item. If such bin exists, it puts the object in the bin. If it doesn't, it creates a new bin and puts it there.

A non-trivial bin-packing instance is an instance of the problem, which can't be optimally solved by the best-fit-decreasing heuristic.

For example, the instance $v = 7$, $n=6$ where sizes are $3, 2, 3, 2, 2, 2$ is non-trivial, because the best-fit decreasing heuristic will:

1. Sort the items to give $3, 3, 2, 2, 2, 2$
2. Put the first two items in the first bin, producing a bin $\[3, 3\]$
3. Put the next three items in the second bin, producing a bin $\[2, 2, 2\]$
4. Put the last item in the third bin, producing a packing $\[3, 3\], \[2, 2, 2\], \[2\]$

This is a valid packing, but non-optimal, as it requires 3 bins, and there exists a valid packing with two bins: $\[3, 2, 2\], \[3, 2, 2\]$.

Is there a non-trivial bin-packing instance with $n=5$?

# Answer
> 1 votes
Let's look at two algorithms: Best Fit Ordered, and First Fit Ordered. Both take the items in descending order and put them into a non-empty bin if possible, or into a new empty bin if they don't fit into any existing bin. Best Fit Ordered puts an item into the filled bin with least available space, First Fit Ordered puts an item into the first filled bin with enough space.

Question: Are there five items A ≥ B ≥ C ≥ D ≥ E such that BFO or FFO are not optimal?

If all items fit into one bin then BFO and FFO will fit them into one bin, because both will just put items in the first bin. Both are optimal.

If five bins are optimal then BFO and FFO cannot be non-optimal, since they can't use more than five bins.

If four bins are optimal then there are two items fitting into one bin, therefore D and E fit into one bin, therefore when BFO and FFO finally try to find a bin for E, either four bins are filled and E fits into the bin with D, or there are only three bins filled and E goes into the fourth bin.

So the only cases to consider are those where two or three bins are optimal. I'll consider cases systematically:

A, B and another fit -\> 2 bins, BFO and FFO are optimal A, B fit, C, D, E fit -\> 2 bins, BFO and FFO are optimal A, B fit, C, D, E don’t fit -\> 3 bins required, BFO and FFO are optimal.

We now assume A and B don't fit into a bin, so A goes in the first and B in the second:

A, C and another fit -\> 2 bins, BFO and FFO are optimal A, C fit, B, D, E fit -\> 2 bins, BFO and FFO are optimal A, C fit, B, D, E don’t fit: A, D, E don’t fit, A, D or A, E doesn’t help -\> 3 bins required -\> BFO and FFO are optimal.

We now assume neither A and B, nor A and C, fit into one bin. If B and C don't fit, then A, B, C go in three different bins. 3 bins are optimal, so D and E can be made to fit, and BFO and FFO will both find a way.

So we assume B and C fit in one bin. Both BFO and FFO will fit them in one bin. D E must also fit into one bin, so if three bins are optimal, then BFO and FFO will find a solution.

If two bins are optimal, then one bin must contain A, one must contain B and C. D and E fit, so BFO and FFO will fit them.

# Answer
> 0 votes
Interesting little brainteaser. The answer likely depends on your precise definition of "optimally solved". But if you mean "solved with the least number of bins", then the answer is no. The algorithm will always find an optimal solution.

Think about it this way. The optimal solution for 5 items needs to be a two-bin solution. A one-bin solution will always be found by the algorithm. For a two-bin solution, it is trivial to see that the algorithm needs to place the first two items in the first bin, while the optimal solution has them spread over two bins.

Then the reasoning is as follows: the algorithm will place $s\_{1}$ and $s\_{2}$ in bin 1, $s\_{3}$ and $s\_{4}$ in bin 2, and $s\_{5}$ in bin 3, which implies that: $$ s\_{3} + s\_{4} + s\_{5} \> v $$

One optimal solution would be to fit item $s\_{3}$ and $s\_{5}$ in with $s\_{2}$, because there is more room left over there. Then $s\_{4}$ goes in with $s\_{1}$, necessarily leaving some space there. If that all does not fit, then there is no optimal solution with 2 bins.

For that to work, it needs to be true that: $$ s\_{2} + s\_{3} + s\_{5} \leq v $$ Which necessarily implies that: $$ s\_{3} + s\_{4} + s\_{5} \leq v $$ because $s\_{4} \leq s\_{2}$.

But that means that the algorithm would have been able to put $ s\_{3}$, $s\_{4}$, and $s\_{5}$ together in the second bin.

---

You might think that an optimal solution for 3 bins would be possible, with the algorithm taking 4 bins. But it is easy to see that that is not possible.

The optimal and the algorithm solutions need to differ in the first bin already. If not, then you can imagine replacing whatever items are placed there with one large item, giving you a solution for 4 items. For the optimal solution to beat the algorithm, the algorithm must place a second large item in the first bin, while two smaller ones would fit there. That can only be $x\_2$ or $x\_3$, for otherwise there are no two items left over. That implies that that item, and all the remaining ones, are all smaller than $\tfrac{1}{2}v$. But in that case it is trivial to put the remaining items in the third bin.

---
Tags: algorithms, combinatorics, packing
---


# Question
Title: Are process-safe mutexes shared between OSes?
I understand you can use process wide mutexes, but does this still apply if you have an additional virtualized operating system provisioned?

For example, take two OSes: `O1` and `O2` where `O2` is a virtualized OS provisioned on `O1`. Now take some code `C` that uses a process-wide mutex. Run `C` on `O1` **and** `O2`. Assuming they have access to the same resource through some file sharing mechanism (e.g. guest additions.) Does the mutex still work?

# Answer
For most implementations of a mutex it won't work, but in principle it depends on how the mutex is implemented. If the mutex was implemented using files, perhaps it could be made to work. Usually the mutex is managed by the operating system, and the operating system keeps track of the state of the mutex, so both processes have to be running in the same operating system to be able to share a mutex.
> 2 votes

---
Tags: operating-systems, concurrency, os-kernel
---


# Question
Title: Mathematical conjectures equivalent to the halting of a Turing machine
This question is about whether every mathematical theorem can be reduced to the question of whether a single Turing machine halts. In particular, I'm interested in conjectures that are currently unproven.

For example: Wikipedia says that it's currently unknown whether there are any odd perfect numbers. Since it's decidable whether a given number is perfect, one could write a Turing machine that checks each odd number in turn and halts if it finds one that's perfect. (This Turing machine does not take any input.) If we knew whether that Turing machine halts, then we would know whether the conjecture is true, and vice versa.

However, as another example, what about the twin primes conjecture? It's decidable whether a given number is the first prime in a twin pair, but in this case we can't just halt when we find the first one, because the question is about whether there are an infinite number. It's not clear to me whether it's possible to make a Turing machine that halts if and only if the twin primes conjecture is true.

We can surely make a Turing machine that halts if and only if the twin primes conjecture is *provable* within Peano arithmetic or some other formal system, but that's a different question, since it might be true but not provable in the particular system we choose.

So my questions are

* Is it possible to make a Turing machine that halts if and only if the twin primes conjecture is true? (And if so, how?)
* Is it possible, in general, to make a Turing machine that halts if and only if some given mathematical statement is true? Can this Turing machine be constructed algorithmically from the formal statement?
* If it's not possible in general, is there some way to classify mathematical statements into whether they're equivalent to the halting of a single Turing machine, or a turing machine with an oracle, etc.? If so, is this classification decidable for a given statement?

# Answer
> 13 votes
Your question is answered by the arithmetical hierarchy. The existence of an odd perfect number is a $\Sigma\_1$ statement, and so you can test it using a $\Sigma\_1$ machine, which halts iff the statement is true. The twin prime conjecture is a $\Pi\_2$ statement, and so you can construct a TM with access to the halting oracle which halts iff the statement is false.

In a strict logical sense, you can always make a Turing machine that halts iff statement $\phi$ holds:

1. If $\phi$ holds, then take a machine which halts.
2. If $\phi$ doesn't hold, then take a machine which doesn't halt.

To see that this construction is valid, consider the logical form of your statement:

$$ \forall \phi \exists T . \phi \Leftrightarrow T\text{ halts}. $$ You can clear this confusion up by asking a slightly different questions:

> What is a set of statements $\Phi$ such that there exists a Turing machine which halts on $\phi \in \Phi$ iff $\phi$ is valid?

Above I have indicated that $\Sigma\_1$ statements form such a set.

# Answer
> 0 votes
Let $f(1)=2$, $f(2)=4$, and let $f(n+1)=f(n)!$ for every integer $n \geq 2$. For a positive integer $n$, let $\Theta\_n$ denote the statement: if a system

$$S \subseteq \\{x\_i! = x\_k: i,k \in \\{1,\ldots,n\\}\\} \cup \\{x\_i \cdot x\_j=x\_k: i,j,k \in \\{1,\ldots,n\\}\\}$$

has only finitely many solutions in integers $x\_1,\ldots,x\_n$ greater than $1$, then each such solution $(x\_1,\ldots,x\_n)$ satisfies $\min(x\_1,\ldots,x\_n) \leq f(n)$. We conjecture that the statements $\Theta\_1,\ldots,\Theta\_{16}$ are true.

The statement $\Theta\_{16}$ proves the implication: if there exists a twin prime greater than $f(16)+3$, then there are infinitely many twin primes, please see this paper by A. Tyszka (*On sets $W \subseteq \mathbb{N}$ such that the infinity of $W$ is equivalent to the existence in $W$ of an element that is greater than a threshold number computed with using the definition of $W$*)

That is, assuming the statement $\Theta\_{16}$, a single query to $0'$ decides the twin prime problem.

---
Tags: formal-languages, computability, mathematical-foundations
---


# Question
Title: If $V$, $E$ and $F$ is respectively the number of vertices, edges and faces in a maximally triangulated graph, then why do we have $3F = 2E$?
Suppose we have a *maximally triangulated graph* $G$, where $V$, $E$ and $F$ is respectively the number of vertices, edges and faces. The following graph should be a maximally triangulated graph.

Apparently, the equation $3F = 2E$ holds for $G$. Why (intuitively) is this the case?

# Answer
> 1 votes
Every face is a triangle (hence, the name, "maximally triangulated graph"). Every face is thus composed of three edges (or sides). So, if we have $F$ faces, then we may be tempted to say that there are $3F$ edges. This is **not** the case because an edge contributes to exactly $2$ faces. So, in $3F$ we are counting every edge twice. So, $\frac{3F}{2} = E \iff 3F = 2E$.

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


# Question
Title: Prove that, if deg(v) ≥ (n−2)/3 for every vertex v in G, then G contains at most two connected components
Let G be a graph with $n$ vertices such that $n\geq2$. Prove that, if $\mathrm{deg}(v)\geq \frac{n-2}{3}$ for every vertex $v$ in G, then G contains at most two connected components.

# Answer
> 1 votes
Assume there are are at least 3 connected components. Then there must be a connected component of size $\le\frac{n}{3}$. Let $v$ be a vertex in that connected component. By assumption we have $deg(v)\ge\frac{n-2}{3}$. Since the size of that connected component is at most $\frac{n}{3}$ than it must be that $deg(v)\le\frac{n}{3}-1=\frac{n-3}{3}$. So we get both $deg(v)\ge\frac{n-2}{3}$ and $deg(v)\le\frac{n-3}{3}$, a contradiction. Thus, there must be at most 2 connected components.

---
Tags: graphs, discrete-mathematics
---


# Question
Title: Proving $L'=\{uv : u \in L \; \land v \in L^R \; \land |u|=|v|\}$ is a CFL with closure properties
Given a language $L$ over $\Sigma=\\{a,b\\}$ let us define $L'=\\{uv : u \in L \\; \land v \in L^R \\; \land |u|=|v|\\}$

Prove: if $L$ is regular, then $L'$ is a context free language.

---

I know how to solve it by building a push down automaton and proving it acceps $L'$, but I'm trying to solve it by using closure properties of context free languages (e.g closure under homomorphism, intersection with a regular languae, etc.) but I couldn't think of such solution. Any ideas?

# Answer
Let $\tilde\Sigma = \\{\tilde a,\tilde b\\}$. It is well-known that the language $X = \\{a^n b^n : n \geq 0\\}$ is context-free. Let $h \colon \Sigma \cup \tilde\Sigma \to \Sigma$ be the homomorphism defined by $h(a) = h(b) = a$ and $h(\tilde a) = h(\tilde b) = b$. The following language is context-free: $$ h^{-1}(X) = \\{uv : u \in \Sigma^\*, v \in \tilde\Sigma^\*, |u| = |v| \\}. $$ Let $t\colon \Sigma \to \tilde\Sigma$ be the homomorphism defined by $t(a) = \tilde a$, $t(b) = \tilde b$. The following language is regular: $$ Lt(L)^R = \\{ uv : u \in L, v \in t(L)^R \\}. $$ Since the context-free languages are closed under regular intersection, it follows that the following language is context-free: $$ h^{-1}(X) \cap Lt(L)^R = \\{ uv : u \in L, v \in t(L)^R, |u| = |v| \\}. $$ Finally, let $s\colon \Sigma \cup \tilde\Sigma \to \Sigma$ be the homomorphism defined by $s(a) = s(\tilde a) = a$, $s(b) = s(\tilde b) = b$. The following language is context-free: $$ s(h^{-1}(X) \cap Lt(L)^R) = \\{ uv : u \in L, v \in L^R, |u| = |v| \\}. $$ This is the language you're interested in.
> 2 votes

# Answer
Here is another solution, using context-free grammars. Let $\langle Q, \Sigma, q\_0, \delta, F \rangle$ be an NFA for $L$, where $\Sigma = \\{a,b\\}$. We construct a context-free grammar whose non-terminals are $Q \times Q$. The starting symbol is $(q\_0,q\_0)$. For every $q\_1,q\_2 \in Q$ and $\sigma\_1,\sigma\_2 \in \Sigma$ we have the production $$ (q\_1,q\_2) \to \sigma\_1 (\delta(q\_1,\sigma\_1),\delta(q\_2,\sigma\_2)) \sigma\_2. $$ For every $f\_1,f\_2 \in F$, we have the production $$ (f\_1,f\_2) \to \epsilon. $$ A simple induction shows that for all $q\_1,q\_2$, we have $$ (q\_1,q\_2) \Rightarrow^\* w\_1 (p\_1,p\_2) w\_2 $$ if and only if $p\_1 = \delta(q\_1,w\_1)$, $p\_2 = \delta(q\_2,w\_2^R)$, and $|w\_1| = |w\_2|$. Any word produced by the grammar must be produced via a derivation $$ (q\_0,q\_0) \Rightarrow^\* w\_1 (f\_1,f\_2) w\_2 \Rightarrow w\_1w\_2, $$ where $f\_1,f\_2 \in F$. From here it is easy to check that $w\_1 \in L$, $w\_2 \in L^R$, and $|w\_1| = |w\_2|$. The converse is also easy to check. Therefore this grammar generates $L'$.
> 1 votes

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


# Question
Title: Suffix array construction algorithm linear complexity constant
A non-recursive linear Suffix Array construction algorithm is presented in this thesis: Linear-time Suffix Sorting. The author claims that, overall, the algorithm runs at $O(n)$. While it is well explained, there are only hints that this is case. The implementation of the algorithm is in this GitHub repository written in C.

My question is: What are the complexity constants (say $O(\alpha n + \beta)$ where $\alpha$ and $\beta$ are constants) for C code between lines 92 and 186?

# Answer
> 1 votes
Constants like this are generally not calculated for the run time of algorithms, because it's not clear what they would count - would they count the number of some sort of primitive C operation executed, or the number of x86-64 operations, or the number of arm64 operations, or the microcode operations, or ...?

More frequently than *calculating* the constants, people *measure* the run time and show the $\alpha$ that fits best. They will also sometimes calculate the number of times a specific operation is executed, like comparisons or swaps in a sorting algorithm.

---
Tags: algorithm-analysis, time-complexity, suffix-array
---


# Question
Title: Is z-buffering the same as rasterization?
I understand z-buffering as being "object-first" in contrast to "pixel-first" since the for loop starts with checking each triangle in the scene rather than each pixel. However, is this the same as rasterization, or is rasterization just a general technique that encompasses z-buffering?

# Answer
> 3 votes
Z-buffering is easy to implement depth-buffering, where you check whether pixel is visible or not (in case of transparency, it is handled separately). This is optimisation to avoid calculating color at every pixel but instead check which are nearest to the screen, paying with memory.
Rasterization is general technique converting vector graphics into rasters, including filling triangle with pixels. Different technique is to use raytracing or photon mapping, in that case triangles are not rasterized (as in scanline rasterization) but rays (photons) are cast and traced.

So, yes, z-buffering is part of realisation of rasterization.

---
Tags: graphics
---


# Question
Title: Does an algorithm exist for scheduling jobs on two processors?
I have two processors, and I want to schedule as many jobs as I can. I have their starting time and finishing time, and each job has to be unique to a processor (no overlap). I looked around and found one processor, or `n` processors - but none for two. I thought it'd be popular but I can't find if anyone's done this before?

My idea is just like the normal interval scheduling algorithm, to implement a greedy approach. First, sort by earliest starting time. Then, start by scheduling the first job to the first processor. The second job to the second processor. From there, schedule the next job to the processor who is going to finish their job first.

I think it would work, but I think this is in `O(n^2)` time and I'm trying to get to `O(n)` or `O(n log n)`

Any help is appreciated :)

# Answer
The algorithms for $n$ processors will do the job just fine for the 2-processor case. In this context, $n$ does not refer to the number of tasks to be scheduled, which probably caused the confusion when you looked for algorithms.

Then, there is a great website for searching for scheduling problems, which you can access at http://www-desir.lip6.fr/~durrc/query/ -- You select the properties of your problem and will receive an overview of known results. Your case is called $P2 \mid r\_j \mid C\_\mathit{max}$ on that page. This is not quite your setting, as this assumes that the finishing times are the same for all tasks. But even in this slightly easier case, the web page gives you a reference for an NP-completeness proof for your problem:

Complexity of machine scheduling problems, Lenstra, J.K. and Rinnooy Kan, A.H.G. and Brucker, P., Ann. of Discrete Math., Vol. 1, p.343-362 1977.

So your algorithm will probably not yield a feasible schedule whenever there exists one.
> 3 votes

---
Tags: algorithms, runtime-analysis, greedy-algorithms, scheduling
---


title: Context-free grammar from language

text:
# Question
Title: Context-free grammar from language
I'm trying to come up with a context-free grammar for the following language:

$$L = \\{a^mb^nc^{m+n}\mid 0 \le n \le m\\}$$

My thinking is that i can rewrite this to

$$L = \\{a^mb^nc^nc^m\mid 0 \le n \le m\\}$$

and then create the grammar

$$ \begin{align\*} S &\rightarrow aSc \mid B\\ B &\rightarrow bBc \mid \epsilon \end{align\*} $$

The problem is that this grammar doesn't capture $0 \le n \le m$ and I can't figure out how to do this. Any help would be greatly appreciated.

# Answer
> 1 votes
Hint: is the language $L' = \\{a^n b^n c^{2n} \mid n \ge 0\\}$ context-free?

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


# Question
Title: What is the time complexity of MergeSort without its penultimate merge?
As in, with the two final sublists which are sorted arrays, let's say just for this example (yes it is no longer fully MergeSort but I am interested in the time complexity only), that we finish with a constant time operation involving the two sublists. MergeSort in worst case is $O(n\log(n))$, and not having the final merge would definitely lead to greater efficiency than this, but by how much? Again, I understand that MergeSort has not completed it's full run, I am only interested with its time complexity for my specified run only.

# Answer
It will still take $O(n \log n)$.

There are four steps in mergesort.

1. Divide the list in half.
2. Mergesort the left half.
3. Mergesort the right half.
4. Merge the two together.

If I understand right, you're asking about removing the fourth step, *in the final stage only* (that is, not in any of the recursive calls).

In this case, you'll still have to do step 1 in $O(1)$, step 2 in $O(\frac{n}{2} \log \frac{n}{2})$, and step 3 in $O(\frac{n}{2} \log \frac{n}{2})$ (since steps 2 and 3 still call conventional mergesort, which is $O(n \log n)$).

So your total time complexity will be $O(1 + \frac{n}{2} \log \frac{n}{2} + \frac{n}{2} \log \frac{n}{2}) = O(n \log \frac{n}{2}) = O(n \log n)$.

The final merging only takes $O(n)$ time; it's the recursive part that's the real cost.
> 1 votes

---
Tags: time-complexity, mergesort
---


# Question
Title: Are there any estimated, imperfect or fuzzy sorting algorithms?
I'm implementing some estimation metrics that take samples of optimisation functions and estimate their properties. One of the metrics requires the data to be sorted; however, since the metric is only an estimation, I was wondering if I could get a comparatively accurate result if the data wasn't sorted precisely, but *well enough*.

I would expect data could be *nearly* sorted in less time than actually sorting it. However, I can't find any algorithms that will do this, which I find rather odd, so I thought I'd ask around here.

My idea of "imperfectly sorted" is quite loose. It could, for example, mean:

* Many elements are perfectly sorted, but some are not
* Adjacent elements are not necessarily in the correct order, but when comparing groups of elements, the elements increase on average; if plotted, there would be a visible general upwards trend

For the first definition above, I suppose you could take a sub-sample of the data and just quick-sort that, but I don't imagine it'll get you much of a performance improvement without seriously reducing the quality of the estimation.

It might also be possible to take something like quicksort and limit the depth of the recursion.

Do imperfect sorting algorithms exist? Can they significantly out-perform regular sorting algorithms?

# Answer
> 3 votes
The term you're looking for is *approximate sorting*. This is a topic that, as greybeard mentions in a comment, was more popular back in the 90s. But it's quite helpful for *presorting* (e.g. getting an array a little bit sorted to ensure that Quicksort doesn't get stuck in its worst case), and this is what's led to most of the research in the area.

You can, in fact, make it somewhat faster than full sorting. Giesen, Schuberth, and Stojaković showed that you can get $n$ elements sorted to a Spearman distance (\*) of $\frac{n^2}{\nu(n)}$ in $O(n \min(\log n, \log \nu(n)))$. So the more you're willing to sacrifice accuracy (the smaller you make $\nu(n)$), the faster the algorithm can run.

Giesen, Schuberth, and Stojaković also present a very simple algorithm to do this approximate sorting, either deterministically or with a bit of randomness mixed in. The full details are in the linked paper, but basically they use Quicksort's partitioning a limited number of times and don't care about the order of the elements between the partitions, as long as they end up in the right "bin". If you pick your partitions well, this is in fact equivalent to running Quicksort and limiting the recursion depth.

(\*) The Spearman footrule distance between two sequences is the sum of the distance between each element's intended position and its actual position. So if you swap two elements, that leads to a Spearman distance of 2: those two elements are each one position away from their intended place.

---
Tags: algorithms, sorting, nondeterminism, fuzzy-logic
---


# Question
Title: Describe briefly how analogue data differs from digital data.
I was wondering if you could help me to understand the difference between analogue and digital data. I looked it up online but couldn't find a proper answer. If for any reason this is the wrong site for my question please guide me to the correct site, Thank you.

# Answer
> 1 votes
The simplest answer is: analog data is continuous, while digital data is quantized. In other words, a signal that at any point in time might have any real value between 0 and 1 would be considered analog. A signal that at any point in time has a value of either 0 or 1 would be considered digital.

---
Tags: data-sets
---


# Question
Title: Necessity to define co-NP in the first place?
I've recently started to deal with complexity theory and I'm trying to wrap my head around all the definitions and why they make sense.

One thing I don't quite understand is the importance/necessity of co-NP as its own set/class of problems. Couldn't for example TAUT be classified as a NP-complete problem just like SAT or is there some specific motivation to not put complements of a problem in the same set as the problem itself?

I'm sorry if this has been asked before or if my question is silly and doesn't make sense at all (In this case I'd like to know why if possible), I've really tried to look for it beforehand on the internet.

Kind regards,

# Answer
> 1 votes
Note that we don't know if $\text{NP=coNP}$. In fact, it is believed that they are not equal. Also note that the $\text{NP-complete}$ class requires its languages to be both $\text{NP-Hard}$ and in $\text{NP}$, so we can't say (unless proven $\text{NP=coNP}$) that $\text{TAUT}\in\text{NP}$.

The difference from $\text{P}$ is that to get the complement language, one can not just swap the $yes$ and $no$ instances of the Non-Deterministic Turing Machine, since its definition of accepting requires that there **exists** a computational path for which it accepts the input, and for rejecting it requires that **all** paths must not end in an accepting state.

One thing that is interesting about $\text{coNP}$ is that it describes the set of problems for which there is an easy way to verify that there is a $no$ instance for (i.e, verify a counter-example to the problem).

# Answer
> 2 votes
We don't *define* problems to be **NP**-complete. We define classes of problems, define the concept of completeness for those classes, and then *prove* that problems are complete, because they have the properties that define completeness.

Analogously, we don't define 13 to be prime; rather, we define the property of being prime and then prove that 13 has that property.

---
Tags: complexity-theory, co-np
---


# Question
Title: Maximizing the sum from m stacks using k pop's
Assume you have **m** stacks each some elements within it. If you are allowed to do **k** pops , the objective is to maximize the sum(*sum increases by the value of the popped element*). What is the best algorithm which would be able to solve this problem.
Can the complexity be improved if the details of the elements in each stack is known beforehand.

# Answer
You can use dynamic programming to solve this problem in polynomial time. Create a table $A\[i,l\]$ with $0\le i \le m$ and $0\le l\le k$, where $A\[i,l\]$ reprensents the optimal allocation using at most $l$ pops among the first $i$ stacks. We initiate by $A\[.,0\]=A\[0,.\]=0$ and we have the following inductive step : $$ A\[i+1,l\]=\max\left\\{A\[i,l-t\]+(t \text{ pops from stack } i+1), 0\le t \le l\right\\} $$ We can compute $A\[m,k\]$ in time $O(k^2m)$.
> 3 votes

---
Tags: algorithms, complexity-theory, stacks
---


# Question
Title: In the Traveling Salesperson Problem, is the shortest tour the same regardless of the start/return city? How do you prove it?
This is the form of the problem where you start at a city, visit every other city, and return to the start city. Since you "return" to every city in the completed cycle, it seems intuitive that the cycle would be the same regardless of the starting city.

# Answer
From an intuitive standpoint, no matter where you start on the path, the length of the whole path will remain the same.

More formally:

Suppose you have a valid solution to TSP for a given graph: that is, an ordering $a,b,c,d \cdots j,k,l,m \cdots x,y,z,a$ that contains every vertex and has the minimum length. Let $k$ be an arbitrary vertex in this sequence. (I've named them in alphabetical order for convenience, but of course there might be more or less than 26, depending on the graph.)

We know that the length of this cycle is the same as the length of the path $a,b \cdots j,k$ plus the length of the path $k,l \cdots y,z,a$ (by the definition of path length).

Now, let's change the cycle to start and end at $k$ instead. In other words, make a new cycle $k,l \cdots y,z,a,b \cdots j,k$. By the definition of path length, the length of this cycle is the length of $k,l \cdots y,z,a$ plus the length of $a,b \cdots j,k$. All we've done is changed the order of these two sub-paths within the cycle.

Since addition is commutative, the length of the cycle starting and ending at $a$ must be the same as the length of the cycle starting and ending at $k$. So, since $k$ is an arbitrary vertex, the length must be the same no matter which vertex you start and finish at.

EDIT: The question was clarified, so here's a better explanation of the part you're looking for.

Suppose you can get a shorter cycle by starting and ending at some arbitrary node $k$. By using the technique above, you can show that this shorter cycle can be converted to a cycle of equal length starting and ending at $a$.

But the assumption was that your original cycle was the shortest: otherwise it wouldn't be a solution to the TSP. Contradiction!
> 2 votes

# Answer
The optimal tour visits all vertices so it's still a tour regardless of where you start. The length of the tour is the sum of the lengths of its edges. Addition is commutative and associative so it doesn't matter what order you do the addition.
> 3 votes

---
Tags: traveling-salesman
---


# Question
Title: Prove/Disprove: If $A _{\leq M} B$ and $B _{\leq M} A$ then $A=B$
> Given $A, B$ languages over $\Sigma,$ Prove/Disprove: If $A \_{\leq M} B$ and $B \_{\leq M} A$ then $A=B$.

I would like to disprove this claim, with the languages $H\_{TM}$ and $H\_\epsilon = \\{\langle M \rangle\ |\ M \ halts\ on\ empty\ tape\\}$

I can prove $H\_{TM} {\_{\leq M}} H\_\epsilon$ by taking $\langle M,w \rangle$, and build new machine $M’\_w$ that writes $w$ on tape and then simulates $M$. Then $\langle M,w \rangle \in H\_{TM} \iff \langle M'\_w \rangle ∈ H\_\epsilon$

I got stuck proving the other direction.

Any help is appreciated.

# Answer
> 3 votes
Let $\Sigma = \\{0,1\\}$, $A=\\{0\\}$, $B=\\{1\\}$.

Define the following reductions:

$f(0)=1$ and $\forall x\ne0 . f(x)=0$,

$g(1)=0$ and $\forall x\ne1 . g(x)=1$.

Then you can easily show that $A \le\_{M}B$ (using $f$) and $B \le\_{M}A$ (using $g$) but obviously $A\ne B$.

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


# Question
Title: give a nfa without ε-transitions corresponding to the Regular expression
Regular expression: (0 + 01)(ε + 1)1(ε + 0 + 1)\*

I dont know if my answer to this is entirely right but please enlighten me if i'm way out of line.

\begin{array}{c|ccc} \ &0&1&\\\hline q0&\\{q0\\}&\\{q1\\}&\\\ q1&\\{q1\\}&\\{q1\\}&\ \end{array}

# Answer
> 1 votes
This regular expression is equivalent to `0 1? 1? 1 (0+1)*`, which is equivalent to `0 1 (0+1)*`. So you just have to look for a zero and then a one at the beginning. If you see those, the string is acceptable.

You can do this with four states: `start`, `0`, `good`, and `bad`.

```
state |  0   |  1
------+------+------
start | 0    | bad
    0 | bad  | good
  bad | bad  | bad
 good | good | good

```

The only accepting state is `good`. The initial state is `start`. Note that this is in fact a DFA: you don't need any nondeterminism at all. (The only difference is, you can replace the `bad` state with an empty set in an NFA, and it won't change the meaning.)

The NFA you've come up with won't work, since it'll accept any number of zeroes at the beginning (including none, or two, or fifty), rather than exactly one.

---
Tags: finite-automata
---


# Question
Title: is it possible to have a mapping reduction between 2 NP complete languages?
so i have a good understanding about languages that belong to NP, P and NP complete, and how Polynomial reduction works between languages that belong to those areas. but i just can't figure out a conclusion about mapping reduction between languages in those areas. for example if i have 2 languages - A and B, that both of them are NP-Complete, can i do a A ≥m B (mapping reduction) or B ≥m A ?

# Answer
You certainly can! This is how NP-completeness works: every NP-complete problem can be mapping-reduced to every other NP problem, by definition.

For example, consider the Boolean Satisfiability Problem: given some assortment of variables joined together by AND, OR, and NOT, is there any assignment of True and False to those variables that will make the whole thing evaluate to True? This problem is NP-complete.

Consider also the 3Sat problem, a convenient one to use in all sorts of NP-completeness proofs. This is the same as the Boolean Satisfiability Problem, except that the input is a series of *clauses* joined by AND, where every clause consists of exactly three *terms* joined by OR, and a term is either a variable or the negation of a variable.

Since every 3Sat input is a Boolean formula, 3Sat can be trivially reduced to Boolean Satisfiability. And there's a method of converting any Boolean Satisfiability problem into an equivalent 3Sat input in polynomial time.

Therefore, $\mathrm{3Sat} \leq\_M \mathrm{BooleanSatisfiability}$, and $\mathrm{BooleanSatisfiability} \leq\_M \mathrm{3Sat}$.

(It's easier to understand this with general *problems*, but this can be trivially rephrased to work with *languages*, as in your question: let the language $\mathrm{BooleanSatisfiability}$ consist of the binary encodings of inputs for which the Boolean Satisfiability Problem should return true, for example.)
> 1 votes

---
Tags: computability, np-complete, reductions
---


title: What is sub graph isomorphism?

text:
# Question
Title: What is sub graph isomorphism?
I am confused about the definition of sub graph isomorphism, wikipedia says that the subgraph isomorphism problem is a computational task in which two graphs $G$ and $H$ are given as input, and one must determine whether $G$ contains a subgraph that is isomorphic to $H$.

Is this the correct statement or is it whether $G$ contains a subgraph that is isomorphic to a *subgraph* in $H$?

# Answer
> 1 votes
No, that is not the correct statement.

Every graph contains the empty graph as a subgraph, the problem as you define it would return `TRUE` for all pairs of graphs, which isn't very interesting.

Finding the largest common subgraph of two graphs would be an interesting problem, and it is at least as hard as the actual subgraph isomorphism problem (since $G$ contains a subgraph isomorphic to $H$ if and only if the largest common subgraph is isomorphic to $H$.)

---
Tags: graph-isomorphism
---


# Question
Title: What is the fastest way to bytewise examine the contetnt of quadword
I have the following byte: `0x0A` and I need to test if a quadword contains it or no using standard bitwise operarion (or, nor, xor). For instance:

0x1689FFBB768922AC ---\> false 0x106489320A792399 ---\> true

Unfortunately I cannot use intel SSE2 extension because this will make the code heavily depndent on the platform.

Can we find some bitmask to bitwise or with? Or maybe something else...?

# Answer
> 3 votes
Yes, it can be done. Here is one reasonable approach. First XOR the value with `0x0A0A..0A`:

```
t = x ^ 0x0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A0A;

```

So now the problem becomes testing whether `y` contains a zero byte. First we'll replace every byte with a single bit that is `1` if the byte is non-zero, or `0` if the byte is zero:

```
u = t | (t>>4);
u = u | (u>>2);
u = u | (u>>1);

```

(Here we only care about the least significant bit of each byte; the remaining bit positions hold garbage that we don't care about.) Now we'll flip each of those bits:

```
v = ~u;

```

At this point the LSB of each byte is `1` if the original value contained a `0x0A` there, or `0` otherwise. So, we'll test whether any of these bits are `1`:

```
w = v | (v>>64);
w = w | (w>>32);
w = w | (w>>16);
w = w | (w>>8);
y = w & 1;

```

At this point, `y` is the result you are looking for: it will be `1` if the original value had a `0x0A` byte anywhere, or `0` otherwise.

---
Tags: algorithms, testing
---


title: Algorithm to place apples in boxes

text:
# Question
Title: Algorithm to place apples in boxes
Suppose we have $x$ apples and $y$ boxes. Each box can fit at most 3 apples, and we say that a box is half full iff the box contains $\leq$ 1 apple. If each apple has a (non-empty) list of boxes that it can be placed in, what is a polynomial time algorithm that places apples in boxes such that the number of half full containers is maximized?

***My attempt***

Sort apples in ascending order of the number of boxes that they can be placed into. For each apple, if there is an empty box that it can be placed into, then place the apple there. Otherwise, if there is a box with 2 apples in it that the current apple can be placed into, place the apple in that box. Otherwise, place the apple in a half full box. This algorithm clearly runs in polynomial time, but I don't think it is optimal, especially since I haven't specified how to break ties between boxes.

# Answer
Here is the reduction to a maximum matching, following the comments. We construct a graph $G$ with weighted edges as follows. The vertices of $G$ are $A$ and $B$.

Each apple has a corresponding vertex $a$ in $A$, and each box $b$ has $3$ corresponding vertices $b\_1,b\_2,b\_3$ in $B$. Add the edges $b\_1b\_2, b\_2b\_3$ and $b\_1b\_3$ so that they form a triangle, and put a weight of $1$ to each of these $3$ edges.

Now, for each apple $a$ that is allowed to go into box $b$, add the edges $ab\_1, ab\_2$ and $ab\_3$, each with a high weight, say $n^2$ (where here $n = x + y$).

Now consider any maximum weight matching $M$. Then $M$ must place as many apples in boxes as possible, due to the high weight of the edges incident to the $A$ vertices. Also, $M$ must maximize the number of half-full boxes while doing so. This is because if a box $b$ is half-full, then at least two of its vertices are unmatched with apples, so the edge of weight $1$ can be added into the matching. However, if a box is not half-full, no edge of the $b\_1b\_2b\_3$ triangle can be added into the matching. In other words, each half-full box allows us to add a weight $1$ edge into $M$.
> 2 votes

# Answer
The below isn't necessarily a very practical algorithm, but (if I didn't make any mistakes) it shows this problem is in fact polynomial time.

---

I believe you can pose your problem as a series of integral maximum flow problems. I will phrase the problem with lower bound edge demands. This is equivalent to a regular flow problem.

We construct a maximum flow problem as follows:

1. Make a node for each apple and construct an edge from the source $s$ with capacity $\[1, 1\]$.
2. Made two nodes for each box (one input and one output node). For each apple that can fit in that box construct an edge from that apple to that box's input node with capacity $\[0, 1\]$. Connect the input and output node of each box with capacity $\[0, 3\]$.
3. Make two nodes $A$ and $B$. Connect each box's output node to both $A$ and $B$, all edges with capacity $\[0, 1\]$.
4. Connect each box's output node to the sink $t$ with capacity $\[0, 1\]$.
5. Connect $A$ and $B$ to $t$ with respective capacities $\[0, n\]$ and $\[0, n\]$.

Now we will minimize the number of *overfull* boxes ($\geq 2$ apples), which is the same as maximizing the number of half full boxes. The critical observation is that each box can lose at most one of its apples to the sink - if it is overfull it must start flowing its apples through either $A$ or $B$. In the case of 3 apples both $A$ and $B$ must be utilized to maintain the $\text{out} - \text{in} = 0$ property of the flow problem.

Now when there is a feasible solution for $n = 0$ you know that there are no overfull boxes. Vice versa, if there exists a solution where there are no overfull boxes, there will be a feasible solution for $n = 0$.

Similarly, if there exists a solution where there are $k$ overfull boxes, there will be a feasible solution for $k = n$. This means that if we try all $n$ in increasing order, the first time we find a feasible solution we know it's optimal in $k$.

By inspecting the flow graph you can then find which apple goes in which box.

Since solving this maximum flow problem is polynomial in $x, y$ and $n$ is bounded in $y$, this algorithm is polynomial in the worst case as well.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Why does TSP require no repetition of cities?
It seems odd to me that the TSP denies the possibility of repeated cities. The goal of this traveling salesman is to go as fast as possible and visit all of the cities, right? So what if it is faster to travel through a city you have already been to?

# Answer
It doesn't matter exactly how you define it because it's just a way of modelling a real-world problem. In TSP, you just have a set of cities and the cost of travelling between each pair of them. That doesn't exclude the possibility that, in the real world situation you're modelling, the best route between B and C might go through A. If that was the case then, yes, the route that is modeled as ABCA in TSP may very well really involve driving through A an extra time on the way from B to C but such detail is abstracted away in the TSP model.
> 3 votes

# Answer
I agree that the constraint looks odd, and for many practical situations, it is not relevant. As pointed out by David in his answer, if you can alter the modeling yourself, then it does not really matter. But given a non-modifiable instance, it will make a difference, because general TSP with this constraint is not approximable within any constant factor, while relaxing the single-visit constraint seems to make it approximable within factor 2 (even though it is not metric). Unless I miss something, by standard arguments, you may first build a minimum spanning tree (of cost say $c$), then visit this tree with the euler tour technique. Clearly, the total cost of your tour is then $2 c$ (twice every edge). By contradiction, if there existed a tour of cost less than $c$, then this tour could be used to infer an MST of cost less than $c$, which is a contradiction.
> 2 votes

# Answer
Given any tour with repetitions, you can come up with a shorter tour that doesn't repeat any city. For example, consider a tour of the form $$ \cdots \to A \to \cdots \to X \to A \to Y \to \cdots, $$ which visits $A$ twice. You can take a shortcut on your second visit to $A$, going straight from $X$ to $Y$: $$ \cdots \to A \to \cdots \to X \to Y \to \cdots. $$

It might be that the shortest way from $X$ to $Y$ goes through $A$, but that is already encapsulated in the edge $X \to Y$. You can think of a mention of $A$ not as "passing through" $A$ but rather "stopping at" $A$. You need only stop at $A$ once, though you might pass through $A$ several times.

Actual algorithms for TSP could have this step of "taking shortcuts", for example Christofides's algorithm. See for example this description or that shorter account.
> 1 votes

# Answer
If repetitions are allowed, then you just go examine all connections X -\> A -\> Y, and if that is shorter than X -\> Y then you replace the length of X -\> Y with the length of X -\> A -\> Y, and solve the resulting problem with the standard algorithm. I think you have to repeat the replacement process until there are no changes, because if you find a shorter connection X -\> Y this might mean that now X -\> Y -\> Z is shorter than X -\> Y.

Keep track of which connections you changed, go through the connections in the solution, and if the solution contains X -\> Y then you replace this with X -\> A -\> Y.

PS. I think my idea is great, but I'm not very sure at the moment that it is correct. Because X -\> A -\> Y instead of X -\> Y is not just a shortcut, it also covers city A.
> 0 votes

# Answer
There's no general answer to this, except "people aren't stupid." They'll apply the solution that is appropriate to their situation. Rarely are people concerned with the traveling salesperson problem itself. Eveb in the classical instance, a real world salesperson would be more concerned with the problem of maximizing their income over a given time period within a specific set of constraints. In this instance of the problem, total distance traveled is only one of a number of different factors that go into finding the optimal answer.
> 0 votes

---
Tags: terminology, traveling-salesman
---


# Question
Title: Calculate ϴ dependent on n for an algorithm with constant c
I want to calculate ϴ dependent on n for this algorithm:

```
for (k = n; k < c; k++){
    j = 1;
    while(j < n){
        j++;
    }

```

n is the parameter. c is a constant.

I calculated the amount of operations to (c-n)\*(n-1). But now I don't now how to deal with c.

# Answer
> 0 votes
> I calculated the amount of operations to (c-n)\*(n-1)

Not quite. If $n \> c$ then the cost is not negative: it should be $(n-1) \max(c-n, 0) = \Theta(n) \max(c-n, 0)$. When $n$ is large (and in particular when $n \> c$) what does this reduce to?

---
Tags: algorithms, complexity-theory, algorithm-analysis
---


# Question
Title: How to apply Operational Semantics to this function
Say I have a function like this:

```
function colorize(integer) {
  var hex = '#'

  if (integer > 1) hex += 'ff'
  else hex += '00'
  if (integer < 100) hex += 'aa'
  else hex += 'bb'
  if (integer > 10) hex += '11'
  else hex += '22'

  return hex
}

```

It returns CSS hex colors, not named colors or `rgb(...)` values or anything else. For now we can ignore the low-level / platform specific details of JavaScript and hardware and just deal with this abstractly as if it was in a perfect environment.

The goal is to use small step operational semantics to prove that it returns a CSS hex color. If it requires too much initialization to do the proof, then assume the initialization is already handled so all that's focused on is the specific function and its implementation.

From my understanding this means we would have some rule for `var`, `=`, `if`, `===`, `+=`, and `return`. In addition, there is sort of a *trace*, since it is modifying the value in memory step by step.

From my understanding this would involve using the operational semantics configuration evaluation〈a, σ〉→〈a', σ'〉like:

〈=, σ〉→〈=, σ'\[hex ↦ #\]〉
→
〈if (e) x else y, σ〉→〈...〉
→
...

I am not sure how to:

1. Actually write the configurations out.
2. Write out the sequence of the evaluations.
3. Write a proof that the output will be a hex string such as `#00aa22` if given 0 for example.

I was wondering if one could point me in the right direction on how to solve this. Basically:

1. What some configurations look like using this function as an example.
2. What a sequence of the evaluations (or trace) looks like.
3. What a proof would entail (not the actual proof as I imagine there will be lots of steps), maybe just the first few steps of the proof.

Thank you very much for your help.

# Answer
You are looking for Hoare logic. Writing out the answer to the question would pretty much amount to copying the introduction to Hoare logic from Wikipedia. I suggest that you have a look at proving program correctness using Hoare logic, and try to apply it to your problem. It's actually an easy case because there are no loops. If you get stuck, come back and ask a specific question about Hoare logic.

I would break up the problem into proving several properties about `hex`:

1. The length of `hex` is 7 at the end.
2. The first character of `hex` is `#`.
3. All characters, except the first one, are hexadecimal digits.

Also not that the proof does not require you to write out any operational semantics. You can just use the Hoare logic to argue about your program, and there is a theorem which guarantees that Hoare logic is correct with respect to the standard operational semantics.
> 2 votes

---
Tags: logic, proof-techniques, formal-methods, software-verification
---


# Question
Title: Operation with second-order logic formulas
I have one or more second-order logic formulas that correct for some finity model. What operation can I perform on them, so that resault is also correct for some finity model?

Just conjunction is impossible, example: $x$ has finity model, $\lnot x$ has finity model, but $x \wedge \lnot x$ has not finity model. Are there any restriction?

# Answer
> 2 votes
Out of the standard logical operations ($\lor$, $\land$, $\neg$, $\implies$), the only ones that meet your conditions are $\lor$ and $\implies$.

---
Tags: logic
---


title: Lower bound for point set triangulation

text:
# Question
Title: Lower bound for point set triangulation
How can I show that the lower bound for getting a triangulation from a point set in the plane is $\Omega(n \log n)$?

I know that the lower bound for finding the convex hull for a point set is also $\Omega(n \log n)$. Is it valid to argue that since the convex hull is also part of the triangulation it can't be done faster or else the lower bound for the hull would also be lower?

Edit: By Triangulation I mean connecting all the points via non-crossing edges such that they form triangles: https://en.wikipedia.org/wiki/Point\_set\_triangulation

# Answer
> 2 votes
No, that's not a valid argument. You'd have to describe how to find which part of the triangulation is the convex hull, in $o(n \log n)$ time, to make that a valid argument.

---
Tags: time-complexity, convex-hull
---


# Question
Title: Why is the start symbol "not allowed" on the right hand side in Chomsky normal form?
I had a question regarding CNF (Chomsky normal form) in formal language theory.

I noticed that a lot of authors (including my own professor, and the Wikipedia page for CNF) frown upon or don't allow the start symbol to be on the right hand side of the production. However, I just can't wrap my head around why this is so.

In these cases, they put as the first step of converting a general context-free grammar into CNF to add the production

$$S\_0 \rightarrow S$$

but I noticed that in some cases this actually leads to having one more unnecessary production, and in other cases it's impossible to completely remove the start symbol completely from the right hand side of productions (excluding the $S\_0 \rightarrow S$ production). Also, the textbook that I'm using (*Formal Languages and Automata, 6e - Peter Linz*) allows the start symbol to be on the right side of a production.

What's the reason that this production is frowned upon?

Thank you.

# Answer
> 7 votes
Recall that in Chomsky normal form, we are allowed productions of three forms:

1. Productions of the form $A \to a$.
2. Productions of the form $A \to BC$.
3. The production $S \to \epsilon$.

We have to allow the production $S \to \epsilon$, since otherwise it will be impossible to generate the empty string.

Suppose for a moment that the production $S \to \epsilon$ is absent. Then we have the following very useful property:

> If $A \Rightarrow^\* w$ then $w \neq \epsilon$.

This comes up in some proofs of the pumping lemma, for example.

If we have the rule $S \to \epsilon$, then we no longer have the property above. However, a similar property holds:

> If $A \Rightarrow^\* w$ and $A \neq S$ then $w \neq \epsilon$.

This is due to our insistence of not having $S$ on the right-hand side of productions; otherwise we might have rules like $A \to SS$ and then derivations like $A \Rightarrow SS \Rightarrow^\* \epsilon$.

If the rule $S \to \epsilon$ is absent, then there is no reason to disallow $S$ on the right-hand side of productions. Indeed, some authors allow $S$ on the right-hand side of productions as long as the production $S \to \epsilon$ is absent.

# Answer
> 2 votes
All these formalizations are proposed solutions for a problem that can be handled more elegantly. The production $S\to \varepsilon$ is only a trick to indicate that the empty string belongs to the language.

Here is the definition of "Chomsky normal form" as given by Chomsky \["On Certain Formal Properties of Grammars". Information and Control (1959) 137-167. doi:10.1016/S0019-9958(59)90362-6, open archive\]. Note, sixty years ago, the meaning of "regular" was not yet fixed as we know it.

> Definition 8. A grammar is *regular* if it contains only rules of the form $A\to a$ or $A\to BC$, where ... \[additional restrictions omitted\].

It is clear from this that Chomsky was not interested in languages that contained the empty string. And, if we want to have convenient derivations for strings in a grammar it certainly is not very inconventient to have just a single string $\varepsilon$ that has no derivation?

So, as a Lemma, Chomsky's normal form would be stated like this, if we want to leave inclusion of the empty string open.

> **Lemma.** For every context-free language $L$ there exists a grammar $G$ in Chomsky normal form, such that $L(G) = L -\\{\varepsilon\\}$.

---
Tags: formal-languages, context-free, formal-grammars, normal-forms
---


title: Comprehensive reference for automata

text:
# Question
Title: Comprehensive reference for automata
I'm looking for a general reference cataloguing types of automata. Any introductory textbook will cover DFAs, NFAs, PDAs, and TMs, but there are countless more automata of practical or theoretical interest — linear bounded, embedded pushdown, nested stack, tagged finite, and so on. Online resources for these tend to be scattered.

Is there any sort of comprehensive reference, whether online or in print? Even incomplete surveys would be helpful.

# Answer
There is no list out on the web, nor even a partial list. I spent a few days looking and found nothing. The best you can do is piece together a list on your own (and post it here! :D).
> 1 votes

---
Tags: automata, reference-request
---


title: Understanding Hoare Logic Axioms

text:
# Question
Title: Understanding Hoare Logic Axioms
Given these 5 axioms of Hoare Logic:

\begin{array}{cl} \frac{}{\\{\phi(\[x \leftarrow E\])\\}\ x := E\ \\{\phi(x)\\}} & \mathtt{Assignment}\\\\ \frac{\\{\phi\\}\ P\_1\ \\{\eta\\} \quad \\{\eta\\}\ P\_2\ \\{\psi\\}}{\\{\phi\\}\ P\_1; P\_2\ \\{\psi\\}} & \mathtt{Sequencing}\\\\ \frac{\\{\phi \land B\\}\ P\_1\ \\{\psi\\} \quad \\{\phi \land \neg B\\}\ P\_2\ \\{\psi\\}}{\\{\phi\\}\ \mathtt{if}\ B\ \mathtt{then}\ P\_1\ \mathtt{else}\ P\_2\ \\{\psi\\}} & \mathtt{Conditionals}\\\\ \frac{\\{\phi \land B\\}\ P\ \\{\psi\\}}{\\{\phi\\}\ \mathtt{while}\ B\ P\ \\{\psi \land \neg B\\}} & \mathtt{Iteration}\\\\ \frac{\phi ⇒ \phi1 \quad \\{\phi1\\}\ P\ \\{\psi1\\} \quad \psi1 ⇒ \psi}{\\{\phi\\}\ P\ \\{\psi\\}} & \mathtt{Weakening \to Strengthening} \end{array}

Trying to understand the following:

1. $\mathtt{Assignment}$
    1. What $\phi(\[x \leftarrow E\])$ means. In the presentation it says $\phi(\[x \leftarrow E\])$ replaces every "free occurence" of $x$ in $\phi$ by $E$. I am confused because I thought that was what the assignment $x := E$ was doing. So my reading is: "precondition: replace each free occurrence of $x$ in state $\phi$ with $E$, program: assign $x$ to $E$, postcondition: $x \in \phi$". I am confused by both the pre and post conditions. To me it should be written $\\{\phi\[x\] \land \phi\[E\]\\}\ x := E\ \\{\phi\[x == E\]\\}$, that is, "given $x$ in state $\phi$ and $E$ in state $\phi$, when I assign $x$ to $E$, I get the new state where $x$ is equal to $E$". Wondering if someone could help clarify this my interpretation.
2. $\mathtt{Sequencing}$
    1. This one makes sense. If program $P\_1$ leads state $\phi$ to state $\eta$, and program $P\_2$ leads state $\eta$ to state $\psi$, then program $P\_3 := P\_1 ; P\_2$ leads state $\phi$ to state $\psi$.
3. $\mathtt{Conditionals}$
    1. "If we're in state $\phi$ and we have variable $B$, then program $P\_1$ leads to state $\psi$. Similarly for $P\_2$, but when we don't have $B$ in state $\phi$"
    2. This is essentially a sequential composition.
    3. I would've written it as $\\{\phi\[B\]\\}\ P\_1\ \\{\psi\\}$ and $\\{\phi\[\neg B\]\\}\ P\_1\ \\{\psi\\}$, would be helpful to better understand the notation on why they wrote it with the $\land$. To me $\\{\phi \land B\\}$ says either "B is *true* in $\phi$ state" or "B *exists* in $\phi$ state", can't tell.
4. $\mathtt{Iteration}$
    1. "If $B$ is in state $\phi$, and program $P$ leads to state $\psi$, then $\mathtt{while}\ B\ P$ leads to state $\psi$ without $B$". So this is an *axiom*.
    2. I don't understand how this can be an axiom because there is so much that is going on (tons of iterations for example). Wondering what allows this to be an axiom.
5. $\mathtt{Weakening \to Strengthening}$
    1. I don't understand this one yet.

To summarize, these are my questions:

1. What the notation is for having certain values in a state in the pre- or post-condition. If it's $\\{\phi\[B\]\\}$ or $\\{\phi(x \leftarrow B)\\}$ or $\\{\phi \land B\\}$ or $\\{\phi(B)\\}$. What the preferred notation is and its meaning. I have also seen $\\{\phi\[B/x\]\\}$
2. How to interpret the assignment rule.
3. How the while loop is allowed to be an axiom, when it does so much.

Thank you so much for the help.

# Answer
Here are some answers and hints to pursue your reflexions.

1. $\mathtt{Assignment}$
    1. What $\phi(\[x \leftarrow E\])$ means. You said yourself that the semantic of the precondition confuses you that was what the assignment $x := E$ was doing. But in fact your are precisely pointing out the crux of this rule: it affects the precondition **exactly** as the assignment would do it. This is the core reason of why this rule is actually sound.

Let study an exemple and leave the abstraction for a bit. Take the program $P = (z:=x+1)$.

Suppose we want to prove the postcondition $\phi(z) := \\{z=2\\}$ Intuitively what do we need to prove this ? Obviously we need $x$ to be equal to $1$. Let see how it translates in Hoare's logic. The assignment rule tells us that the triple: $$ \\{\phi\[z \gets x+1\]\\} (z:=x+1) \\{\phi(z)\\} $$ is valid.

Unrolling the syntax gives: $$ \\{(z=2)\[z \gets x+1\] \\} (z:=x+1) \\{x=2\\}, $$ that is $$ \\{x+1 = 2 \\} (z:=x+1) \\{z=2\\}, $$ and a bit of meta-logic says: $$ \\{x = 1 \\} (z:=x+1) \\{z=2\\}. $$

Which is what you wanted.

In an nutshell the assignment intuitively says: "The postcondition is true as soon as when I replace everything by the value of E in it, it is true"

$\mathtt{Conditionals}$

First of all $B$ is not a variable but a boolean predicate (like $X==1$ for instance).

1. $\\{\phi\[B\]\\}\ P\_1\ \\{\psi\\}$ doesn't make any sense. $\phi$ is a predicate, so does $B$, so that you can't apply one to another. For instance if $\phi = (x==1), B = (y==2)$ you can speak of $\phi\wedge B$ but $\phi\[B\] has absolutely no meaning.
2. $\\{\phi \land B\\}$ is true says $\phi$ is true and $B$ is true. With my previous instances: $\\{\phi \land B\\}$ as precondition asserts that on the one hand $(x==1)$, and on the other $(y==2)$. Nothing else.

$\mathtt{Iteration}$ This one is subtle. As long as it terminates, you can have arbitrary many iterations BUT still a finite number. Think of a while as a for loop on which you don't know a priori the number of runs in this case. To see why the rule is sound, think of it as a nested sequence of if :

```
if B then
     P
     if B then
         if B then
            P
            if B then
                 .....

```

And use a recurrence + conditional+ composition to convince you that the rule does what it is supposed to do.

If it doesn't terminates you can't say anything a priori so it doesn't matter. Remark that the rule DOES NOT say that the loop terminates.

$\mathtt{Weakening \to Strengthening}$ It is the causal reasoning. Let us unroll the rule: Suppose that $\phi$ is true. Then $\phi$ is also true since $\phi \Rightarrow \phi\_1$. But the Hoare triple $\\{\phi\_1\\}\ P\_1\ \\{\psi\_1\\}$ is valid by hypothesis. Then $\psi\_1$ is true. But we know that $\psi\_1\Rightarrow \psi$. Hence $\psi$ is true as well: we just proved that $\\{ \phi \\} P \\{\psi\\}$ is a valid triple.
> 3 votes

---
Tags: proof-techniques, hoare-logic
---


# Question
Title: How to use Hoare Logic to Prove this Assertion
Given this assertion in Hoare Logic:

\begin{align} &\mathbf{\\{p \>= 0\\}}\\ &s = 0 ; n = 1 ;\\ &\mathtt{while}\ (n \<= p)\ \\{\\ &\quad s = s + n ;\\ &\quad n = n + 1\\ &\\}\\ &\mathbf{\\{s == p * (p + 1) / 2\\}} \end{align}

How to prove this using the rules of Hoare Logic. I am not sure where to really begin, I only currently understand (most) of the meaning of the axioms, but not what is required for a proof.

# Answer
Its a question of chaining/glueing the axioms between them.

Let's start from the end:

$$\mathbf{\\{s == p * (p + 1) / 2\\}}$$

Use the strengthening rule to change the postcondition to

$$\mathbf{\\{s == p * (p + 1) / 2 \wedge p == n \wedge p \>= 0\\}} $$

which is equivalent to

$$\mathbf{\\{s == n * (n + 1) / 2 \wedge p == n \wedge p \>= 0\\}}$$

By the Loop rule in order for the triple:

$$ \mathbf{\\{s == n * (n + 1) / 2 \\}} \mathtt{while}\ (n \<= p)\ \\{s = s + n ; n = n + 1\\} \mathbf{\\{s == n * (n + 1) / 2 \wedge p == n \\}} $$

we need to prove that the triple

$$\mathbf{\\{s == n * (n + 1) / 2 \\}} \\{s = s + n ; n = n + 1\\} \mathbf{\\{s == n * (n + 1) / 2\\}}$$

is valid.

Let then use the composition to reduce this to proving that the two following triples are valid:

$$\mathbf{\\{s == n * (n + 1) / 2 \\}} \\{s = s + n\\} \mathbf{\\{s == (n+1) * (n + 2) / 2\\}}$$

and

$$\mathbf{\\{s == (n+1) * (n + 2) / 2 \\}} \\{ n = n + 1\\} \mathbf{\\{s == n * (n + 1) / 2\\}}$$

The latter one is just an application of the Assignment rule (just replace the occurrences of $n$ by $n+1$ in the postcond to get the precondition).

To prove the first one, we need to apply Strengthening to reduce it to the triple $$\mathbf{\\{s == n * (n + 1) / 2 \\}} \\{s = s + n\\} \mathbf{\\{s == (n) * (n +1) / 2 + n\\}}$$ and then use the Assignment rule trivially.

Okay so now we only need (by Sequence rule) to prove that the triple

$$\mathbf{\\{p\>=0 \\}} s:=0; n:= 1 \mathbf{\\{s == n * (n + 1) / 2 \wedge p \>= 0\\}}$$ which can be done in the same way by splitting with sequence.
> 1 votes

---
Tags: formal-methods, software-verification, hoare-logic
---


title: Does this constitute as an LL grammar?

text:
# Question
Title: Does this constitute as an LL grammar?
For the language, $L(aa^\*ba) \cup L(abbb^\*)$ and the grammar

\begin{align\*}S&\to aAba \mid abbB\\ A &\to Aa \mid \lambda\\ B &\to Bb \mid \lambda \end{align\*}

Would the grammar above constitute as LL? I'm having trouble recognizing what exactly constitutes an LL grammar.

# Answer
> 2 votes
An LL grammar is a grammar that can be parsed by an LL parser. An LL parser is a parser which parses input from **L**eft-to-right and constructs a **L**eftmost derivation of the sentence. (https://en.wikipedia.org/wiki/LL\_grammar).

The explanation is still a bit confusing, so it's easier to think of it that by looking at only a portion of the input string, we can predict exactly which production rule to apply.

In the grammar you've given: $L(aa^\*ba) \cup L(abbb^\*)$

which has the production rules:

$$S \rightarrow aAba | abbB$$ $$A \rightarrow aA | \lambda$$ $$B \rightarrow Bb | \lambda$$

this grammar is the union of all strings which start with either an arbitrary amount of $a$'s or an $ab$.

Remember what I mentioned earlier about LL grammars parsing strings from left to right, and that we'd be able to predict which production rule to use by looking at a portion of the input string? This specific grammar satisfies these properties, and is therefore LL.

Let's look at an example:

Say we're given the strings $aaaaaba$ and $abbbbb$. Starting from the left, how many input characters must we read to see which production rule to use?

The answer is two.

All strings in the grammar $L(aa^\*ba) \cup L(abbb^\*)$ start with an $a$, and if the second character of the input string is also an $a$, then we must use the production

$$S \rightarrow aAba$$

and if the second character is a $b$ then we must use the production

$$S \rightarrow abbB$$

The only basic concept to keep in mind when dealing with LL grammars is whether or not you can accurately predict which production rule to use when only looking at a portion of the string.

I hope this helped, and if I either missed something or didn't explain sufficiently please feel free to correct me.

---
Tags: formal-languages, formal-grammars
---


title: What is the output of a 2-tag system?

text:
# Question
Title: What is the output of a 2-tag system?
Considering a 2-tag system as defined by wikipedia, how do I identify the result of the computation?

# Answer
> 1 votes
There are two types of Post tag systems: with halting symbols, and without.

A Post tag system *with* a halting symbol gives its output in the same way that a standard Turing machine does: on the tape. Whatever is written on the tape when it hits the halting symbol is its output.

A Post tag system *without* a halting symbol is a bit trickier. It only halts when the tape has too few symbols left to do another step of processing. So there's no way to give any output on the tape. Thus, its output is the sequence of intermediate states the system has been in in the process of producing the result.

The Wikipedia article you linked gives an example of this: a halting-symbol-less 2-tag system to compute the modified Collatz sequence.

---
Tags: computability
---


# Question
Title: Does This Prove $P \neq NP$? (Randomly Populated Binary Tree)
Suppose a binary tree with $n$ levels and exactly $2^n-1$ nodes.

The nodes are random and their value does not determine their position in the tree at all. This isn't demonstrated in the picture, because I couldn't find a better image to use.

The task is to find the path to a given node. Since the nodes are random, we'd have to visit each node until we find the target. This should be $O(2^n)$ with the best case being $\Omega(1)$ (the target node is the root node). The output is at most an $n$-bit value, each bit specifying whether to traverse the left or right child node. When there are no more bits to be read, we know we've reached the target node. Therefore, the output can be read and verified in $O(n)$. Are there any flaws with this?

# Answer
No, it doesn't. Your input size is exponential in terms of n. So the proper way to look at it would be to define k=2n-1 and solve the problems in terms of k.
> 2 votes

---
Tags: complexity-theory
---


title: Does $R(L_1\cdot L_2)=L_2\cdot L_1$?

text:
# Question
Title: Does $R(L_1\cdot L_2)=L_2\cdot L_1$?
Does $R(L\_1\cdot L\_2)=L\_2\cdot L\_1$?

Where $R$ is the reverse.

I can't think about counter example

# Answer
> 3 votes
Did you mean to write $R(L\_1⋅L\_2)=R(L\_2)⋅R(L\_1)$? If so, then the answer is yes (prove it!).

The way your question is currently formulated, the answer is no: for example, take $L\_1=\\{ab\\}$ and $L\_2=\\{b\\}$.

---
Tags: formal-languages
---


# Question
Title: Acceptance conditions when translating LTL to Büchi automaton?
As an exercise in better understanding, I have been implementing the LTL to Generalized Büchi Automaton translation algorithm of Gerth, *et al.* (which is also discussed in Clarke, *et al.*, *Model Checking*).

What I have ended up with seems incorrect, but also seems to accord with the discussion. Both of the presentations state that we should create a separate multiple sets of accepting states as follows: for each "subformula of $\phi$ \[the LTL property to be checked\] of the type $\mu U \psi$, there will be a\[n accepting\] set $F \in \cal F$ which includes the nodes $q \in Q$ such that either $\mu U \psi \not \in Old(q)$, or $\psi \in Old(q)$." By the standard translation of GBA to BA, the BA will be compelled to step through an accepting state for each of these component machines infinitely often.

Can someone clarify this definition? It seems wrong to me for a few reasons, which suggests I have failed to comprehend it:

1. As I understand it, the definition of "subformula" means that any formula contained, arbitrarily deeply, in $\phi$ would have its own acceptance condition. But surely this must be wrong, because, for example, an until condition buried in a release condition might not ever need to be satisfied. Even more simply, Clarke's textbook gives as an example the property $$ (A U B) \rightarrow F C) $$ which gets translated to $$( (\neg A) R (\neg B) ) \vee ( \top U C )$$ ($\top$ is the boolean constant true; Clarke, *et al.* use **R** for "release" where Gerth, *et al.* use **V**). In this case, the algorithm as described seems to demand that we satisfy $(\top U C)$, but this is only a disjunct. Perhaps that is correct because parts of the graph where this disjunct has not been introduced, will be accepting for it?
2. The following seems to be a more difficult example of the same question: $$((p U q) R r)$$ In this case, if r holds universally, then $(p U q)$ need never hold, so I don't believe I should have a GBA acceptance condition for it.
3. The discussion of the algorithm directs the implementer to translate into a negation normal form, which is what gives the subformula $( (\neg A) R (\neg B) )$, above. But this is not an "until" subformula, so does not give rise to any acceptance condition at all, which means that it's not possible to satisfy the above disjunction by satisfying this release condition. Is this an oversight? Should one be generating acceptance conditions for these subformulas, as well? Looking at the experimental results reported, I see that the expression $$\neg (p\_1 U (p\_2 U p\_3))$$ is listed as not having any entries in the acceptance table. In a sense, this agrees with my expectation, because this is equivalent to $$\neg p\_1 R (\neg p\_2 R \neg p\_3)$$ But surely this is satisfiable by infinite traces where, for example, $\neg p\_3$ is always satisfied? So why are there no acceptance states? There's a caption to this example, but unfortunately, it's syntactically garbled: "The rightmost column represents the number of pairs in the acceptance table of the constructed automaton. Notice that for the safety property ...\[described above\]... there are no U subformulas satisfy \[sic\]. Yet, for the automaton to be nonempty, it has to contain a reachable cycle. \[???\]" I suppose in this case, it might be that when we translate this formula we get zero sets of accepting states and so vacuously any cycle is treated as accepting? But even so that would leave the earlier disjunctive case...

# Answer
I will start with the last question and then come to the question at the top of your post.

1. The construction assumes that the LTL formula is given in negation normal form, so that no temporal operator occurs in negated form (as you wrote).
2. So $\neg (p\_1 U (p\_2 U p\_3))$ gets translated to $\neg p\_1 R (\neg p\_2 R \neg p\_3)$, and because in the latter formula, there is no Until subformula, we have 0 acceptance pairs in the Generalized Buchi automaton.
3. Now, a generalized Buchi automaton accepts all words for which there exists an infinite run on which all acceptance sets are visited infinitely often. If there are none, then this condition is vacuously true on any infinite run, which still has to exist. For example the word $(\\{p\_1,p\_2\\}^\omega)$ does not satisfy the LTL formula, and the corresponding generalized Buchi automaton has not infinite run for the word. If you model check with this automaton, every reachable cycle represents a case in which the LTL property holds. If you translate the generalized Buchi automaton to a Buchi automaton, then the standard construction makes every state in the latter accepting.
4. As far as the subformulas are concerned, you have to take the definition quite literally. For every Until-subformula in the NNF LTL property, you have an acceptance set. For instance, for $(a\\,\mathcal{U}\\,b)\\,\mathcal{U}\\,c$, you will have acceptance sets for $(a\\,\mathcal{U}\\,b)\\,\mathcal{U}\\,c$ and $(a\\,\mathcal{U}\\,b)$. For the All states in the generalized Buchi automaton containing $b$ or not containing $(a\\,\mathcal{U}\\,b)$ as a disjunct are accepting for the latter acceptance set. All states containing $c$ as a disjunct or not containing $(a\\,\mathcal{U}\\,b)\\,\mathcal{U}\\,c$ as a disjunct are labeled as contained in the acceptance set for $(a\\,\mathcal{U}\\,b)\\,\mathcal{U}\\,c$.
5. The example $((\neg A)R(\neg B))\vee(\top U C)$ that you mentioned is actually not problematic. Depending on how you write down the algorithm, either (1) no state will ever be labeled by $((\neg A)R(\neg B))\vee(\top U C)$, but only by $((\neg A)R(\neg B))$ or $(\top U C)$ (and you will have two initial states), or (2) all states labeled by $((\neg A)R(\neg B))\vee(\top U C)$ need to also be labeled by either $((\neg A)R(\neg B))$ or $(\top U C)$, and for determining in which acceptance set a state is, you only look at the whole subformulas, so a state labeled by $((\neg A)R(\neg B))$ would be accepting for all acceptance sets, while one also labeled by $(\top U C)$ would not be labeled by the acceptance set for $(\top U C)$ (unless it is also labeled by $C$).
> 2 votes

---
Tags: model-checking, linear-temporal-logic, buchi-automata
---


# Question
Title: DFA complexity of reverse of language recognized by "maximal" DFA
Let's assume that DFA $A$ over the alphabet $\Sigma$ and with states $Q$ is *maximal* if for every function $f\colon Q\rightarrow Q$ there exists such word $w \in \Sigma^{\*}$, that $q \cdot w = f(q)$ for every state $q \in Q$. Let $L \subseteq \\{a, b, c\\}^{\*}$ be a non-empty language recognized by a maximal automaton with $n$ states.

Prove that all DFAs recognizing language $L^R$ have got at least $2^n$ states.

# Answer
Maximality implies that every state is reachable. Let $w\_q$ by a word such that $q\_0 \cdot w\_q = q$.

Since $L$ is non-empty and its complement is also non-empty, there must be some accepting state $q\_1$ and some non-accepting state $q\_2$. For every subset $A \subseteq Q$, let $w\_A$ be a word such that $q \cdot w\_A = q\_1$ for $q \in A$ and $q \cdot w\_A = q\_2$ for $q \notin A$.

I claim that if $A \neq B$ then $w\_A^R$ and $w\_B^R$ are not equivalent modulo $L^R$. Indeed, suppose (without loss of generality) that $q \in A \setminus B$. Then $w\_A^R w\_q^R \in L^R$ since $q\_0 \cdot w\_q w\_A = q \cdot w\_A = q\_1$, whereas $w\_B^R w\_q^R \notin L^R$ since $q\_0 \cdot w\_q w\_B = q \cdot w\_B = q\_2$. The result immediately follows.
> 1 votes

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


# Question
Title: Independence groups and fully connected groups
Let G be a connected graph, knowing that it has more than 9 vertex, Show that either its independence number is bigger-equal than 4 or its click number (the size of the biggest fully connected group) is bigger-equal than 3.

# Answer
> 0 votes
You can prove by induction the following more general claim:

> Let $a,b \geq 1$. Every graph on $\binom{a+b-2}{a-1}$ vertices contains either an independent set of size $a$ or a clique of size $b$.

The proof is by induction. If $a=1$ or $b=1$, then the claim is trivial, so suppose that $a,b\>1$. Consider an arbitrary vertex $v$ in the graph. Since $$ \binom{a+b-2}{a-1} - 1 \> \binom{(a-1)+b-2}{(a-1)-1} - 1 + \binom{a+(b-1)-2}{a-1} - 1,$$ one of the following cases must hold:

1. $v$ is not connected to at least $\binom{(a-1)+b-2}{(a-1)-1}$ vertices.
2. $v$ is connected to at least $\binom{a+(b-1)-2}{a-1}$ vertices.

In the first case, induction shows that among the vertices that $v$ is not connected to, we can find either an independent set of size $a-1$ or a clique of size $b$. In the former case, we add $v$ to obtain an independent set of size $a$. In the latter case, we are done.

In the second case, induction shows that among the vertices connected to $v$, we can find either an independent set of size $a$ or a clique of size $b-1$. In the former case, we are done. In the latter case, we add $v$ to obtain a clique of size $b$.

---

Plugging $a=4$ and $b=3$, we calculate $\binom{a+b-2}{a-1} = \binom{5}{3} = 10$. Hence every graph on 10 vertices contains either an independent set of size 4 or a clique of size 3.

---

The topic of this question is known as Ramsey theory, a major topic in combinatorics with various applications to several areas of mathematics. The claim proved above is one form of Ramsey's theorem. It is not known what is the minimal number that can replace $\binom{a+b-2}{a-1}$ in the claim. The optimal number is called the Ramsey number $R(a,b)$.

---
Tags: graphs, discrete-mathematics
---