# Question
Title: Problem with formalism in first order logic
This is a general question in first order logic.
Assume I have alphabet $\Sigma$ that contains one-argument function (among other symbols).
I want a new alphabet, $\Sigma'$, which is the same as the original, except that the function $f$ will be replaced by a new binary relation $R\_f$.
I ran into difficulties when I tried to formulate it. For example, for formulas as: $R(x,f(x))$, I need to replace $f(x)$ but I don't know how exactly.
In general, I couldn't find a way that accurately defines a new formula, such that: the new formula will be satisfied above $\Sigma'$ iff the original formula was satisfied $\Sigma$.

# Answer
> 2 votes
What you are looking for is replacing a function symbol $f$ with the corresponding **graph**, which is the relation $R\_f$ characterized by $R\_f(x,y) \iff f(x) = y$.

So we can replace $f(x) = y$ with $R(x,y)$ if $x$ and $y$ are variables. But what do we do about $f(t)$ where $t$ might contain futher occurrences of $f$? That's the tricky bit.

The idea is to use *intermediate* equations, for instance $$f(f(x)) = f(f(f(y)))$$ can be replaced with $$ \exists x\_1, y\_1, y\_2, y\_3. f(x) = x\_1 \land f(y) = y\_1 \land f(y\_1) = y\_2 \land f(y\_2) = y\_3 \land f(x\_1) = y\_3 $$ which in turn is replaced with $$ \exists x\_1, y\_1, y\_2, y\_3 . R\_f(x, x\_1) \land R\_f(y, y\_1) \land R\_f(y\_1, y\_2) \land R\_f(y\_2, y\_3) \land R\_f(x\_1, y\_3). $$ We can use a similar trick even if some other symbols and relations are present. For example $$f(x) + 3 \leq f(5)$$ translates to $$\exists y\_1, y\_2 . R(x,y\_1) \land R(5, y\_2) \land y\_1 + 3 \leq y\_2.$$ It is a good exercise to spell out the precise procedure after you've learned the trick, but let me know if you'd like more details.

# Answer
> 0 votes
You can always find a relation to replace any total or even partial function albeit it inevitably complicates the original wff with additional quantifiers and conjuncts, so usually you'd much better off with more generic and flexible function symbols defined in your alphabet $\Sigma$. However, a relation symbol cannot be replaced with only function symbol(s) in general in first order languages because function symbol is used to get terms corresponding to grounded objects in the domain of discourse and truth values are never grounded objects in the object language.

Now for your specific question to translate the formula $R(x, f(x))$ using only $R\_f$. For simplicity the first case assumed here is that your function $f$ is total and per your function replacement $R\_f$ assumption we can derive in a formal system:

$$\forall x \exists! y (f(x)=y \rightarrow R\_f(x, y)) \vdash \forall x(R(x, f(x)) \rightarrow \exists! y (R(x, y) \land R\_f(x, y)))$$

, where $\exists!$ is just a shorthand for the unique existence quantifier which can be replaced using a more complicated formula by adding a universally quantified conjunction.

Now for the second case where your original function $f$ is partial, then we can have a similar derivation in the same formal system:

$$\exists x \exists! y (f(x)=y \rightarrow R\_f(x, y)) \vdash \exists x (R(x, f(x)) \rightarrow \exists! y (R(x, y) \land R\_f(x, y)))$$

Or if you know $f$ is undefined at $p$, for example, then you can derive below: $$\forall x \exists! y (x \neq p \land f(x)=y \rightarrow R\_f(x, y)) \vdash \forall x(x \neq p \land R(x, f(x)) \rightarrow \exists! y (R(x, y) \land R\_f(x, y)))$$

---
Tags: logic, first-order-logic, propositional-logic
---


# Question
Title: while(l < r) vs. while(l <= r) advantages/disadvantages in binary search
There many many ways to code binary search, but one of the main distinctions I've seen in people's code is one group of people use `while(l < r)` and another uses `while(l <= r)`. I personally use the latter.

Is there any advantages/disadvantages to using either? I've never used `while(l < r)`, so when I see it, it's not always clear to me how it guarantees correctness.

# Answer
Binary search may be a name for some specific algorithm, but more often it is seen as a generic approach. Namely, you repeatedly subdivide the search space into two halves and then disregard the one which is known not to contain the solution. What exactly you put into the code depends on the context and on the details of your proof of correctness, as you seem to have noticed.

For example, in the following contexts neither `while (L < R)` nor `while (L <= R)` makes much sense:

1. Finding a zero of a continuous monotone function uses either `while(abs(R - L) > eps)` or simply fixed number of iterations.
2. Finding an integer bit-by-bit from the most significant to the least significant doesn’t have “left” or “right” indices.
3. https://en.wikipedia.org/wiki/Level\_ancestor\_problem#Jump\_pointer\_algorithm also doesn’t require having two pointers.

The textbook binary search is derived from maintaining (a variation of) these conditions throughout the runtime of the search:

1. $L \< R$
2. Probe is taken strictly between $L$ and $R$
3. $P(L)$ is always false
4. $P(R)$ is always true

On integer domains this yields the following algorithm for boundaries $L$, $R$ and a function (or “predicate”) $P$:

```
ensure P(L) is false
ensure P(R) is true

while R - L > 1 do
  M = (L + R) / 2

  if P(M) is false,
    L := M
  otherwise,
    R := M

```

This algorithm is guaranteed to end with $L$ and $R$ “sticking together”, where $L$ points to “false” and $R$ points to “true”, thus finding the boundary where the function $P$ changes its value. The only tricky part is to prove that $M$ indeed never equals $L$ or $R$ (otherwise the algorithm may get stuck). This property of $M$ also allows to avoid invariant checks before the while loop: we can simply move boundaries one step outside, for we know they’ll never be probed.

```
L := L - 1
R := R + 1

while R - L > 1 do
  M = (L + R) / 2

  if P(M) is false,
    L := M
  otherwise,
    R := M

```

I don’t know any direct derivation of the other variants, but you can easily get them using simple substitutions. If you want `while (L < R)` in your code, just rearrange $R - L \> 1$ into $L \< R - 1$ and then call $R - 1$ the new $R’$:

```
while L < R’ do
  M = (L + R’ + 1) / 2

  if P(M) is false,
    L := M
  otherwise,
    R’ := M - 1

```

If you want `while (L <= R)`, then you first change $R - L \> 1$ into $R - L \geq 2$, which can be rearranged as $L + 1 \leq R - 1$, and then $L’$ is $L + 1$, and $R’$ is $R - 1$.

```
while L’ <= R’ do
  M = (L’ + R’) / 2

  if P(M) is false,
    L’ := M + 1
  otherwise,
    R’ := M - 1

```

All three versions are behaviourally the same, so the question is whether you see the correctness of your particular version easily and how well it fits in the context.
> 3 votes

---
Tags: binary-search
---


# Question
Title: Proving correctness for greedy algorithm in string removal problem
Problem Statement: You are given a string s and two integers x and y. You can perform two types of operations any number of times. Remove substring "ab" and gain x points. For example, when removing "ab" from "cabxbae" it becomes "cxbae". Remove substring "ba" and gain y points. For example, when removing "ba" from "cabxbae" it becomes "cabxe". Return the maximum points you can gain after applying the above operations on s.

A greedy algorithm solves this problem in O(n). The greedy algorithm works by eliminating all pairs with a higher scoring value before removing pairs of a lower scoring value. Can anyone present a proof for the correctness of a greedy algorithm here. I have been trying, and I cannot convince myself.

# Answer
(For the greedy algorithm described to be optimal, it is also necessary to assume that $x$ and $y$ are nonnegative.)

Without loss of generality, we can assume $y \ge x$.

Suppose to the contrary that the greedy algorithm is not optimal. Then there exist some string (possibly an intermediate state) containing a consecutive pair $\mathrm{ba}$ whose removal is suboptimal. Consider what happens to those letters in the optimal solution.

* If neither is removed in the optimal solution, then also removing the pair gives a better solution – a contradiction.
* If exactly one of those letters is removed in the optimal solution, then modifying the solution by first removing the $\mathrm{ba}$ pair, and omitting whatever removal applied to one of them later, gives another solution that is at least as good, contradicting the assumed suboptimality of removing the $\mathrm{ba}$ pair. (Because the other member of the pair was never removed in the optimal solution, this change works, in that it cannot break any later removals.)
* If both of those letters are removed in the optimal solution, that means they are paired up with an $\mathrm{a}$ on the left and a $\mathrm{b}$ on the right. In this case, we can modify the solution by first removing the $\mathrm{ba}$ pair, and later pairing up and removing those other $\mathrm{a}$ and $\mathrm{b}$, which is again a contradiction.
> 1 votes

---
Tags: strings, greedy-algorithms, correctness-proof
---


# Question
Title: Find if two elements in an array sum up to a given number
I'm currently solving some problems over at kattis, in particular the Add 'Em Up task.

A quick summarizing:

You are given an array with $1 \leq n \leq 100000 $ elements and an integer $2 \leq s \leq 200 000000$. You want if there exists two elements $x\_i,x\_j, i \neq j, $ in the array such that $x\_i + x\_j = s$. However, there's a twist that you can flip certain numbers to obtain a new number. For example, if $ x\_i = 51 $ then a flip would yield $ \bar{x}\_i = 15.$ Still, you can just use an element once, so $ x\_i + \bar{x}\_i = s $ is not an accepted answer.

Looking at the worst case scenario, our new array would contain $2n$ elements, $ \\{x\_1, ..., x\_n, \bar{x}\_1, ..., \bar{x}\_n \\}. $

I've written an algorithm that works, but it's not efficient enough. I believe it's $ \in O(n^2) $.

If $ N = \\{x\_1, ..., x\_n, \bar{x}\_1, ..., \bar{x}\_n \\} $, and if $x\_i $ doesn't have a flip, then $ \bar{x}\_i = $ 'NF'. (NoFlip, str).

```
for i in range(2*n) do
    for j in range(2*n) do
        if (j-i) % n != 0 and N[i], N[j] != 'NF':
            if N[i] + N[j] == S:
                return True

return False

```

How can I make the code more efficient?

I've tried:

* Removed all elements $ \geq S $ first

# Answer
> 3 votes
There is an $O(n)$ solution, using a nice trick:

Keep track of the different values you have already seen in an auxiliary hashmap, called $seen$.

Now, loop over the elemnts of the array (the original array, you don't have to add the negations), and for each $x\_i$ do the following:

1. If either $s-x\_i\in seen$ or $s-\overline{x\_i}\in seen$, then return $True$.
2. Else, add both $x\_i,\overline{x\_i}$ to $seen$, and continue to the next element in the list.

You will see that if for any $i$ we get that $s-x\_i\in seen$ **before** we added $x\_i$ at the $i$'th iteration, then there must be some $j\< i$ such that $x\_i+x\_j=s$ or $x\_i+\overline{x\_j}=s$. And for a similar reason, if $s-\overline{x\_i}\in seen$ before we added it in the $i$'th iteration, then there must be some $j\<i$ with $\overline{x\_i}+x\_j=s$ or $\overline{x\_i}+\overline{x\_j}=s$.

---

Thechnically speaking, the solution works in $O(n^2)$ in the worst case, but since we deal with a hash map, we can say that on average (or at least, its very likely) that it will run in $O(n)$.

---
Tags: algorithms, optimization
---


# Question
Title: What are the maximum possible values of X and Y?
30 buses are used to transport 2000 passengers. Each bus has 80 seats and each passenger will occupy exactly one seat.

Consider the following statement: At least X buses will carry at least 67 passengers and at least Y buses will have at least 14 vacant seats.

Assuming that this statement is always true irrespective of the way passengers are assigned to buses, what are the maximum possible values of X and Y?

# Answer
Let's try to find a feasible allocation of passengers to buses that minimizes $X$. Let's consider the ideal situation in which all non-empty buses, except possibly one, are filled with one less than $67$ passengers (i.e., with $66$ passengers).

In this setting the number of buses needed to transport $2000$ people is $\left\lceil \frac{2000}{66} \right\rceil = 31$, which is not feasible. Therefore we need *at least* one bus with at least $67$ people. Unfortunately using *exactly* one bus with at least $67$ people is also not feasible since we would be able to carry at most $29 \cdot 66 + 80 = 1994$ people. We can however allocate $66$ people per bus to $28$ buses and the remaining $152$ people to the remaining two buses. This shows that $X=2$.

Let's now try to find an allocation that minimizes $Y$. We want as few buses as possible to have at least $14$ vacant seats, i.e., we want as many buses as possible to have at least $80-14 + 1 =67$ passengers. The maximum number of buses with at least $67$ passengers is $ \left\lfloor \frac{2000}{67} \right\rfloor = 29$. This shows that $Y = 1$ (we can allocate $67$ people per bus to $29$ buses, and the remaining $57$ people to the final bus).
> 1 votes

---
Tags: gate-cs
---


# Question
Title: Lower bound on number of zero columns in matrix
I've been looking for an algorithm to tell the number of non-zero rows (or columns) in a row reduces matrix $A\in \mathbb{R}^{m\times n}$. A simple approach would be to check it, row by row, which would take $O(m\cdot n)$ time and I believe would be linear. It seems to be the lower bound, but I am not sure, could there be a more efficient deterministic algorithm for this?

# Answer
> 1 votes
You can't.

Consider a matrix that is nearly all zeros. Consider what happens if you have an algorithm that starts inspecting entries, keeps finding a zero in each place it looks, but halts without having looked at all entries. Consider any entry it didn't look at. The output needs to be different if the matrix is all zeros except for that entry, vs if it is all zeros. (Both matrices are in reduced row echelon form, so both are valid inputs.) However this algorithm will output the same thing for both inputs. Hence this algorithm cannot be correct.

---
Tags: algorithms, matrices, linear-algebra
---


# Question
Title: Speed up counting the number of A[i] * A[j] * A[k] = A[l] where i < j < k < l
I recently got onto the following problem: we consider the following array:

```
A = [2, 3, 6, 1, 6, 4, 12, 24]

```

we need to count the number of times these two conditions are satisfied within the array:

```
A[i] * A[j] * A[k] = A[l] so that 0 <= i < j < k < l < len(A)

```

for this example the result should be 8. example of satisfied conditions within the array:

```
2 * 3 * 1 = 6
2 * 6 * 1 = 12
6 * 1 * 4 = 24
3 * 1 * 4 = 12

```

The straightforward solution I created using python:

```
A = [2, 3, 6, 1, 6, 4, 12, 24]
result = 0
for i in range(len(A)):
    for j in range(i + 1, len(A)):
        for k in range(j + 1, len(A)):
            for l in range(k + 1, len(A)):
                if A[i] * A[j] * A[k] == A[l]:
                    result += 1
print(result)

```

I need to find a way to speed up the program using dynamic, maybe memoization or pre computing.

```
result = 0
for i in range(A):
    for j in range(i + 1, A):
        for k in range(j + 1, A):
             #TODO
print(result)

```

I was thinking of creating a dictionary that contains a set of dictionaries for each number, to indicate the number and its position, example:

```
speed_up = {
    6: {
        2: True
        4: True
    },
    1: {
       3: True
    },
    ...
}

```

then we check like the following:

```
result = 0
for i in range(A):
    for j in range(i + 1, A):
        for k in range(j + 1, A):
            x = A[i] * A[j] * A[k]
            if x in speed_up:
                result += len([z[0] for z in speed_up[x].items() if z[0] > k])

```

This way we will count all occurrences of the same number after the index k at once, we will not have to go through all array.

Please let me know if my optimisation is flawed, and if there's better optimisation using dynamic programming techniques such as memoization or pre computing.

# Answer
> 2 votes
Here is a simpler version of your algorithm, using a simpler dictionary structure.

```
result = 0
cnt = {}
for elem in A:
    if elem not in cnt:
        cnt[elem] = 0
    cnt[elem] += 1

for k in range(len(A)):
    cnt[A[k]] -= 1  # uncount A[k]
    for j in range(k):
        for i in range(j):
            x = A[i] * A[j] * A[k]
            if x in cnt and cnt[x] > 0:
                result += cnt[x]

```

Notice that through the loop structure we ensure i \< j \< k and that A\[0,...,k\] are always erased from the counts in the cnt dictionary. This runs in $O(n^3)$ (assuming $O(1)$ hashmap)

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


# Question
Title: Time Complexity for brute force algorithm finding cliques of size k in a graph, in terms of n m and k
I currently have an algorithm that uses brute force/exhaustive search to find all of the cliques of size exactly k in a graph G.

My algorithm is as follows:

**Generate all subgraphs of size k, and check each one to determine if it is a valid clique.**

I'm trying to find the time complexity of my algorithm, but I'm stuck on how to show it as a function of all three n, m and k.

Where n is the number of vertices in the graph, m is the number of edges and k is the specified size we are looking for.

I need to answer the following:

1. How many subgraphs of size k can we generate, in Θ notation as a function of n, m and k? (and why is it so)
2. What is the worst case time complexity of the algorithm, in O notation as a function of n, m and k? (and why is it so)

so far, I have the following:

* there are O(n^k) subgraphs to check
* worst case run time of the algorithm is O(n^kk^2)
* because there are O(n^k) subgraphs to check, each of which has O(k^2) edges

but I need it bound it in terms of m, the number of edges in the graph as well.

# Answer
> 1 votes
There are $\binom{n}{k}$ sets of $k$ vertices out of $n$, to check that they are actually a clique you need to check $\binom{k}{2}$ pairs to see if they are edges, for a total of $\binom{n}{k} \binom{k}{2}$ edge checks. If you store the graph as an adjacency matrix, each check is $O(1)$. So in all:

$\begin{align\*} \binom{n}{k} \binom{k}{2} O(1) &= O(n^k) O(k^2) O(1) \\ &= O(n^k k^2) \end{align\*}$

# Answer
> 0 votes
You should check combination $$\binom{n}{k}$$ and each check need $\mathcal{O}(n+m)$ because you should check any subset of vertices with size $k$ form a complete graph or not, so overall running time is $$\binom{n}{k}\mathcal{O}(n+m)=\mathcal{O}\left(n^k(n+m)\right).$$

---
Tags: complexity-theory, graphs, time-complexity, big-o-notation, clique
---


# Question
Title: What is an example of an algorithm that requires synchronised clocks?
What is an example of an algorithm that requires synchronised clocks? Synchronised in an absolute sense, not just synchronised clock rates.

For more background, I've read Barbra Lisksov's 1993 paper 'Practical Uses of Synchronized Clocks in Distributed Systems' and also some content on Cloud Spanner and TrueTime. I'm still struggling to understand the advantages of using synchronised clocks on nodes in a distributed system.

# Answer
I did some more thinking about this and I see at least one benefit of synchronized clocks, which is '**fairness when the topology is skewed**'.

Imagine a situation with a server and two *trusted* clients. Eg. perhaps they're API servers in different data centers that end-users communicate with.

```
Server------------------------------Client A
      \------Client B

```

Client A is much closer to the server than Client B.

Imagine that both clients send a message to purchase the last seat to a concert. Client A sends a request first and Client B sends a request shortly after.

```
Client A  |A(send)
Client B    |B(send)
Server           |B(receive)         |A(receive)
         ------------------------------------------------> time

```

The server received Client B's request before Clent A's. That is, the ordering seen by the server was different from the real-time ordering.

The real-time ordering is the order in which the events occurred in the physical world.

Client A may see this as unfair since they requested the ticket before Client B.

It's possible to maintain the real-time ordering of messages if each client has synchronized clocks in an absolute sense. That is, the clocks should have zero skew (and also zero drift).

If that's true then the server can preserve real-time ordering of events by 'waiting out' the uncertainty of both the clock skew and the network latency. The server will need to wait

$$t\_{wait}=t\_{max\\\_skew}+t\_{max\\\_system\\\_latency}$$

from the time that the message was sent. That is, before processing a message the server has to wait as long as the maximum clock skew, plus the maximum one-way latency to the furthest client, minus the one-way latency of that message.

This approach assumes a synchronous system however it can be extended to work with the asynchronous timing model by making the server reject any message that was received more than $t\_{wait}$ seconds after it was sent (the send time is in the message). In that case, the client would have to retry.

**To summarise (TL;DR)**, synchronized clocks (with zero skew) can provide real-time ordering to a system. A concrete advantage of real-time ordering is that it's more 'fair' to participants when the network topology is skewed. The cost of real-time ordering with synchronized clocks is that the system has to 'wait out' the worst-case one-way latency and clock skew.
> 1 votes

# Answer
If you ask two systems "which happened first, A or B", and they give you the same answer, surely that's an advantage compared to getting two inconsistent answers.

On the other hand, what is the meaning of "synchronised clocks"? I would take it to mean "if I ask both clocks for the time at the same moment, I will get the same reply". But I can't ask two clocks at the same time; not if they are in different places. If I ask two clocks at almost the same moment, each can legitimately claim it is earlier in time. That's just physics.

The best method that I know is trying to get precise timing information from a clock, and then have a server who is the arbiter which events happened before which others, giving a total ordering to all events.
> 0 votes

---
Tags: distributed-systems, clocks
---


# Question
Title: Language for starting and ending with same symbol
Alphabet = {a,b} should null string be the part of this language? L ={^,a,b,aa,bb,abba ......} I have seen on different sources not including null string. Is null string a part of this language or not?

# Answer
When confronted to an ambiguous english definition of a language, you can do one of the following:

* ask for precision to the person giving the exercise/statement;
* chose arbitrarily one of the suitable formal definition;
* study all the suitable formal definitions.

If it is an exercise, it is more likely that either of the definitions (with or without the empty word) are good enough to reach the objective of the question.
> 2 votes

---
Tags: formal-languages
---


# Question
Title: Context-free grammar for $a^{2n} b^{2n}$
I have just started learning formal languages and here is a question I am facing a little hurdle:

> Construct a context-free grammar for $\\{ a^{2n}b^{2n} \mid n \ge 0 \\}$.

This was what I got at first. $$S \to ab\mid aS\mid Sb\mid ab$$ Now I am getting this, $$S\to \epsilon$$

$$S\to aaSbb$$

$$G=(V,\Sigma,R,S)=(\\{S,a,b\\},\\{a,b\\},R,S)$$

$$R= \\{S \to aaSbb\mid \epsilon\\}$$ Is the approach to this question, right or is it done in a different way?

# Answer
Here is a derivation in your grammar:

$$ S \to aS \to aab. $$

The word $aab$ does not belong to your language, hence your grammar is incorrect.
> 1 votes

# Answer
I think this is the solution: $$S\to \epsilon \mid aaSbb $$
> -1 votes

# Answer
the second grammer you wrote, is right. it can involve all strings belongs to the language with no extra string.
> -1 votes

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


# Question
Title: Number of optimal solutions for Longest Common Subsequence (Substring) problem
The Longest Common Subsequence (or Substring) problem (LCS) asks, given two strings $s\_1$ and $s\_2$, to find one string which is substring both of $s\_1$ and $s\_2$ and it is of maximum length.

Each instance of the problem (i.e. each choice of $s\_1$ and $s\_2$) can have multiple optimal solutions. The size input of the problem is the sum of the length of $s\_1$ and $s\_2$.

Is the number of optimal solutions polynomial with respect to the size of the instance?

# Answer
> 3 votes
Consider the following two strings: $$ s\_1 = (abc)^n, s\_2 = (bac)^n. $$ You can show that the longest common substrings of $s\_1,s\_2$ have length $2n$. There are at least $2^n$ of these: $\sigma\_1 c \sigma\_2 c \ldots \sigma\_n c$, where $\sigma\_i \in \\{a,b\\}$.

# Answer
> 3 votes
Consider the following two strings:

$$s\_1 = a^n, s\_2 = a^{2n}$$

The longest common subsequence has length $n$. There are \[$2n$ choose $n$\] such longest subsequences, or $\frac{(2n)!}{n!n!} = \frac{2n \cdot \ldots \cdot (n+1)}{n \cdot \ldots \cdot 1} = \frac{2n}{n} \cdot (\ldots )\cdot \frac{n+1}{1}$. Each factor in this product is at least 2 and there are $n$ factors, so this is at least $2^n$.

---
Tags: longest-common-substring
---


# Question
Title: Is it possible to build any regular expression in a computer language with just 3 basic operators?
Many computer languages have complex regular expressions tools. For example, in Javascript you have global flags, escape characters, whitespace character, assertions, character classes, groups and ranges etc. I'm wondering if using just the 3 basic regular expressions operators as defined in formal languages, that is concatenation, alternation and Kleene star can achieve the same result as any pattern described with more tools as for example in Javascript. Is there a theorem about this?

# Answer
> 25 votes
Regular expressions using only concatenation, alternation and Kleene star describe regular languages. In contrast, extended regular expressions available in modern programming languages can describe non-regular languages. For example, `(.*)\1` describes the language $\\{ ww : w \in \Sigma^\* \\}$, which is not even context-free.

# Answer
> 1 votes
Most real-world regular expression constructs can be converted to what I lovingly call ivory tower regular expressions.

For example:

* $a? = (\epsilon + a)$
* $a+ = a(a\*)$
* $a\\{n,m\\} = aaa\ldots{}a(a?)(a?)\ldots{}(a?)$ where $a$ is repeated $n$ times and $(a?)$ is repeated $m$ times.

Most lookahead operations can be expressed as the intersection of two languages (perhaps you need some clever product constructions, starting from the state you are currently at, or some such tricks and techniques).

Back-references make the whole exercise NP-complete, though; see e.g. https://perl.plover.com/NPC/NPC-3COL.html.

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


# Question
Title: Find the 'best' longest common subsequence
I am writing a program that computes and displays diffs. I implemented Meyers algorithm that computes the LCS between 2 subsequences (`seq1` and `seq2`); its output is one of the possible LCS and a partition of `seq1` and `seq2`, one projection of which is `lcs`.

I want to improve it so that the LCS displayed minimizes the number of breaks; to do so, I implemented a function `f(lcs, seq)`:

* `seq` is a sequence of characters
* `lcs` is a subsequence of `seq`
* the output is a partition of `seq` `p0, p1, p2, ... pn` such as
    + either `p0 + p2 +` or `p1 + p3 + ...` is `lcs`
    + and `n` is minimal

I did so using some sort of BFS, at each step finding the next element non-covered in `lcs` in `seq` and greedily expanding the common part.

The resulting algorithm is quite slow: on a typical input, ~3x slower that the Myers algorithm which seems to compute something way more complex. See code here: https://github.com/mookid/diffr/blob/c9ed7746193fd9833ddce1237d6e5005e91deaf4/diffr-lib/src/best\_projection.rs

Am I missing a better algorithm?

# Answer
> 1 votes
Your applications may be different from mine, but I think want you want is to input two strings $a$ and $b$ and output a diff $d$ such that no diff is shorter than $d$ and no *shortest* diff has fewer breaks than $d$. By a diff I mean the algebraic data type `List of ((CommonToBoth | FromLeftString | FromRightString) * Char)`, best expressed in Rust as a sequence of a three-variant Enum, each storing a character (or a `T`, if generic). Minimizing breaks amounts roughly minimizing the number of runs of `CommonToBoth`. \[Concretely I call mine `Common`, `Insert` and `Delete`.\]

I'm not sure that computing a break-minimizing matching $m\_a$ between $d$ and $a$ and a break-minimizing matching $m\_b$ between $d$ and $b$ will let you compute a break-minimizing matching $m\_{ab} = g(m\_a, m\_b)$ between $d$ and \[$a$ and $b$ simultaneously\], which is the thing I think you really want.

I've managed to compute a shortest diff with the smallest number of breaks, using an adaptation of Wagner-Fischer (dynamic programming, $O(n^2)$ space for a big table).

Normally you store the LCS length in the Wagner-Fischer table. Instead of doing that, you can choose a score of your own and store it instead. I've used triples similar to `(lcsLength, numberOfBreaks, isCurrentRunSharedOrEdits)`. There's a trick: when characters don't match you need to do something more complicated than `max`, and when they do it's not always dominant to include the particular match you're looking at: table entry `(i, j)` is the best among `adjustScoreInMatchingCase(table[i-1, j-1])` and `combineMismatchingScore(table[i-1, j], table[i, j-1])`, where the two functions depend on the particulars of how you score things.

This works, but takes $O(n^2)$ time and space. I can't do much about asymptotic time (provably so if the exponential time hypothesis is true, IINM). I think you can improve the space requirements by only storing the previous and current row of the table; you don't refer back more than a single row in the Wagner-Fischer algorithm.

Incidentally, I think the logic in the Myers algorithm which cleverly constructs and (re)uses the `v` array doesn't work in this case; the fact that if `a[i] == b[j]` you don't always extend from `LCS(a[..i-1], b[..j-1])` is rooted in the reason why we can't trivially extend the `v` array. But I might be wrong, I haven't fully explored the problem.

Postscript: Unless smake is a new build tool I haven't heard about, you probably want to rename `max_sMake_len` ($m \rightarrow n$). If you like property testing you may want to steal my tests at https://github.com/jonaskoelker/equate/blob/master/test/EquateProperties.scala; but beware, one or two of them have slightly wrong labels.

---
Tags: dynamic-programming, strings, graph-traversal, string-matching
---


title: Is A and C NP-complete?

text:
# Question
Title: Is A and C NP-complete?
Given 3 decision problems in $NP$: $A,B,C$. Consider that there are $2$ reduction algorithms, one is $A\le\_p B$ (with run-time $n^{10}$) and the other is $B\le\_p C$ (with run-time $n^5$).

If $B$ is $NP-complete$, is it valid to say that $A$ and $C$ are also $NP-complete$?

# Answer
Note that, if we reduce problem $\mathcal{A}$ to $\mathcal{B}$ in polynomial time, formally $\mathcal{A}\le\_p \mathcal{B}$, then we can conclude that, $\mathcal{B}$ is at least hard as $\mathcal{A}$, so according to your question, we can't conclude that $\mathcal{A}$ should be NP-Complete, because it can be member of $\mathcal{P}$. But because of $\mathcal{B}\le\_p \mathcal{C}$, we can say that $\mathcal{C}$ is at least NP-Complete.
> 1 votes

# Answer
Only $C$ will be $NP-complete$

To say that a language $L$ is $NP-complete$, you need two things:

1. $L\in NP$
2. $L\in NP-hard$

The reductions $A\le\_p B\le\_p C$ will guarantee you that:

1. $A\in NP$, but it won't guarantee that $A\in NP-hard$
2. $C\in NP-hard$, and since we assumed it was in $NP$ as well then $C\in NP-complete$

Hence, we cannot conclude that $A$ $NP-complete$, but we can say that $C$ is.
> 0 votes

---
Tags: np-complete, reductions, decision-problem
---


# Question
Title: Three dimensional matching expressed as SAT
The posting in the website Embedding SATISFIABILITY into 3-DIMENSIONAL MATCHING seeks $3SAT$ as a $3$ dimensional matching instance.

I am looking to solve the converse problem. How to solve three dimensional matching using SAT solvers?

I know 3dm is NP complete and so can be solved by SAT. How do you embed 3DM as a SAT instance to be solved by solvers?

# Answer
> 3 votes
You can express 3DM as SAT in several ways.

First, let us recall that in 3-dimensional matching we are given a list of triples $T \subseteq X \times Y \times Z$, consisting of triples $(x\_1,y\_1,z\_1),\ldots,(x\_n,y\_n,z\_n)$, and a number $k$, and the question is whether there are $k$ triples $(x\_{i\_1},y\_{i\_1},z\_{i\_1}),\ldots,(x\_{i\_k},y\_{i\_k},z\_{i\_k})$ such that $x\_{i\_r} \neq x\_{i\_s}$, $y\_{i\_r} \neq y\_{i\_s}$, $z\_{i\_r} \neq z\_{i\_s}$ for $r \neq s$.

**Unary encoding**

For every $1 \leq r \leq k$ and $1 \leq i \leq n$ we have a variable $t\_{r,i}$, whose meaning is "$i\_r = i$".

For every $1 \leq r \leq k$, we have the constraint $$ \bigvee\_{i=1}^n t\_{r,i}, $$ stating that some triple must be the $r$'th triple.

For every $r \neq s$ and $i,j$ (possibly $i=j$) such that $x\_i = x\_j$, or $y\_i = y\_j$, or $z\_i = z\_j$, we have the constraint $$\lnot t\_{r,i} \lor \lnot t\_{s,j}, $$ stating that you cannot choose both the $i$'th triple and the $j$'th triple (when $i = j$, that you cannot choose the same triple twice).

**Binary encoding**

Let $\ell = \lceil \log\_2 n \rceil$. For every $1 \leq r \leq k$ we have an $\ell$-tuple of variables $\vec{t}\_r$ which encodes the index of the $r$'th triple. The constraints are:

* For all $r$, clauses encoding "$\vec{t}\_r \leq n$". This can be encoded using at most $\ell$ clauses (for each $r$).
* For all $r \neq s$ and $i,j$ as in unary encoding, a clause encoding "$\vec{t}\_r \neq i$ or $\vec{t}\_s \neq j$".

I'll let you work out how to express these as clauses.

---
Tags: np-complete, satisfiability, matching, 3-sat, sat-solvers
---


# Question
Title: Would all objects in a reversible computing language be mutable?
Full disclosure, I'm asking this after watching a couple pop science videos; I do not know anything about the actual physics and hardware. I suspect the presenters expected an audience like me because they explained irreversibility at the level of a *programming* language ( `irreversible_add(a, b) = a+b` erases information; `reversible_add(a, b) = (a, a+b)` does not ) and simply said "reversibility must be at every level of abstraction".

Would such an irreversible programming language have to use mutable objects to avoid erasing information? In contrast, some programming languages treat primitive types as immutable, so a statement like `a += 1` would create a new number, rebind the name `a` to that new number, and discard the old number. For example, this means `reversible_add(a, b) = (a, a+b)` would in fact discard the number bound to the name `b`.

Almost all sources that I have run across talk about reversibility at a hardware level (logic gates). I did find a source about immutable objects (strings) in a reversible programming language (Arrow), but reading it didn't answer my question.

# Answer
No. For example,

```
c := a
d := a+b

```

avoids erasing information; but it does not use any mutable objects (c,d can be fresh variables that are assigned only once). It is not clear to me why you think that avoiding information erasure requires mutable objects, or what is the exact definition of an irreversible programming language.
> 1 votes

---
Tags: programming-languages, reversible-computing
---


# Question
Title: Complexity analysis for finding all powers of 2 within a range
Suppose you're given $x,y$ integers s.t. $x \leq y$. I want to find all values $\in \[x, y\]$ (inclusive) that are a power of $2$.

There's a $O(\log y)$ approach, where you just start at $1$, and keeping multiplying by $2$ until you get to the first value that is $\geq x$. Then you can start storing these values until you get to a power of 2 that is $\> y$.

There's another approach that I believe is $O( \log (\log b))$, but I am not certain. The idea I am thinking of is rather than multiplying by $2$ each time, you square the value. So you'd have to start at $2$, then check $4$, then $16$, then $256$ and so on until you find the first value that is $\>= x$. Say this value is $k$ where $k \geq x$. I believe finding $k$ is $O(\log(\log b))$. Is that correct?

After finding $k$, you can keep dividing by $2$ until you get a value that is $\< x$ and store all the values along the way (unless it's greater than $y$). Then you can do this in the upward direction and keep multiplying by $2$ until you get to a value that's greater than $y$. It's not clear to me what the complexity of this step is. I want to say it's $O(\log (\log b))$ as well, but it seems it may actually be $O(\log b)$.

# Answer
> 2 votes
Yes, that is correct, in a sense, but there is also a sense in which it is not correct.

You want to find $j$ such that $2^j \in \[x,y\]$. The naive algorithm uses linear search on $j$. Your proposed algorithm amounts to binary search on $j$ (starting with iterative doubling). So your analysis is correct, that it uses $O(\log \log y)$ iterations.

The shortcoming of your analysis is that you assume each iteration can be done in $O(1)$ time. This might be accurate, or it might not, depending on the specific theoretical model of computation you are using. In practice, it is probably not reasonable, if $x,y$ are very large, as the running time of each iteration is not $O(1)$. For instance, squaring a $n$-bit number takes $O(n)$ time (in many reasonable ways of measuring running time); here we have $n=\lg y$, so each iteration takes $O(\log y)$ time, for a total running time of $O((\log y)(\log \log y))$ time (at least under one way of measuring running time).

Another way to put it is that it takes $O(\lg y)$ time even just to read the input or produce the desired output, because the output will be $\Omega(\lg y)$ bits long, and the time it takes to print such an output is proportional to its length.

# Answer
> -1 votes
A simple algorithms is, start from $x$, and check whether it's power of $2$ or not, then increment one by one until you get $y$, this algorithm need $\mathcal{O}(y-x)$ steps, that each steps needs to read $\mathcal{O}(\log i)$ bits. Hence the running time is $$\sum\_{i=x}^{y}\mathcal{O}(1+\log i)=\mathcal{O}\left(y-x+\log \left(\frac{y!}{(x-1)!}\right)\right)\leq\mathcal{O}((y-x)\log y)$$.

**So the lower bound for solving your problem is $\mathcal{\Omega}(\log y)$ .**

Note that, by using Binary search idea, we can at each step increment the counter by a $2^{2^c}$ that reduce the running time to $\mathcal{O}(\log y\log\log(y-x))$.

---
Tags: time-complexity
---


# Question
Title: Why is $\mathcal{D}^m(\{S:L_{(\mathcal{D},f)}(A(S))\gt \epsilon\})\leq \mathcal{D}^m\left(\bigcup^4_{i=1}F_i\right)$ true?
I am studying the book "Understanding Machine Learning: From Theory to Algorithms". I am struggling to understand the solution to exercise 3 (2) on page 41.

Exercise:

> An axis aligned rectangle classifier in the plane is a classifier that assigns 1 to a point if and only if it is inside a certain rectangle. Formally, given real numbers $a\_1\leq b\_1, a\_2\leq b\_2,$ define the classifier $h\_{(a\_1, b\_1, a\_2, b\_2)}$ by $$ h\_{(a\_1, b\_1, a\_2, b\_2)}(x\_1, x\_2) = \begin{cases}1&\textrm{if $a\_1\leq x\_1\leq b\_1$ and $a\_2\leq x\_2\leq b\_2$}\\ 0&\textrm{otherwise}\end{cases} $$ The class of all axis aligned rectangles in the plane is defined as $\mathcal{H}\_\mathrm{rec}^2 = \\{h\_{(a\_1, b\_1, a\_2, b\_2)}:\textrm{$a\_1\leq b\_1$ and $a\_2\leq b\_2$}\\}$...rely on realizability assumption. Let $A$ be an algorithm that returns the smallest rectangle enclosing all positive examples in the training set. It is shown in (1) that $A$ is an ERM.

> (2): Show that if $A$ receives a training set of size $\geq \frac{4\log(4/\delta)}{\epsilon}$ then, with probability of at least $1-\delta$ it returns a hypothesis with error of at most $\epsilon$.

> Hint: Fix some distribution $\mathcal{D}$ over $\mathcal{X}$, let $R^\*=R(a\_1^\*,b\_1^\*,a\_2^\*,b\_2^\*)$ be the rectangle that generates the labels, and let $f$ be the corresponding hypothesis. Let $a\_1\geq a\_1^\*$ be a number such that the probability mass (w.r.t $\mathcal{D}$) of the rectangle $R\_1=R(a\_1^\*,a\_1,a\_2^\*,b\_2^\*)$ is exactly $\epsilon/4$. Similarly, let $b\_1,a\_2,b\_2$ be numbers suh that the probability masses of the rectangles $R\_2=R(b\_1,b\_1^\*,a\_2^\*,b\_2^\*),R\_3=R(a\_1^\*,b\_1^\*,a\_2^\*,a\_2),R\_4=R(a\_1^\*,b\_1^\*,b\_2,b\_2^\*)$ are all exactly $\epsilon/4$. Let $R(S)$ be the rectanlge returned by $A$. See the following illustration:

* Show that $R(S)\subset R^\*$
* Show that if $S$ contains (positive) examples in all of the rectangles $R\_1,R\_2,R\_3,R\_4$, then the hypothesis returned by $A$ has error of at most $\epsilon$.
* For each $i\in\\{1,...,4\\}$, upper bound the probability that $S$ does not contain an example from $R\_i$
* Use the union bound to conclude the argument.

From the solution manual, here is the answer on page 2:

Fix some distribution $\mathcal{D}$ over $\mathcal{X}$, and define $R^\*$ as in the hint. Let $f$ be the hypothesis associated with $R^\*$ a training $S$, denoted $R(S)$ the rectagnle returned by the proposed algorithm and by $A(S)$ the corresponding hypothesis. The definition of algorithm $A$ implies that $R(S)\subset R^\*$ for every $S$. Thus, $$L\_{(\mathcal{D},f)}(R(S))=\mathcal{D}(R^\*\setminus R(S))$$

Fix some $\epsilon\in(0,1)$. Define $R\_1,R\_2,R\_3,R\_4$ as in the hint. For each $i\in\[4\]$, define the event $$F\_i=\\{S|\_x:S|\_x\cap R\_i=\emptyset\\}$$

Applying the union bound we obtain

$$\mathcal{D}^m(\\{S:L\_{(\mathcal{D},f)}(A(S))\gt \epsilon\\})\leq \mathcal{D}^m\left(\bigcup^4\_{i=1}F\_i\right)\leq \sum^4\_{i=1}\mathcal{D}^m(F\_i)$$

So the above is what I don't understand:

Why is $$\mathcal{D}^m(\\{S:L\_{(\mathcal{D},f)}(A(S))\gt \epsilon\\})\leq \mathcal{D}^m\left(\bigcup^4\_{i=1}F\_i\right)$$

I know what these quantities mean:

* $\mathcal{D}^m(\\{S:L\_{(\mathcal{D},f)}(A(S))\gt \epsilon\\})$ is equivalent to "the probability of observing samples $S$ such that when algorithm $A$ is applied to $S$, the true error is greater than $\epsilon$.
* $\mathcal{D}^m\left(\bigcup^4\_{i=1}F\_i\right)$ is equivalent to "the probability of observing samples which don't intersect $R\_1$ or $R\_2$ or $R\_3$ or $R\_4$.

But why is the inequality true? The root of my understanding is that I can't understand how $\epsilon$ and $A(S)$ are supposed to be involved in interpreting this inequality. As in I don't understand geometrically how $A(S)$ and $\epsilon$ form subsets in the context of the figure above. I can easily imagine the sets $F\_i$ though.

# Answer
> 0 votes
Lets say our algorithm chose some rectangle $\hat R$ with (true) error bigger than $\epsilon$. To prove the inequality, we want to show that we are in one of the 4 events: $F\_1,F\_2,F\_3,F\_4$.

Notice - that we know that $\hat R\subseteq R^\*$. Therefore, intuitively, the entire $\epsilon$ error comes from the fact that $\hat R$ is "much smaller" than $R^\*$.

Now, from the pigeonhole principle - since we have $\epsilon$ error that is "distributed" between the $4$ sides, we know that at least one side must contribute with *at least* $\frac{\epsilon}{4}$ error. Formally you can see this from an extension of the pigeonhole principle.

Combining the last two statements, you can conclude that we are in one of the events $F\_1,F\_2,F\_3,F\_4$ as required.

---
Tags: machine-learning, probability-theory
---


# Question
Title: Is the differential privacy definition with lower and upper bound equivalent to the definition with just an upper bound?
According to Wikipedia, given a randomized algorithm $\mathcal{A}$, two neighboring datasets $D\_1, D\_2$, a real number $\epsilon \> 0$, $\mathcal{A}$ provides $\epsilon$-differential privacy, if $$ \frac{\mathbb{P}\[\mathcal{A}(D\_1) \in S\]}{\mathbb{P}\[\mathcal{A}(D\_2) \in S\]} \leq e^\epsilon $$ for all subsets $S$ of $\mathcal{A}$’s support.

However, I've stumbled across a different definition of $\epsilon$-DP, where also a lower bound is required: $$ e^{-\epsilon} \leq \frac{\mathbb{P}\[\mathcal{A}(D\_1) \in S\]}{\mathbb{P}\[\mathcal{A}(D\_2) \in S\]} \leq e^\epsilon. $$ Are these two definitions equivalent?

# Answer
Yes, the definitions are equivalent. That the second implies the first is obvious. To see that the first implies the second, note that the datasets $D\_1,D\_2$ can be interchanged. So, if

$$ \frac{\mathbb{P}\[\mathcal{A}(D\_1) \in S\]}{\mathbb{P}\[\mathcal{A}(D\_2) \in S\]} \leq e^\epsilon $$

for all $D\_1,D\_2$, then in particular

$$ \frac{\mathbb{P}\[\mathcal{A}(D'\_2) \in S\]}{\mathbb{P}\[\mathcal{A}(D'\_1) \in S\]} \leq e^\epsilon, $$ hence $$ \frac{\mathbb{P}\[\mathcal{A}(D'\_1) \in S\]}{\mathbb{P}\[\mathcal{A}(D'\_2) \in S\]} \geq e^{-\epsilon}, $$ because all values are positive.
> 5 votes

---
Tags: cryptography, differential-privacy
---


# Question
Title: How do we say there is A Turing machine when it does not halt
Generally we will say there is A DFA for a language if we give a string to that DFA and after processing it it will reach to DFA and DFA more or less stops at final state,so then we say there is a DFA, and if that string does not reach final state we say there is no DFA

In Contrast

When it is case for Recursively enumerable language how do you say there is a turing machine for a language if it never halts as we don't know whether it halts or not so its like its not reaching any state to be called as turing machine for that language.

# Answer
> 1 votes
The definition of a $TM$ for a language is the following:

The language of a TM $M$ is defined as $L(M):=\\{w\in \Sigma^\* \mid M(w) \text{ halts and accepts}\\}$

Now, for a fixed language $L\_0$, we say that $M$ is a TM for $L\_0$ if $L(M)=L\_0$.

# Answer
> 1 votes
*There is a machine* for some language is a shorthand for, either:

* some machine can *accept* the language, or
* some machine can *decide* the language.

They are subtly different things.

When a machine *decides* a language, and you throw a string at it, it is guaranteed to confirm that the string is in the language, when it is, and to confirm that it is *not* in the language, when it is not.

When a machine *accepts* a language, and you throw a string at it, it is guaranteed to confirm that the string is in the language, when it is, and to *not* produce the verdict that it is in the language, when it is not - but in that case, it may fail to produce any verdict at all.

DFAs always produce a verdict for any string you throw at them: just run the DFA on the string, which will take one step for each character of the string, and when you're done, check whether the DFA is in an accepting state. So DFAs always decide a language, and when we say there is a DFA for a language, we always mean it decides the language.

Not so for TMs. They accept and decide languages differently: they always run until they are in a halting state, and they may never get there. The reason we need to allow this, and that we need to make the distinction between accepting and deciding a language for TMs, is that some languages are *semidecidable* (some machine accepts them) but not *decidable* (no machine decides them). So the best we can do, for such languages, is to have a machine that accepts them but does not decide them.

---
Tags: turing-machines, turing-test
---


title: What are address shadows?

text:
# Question
Title: What are address shadows?
In my uni lecture, I am covering address decoding. I understand that memory addresses are decoded to find if they point to the RAM, ROM, or I/O, by way of the address (in the example of BBC Micro) being in the RAM range, user ROM range or OS ROM range (e.g. 0x0000 to 0x7FFF is the range of RAM in the address space).

Addresses can be decoded as little as possible, that is, the minimum number of bits in the address are checked to determine the chip select signal, the signal which determines which chip to access. This approach allows for 'address shadows'. Now I'm not sure what this means, I'm repeating my lecturer.

What I understand address shadows to be are addresses which will point to the same place in memory as another, but only because we are decoding the address as little as possible.

The example my professor gave is of the original Apple Macintosh. The SCC READ chip had addresses from 90000 to A0000, but it only had 4 or 5 registers. This meant the same registers were repeated in memory, which is what an address shadow or mirror is.

Could someone expand on or correct this definition, because web searches have not turned up much fruitful information.

Thanks

# Answer
> 2 votes
Suppose you have a 16-bit CPU (65536 bytes of address space) and you have 2 16kB (16384-byte) RAM chips (and nothing else). How do you connect them together?

Each chip has 14 address pins. You connect those directly between both chips and the CPU.

You take the 15th address pin from the CPU and connect it to one RAM chip's chip-select pin. You also connect it to a NOT gate and you connect the output of the NOT gate to the other RAM chip's chip-select pin.

The 16th address pin on the CPU is not connected to anything, because it is not minimally required to make the system work with two 16k RAM chips.

The address space which this arrangement forms, looks like this:

```
+-------------+ 0xFFFF
| also chip 2 |
+-------------+ 0xC000
| also chip 1 |
+-------------+ 0x8000
|   chip 2    |
+-------------+ 0x4000
|   chip 1    |
+-------------+ 0x0000

```

Because the 16th address pin is not connected, addresses 0x8000 and 0x0000 (for example) act exactly the same on the hardware level. The only difference is the 16th address pin, which is not connected to anything. Byte 0 of chip 1 is intended to be accessed at address 0x0000, but you can also access it at address 0x8000. This is called a "mirror" or "shadow".

The official documentation for the system would probably tell you not to use addresses above 0x7FFF. This leaves room for them to add more RAM, ROM or peripherals in that space in the future, which would break the mirroring.

You might find more information by using the term "mirror" instead of "shadow", or then again, you might not. Once you understand the concept, it is very simple, so maybe few people bother to write about it.

---
Tags: memory-management, cpu, memory-access
---


# Question
Title: Topological sort and finding longest path in DAG to solve a stacking boxes variation (no rotation)
Given n elements (boxes) I have to output the max number of boxes that can fit one into another. Each box has width (x), height (y) and depth (z). One box j can hold another box k if: `j.x > k.x and j.y > k.y and j.z > k.z`. Rotation is not allowed.

Searching some approaches on the net, I found this can be a way:

```
organize boxes in a directed unweighted graph where the edge (j,k) means j holds k
use topological sort on the grapgh
find the longest path and print it

```

I'm trying to better understand what will happen after doing the topological sort on the graph. If I understand correctly, I should be able to perform topological sort with a DFS-visit variation. In an example I've seen, the output of the sort is a single linked list. So if i output the list, why this is not already the longest path (meaning the longest sequence of boxes that can fit one into another)? If that's not the case and I also need to find the longest path, do I need to do it on the new graph made by the edges in the list returned by the topological sort (meaning it'll be a directed acyclic graph)?

# Answer
> 1 votes
The topological order is **not** guaranteed to be a solution. Indeed the topological order clearly has length $n$ while there are instances in which it is not possible to stack all boxes. As an example consider $n=2$ boxes that do not fit into one another (e.g., with sizes $(1,1,2)$ and $(1,2,1)$).

You need to find the longest path in the original graph. You can do that by computing the longest path from each vertex $v$. In order to do so let $G=(V,E)$ be the graph (notice that $G$ is acyclic!), let $\sigma = \langle v\_1, v\_2, \dots, v\_n \rangle$ be a topological order of $G$, and define $d(v\_i)$ as the length of the longest path starting from $v\_i$ in $G$. When the out-degree of $v\_i$ is $0$ we have $d(v\_i)=0$. Otherwise we have: $$ d(v\_i) = 1 + \max\_{(v\_i,v\_j) \in E} d(v\_j). $$ Notice that, by the definition of topological order, $v\_j$ must follow $v\_i$ in $\sigma$. This means that we can compute all values $d(v\_i)$ using a dynamic programming algorithm that examines the vertices of $G$ in reverse topological order. To find a longest path (rather than just the path's length), and hence the sequences of boxes to stack, you can store for each $v\_i$ a value $\pi(v\_i) \in \arg \max\_{(v\_i,v\_j) \in E} d(v\_j)$. Then, if $v^\*$ maximizes $d(v^\*)$, the sought path is: $$ \underbrace{ v^\*, \pi(v^\*), \pi(\pi(v^\*)), \pi(\pi(\pi(v^\*))), \dots}\_{d(v^\*)+1\mbox{ times}} $$

The whole algorithm can also be formulated in terms of boxes, doing away with the graph $G$. The main observation is that if box $b\_1$ stacks into box $b\_2$ then the volume of $b\_1$ must be smaller than the volume of $b\_2$. As a consequence, it suffices to consider boxes in non-decreasing order of volume.

---
Tags: graphs, time-complexity, graph-traversal, dag, topological-ordering
---


# Question
Title: XOR gate from default-on/default-off relays, this simplest possible?
Playing nandgate to learn logical gates. Is the design below the simplest xor gate that can be built using the relays available? Seems like crossover relays allow a much simpler xor gate but don't have those there.

# Answer
> 1 votes
"Simplest" is not well-defined so I assume you are interested in knowing if you can use less than 7 relays of types "default-off" or "default-on".

It seems that a default-off relay is essentially an "and" gate (both the "in" and the "on" input must be high for the output to be "high"). I will denote this with $\wedge$.

A default-on relay is essentially an "and" gate where one of its inputs is negated. I will denote $\neg a \wedge b$ with $a \otimes b$ (notice that $\otimes$ is not commutative!). As a consequence, $a \otimes 1 = \neg a \wedge 1 = \neg a$ and $$ a \vee b = \neg (\neg a \wedge \neg b) = ((a \otimes 1) \wedge (b \otimes 1)) \otimes 1. $$ This shows that $a \vee b$ can be computed using $4$ relays.

Consider then:

$$ \begin{align\*} a \oplus b &= (\neg a \wedge b) \vee (\neg b \wedge a) = (a \otimes b) \vee (b \otimes a) \\ &= (((a \otimes b) \otimes 1) \wedge ((b \otimes a) \otimes 1)) \otimes 1 \end{align\*} $$

This shows that $a \oplus b$ can be computed using at most $6$ relays, while your solution uses 7.

---

Following you comment it seems that you are interested in minimizing the number of relays. The following solution uses only 5 relays. Let $ \overline{b} = \neg b = b \otimes 1$. Then: $$ a \oplus b = (a \otimes \overline{b}) \otimes ((\overline{b} \otimes a) \otimes 1). $$

Notice that $\overline{b}$ can be found using only one relay but it is then used twice in the expression for $a \oplus b$. Here is the corresponding truth table:

| $a$ | $b$ | $\overline{b}$ | $a \otimes \overline{b}$ | $\overline{b} \otimes a$ | $(\overline{b} \otimes a) \otimes 1$ | $(a \otimes \overline{b}) \otimes ((\overline{b} \otimes a) \otimes 1)$ |
| --- | --- | --- | --- | --- | --- | --- |
| 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 0 |

An exhaustive search shows that there are no solutions using at most 4 relays. Moreover, this shows that $5$ relays suffice even when just default-off relays are available.

---
Tags: logic
---


# Question
Title: How does fan-out change circuit complexity?
Edit: Here's maybe a clearer presentation of my question. In a Boolean formula, all the gates have fan-out 1, and the graph representing the formula is a tree. In a Boolean circuit, the gates can have multiple outputs. What can be said about formula size as compared to circuit size?

I am learning some basics about classical circuit complexity, and have a confusion centering around the role of fan-out.

In various references (e.g. the textbook by Vollmer), circuit size is defined with respect to a basis where each gate has fan-out 1, like say AND, OR and NOT. A natural, simple operation seems to me to be fan-out, where I just copy a bit so it can be used twice in the circuit.

I am wondering how allowing fan-out changes the size of a minimal circuit computing a Boolean function.

A naive observation is that if I have a circuit of depth d that uses fan-out (say with two outputs), I could replace it with a circuit without fan-out while increasing the circuit size by at most $2^d$ (make a copy of the circuit below each fan-out, to compute that bit twice). Unless $d$ is $O(\log n)$ for $n$ the input size, this changes a polynomial size circuit to a super-polynomial one, so at least using this observation alone fan-out seems to have a notable effect on circuit size.

Is there a better way to remove fan-out gates than the above? Or is there a motivation for focusing on notions of circuit size / complexity that exclude fan-out?

# Answer
> 1 votes
Restricting fan-out is crucial in reversible computing, in which duplicating values is impossible. This is related to quantum computing.

Another circuit model without fan-out which has been studied recently is *comparator circuits*, see for example Mayr and Subramanian, The complexity of circuit value and network stability or the more recent The complexity of the comparator circuit value problem. Comparator circuits are not expected to be P-complete, and in particular, are expected to be weaker than circuits which do allow fan-out. See Comparator Circuits over Finite Bounded Posets for what happens when we allow the wires to carry values from different posets (rather than the Boolean lattice $\\{0,1\\}$).

---
Tags: complexity-theory, circuits
---


# Question
Title: Intuitive reason why the language of halting machines is Turing reducible but not many-one reducible to its complement
I have seen this statement in my studies and I cannot figure out why it is true.

We know that $P\_{HALT} \leq\_T \overline{P\_{HALT}}$, but $P\_{HALT} \leq\_m \overline{P\_{HALT}}$ does not hold.

I know, that If the many-one-reduction was possible, then both problems were semi-decidable, which makes the Halting problem decidable. But I would prefer a more intuitive answer.

# Answer
If $P\_{\mathrm{HALT}} \leq\_m \overline{P\_{\mathrm{HALT}}}$ then given a Turing machine $M$, you can come up with another Turing machine $M'$ such that $M$ halts iff $M'$ doesn't halt (in both cases, we run the machine on a blank tape). Let's break this into two conditions:

1. If $M$ halts then $M'$ doesn't halt.
2. If $M$ doesn't halt then $M'$ halts.

It is easy to satisfy the first condition: $M'$ can simulate $M$, and if $M$ halts, enter an infinite loop. However, it is not clear how to satisfy the second condition — how can you tell that $M$ doesn't halt? This is, intuitively, the reason that no such reduction exists.

In contrast, $P\_{\mathrm{HALT}} \leq\_T \overline{P\_{\mathrm{HALT}}}$ trivially: you can solve the halting problem given an oracle for the not-halting problem. If you don't see it immediately (as you indicate in the comments), then you haven't internalized the definition of a Turing reduction.
> 1 votes

---
Tags: reductions, undecidability
---


# Question
Title: How to represent $x$ in hexadecimal form where $x=2^n$?
When a value $x$ is a power of $2$, that is, $x = 2^n$ for some nonnegative integer n, we can readily write $x$ in hexadecimal form by remembering that the binary representation of $x$ is simply $1$ followed by $n$ zeros. The hexadecimal digit $0$ represents $4$ binary zeros. So, for $n$ written in the form $i + 4j$ , where $0 ≤ i ≤ 3$, we can write x with a leading hex digit of 1 (i = 0), 2 (i = 1), 4 (i = 2), or 8 $(i = 3)$, followed by $j$ hexadecimal $0$s. As an example, for $x = 2,048 = 2^{11}$, we have $n = 11= 3 + 4 . 2$, giving hexadecimal representation `0x800`.

I have few questions about the above statement.

Firstly, if $x = 2^n$, then why the binary representation of $x$ is simply $1$ followed by $n$ zeros? More specifically, why $1$? We can see the representation at the end is `0x800`, which is $8$ followed by $2$ zeros.

Secondly, the form $i + 4j$, since the hexadecimal digit $0$ represents $4$ binary zeros, I guess there is some relation between. But I'm still not clear why.

I'm not sure if I can totally understand it if I solved these two questions. I feel mess up. I'll appreciate it if someone can expand this statement and make a better explanation.

Thank you so much!

# Answer
> 2 votes
> Firstly, if x=2n, then why the binary representation of x is simply 1 followed by n zeros?

That's how positional numeral systems work. If you are writing (natural) numbers in base $b$ then the least significant digit can represent any amount between $0$ and $b-1$, then 2nd least significant digit represents one of $0, b, 2b, \dots, (b-2)b$, or $(b-1)b$, and so on so forth. In general, if the value of $i$-th least significant digit is $x\_i$, then the contribution of that digit to the represented number is $x b^{i-1}$.

If there are $n$ digits $x\_n, x\_{n-1}, \dots, x\_1$ (from the most to the least significant) then, the represented number is: $$ \sum\_{i=1}^n x\_i b^{i-1} $$

As a consequence, adding a $0$ in the least significant position has the effect of multiplying the represented number by $b$. Therefore, for the special case $b=2$, we have that $2^0=1$ and $2^n$ can be written (in base $2$) by starting with $1$ and multiplying it $n$ times by $2$. This amounts to appending $n$ zeros.

> Secondly, the form i+4j, since the hexadecimal digit 0 represents 4 binary zeros, I guess there is some relation between. But I'm still not clear why

Since $16 = 2^4$, you can think of each hexadecimal digit as representing 4 binary digits. For example $(A7)\_{16} = (1010 \\; 0111)\_2$ where $(1010)\_2$ is represented by $(A)\_{16}$ and $(0111)\_2$ is represented by $(7)\_{16}$.

Then, to convert a binary number into an hexadecimal number you can just just arrange the binary digits into groups of four (with suitable padding of the leading zeros) and replace each group with the corresponding hexadecimal digit.

Since $2^n$ has exactly one $1$ when written in binary (and this is the $(n+1)\mbox{-th}$ least significant digit) we know that we can form $j=\lfloor n/4 \rfloor$ groups of $4$ digits that are $(0000)\_2$ (and will be converted to $(0)\_{16}$), while the remaining group will have a $1$ followed by $i = n \bmod 4$ zeros (and will be converted to one of $(1)\_{16}$, $(2)\_{16}$, $(4)\_{16}$, or $(8)\_{16}$).

Equivalently, we are writing $n$ as $i + 4j$, where $i$ must be between $0$ and $3$.

---
Tags: integers, binary
---


# Question
Title: Why does random noise in recurring task periods result in uniform period offsets?
I have a recurring task which finished just now. I schedule it to run every ten minutes; the task will reoccur $10n$ minutes from now for all positive $n$. If instead I choose 50/50 between ten minutes and ten minutes plus one second, eventually all offsets (in seconds) relative to the start of a ten-minute period becomes equally likely (or rather we converge towards that), according to my simulations. Why is that?

Once more, with formality:

Let $a\_{0,0} = 1$ and $\\{a\_{1,0}, \ldots, a\_{n-1,0}\\} = \\{0\\}$. (Think of each $a\_{i,0}$ as representing one minutes within the hour; its value is the probability of the task running during that minute.)

Let some offsets $D \subseteq \\{0, \ldots, n\\}$ be given, with $D$ containing at least one pair of numbers $d\_1$ and $d\_2$ such that $gcd(d\_2 - d\_1, n) = 1$. (The offsets are uniformly sampled gaps between two successive runs of the task.)

Let $$a\_{i,t+1} = \frac{1}{\\|D\\|} \cdot \sum\_{\delta \in D} a\_{i-\delta,t}$$

**Conjecture**: $$\forall i \in \\{0, \ldots, n-1\\}: \lim\_{t \rightarrow \infty} a\_{i,t} = \frac{1}{n}$$

In other words, if we interpret the $a\_{i,\*}$ for each $t$ as a discrete probability distribution, it converges towards the uniform distribution on $\\{0, \ldots, n-1\\}$ as $t$ increases.

Is this true? How does one go about proving this? Is it more true or easier to prove if $D$ is restricted to be an interval?

# Answer
> 1 votes
This basically comes down to a fact about what happens when you take a normally distributed random variable (with large variance) and reduce it modulo 10.

Let $X\_i$ denote the additional offset (in minutes) in the $i$th iteration compared to the previous iteration. After $n$ iterations, let $Y=X\_1+\dots+X\_n$. Then $Y \bmod 10$ represents the offset of the last iteration, relative to the next lowest multiple of 10 minutes.

The $X\_i$ are iid, so by the Central Limit Theorem, $Y$ is approximately Gaussian with mean $n/120$ and standard deviation $\sqrt{n}/2$.

Now, when $Z \sim \mathcal{N}(n/120,\sqrt{n}/2)$ and $\sqrt{n}/2$ is much larger than 10, $Z \bmod 10$ is approximately uniformly distributed. I don't have a simple intuitive explanation for this, but if you want a very crude intuition, you can very roughly approximate $Z$ as distributed uniformly at random on the range $\[n/120-\sqrt{n}/2,n/120+\sqrt{n}/2\]$, and then if you take the uniform distribution on such a large interval and reduce it modulo $10$, the result will be approximately uniformly distributed. I realize this is not likely to be a convincing proof.

---
Tags: probability-theory, randomized-algorithms, scheduling, randomness, probabilistic-algorithms
---


# Question
Title: Which languages do Perl-compatible regular expressions recognize?
As the title says, I spent a couple of hours last weekend trying to wrap up my mind about the class of languages matched by Perl-compatible regular expressions, *excluding any matching operator that allows to execute arbitrary code inside the pattern*.

If you don't know what PCREs are, please read this and this.

The problem is, the resources available on internet pretty much stop at context-free languages, and PCREs can match more than those (see below); but I really don't know where to find more theorems or papers about this kind of stuff.

In particular: PCREs are obviously a superset of regular languages (as the PCRE syntax has all the regular language operators).

Any CFG can be put in Greibach normal form, which removes left recursion. I think this can be used by means of `(?(DEFINE)...)` groups to "translate" the grammar into matching subroutines, avoiding to choke on left recursion, by translating:

* the non-terminal at the head of each production becomes a subroutine `(?<HEAD>...)`
* the body of each production is put in the subroutine; terminals are left as-is, non-terminals become procedure invocations (i.e. `(?&NONTERMINAL)`);
* all the productions with the same nonterminal as head are ORed together by means of the `|` operator (plus additional grouping with `(?:...)`, if necessary)
* the pattern then becomes a `(?(DEFINE)...)` group containing all the "translated" productions, and an invocation for the procedure of the starting symbol, to match the entire string, i.e. `^(?(DEFINE)...)(?&START)$`

This should deal with any CFG. Therefore, PCREs should be able to match any CFL.

There's more: let's take the simple language $$L = \\{ ww | w \in \Lambda^\* \\} $$ i.e. the language of the strings repeated twice. This language is not a CFL -- the pumping lemma for CFLs fails. (Pay particular attention that $$ |vxw| \leq p$$ must hold, thus you can't just pump the beginnings or the ends of the two repeated strings.)

However, this language is easily matched by a PCRE: `^(.*)\1$`. Therefore, we're strictly above CFLs.

How much above? Well, as I said, I have no idea. I couldn't find any resources about CSLs or all the other classes in between to make up my mind. Any expert willing to discuss this?

**Addendum:** I was asked to specify exactly which subset of the PCRE syntax must be allowed. As I wrote at the beginning of the post, I wanted to exclude any operator that allows to execute arbitrary code inside of the pattern, such as `??{}`.

For the argument's sake, I think we can stick with the syntax defined by the pcresyntax(3) man page, which is a reasonable subset of what Perl 5.10-5.12 offers, minus the callouts (as they're not inside the pattern). I'm not sure that adding or removing backtracking control verbs change the language we can recognize; if so, it would be nice to figure out which classes we get with and without those.

# Answer
> 11 votes
I've also found this blog post extremely interesting http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html. It provides the very same proof I gave before about the fact that regexps recognizes the CFLs (by rewriting the grammar through `DEFINE` blocks), and even some CSLs (like the language of repeated strings); it builds on that and goes on, giving a proof that regexps with backreferences are NP-hard (by reducing 3-SAT to a regexp).

# Answer
> 7 votes
They decide at most the context-sensitive languages (which, as you point out, is a superset of the context-free languages). See this perl monks post.

The basic insight is that the "memory" of the machine is the number of capture groups, which is linearly bounded.

# Answer
> 6 votes
OP already linked an awesome blog post. I did some more research on it, and found the following pieces of information:

* Wikipedia article on Context-sensitive grammar mentions that right-context-sensitive grammars can express all general CSGs (at the end of section, near reference 13). Unfortunately, neither that nor the referenced page shows *how* to find an equivalent right-CSG for a given CSG.
* The blog post shows that lookbehind and lookahead assertions can be used to specify left and right context (α and β in αAβ → αγβ) respectively. Lookbehind is limited to fixed-length, but lookahead is not restricted at all.

Assuming both sources are true, any given CSG can be converted to a right-CSG, which can be expressed in Perl regex using lookahead. Therefore, **Perl regexes are strong enough to match all CSGs.**

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


# Question
Title: Why doesn't the compiler typecast the pointer and remove the error? (C++ Programming)
```
int *numPtr;
double num;
numPtr = #

```

This code shows an error as pointer points to data of different datatype. But why does it show the error? Why doesn't the compiler typecast the pointer and remove the error?

Just like a character becomes an integer as it is implicitly typecasted. (int a = 'a';) It should do similarly and remove the error.

# Answer
> 2 votes
```
Why doesn't the compiler typecast the pointer and remove the error?

```

What's allowed is not dictated by the compiler but by the C++ standard and implicit conversions from a "pointer to double" to a "pointer to int" are not allowed by the standard. See, e.g., section 7.11 here.

There is nothing, in principle, that prevents you from coming up with a C++-like language where the above program is well-formed, once you specify what the semantics of the above assignment is.

As it is, I don't see any obvious meaning of what you are trying to write and I believe that if you try to formally specify what your expected behavior is, you'll run into problems.

Notice that there is no object of type int. What would be the reasonable thing to do? Should the compiler create one new int for you, initialize it with the result of a cast from double to int, and then assign the address to numPtr? Should that be allocated on the stack or on the heap? If it's on the stack, should using the pointer outside the current scope be illegal? If it's on the heap, who's responsible for free-ing the allocated memory? How should changes on `num` reflect on `*numPtr`? Even worse, `numPtr` is not a pointer to a constant int, so how should changes to `*numPtr` reflect on `num`? What if a new pointer, say of type short, is initialized to `numPtr`?

If no new object is created, how do you reconcile the fact that two pointers of different (and incompatible) types point to the same memory address? (Recall that you can do `numPtr = reinterpret_cast<int*>(&num);` but dereferencing `numPtr` violates aliasing rules).

# Answer
> 0 votes
This is because casting from `char` to `int` is up-casting, since an `int` is "an extension" of a `char` (in `C`, it is the same "thing" except for that it has a larger storage size). You can think of it as the same as casting from `int` to `long`. Basically, we use `char` also for alphabet letters because its size is convenient, but it actually just represents a number with less storage.

However, casting a `double` to `int *` is doing a totally different thing, since you are asking to convert a *number* into a *pointer*. A number and a pointer are inherently two different things, and as such there is no "natural" conversion between them. Therefore, in order to avoid weird mistakes (since most likely you won't want to convert a number to a pointer), the compiler complains that it cannot cast it. However, you can tell the compiler you specifically meant for this cast to happen by explicitly writing a type cast, with the syntax: `(<type>) <variable name>` to convert the variable `<variable name>` into the specified type `<type>`.

# Answer
> 0 votes
The code indicates that the programmer made a mistake. It's easy for the compiler to change the code in a way so that it compiles. But it is impossible for the compiler to know *what* your mistake was.

I would usually assume that if I assign num = 7.0 then \*numPtr == 7. That won't be the case with your suggestion, so the compiler would produce something that is fundamentally broken without any warning.

The statements as written are plainly wrong. If you as a programmer fixed the compiler error by adding the cast I would worry about you. That fix would be utterly stupid. The real fix would be either changing the type of num to int, or the type of numPtr to double\*, or to think about the situation and maybe coming to the conclusion that what you are trying to do just doesn't work. Not something you would leave to a compiler.

After a year or so of programming, you will likely turn on all reasonable warnings in your compiler so that it will warn you *if you do something suspicious*. You don't want a compiler that takes everything without thought. You definitely don't want a compiler that makes ill-judged attempts at fixing your mistakes.

---
Tags: c++, c
---


# Question
Title: How is segmentation a solution to external fragmentation
As per Galvin's book, segmentation is the solution to external fragmentation. But in segmentation, the memory blocks are of different sizes. So, if one segment is removed that creates a hole. If we put the small segment many times then this creates external fragmentation. How, then, is segmentation solution to external fragmentaton?

# Answer
> 1 votes
If segments are referenced indirectly (via a segment table), then the memory manager can move segments in physical memory to fill the holes, as long as it updates the segment pointers. And the segment table cannot have fragmentation because all segment pointers are the same size.

---
Tags: operating-systems, memory-management, virtual-memory
---


# Question
Title: Algorithm that will find the minimum number of steps to get from state $j$ to state $i$
Consider an adjacency matrix $A$ with elements $\[A\]\_{ij}=1$ if one can reach state $i$ from state $j$ in one timestep, and $0$ otherwise. The matrix $\[A^k\]\_{ij}$ represents the number of paths that lead from state $j$ to $i$ in $k$ timesteps. Derive an algorithm that will find the minimum number of step to get from state $j$ to state $i$.

Here is my attempt:

The algorithm takes as input:

* $A$ \- Adjacency matrix
* $j$ and $i$ \- the vertices for which we want to find the minimum path inbetween

Then it calculates in a while loop for which value of $k$, $\[A^k\]\_{ij}\neq 0$ and returns that value of $k$. This way we get the minimum value of $k$ for which there exists a path.

Here is the pseudocode:

(Is this the correct way to do it and would there be a faster way?)

```
shortestPath(A,j,i):
      if [A]_{ij}=1:
           return 1
      else:
           f=0; k=1
           while f=0:
               f = [A^k]_{ij}
               k = k + 1
           return k

```

# Answer
This is indeed a correct approach.

It can be improved further by using binary search on $k$, but you have to be careful with it since you want to multiply a small number of matrices (and computing $A^r$ for an arbitrary $r$, can take a lot of time using a simple multiplication algorithm)

---

As a side note, if you prefer using non matrix-based algorithms, then you can use BFS which will work in linear time
> 2 votes

# Answer
Use the Floyd-Warshall algorithm, it was designed for exactly this kind of task.
> 1 votes

---
Tags: graphs, pseudocode
---


title: Is 3-UNSAT problem coNP-complete?

text:
# Question
Title: Is 3-UNSAT problem coNP-complete?
The 3-SAT problem, i.e. the problem whether a given Boolean formula consisting of clauses of at most 3 literals is known to be NP-complete. Then it’s complement, i.e. whether such a formula is unsatisfiable, is coNP-complete, right?

# Answer
> 2 votes
Let $\ell\subseteq\Sigma^\*$ be some language. The complement of $\ell$ is$$\ell^c=\Sigma^\*\setminus \ell.$$ The class CoNP is complexity class (set of languages) whose complement is in NP. Formally

$$CoNP=\\{\ell\mid \ell^c\in NP\\}.$$ According to this link, because of $3-SAT\in NPC$, so $3-USAT\in CoNPC$.

---
Tags: complexity-theory, np, satisfiability, 3-sat, co-np
---


# Question
Title: equivalence of validity above different alphabet
> Given the next alphabets: $\\,\\,\Sigma\_1=\\{R^2,P^1,=^2\\}\\,\\,,\Sigma\_2=\\{c,f^1,=^2\\}.$
> Prove of Disprove: There's exists an algorithm, that given formula $A$ above $\Sigma\_2$, builds formula $A'$ above $\Sigma\_1$ such that:
> $A$ is valid $\iff$ $A'$ is valid.

I could not come up with a solution, but I have two directions.

1. I thought maybe the idea is to represent the function $f$ by using the binary relation $R$, and to force every element in the domain to be in the relation but with only one other element. With the relation $P$ I thought to force the existence of one element that will "play" the role $c$ plays in $\Sigma\_2$ \- I will force the relation $P$ to contain exactly one element- the representer.
2. Then I thought to change accordingly the formula $A$ in a way that will save validity, but it became so messy, so I'm no longer sure if I'm in the right direction.
3. I'm also not sure how to express formulas as $\exists \\,x\\,(f(f(c))=x)$. I mean, how can I express the "power" of the function $f$. So I'm wandering maybe the claim is false, and by using some reduction I need to show that if the claim is true, some un-decidable problem is solved.

I would appreciate some help!

# Answer
> 1 votes
You can use $P$ to express $c$ and $R$ to express $f$.

The following will guarantee that $P$ is satisfied as a unique element:

$$ \exists c \\, P(c) \land \forall c\_1,c\_2 \\, (P(c\_1) \land P(c\_2)) \Rightarrow c\_1 = c\_2 $$

The following will guarantee that $R$ expresses a function:

$$ \forall x \exists y R(x,y) \land \forall x,y,z (R(x,y) \land R(x,z)) \Rightarrow y = z $$

The formula $A$ will be a conjunction of these two and $$ \forall c\_0,c\_1,c\_2,\ldots (P(c\_0) \land R(c\_0,c\_1) \land R(c\_1,c\_2) \land \cdots \Rightarrow A'), $$ where $c\_i$ replaces $f\_i(c)$ in $A$.

---
Tags: logic, first-order-logic, propositional-logic, logical-validity
---


# Question
Title: `STACK-FULL` and `QUEUE-FULL` with worst-case $\Theta(1)$
There are two problems in CLRS about implementing stacks and queues with singly linked lists. I know the solutions, I know how `STACK-EMPTY` and `PUSH` and `POP` and `QUEUE-EMPTY` and `ENQUEUE` and `DEQUEUE` are defined. But can we define `STACK-FULL` and `QUEUE-FULL` with worst-case $\Theta(1)$ time? One idea is to set a counter and increment or decrement it whenever we add or delete elements but I don't want to use some extra information or add something to the problem. I just want to use the information (like attributes) relevant to singly linked lists only.

# Answer
No, you have to add additional information. There is no way to meet your requirements without adding additional information.
> 1 votes

---
Tags: stacks, linked-lists, queues
---


# Question
Title: To prove (KB ⊭ S) and (KB ⊭ ¬S) is satisfiable
In question (e), I have to prove: A ≡ (KB ⊭ S) and (KB ⊭ ¬S) is satisfiable, where KB and S are propositional variables. I am not able to follow the solution given in the image above as to why it is replacing S with another propositional variable P. Even if we do take P, one of (KB ⊭ P) and (KB ⊭ ¬P) becomes true and other false making A as false. So anyway here's what I tried, I find some interpretation to make statement A false, if I cannot find such interpretation then A is a tautology. From what I understand, (KB ⊭ S) is true (i.e. KB does not entail S is true) when premise KB is true and the consequence S is false. So if I take KB ≡ TRUE and S ≡ TRUE making (KB ⊭ S) ≡ FALSE making A ≡ FALSE, hence A is not a tautology, whereas the answer given in above image is Yes.

# Answer
> 1 votes
When you say $\alpha\models KB$, this means that $models(\alpha)\subseteq models(KB)$ that $models$ of $\alpha$ is used for an assignment that evaluates formula $\phi$ to true.

Under above interpretation, suppose $KB\equiv True$, and $S$ be a formula that isn't Tautology and just satisfiable (i.e. $A\vee B$), in propositional logic, hence we can conclude that

$$True\nvDash S\wedge True\nvDash \neg S.$$

Because $$models(KB)\nsubseteq models(S)\wedge models(KB)\nsubseteq models(\neg S).$$

---
Tags: logic, propositional-logic
---