# Question
Title: How to fill cell-network partition matrix of a function?
I'm trying to understand a paper (Tandem Networks of Universal Cells, Butler, 1978 ), but I can't make it past the first paragraph:

> Consider the $x\_l … x\_{k - 1} | x\_k$ partition matrix of a function $f( x\_1, x\_2, …, x\_k)$, as shown in Fig. 1, where $C\_0$ and $C\_1$ represent the $x\_k = 0$ and $x\_k = 1$ columns, respectively. Let $0$ and $1$ represent the columns of all 0's and all 1's, respectively. Let $X$ denote a column with at least one 0 and at least one 1, and $\overline{X}$ its complement. The concatenation of two columns will represent a complete partition matrix. Thus, for example, $01$ represents $f(x\_1, x\_2, …, x\_k) = x\_k$ and $XX$ represents a function independent of $x\_k$, but dependent on at least one of the remaining variables.

I'm trying to build something like a Karnaugh map, but the result I'm getting doesn't make sense.

For example, here's what I made from $f = x\_1 \times x\_2 \times x\_3$ (with digital logic "&" for boolean times):

The first column ($C\_0$) I would call $0$, from the author's definition, but the second column ($C\_1$) doesn't seem to be a $0$, $1$, or $X$. What am I doing wrong?

# Answer
> 1 votes
You're pretty close.

I don't think that's what they intended as the partition matrix. Instead, I think they intended the following matrix:

```
         x3
x1 x2 \  0 1
       -----
 0  0  | 0 0
 0  1  | 0 0
 1  0  | 0 0
 1  1  | 0 1

```

That's slightly different from what you have written. In particular, the partition matrix will have $2^{k-1}$ rows and 2 columns.

It's best to think of the first sentence as one paragraph, and the remaining sentences as a second disconnected paragraph that is trying to explain a taxonomy for classifying a column of this matrix. The author is proposing to classify every column into one of three types: all-zeros, all-ones, or contains both a 0 and a 1. The paper represents an all-zeros column by 0, an all-ones column by 1, and the third case by X. Thus, X is used to represent any column that contains at least one 0 and at least 1, i.e., any column that is not all-zeros and not all-ones.

By this classification, the partition matrix above would be of the form 0X: the first column is all-zeros (type 0), and the second column is type X.

---
Tags: boolean-algebra
---


# Question
Title: How to tackle different sample size in the training set in SVM
I have to train a SVM for a classification problem. I have some strings that are the paths in a deterministic finite automata (DFA). If the alphabet is -01- then possible strings are 011101110 or 0110 for example. The purpose of classifier (SVM) is the correct prediction (label) of unseen strings like accepting or rejecting(label 1 or label -1, binary classification). The problem is that the strings have different lenghts. How can I tackle this problem?

# Answer
A SVM classifier requires a fixed-length feature vector, i.e., all feature vectors must have the same length. There are multiple solutions:

* Pad out the strings to fixed length.
* Choose a different set of features, so that there is a fixed number of features.
* Pick a fixed number $k$, and look at windows of length $k$ (i.e., substrings of length $k$). Classify each window of length $k$ using your SVM, then combine those results somehow (e.g., majority vote).
* Use a different classifier, such as a recurrent neural network (e.g., LSTM). See also https://datascience.stackexchange.com/q/16115/8560 for more possibilities.

It's hard to say what will be most appropriate for your particular situation, without knowing more about your learning task.

---

Based on your subsequent comments, it sounds like you want to learn a DFA. There's lots written on learning DFAs, using Angluin's algorithm, SAT solvers, or other methods. Follow the link above for some entry points into the literature on that. I don't think a SVM is the right tool for that job -- this sounds like an XY problem.
> 3 votes

---
Tags: machine-learning, neural-networks, classification, svm
---


title: Finding best three numbers of an array

text:
# Question
Title: Finding best three numbers of an array
> Given a sorted array of $n$ integers ,and some other integer $m$, find the $3$ numbers in the array $x,y,z$ such that $x+y+z\ge m$,and their sum is minimal.
>
> If there are no such,return null.

Any ideas for an efficient algorithm to find it?

# Answer
The algorithm for finding three number $x, y, z$ under the constraint $x+y+z \ge m $ can be extended from the idea of finding two numbers $x, y$ under a similar constraint $x+y \ge m $.

Initially we fix the value of $x = A\_1$, first element of array. Next we will look for $y$ and $z$ in the subarray $A\_2 ... A\_n$. We repeat the above step by setting $x = A\_2$ in the next iteration and look for $y$ and $z$ in the subarray $A\_3 ... A\_n$. We repeat this step until one of the following conditions are meet.

1. We find a triple $x, y, z$ such that $x + y + z = m$. As that is the minimum we have to look for, and you just need one of them.
2. We reach a point where we have set $x = A\_{n-2}$ and looked for other two values in the second last and last element of the array i.e., the triple $\$

Also, there could be many triples in an array satisfying the condition $x+y+z \ge m$ and we need the one with the minimum sum. For this, we keep a separate copy of triple found so far under the specified condition and compare it everytime we find a new one.

Here is the pseudocode

```
FindTriple(A,n,m)
    if A[n-2]+A[n-1]+A[n] < m
        print "No solution"
        return 0

    #Set to some maximum value, for first time comparison
    x = y = z = INFINITY

    for i = 1 to n
        j = i+1
        k = n

        while k>j
            sum = A[i]+A[j]+A[k]

            if sum == m
                print <A[i],A[j],A[k]>
                return 1
            else if sum > m
                if sum < (x+y+z)
                    <x,y,z> = <A[i],A[j],A[k]>
                k=k-1
            else j = j+1

    print <x,y,z>

```

Runtime complexity of this algorithm is $O(n^2)$.

I took time answering this question because I was looking for an algorithm with better runtime complexity. Thanks to Yuval Filmus's answer that saved a lot of my time.

---

Here is the link to the working implementation of this algorithm in C language
> 2 votes

# Answer
You can solve this in $O(n^2\log n)$ in the following way:

1. Construct and sort the list consisting of all sums $x + y$.
2. Go over all $z$, and for each them find the minimal $x+y \geq m-z$ using binary search.

It is very likely that this can be improved to $O(n^2)$ by adapting the 3SUM quadratic algorithm.

On the other hand, you can clearly solve 3SUM given a solution to your problem (just check whether $x+y+z=m$), making it 3SUM-hard to improve $O(n^2)$ to $O(n^{2-\epsilon})$ for any $\epsilon \> 0$. (That is, the 3SUM conjecture implies that no $O(n^{2-\epsilon})$ algorithms exist.)
> 2 votes

# Answer
Not getting the down votes so I wrote a program to test.

a, b, c are the indexes
a \< b \< c

m is target

Where this differs from the accepted solution is for each a, a+1 it does a binary search for the c rather than walk it down. And it gives up if a + the last two (biggest) are \< sum. This shifts it towards $O(n log n)$ but worst case it is still $O(n * n)$.

1. a = 0, b = 1
2. perform a binary search on c
3. if sum = m then done
4. if sum \> target then c-- else b++
5. if a == m.length - 2 done solution not found
6. if c == b then a++ b=a+1 go to 2
7. goto 3

I think this is *close* to $O(n log n)$

```
public static int BinarySearch(int[] A, int T, int? l, int? r)
{
    // Given an array A of n elements with values or records A0 ... An−1, sorted such that A0 ≤ ... ≤ An−1, and target value T, the following subroutine uses binary search to find the index of T in A.[6]
    // 1. Set L to 0 and R to n − 1.
    // 2. If L > R, the search terminates as unsuccessful.
    // 3. Set m(the position of the middle element) to the floor of (L + R) / 2.
    // 4. If Am < T, set L to m + 1 and go to step 2.
    // 5. If Am > T, set R to m – 1 and go to step 2.
    // 6. Now Am = T, the search is done; return m.
    Array.Sort(A);
    int M = -1;
    int L = l == null ? 0            : (int)l;
    int R = r == null ? A.Length - 1 : (int)r;
    while (L <= R)
    {
        M = (L + R) / 2;
        if (A[M] < T) L = M + 1;
        else if (A[M] > T) R = M - 1;
        else return M;
    }
    return M;
}
public static int BinarySearchList(List<int> A, int T, int? l, int? r)
{
    // Given an array A of n elements with values or records A0 ... An−1, sorted such that A0 ≤ ... ≤ An−1, and target value T, the following subroutine uses binary search to find the index of T in A.[6]
    // 1. Set L to 0 and R to n − 1.
    // 2. If L > R, the search terminates as unsuccessful.
    // 3. Set m(the position of the middle element) to the floor of (L + R) / 2.
    // 4. If Am < T, set L to m + 1 and go to step 2.
    // 5. If Am > T, set R to m – 1 and go to step 2.
    // 6. Now Am = T, the search is done; return m.

    int M = -1;
    int L = l == null ? 0 : (int)l;
    int R = r == null ? A.Count() - 1 : (int)r;
    while (L <= R)
    {
        M = (L + R) / 2;
        if (A[M] < T) L = M + 1;
        else if (A[M] > T) R = M - 1;
        else return M;
    }
    return M;
}
public static List<int> Sum3(List<int> input, int sum)
{
    //a,b,c are index to input
    //start a = 0, b = 1 and solve for c
    //add b until over
    //reduce c until under
    //when b=c the a++ b=a+1

    if (input.Count() < 3)
        throw new ArgumentOutOfRangeException();
    //is it sorted
    int? iLast = null;
    for (int i = 0; i < input.Count(); i++)
    {
        if (iLast != null && i <= iLast)
            throw new ArgumentOutOfRangeException();
        iLast = i;
    }
    if (input[0] + input[1] + input[2] > sum)
        throw new ArgumentOutOfRangeException();
    if (input[input.Count() - 1] + input[input.Count() - 2] + input[input.Count() - 3] < sum)
        throw new ArgumentOutOfRangeException();

    int a = -1;
    int b = -1;
    int c = 2;
    int currentSum;
    int? lastC = null;
    int count = 0;
    for (a = 0; a < input.Count() - 2; a++)
    {
        count++;
        if (input[a] + input[input.Count() - 1] + input[input.Count() - 2] < sum)
            continue;
        if (input[a] + input[a + 1] + input[a + 2] > sum)
            break;
        b = a + 1;
        c = BinarySearchList(input, sum - input[a] - input[b], b + 1, lastC);
        lastC = c;
        while(c > b)
        {
            currentSum = input[a] + input[b] + input[c];
            if (currentSum == sum)
                return new List<int> { a, b, c };
            if (currentSum < sum)
                b++;
            else
                c--;
        }
    }
    return null;
}

```
> -2 votes

---
Tags: algorithms, optimization, arrays
---


# Question
Title: What are the challenges of using gradient descent on hyper parameters λ and η to find out their optimum values?
A question from chapter 3 of Michael Nielsen's \[Neural Networks and Deep Learning\]:

> It's tempting to use **gradient descent** to try to learn good values for hyper-parameters such as the regularization parameter $\lambda$ and the learning rate $\eta$. Can you think of an **obstacle** to using gradient descent to determine values of $\lambda$ and $\eta$?

---

What are the challenges of using gradient descent on hyper parameters **λ** and **η** to find out their optimum values?

**C** is the L2 regularized cost function.

**n** is the length of the training data

**w** is the weight

The Learning rule for the weights will be:

---

I am having trouble understanding how λ and η will affect the cost function. I know that we should decrease η as we get closer to the Cost function minima. I don't have a clue how to optimize λ. I think that the values of the hyper parameters will change for every epoch so there can't be constant optimal values.

# Answer
> 4 votes
The cost function $C(w,\lambda)$ is *not* a function of learning rate $\eta$. You can't compute the gradient of $\eta$.

$\lambda$ is part of the cost function. You can indeed compute its gradient and apply SGD on $\lambda$. However, when you do that, $\lambda$ will keep decreasing because its optimal value is obviously $-\infty$.

Note that it is possible to optimize hyperparameters like $\eta$ and $\lambda$ with another neural net, but that is a different story.

# Answer
> 3 votes
You say you want to understand how $\lambda$ and $\eta$ affect the cost function.

If you hold the weights $w$ fixed, the equation for $C$ tells you how $\lambda$ affects the cost function, and $\eta$ doesn't affect the cost function; it only affects the sequence of steps taken by gradient descent.

But the tricky thing is that the final weights $w$ depend on $\lambda,\eta$. If we choose $\lambda,\eta$ and then use gradient descent to train a set of weights, the final weights $w$ will depend on $\lambda$ and $\eta$.

So, we can think of the final weights $w$ as actually being a function of $\lambda,eta$. Similarly, the final cost $C$ is actually a function of $w,\lambda,eta$, and since $w$ in turn depends on $\lambda,\eta$, this means that the final cost $C$ is really a function of the two variables $\lambda,\eta$. Suppose we write it as a function, to make the dependence clearer: $C(\lambda,\eta)$.

Now we want minimize $C(\lambda,\eta)$. If you want to minimize this using gradient descent, you need to be able to compute the partial derivatives ${\partial \over \partial \lambda} C(\lambda,\eta)$ and ${\partial \over \partial \eta} C(\lambda,\eta)$. Unfortunately, it is not at all clear how to write down an analytical expression for those partial derivatives. The tricky bit is that it is not at all clear how the final weights $w$ depend on $\lambda,\eta$ -- we have no nice way to write down an analytical expression for that. So, we can differentiate to get

$${\partial \over \partial \lambda} C(\lambda,\eta) = {\partial \over \partial \lambda} C\_0(\lambda,\eta) + {\lambda \over 2n} \sum\_i 2 w\_i {\partial w\_i \over \partial \lambda} + {1 \over 2n} \sum\_i w\_i^2,$$

but how do we compute ${\partial w\_i \over \partial \lambda}$? And how do we compute ${\partial \over \partial \lambda} C\_0(\lambda,\eta)$? It's not clear, as we don't have an analytical expression for the final weights $w\_i$ as a function of $\lambda$; the only way we have to compute the weights is to run the gradient descent algorithm to completion.

So that's the challenge with using gradient descent to optimize $\lambda,\eta$, and one reason why people often use grid search instead.

I'm not saying applying gradient descent is impossible, but one must apply other black-box methods to compute the gradients, and there are other reasons why this might fail due to multiple local minima. Usually grid search is easy enough to apply and thus that is what is used.

---
Tags: machine-learning, neural-networks, gradient-descent
---


# Question
Title: Avoiding overflows while computing $e^x$ by Taylor series
I'm coding a program to calculate the value of $e^x$ by using the Taylor expansion, that is:

$$ e^x =\sum\_{k=0}^\infty \frac{x^k}{k!} $$

```
from math import factorial
def e_x(x, n):
    return sum(pow(x, k)/factorial(k) for k in range(n))

```

Edit: Python seems to handle large integers pretty well so I'm more interested in the algorithm itself.

I want to avoid overflows during the calculation of the $k!$, so my intuition is that by looking at the $k$th-term and trying to do intermediary divisions an overflow might be avoided.

My naive solution was to just do $\frac{x}{k} \cdot \frac{x}{k-1} \cdot \ldots \cdot \frac{x}{1} \cdot \frac{x}{1}$, but the error became unbearable after some few iterations. I'm not using any high (arbitrary) accuracy floating point library (although I'm interested in knowing how would this be implemented in those).

# Answer
Of course there are better numerical ways to compute exponential, but if you want to use Taylor expansion only, the better approach is to reformulate the expansion to avoid computing large nominators and denominators. This leads to an $O(n)$ algorithm, where $n$ is the number of iterations. Yours is $O(n^2)$ if you compute factorial and power literally (probably the python library is computing factorial with a gamma function and power with `exp`).

Here is a javascript program. `print()` is a function to write strings to console.

```
function myexp(x, max_itr)
{
    var y = 1.0, t = 1.0;
    for (var i = 1; i < max_itr; ++i) {
        t *= x / i;
        y += t;
    }
    return y;
}

var x = 1.2;
print("Math.exp: " + Math.exp(x));
print("10 iterations: " + myexp(x, 10));
print("99 iterations: " + myexp(x, 99));

```

The output is:

```
Math.exp: 3.3201169227365472
10 iterations: 3.3201150098285708
99 iterations: 3.3201169227365472

```

EDIT:

Alternatively, you can reformulate Taylor expansion as:

$$ e^x = 1 + \frac{x}{1}\left(1+\frac{x}{2}\left(1+\frac{x}{3}\left(1+\cdots\right)\right)\right)$$

An implementation in javascript:

```
function myexp2(x, max_itr)
{
    var y = 0.0;
    for (var i = max_itr; i >= 1; --i)
        y = 1.0 + x / i * y;
    return y;
}

```
> 4 votes

---
Tags: algorithms, numerical-algorithms, numerical-analysis, error-estimation
---


title: How to study for the Algorithm courses

text:
# Question
Title: How to study for the Algorithm courses
I'm taking a fairly challenging Algorithm course, in which we are learning about algorithms such as Dijkstra, Bellman-Ford etc. as well as the algorithm design patterns such as recursions, DP and various graph construction techniques such as layering. Now I really have some trouble to design correct and efficient algorithm using stuff we learned in the class. To be specific, I'm having trouble with following:

* Design an algorithm that's fast enough, i.e., I came up with a $O(n^2)$ algorithm but in fact there is a $O(n log n)$ algorithm.
* To find the edge cases for the algorithm I designed. It happened a lot of times to me during exam that I designed some seemingly correct algorithm but will actual fail in some edge cases. I always have some hard time to find those edge cases and therefore falsely believe the algorithm is correct.

I would greatly appreciate any suggestions that can help me deal with my struggle. Also, just for reference, here are the links to the course I'm taking (schedule, and the homeworks)

# Answer
> 0 votes
Designing algorithms that are fast enough is probably a function of experience. There are strategies (recursion, divide-and-conquer, dynamic programming...) that can be used. Often a problem can be approached with multiple strategies but one is more efficient than the other. The more of these strategies you know, the better you are equipped for using them in your algorithms. Experience will also give you a feel for what is an appropriate approach; you may intuitively notice which problems are recursive in nature, which can be expressed as operations on a graph etc. Then you can use what you know to knead the challenge into a familiar shape. Do a Google search for "algorithm strategies" to find useful resources which list generic strategies. Learn about these and then consider for algorithms you encounter how they are instances of these generic approaches (or combinations thereof).

Edge cases tend to occur where **assumptions** are made, and for some situations those assumptions are incorrect. An algorithm attempts to resolve something for some structure which seems consistent; it breaks down where the structure suddenly differs or becomes inconsistent. Edge cases are the sort of place in a program where you need to test assumptions and where decisions branch.

For example, suppose I have some algorithm that takes a list of elements as input and performs a computation over it. You begin your design by stating that for each element in the list, in order, some action is performed. That's an assumption right there. "Each element in the list" assumes there are some. How will it behave for an empty list?

An example of this I encountered in some programming contest a while ago. You were given a list of numbers and had to find out how many ways there were to divide this into three lists, maintaining the original order of the numbers, in some way that satisfied some condition (the sums for the three sub-lists had to be equal). I got started but soon noticed some test inputs failed. It turned out that empty sub-lists were also valid. I had **assumed** that each sub-list had to have at least one element. And then, of course, I'd need to consider whether my fixed program would handle inputs of 0, 1 or 2 numbers correctly as well.

---
Tags: algorithms
---


title: Finite State Automaton Language

text:
# Question
Title: Finite State Automaton Language
We're given these two finite state machines where the alphabet consists of ${a, b, c}$. The question is to determine the language for the following two machines. I tried following the machines to find the language, but the languages I derived are quite verbose.

# FSA #1

This FSA accepts words with at least one a followed by zero or more b's or words with at least one a followed by zero or more b's followed by at least one c.

# FSA #2

This FSA accepts words with at least one a followed by at least one b or words with at least one a followed by at least one b followed by one c.

I tried converting these FSAs to regular expressions and found that my solutions hold up, but I'm wondering if there is a more concise way to explain the language of each FSA. My language explanations seem quite verbose, so any help would be appreciated.

# Answer
Finite state automatons recognize regular languages. The advantage of regular languages is that it is usually trivial to express them formally.

# FSA #1

$$L(M\_1) = \left\\{ a^kb^lc^m | k \> 0, l \geq 0, m \in \\{ 0, 1 \\} \right\\}$$

# FSA #2

$$L(M\_2) = \left\\{ a^kb^lc^m | k \> 0, l \> 0, m \in \\{ 0, 1 \\} \right\\}$$
> 1 votes

# Answer
You could be more precise by stating "This FSA accepts a word if, and only if, ...". You could be more concise by using the word "optional" in the "...".
> 0 votes

# Answer
The regular expressions corresponding to your descriptions are as follows.

---

**FSA #1**

$$a^{\*+1} b^\* + a^{\*+1} b^\* c$$

... which can be simplified to

$$a^{\*+1} b^\* (\epsilon + c)$$

... or, in John Conway's notation

$$a^{\*+1} b^\* c^{\le 1}$$

We can describe this as

* one or more $a$s, followed by ...
* any number of $b$s, followed by ...
* a possible $c$.

---

**FSA #2**

$$a^{\*+1} b^{\*+1} + a^{\*+1} b^{\*+1} c$$

... which can be simplified to

$$a^{\*+1} b^{\*+1} (\epsilon + c)$$

... or, in John Conway's notation

$$a^{\*+1} b^{\*+1} c^{\le 1}$$

We can describe this as

* one or more $a$s, followed by ...
* one or more $b$s, followed by ...
* a possible $c$.

---

You can see that these correspond to @still\_learning's prescriptions.
> 0 votes

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


title: Operating System Paging concept

text:
# Question
Title: Operating System Paging concept
I am quoting a paragraph from the book "Operating System Principles" by Galvin.

> Usually, each page-table entry is 4 bytes long, but that size can vary as well. A 32-bit entry can point to one of $2^{32}$ physical page frames. If frame size is 4 kB, then a system with 4-byte entries can address $2^{44}$ bytes (or 16 TB) of physical memory.

Now, I know we have $2^{44}$ bytes of memory because we have $2^{32}$ page frames and each frame size is 4 kB, i.e. $2^{12}$ bytes of memory, so physical memory is $2^{32}\cdot2^{12} = 2^{44}$.

Please help me to understand the following:

1. How did we get the number of frames as $2^{32}$?
2. If the logical memory space is $2^{32}$ then what should the physical memory space be (considering both the fully used and partially used logical address space concept)?

# Answer
> 2 votes
I found (surprisingly many) copies of that text on the web (see http://www.slideserve.com/janna/virtual-memory). That helps ascertaining there is no vocabulary mismatch.

The 32-bit entry makes for $2^{32}$ physical (not logical as you write in your comment) address space for pages, i.e. $2^{32}$ frames. The address of the logical page is used for indexing the page-table, and the 4 bytes content of the corresponding entry of the page table is the address of a page frame, i.e. a physical page.

So you have $2^{32}$ physical pages. But there is nothing in the above text that tells the size of the logical space. It could be much larger, with logical page addresses of 8 bytes, or it could be smaller which did happen on some architectures. For more details on this, see this discussion regarding virtual memory on 32 bits hardware. There may be other issues with more recent 64 bits hardware. The size of the page-table would tell you what is the size of the virtual memory space, i.e. of logical addresses.

Does this clarifies the problem?

# Answer
> 0 votes
Page frames are units of physical memory. Whether your system actually has $2^{32}$ page frames is a question of how much physical memory it has. The point is that having a page table where each page frame is indexed through 32 bits *allows* you to address up to $2^{32}$ page frames.

Your second question doesn't really make sense as page frames are physical memory.

# Answer
> 0 votes
## 1

Consider, you have a page table off course which will give you frame number corresponding to given page number. And you have specified that page table entry size is 32 bit.Ahhh.. what this 32 bit means(i think u really got stuck here):

---

let if u consider this 32 bit as 2 bit(not possible but let it) then how many different combinations you have?

-00 \- 01 \- 10 \- 11

=2^2 (hmmm) hence when you take 32 bits, no of combination possible would be 2^32 means number of the frame in memory can reach up to 2^32 in number.

## 2

logical and physical addresses generally independent of each other that is if you have a memory of 2MB=2^21 byte still you can take a logical address space of 3 MB OR 1GB etc etc..condition is that we must keep logical address space greater than physical address space since you can't address all physical bytes with a smaller logical address.

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


# Question
Title: How to prove that finding math proofs is $\text{NP}$-hard?
This is Exercise 2.11 of the book "Computational Complexity: A Modern Approach" by Arora and Barak.

> Mathematics can be axiomatized using for example the *Zermelo-Frankel* system, which has a finite description. Argue at a high level that the following language is $\text{NP}$-complete. (You don't need to know anything about ZF.)
>
> $$\text{THEOREMS} = \\{ \langle \varphi, 1^n \rangle: \text{math statement } \varphi \text{ has a proof of size at most } n \text{ in the ZF system}. \\}$$

It is easy to show that $\text{THEOREM} \in \text{NP}$. However, how to prove it is $\text{NP}$-hard?

In addition, why is it $1^n$ instead of just $n$ in $\langle \varphi , 1^n \rangle$? Does this encoding scheme matter with the $\text{NP}$-hardness proof?

# Answer
> 4 votes
Define $\mathrm{Bool}$ to be the set of all subsets of $\\{\varnothing\\}$ (or some arbitrary set with 1 element). Then represent a propositional variable $x$ by some subset $x\in\mathrm{Bool}$, i.e. $x\subseteq\\{\varnothing\\}$.

Now there is an extremely straightforward translation $\rho$ of propositional formulae into such subsets:

* $\rho(x)$ if $x$ is a variable is just some set (also called $x$) $\in\mathrm{Bool}$.
* $\rho(\neg\phi)$ into the complement of $\rho(\phi)$ in $\mathrm{Bool}$.
* $\rho(\psi\vee\phi)=\rho(\psi)\cup\rho(\phi)$
* $\rho(\phi\wedge\psi)=\rho(\psi)\cap\rho(\phi)$

And you don't need any other connectives to get a polynomial sized translation of a propositional formula.

Then a formula $\phi$ is satisfiable iff $$ ZF\vdash\exists x\_1\ldots x\_n\in\mathrm{Bool},\ \rho(\phi) \neq \varnothing$$

I'll let you work out the details. One important thing, though, is to show that a proof will be proportional in **length** to $n$, where $n$ is the number of variables.

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


# Question
Title: Understanding the reduction of REGULARTM from ATM
REGULARTM is defined as below:

```
REGULARTM ={〈M〉| M is a TM and L(M)is a regular language}.

```

I am trying to understand the proof of REGULARTM being undecidable from Sipser's book "Introduction to the Theory of Computation". The book says:

```
We let R to be a TM that decides REGULARTM and construct TM S to decide ATM. Then S works in the following manner.
S = “On input〈M,w〉, where M is a TM and w is a string:

1.Construct the following TM M2.

    M2=“On input x:
        1.If x has the form 0^n1^n,accept.
        2.If x does not have this form, run M on input w and accept if M.”
2.Run R on input〈M2〉.
3.If R accepts,accept; if R rejects,reject.”

```

The problem that I am facing is in the 2nd substep of the 1st step which says:

```
If x does not have this form, run M on input w and accept if M.

```

What if M does not halt on w? Then the decider S that we are building would not halt.

# Answer
> 2 votes
Let's look just at $M\_2$ for the moment. If $M$ accepts $w$, then $M$ will accept strings of the form $0^n1^n$ in step (1) and everything else in step (2). In other words

If $M$ accepts $w$, then the language $L(M\_2)=\Sigma^\*$, which is of course regular.

Now if $M$ doesn't accept $w$, then $M\_2$ will accept all and only strings of the form $0^n1^n$, so $L(M\_2) = \\{0^n1^n\mid n\ge 0\\}$ and this language is certainly not regular.

The important thing here is that we don't have to run $M$ on $w$ to decide its behavior: the behavior is determined solely by whether $M$ accepts $w$ or not. Since $R$ was assumed to be a decider, it doesn't have to run $M$ to determine whether the language of $M\_2$ is regular or not; because $R$ is a decider it is by definition assumed to be able to tell that.

---
Tags: turing-machines, reductions, undecidability, halting-problem
---


title: Must reductions be injective?

text:
# Question
Title: Must reductions be injective?
From Sipser,

Language A is mapping reducible to language B, written $A \leq\_m B$, if there is a computable function $f : \Sigma^\* \rightarrow \Sigma^\*$, where for every $w$, $w ∈ A \Leftrightarrow f(w) \in B$. The function $f$ is called the reduction from A to B.

A function is injective if every element in the co-domain is mapped to by at most one element of the domain.

I'm confused on how $w \notin A$ are handled. It seems that for $w \in A$ every element must map to a unique $b \in B$. Because $w \in A \Leftarrow f(w) \in B $.

---

New question then, is there any use to having an injective reduction? I've noticed that many proofs of NP-hardness seem to have reductions that are injective (at least on $w \in A$). If reductions are not injective ~~ Why don't we simply define our reduction function $R$ as follows, check if $w \in A$, If $w \in A$ then map to a constant $b \in B$. Else, map to a constant $c \notin B$?

# Answer
The function $f$ does not need to be injective. It would be fine to map every $w \in A$ to the same element $w' \in B$ (and to map every $w \in \Sigma^\* \setminus A$ to the same $w'' \in \Sigma^\* \setminus B$). In fact, for every decidable language $A$, we have $A \leq\_m B$ for every $B$ such that $B \neq \Sigma^\*$ and $B \neq \emptyset$.
> 5 votes

---
Tags: complexity-theory, reductions
---


# Question
Title: What's the average number of clauses modern SAT solvers can handle?
It's already known that size doesn't matter always (for SAT problems).

**But is there evidence (from real data from: benchmarks or real cases) on how many clauses an average SAT solver can handle nowadays?**

Another issue that derives is that once they find a solution, most don't stress the fact about finding alternative solution. Is there a reason?

# Answer
You're asking two questions. I'll answer your first question.

There's no simple answer. It depends on the structure of the problem. There are problems with millions of clauses that can be handled by a SAT solver. There are also problems with only tens of thousands of clauses (perhaps fewer) that can't be handled by SAT solvers.

The number of clauses isn't a great predictor of whether a SAT solver will be able to solve the problem in a reasonable amount of time.

Rick Decker has answered your other question.
> 5 votes

---
Tags: satisfiability, sat-solvers
---


# Question
Title: What will be the time complexity for the following search algorithm in a graph?
I have a graph which looks something like below

I am searching for a given string `s` going down such that at every node it makes a decision (either to visit the left node or right). The code goes something like this.

```
String s=input;
Node CurrentNode=start;
int rightSubstringIndex=-1;
int leftSubstringIndex=-1;
while(true){
    if(CurrentNode.getValue()==s){
        return 1;//indicating that the string was found in the graph
    }
    if(CurrentNode.right==null){//there won't be a node with only one child so either both child nodes are there or there is no child
        return 0;//indicating that the string was not found in the graph
    }
    rightSubstringIndex=findSubStringIndex(CurrentNode.right.getValue(),s);
    leftSubstringIndex=findSubStringIndex(CurrentNode.left.getValue(),s);

    if(rightSubstringIndex<leftSubstringIndex){
        CurrentNode=CurrentNode.right;//go towards the right node
    }
    else if(leftSubstringIndex<rightSubstringIndex){
        CurrentNode=CurrentNode.left;//go towards the left node
    }
    else{//i.e when rightSubstringIndex==1000 && leftSubstringIndex==1000
        return 0://indicating that the string was not found in the graph
    }
}

```

`findSubstringIndex(a,b)` returns the index in the string array `b` where the substring `a` starts . Returns 1000 if the the substring `a` doesn't occur in `b`(assuming that there will not be a string having length greater than 1000 characters).The time complexity of function `findSubstring(a,b)` is assumed to be $O(1)$.

I am interested in finding out the time complexity of the above described algorithm.I know that if it was a binary tree and I had to look up for the string using a similar strategy the complexity will be $O(logN)$. I don't know how to think of complexity ***in terms of number of nodes*** in this scenario.

I am not very good at theory so kindly don't go hard on me

# Answer
This answer is under the assumption that `findSubstring()` is $O(1)$, which it realistically is **not**. Notice that at each iteration, when you make a step down to the next level in the graph, the problem size is being reduced by a factor of 2. That is, the amount of possible solutions is being reduced by a factor of 2. Specifically this is because the size of the strings duplicate at each layer down into the graph. So at any rate, if you have a string of length $n$, it will take $\log n$ steps to reach a solution using this algorithm. Furthermore, the string length must be a power of 2. This is a bit easier to visualize if you split your graph into its equivalent binary tree:

This is a valid representation because each time you go left or right, you are cutting yourself off from impossible solutions, and that is exactly what happens in binary trees.

$\log n$ is just the time bound with respects to the length of the string however. You must also consider the height of the graph (number of nodes from start to some end node). If we have a full graph of this format (every layer is filled). If the graph is of height $h$, you could imagine this graph as the top left half of an $h \times h$ grid if you cut it in half along the diagonal. This means for a graph of height $h$, we have $h \cdot h / 2$ nodes in the graph.

So now we have two scenarios, (1) the upper bound of string length ends the algorithm or (2) the upper bounds of graph height ends the algorithm. Which gives a result:

$O(max(\log n, \sqrt{|V|})) = O(\log n + \sqrt{|V|})$ where $n$ is the length of the input string and $|V|$ is the number of nodes in the graph.

Another similar approach to this problem that you might be able to utilize:

If you know the length of the string (assuming it's given), you know the precise layer of the graph it will be in. If you can get to that layer in constant time (not sure if this will be possible with your setup), you might be able to use a different greedy approach to binary search for the solution inside that layer.

A string of length $n$ will be at level $\log n + 2$ in the graph. At level $l$ of the graph there will be $l$ nodes (possible solutions). So if the string is at level $\log n + 2$, there are $\log n + 2$ nodes at that level. If you can binary search somehow (an exercise for the reader) through that layer, you might be able to get a $\log \log n$ solution.
> 4 votes

# Answer
No. The running time is not $O(\log n)$. The running time is at least $\Omega(n)$. In each iteration of the loop, you call `findSubStringIndex()` to check whether the string in a node is a substring of `s` (where $n$ is the length of the string `s`). That check can take $\Theta(n)$ time.

This appears to be an inefficient data structure, and it appears there are better choices -- e.g., a hashtable, a trie.
> 1 votes

---
Tags: algorithm-analysis, data-structures, runtime-analysis, combinatorics, graph-traversal
---


# Question
Title: Useful functions between polylogarithmic and polynomial?
I'm wondering if there are any *useful* functions asymptotically greater than a polylogarithmic function and less than a polynomial function.

That is, a function $f(n)$ such that

$f(n) = \omega(\log(n)^k)$ for some constant $k \> 0$

and

$f(n) = o(n^k)$ for some constant $k \> 0$

What I mean by useful, is that it was used in a proof, algorithm, etc. rather than simply producing a function to fit these restrictions.

# Answer
According to Wikipedia (which attributes the following result to Knuth), the running time of the mixed-level Toom–Cook algorithm for integer multiplication is $$ \Theta(n\log n \cdot 2^{\sqrt{2\log n}}). $$ The function $2^{\sqrt{2\log n}}$ is super-polylogarithmic but sub-polynomial.
> 7 votes

---
Tags: asymptotics
---


# Question
Title: Finding maximal independent sets in an independence system
An independence system is a collection $I$ of subsets of $\Omega$ such that if $A\in I$, then any subset of $A$ is in $I$. These sets are called independent.

Suppose I have an oracle for testing independence. In particular I have an ambient set $\Omega$ and an independence system $I$ of subsets of $\Omega$. I pass a subset $A$ of $\Omega$ to the oracle, and it tells me if $A\in I$. Is there an efficient algorithm for finding all maximal independent sets? I especially care about minimizing the number of calls to the oracle, which is expensive.

I implemented a brute force method (just looping over the powerset) which chokes for inputs sizes above about $n=6$. On the other hand, the Bron-Kerbosch algorithm solves exactly this problem in a special case, and my implementation of it runs quite happily up to around $n=30$. That would be plenty satisfactory to me.

# Answer
> 2 votes
This looks equivalent to finding all maximal zeroes of a monotone function, given ability to make oracle queries to the function. Let $f:\\{0,1\\}^n \to \\{0,1\\}$ be a monotone Boolean function, and call $x$ a maximal zero if $f(x)=0$ and $f(y)=1$ for all $y\ge x$ (i.e., $y\_i \ge x\_i$ for all $i$).

This problem has been studied extensively. I believe there are no known polynomial time algorithms. See https://cstheory.stackexchange.com/q/14772/5038, Maximal Elements in a Lower Set, https://cstheory.stackexchange.com/q/18047/5038, How to enumerate minimal covers of a set, and https://cstheory.stackexchange.com/q/14772/5038. I think the concepts of learning DNF representations for monotone boolean functions and monotone dualization will be relevant. I confess I don't fully understand the literature and don't know if there are any algorithms that are good-enough-in-practice.

The relationship: Suppose $\Omega=\\{1,2,\dots,n\\}$. We can identify the set $A$ with its characteristic vector, which is an element of $\\{0,1\\}^n$. Now an independence system $I$ determines a function $f$ given by $f(A)=0$ if $A \in I$, otherwise $f(A)=1$. You have oracle access to $f$, and want to find all maximal sets $A$ such that $f(A)=0$.

---
Tags: algorithms, optimization, sets
---


# Question
Title: Can a Turing Machine run for infinitely many steps and halt?
Is it possible for an ordinary Turing Machine, for some input x, to run for an infinite number of steps but also halt? Or do we say that Turing Machine does not halt on x?

# Answer
The answer to your question, whether a Turing machine can run for infinitely many steps and subsequently halt, is negative. If a Turing machine runs for an infinite number of steps and never halts, then it just never halts. It runs forever. A Turing machine *halts* if it at some step, it halts. If this never happens, then it doesn't halt, and instead runs for infinitely many steps.

One can define infinite time Turing machines for which infinite computations do result in an output, but these are different from the ordinary Turing machines taught in your class. In particular, infinite time Turing machines can "compute" uncomputable functions.
> 5 votes

# Answer
Maybe you are confusing "arbitrarily large" and "infinite"? If a Turing Machine never halts, then any given step number will be arbitrarily large..but the step number will never be infinite.
> 0 votes

---
Tags: turing-machines
---


# Question
Title: For a regular language $L$, is $\{xy^Rz:xyz\in L\}$ regular?
> For a regular language $L$, is $\\{xy^Rz:xyz\in L\\}$ regular?

\[Where $w^R$ is the reverse of $w$\]

My intuition says it is, as for a regular $L$, the languages $L^\*$, $\\{y: xyz\in L\\}$ and $L^R$ are all regular languages, but I wasn't able to build a DFA/NFA for it, as if I try and "guess" from where to reverse the word I lose track of if it's a word in the original language. Any hints?

# Answer
> 8 votes
Assume we have automaton $\mathcal A$ for regular language $L(\mathcal A) = L$. It is possible to construct a new finite automaton for the new language $L'=\\{xy^Rz\mid xyz\in L\\}$. You need nondeterminism and extra components in the states to remember the choices made.

It is also possible to use closure properties. Let $\mathcal A\_{p.q}$ be the automaton $\mathcal A$, except that initial state is $p$ and final state is $q$. Similarly $\mathcal A\_{p.F}$ for final states $F$.

Now $L'= \bigcup\_{p,q} L(\mathcal A\_{q\_0,p})\cdot L(\mathcal A\_{p,q})^R\cdot L(\mathcal A\_{q,F})$.

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: How to solve the recurrence: T(n) = n*T(n-1) + n?
In a an exercise I'm required to analyze the runtime of recursive function:

```
 foo(n)
     for i from 1 to n
         work() // O(1)
         foo(n-1)
     end for
 end foo

```

The recurrence relation I understand from the code is: `T(n) = n*T(n-1) + n`

But I'm failing trying to analyze it using the iterative method since I don't see a repeating pattern when I'm opening some of the terms

How do I solve this recurrence ?

# Answer
> 2 votes
Looks like $$ T(n) = n! + \left(\frac{n!}{0!} +\frac{n!}{1!} +\frac{n!}{2!} +\frac{n!}{3!} + \dots + \frac{n!}{(n-2)!} + \frac{n!}{(n-1)!}\right) $$ satisfies the recurrent relation (here $T(0) = 1$).

From this for example $T(n) \leq n!(1+e)$.

# Answer
> 0 votes
Looking for the pattern (aka "guess and prove") is definitely a workable approach here. Sometimes it's about arranging things in the right way in your head:

(Assuming $T(0) = 0$ as anchor.)

This path leads to an exact solution in terms of "well-known" functions, namely a sum of *falling factorials* if not a nice closed form. You'd then prove this guess correct using *induction*, which is elementary here.

---

Actually, there is a mechanical approach to solve this: using generating functions. Since clearly $T(n) \in \Omega(n!)$, we know we'll have to use *exponential* generating functions (at least). So, from the ansatz

$\qquad\displaystyle T(z) = \sum\_{n \geq 0} t\_n \cdot \frac{z^n}{n!} = \sum\_{n \geq 1} n \cdot \frac{z^n}{n!} + \sum\_{n \geq 1} n \cdot t\_{n-1} \cdot \frac{z^n}{n!}$

we obtain, using elementary manipulation of sums/series, that

$\qquad\displaystyle T(z) = ze^z \cdot \frac{1}{1-z}$.

Inserting the well known series for $e^z$ and $(1-z)^{-1}$ and applying the *(binomial) convolution*, you get the same solution as "seen" above:

$\qquad\displaystyle t\_n = \sum\_{k=1}^{n} \frac{n!}{(n-k)!}$.

Now, we can rearrange:

$\qquad\displaystyle t\_n \ =\ n! \cdot \sum\_{k=1}^{n} \frac{1}{(n-k)!} \ =\ n! \cdot \sum\_{k=0}^{n-1} \frac{1}{k!} \ \sim\ n! \cdot e$.

---
Tags: runtime-analysis, recurrence-relation, recursion
---


# Question
Title: Architecture, microarchitecture and ISA in microprocessor
What is Architecture, microarchitecture and ISA in processor. How do they relate to each other and what is the difference between them.

Elucidate their differences with examples so that it is clarified.

Also, clarify, do the word computer architecture and processor architecture mean the same thing?

# Answer
> -4 votes
There are three architectures in computer science that relate to the computer hardware, CPU :

ISA

ISA (instruction set architecture) is the set of all instruction that a given cpu has and accordingly, is able to understand. Let's assume a cpu has only five instruction ADD, MULT, WRITE, LOAD, OUT. Then this processor can do only these five things (i.e., addition, multiplication of two or more numbers and writing (to RAM), Loading (reading and getting data and instructions stored in your hdd to RAM and then on register) , and outputting the result onto the monitor.

It is the ISA that is implemented by microarchitecture of a given cpu. If you have less instructions in your ISA then you need less components (transistors, capacitors etc.) in designing the microarchitecture.

\[Note: You can easily counteract me with the following: Snapdragon 835 follows 'ARM RISC ISA' but it has 3 billion transistors. Then, i will elaborate on this as: snapdragon employs 8 core, four of them are semi-custom core kryo 280 (probably, based on the A73 core) and A73 is a big core which needs more die area and transistors, moreover, snapdragon 835 is not meant for mid-range processor, it is the top-of-the-line processor and is designed, keeping in view, of the technologies such as VR (virtual reality), so its extra (higher) transistors are for extra performance, Moreover, today's processor are not completely RISC or CISC, they incorporate the element of both i.e., ARM ISA is not a true RISC ISA and intel CISC is not a true CISC ISA\].

All the instructions in ISA are in binary form and is supported by a accompanying (associated) hardware. For example, in intel, all instructions in ISA are in binary form and to implement that one of several instructions in the ISA, x86 assembly language is used. X86 assembly language produces object code for that x86 instruction, and assembler and linker translates it to machine language, which is then executed by the intel cpu directly. And all programming languages (like c++) is designed according to the ISA and Microarchitecture of a particular processor. Your cpu manufacturer (intel, AMD) or designer (ARM) provides information as to what instructions are supported by a particular processor. You need not worry much about ISA (if you are a casual programmer) because c++ compiler (or any third generation or fourth gen programming language and up compilers) act as translator i.e., translate source code (code written by the user) to assembly language which is again translated to machine language by the assembler.

\[Note: Not all compilers (interpreters) translate high-level language to assembly, e.g. Java compiler translates java code to java bytecode (a code which JVM understands) which is then converted to machine language by JVM (java virtual machine) and then executed by the processor, Moreover, some compilers (interpreters) translate high-level language directly to machine language.\]

You just need to learn the c++ or other programming language, However, if you are a serious programmer or a professional, you do need to take into consideration about addition of new instructions in new generation processors, because it will give you more performance or power reduction or both. Moreover, if there is addition of new instructions in a given ISA of a particular processor then to support that instruction, a new compiler has to be made which must contain that instruction \[Binary or assembly instruction {depending on the type of compiler (interperter) } \] in its database and it’s equivalent high-level instruction for a given programming language (c++, c etc.) that you will use. You can’t make use of that new instruction until the compiler of a given third gen. and up programming language has a support for that instruction (because you will not be able to compile that particular instruction, because it does not understand that).

Role of the ISA-

Any program that you create in any programming language (be it c, c++, java ) has to follow the ISA of a given processor. For example, if there is no instruction in the ISA of a given processor to ‘display output in the monitor’ then you will not be able to display anything on to the monitor, Likewise, if there is no instruction that is supposed to load and write something to your RAM, then you will not be able to do both operations i.e., loading and writing of instructions and data to your RAM.

If a program is designed according to a particular ISA then it can run on two or more different processor having the same ISA i.e., if a program is designed for x64-x86 cpu then it will run on both intel and AMD CPU because they incorporate the same ISA (Note: A 64 bit program will only run on 64 bit processor and not on 32 bit processor even if they have the same ISA as 64 bit processor but not vice versa i.e., a 32 bit program can run on x64 processor because cpu designers provide the compatibility for that).

Examples of ISA are- intel CISC (complex instruction set architecture), ARM RISC ( reduced instruction set architecture)

Microarchitecture

Microarchitecture refers to set of techniques in which a given ISA is implemented. It includes decisions and choices as to how many cores you will have, choice of cache type, size, and their design, pipelinine stages and width, microcode, ILP (instruction level parallellism), buses type (PCI, PCIE etc.), whether to have in-order execution or out-of-order execution (if cpu designer chooses out-of-order execution what will be the depth of out-of-order execution engine), whether to have 'speculative execution'.

It is the ISA that is implemented by microarchitecture of a given cpu. If you have less instructions in your ISA then you need less components (transistors, capacitors etc.) in designing the microarchitecture. Several studies have shown that microarchitecture has a greater importance than ISA i.e., it doesn't matter much if your ISA is of cisc or risc type but it does matter how well your microarchitecture is designed and optimised. what this means is that a well-designed microarchitecture can bring you more performance and power efficiency than the choice of the type of ISA.

Examples of microarchitecture are -Skylake, kabylake, ARM v7, ARMv8

Computer Architecture

It is a collective term that includes ISA, microarchitecture, system design ( system design includes all hardware components in the system, including data processors aside from the CPU, such as the graphics processing unit and direct memory access, on-board or external memory controller , and should you add some other components like integated GPU, Northbridge chip onto the same silicon die chip, whether, northbridge will be having only memory controller (As in the case of AMD, that's why 'AMD cpu compatible' motherboards have Northbridge chipset because in Amd cpu there is no interface for data transfer with southbridge chip) or memory controller + interface for data transfer with south bridge chipset ( as in the case of intel and because of this they do not require 'external' northbridge chip built onto the motherboard) and so on.

It also includes data paths (as mentioned above) and miscellaneous things like multiprocessing and virtualization). In short, computer architecture refers to how a computer system is designed and what technologies it is compatible with.

Examples of computer architecture are -Von neumann architecture, Harvard Architecture

Computer architecture and processor architecture do not mean the same thing. When someone strictly says 'computer architecture' then he is referring to the last one (in this answer) and if someone says 'processor architecture' or 'cpu architecture' (whether by ignorance or laziness), he could mean any of the above. When someone says just 'architecture' (in short form) he could also mean any of the above three, you have to judge it by the context. For example, if someone is talking about instructions and says risc or cisc architecture, you can easily see that he is talking about 'ISA' and if there is no use of words like RISC, CISC, instructions, then surely he is talking about 'Microarchitecture'. And if someone is talking about architecture and saying words like ISA (or is saying CISC, RISC), microarchitecture, system design and mixing up all these things and it is becoming too difficult for you to understand, then, for sure, he is referring to the computer architecture.

SOURCE: https://www.techopedia.com/definition/26757/computer-architecture

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


title: Bounds in NP-completeness proofs

text:
# Question
Title: Bounds in NP-completeness proofs
According to the polynomial-time-reduction definition

"If problem $Y$ can be reduced to problem $X$ in polynomial time, we denote this by $Y \leq\_p X$."

If $X$ is one of already known NP-complete problem then we can say that $Y$ is NP-complete.

From my understanding, $p$ should be always polynomial and this cannot be an exponential function such as $2^n$ or $3^n$.

However, my question is if $Y$ or $X$ already has a lower bound that is not polynomial, which is $2^n$ or $3^n$ then can I still say that $Y$ is NP-complete?

In other words, does lower bounds for $X$ and $Y$ matter?

# Answer
Note that you got it wrong in the question. What you have is that if $Y \leq^p\_m X$ and $Y$ is NP-hard, then $X$ is also NP-hard. This is true by definition, unconditional on any other lower bounds known for $X$ or $Y$ (though, as Ryan points out, such lower bounds could be very interesting).

If $X$ is in NP and has a lower bound on its computational complexity that is super-polynomial, it would mean that $P \neq NP$.
> 4 votes

# Answer
When dealing with known NP-complete problems, they will not have a proven lower bound. If they were to have a proven lower bound, then you could conclude some very interesting results about P vs NP. This question explains what conclusions you could possibly make if you proved a non-polynomial lower bound for an NP-complete problem. This explanation goes in depth with *why* lower bound proofs are so difficult. This isn't much of an answer, more of a point in the right direction.
> 1 votes

# Answer
> "If problem $Y$ can be reduced to problem $X$ in polynomial time, we denote this by $Y \leq\_p X$."
>
> If $X$ is one of already known NP-complete problem then we can say that $Y$ is NP-complete.

No, that's backwards. Very informally, $Y\leq\_{\mathrm{p}} X$ means that $Y$ is no harder to solve than $X$.

Still informally, but a bit more precisely, $Y\leq\_{\mathrm{p}} X$ means that we can solve $Y$ by doing a little \[a polynomial amount of\] work and then solving $X$. A problem $L$ being **NP**-hard means that we can solve every problem in **NP** by doing a little work and then solving $L$. Finally, $L$ is **NP**-complete if it's **NP**-hard and is, itself, in **NP**.

So, if $Y$ is **NP**-complete, and $Y\leq\_{\mathrm{p}} X$ then we can solve every problem in **NP** by doing a little work to convert to $Y$, then doing a little more work to convert to $X$, then solving $X$. This allows us to conclude that $X$ is **NP**-hard. If $X$ is also in **NP**, then it is **NP**-complete.

On the other hand, if $X$ is **NP**-complete and $Y\leq\_{\mathrm{P}}X$, all we can conclude is that $Y$ is in **NP**. Informally, we've been told that $Y$ is no harder than some **NP**-complete problem. $Y$ could be **NP**-complete, or it could be really easy, or something between the two.

> From my understanding, $p$ should be always polynomial and this cannot be an exponential function such as $2^n$ or $3^n$.

It's not that "$p$ should always be polynomial": p doesn't denote a function; rather, it stands for the word "polynomial". (If you look carefully, you'll notice that I've typeset it as $\leq\_{\mathrm{p}}$, denoting a type of reduction that's called "p", rather than $\leq\_p$, which would be a type of reduction parameterized by some mathematical object $p$.)

So your remark is a bit like defining $A\to\_{\mathrm{T}}B$ to mean that you can get from city $A$ to city $B$ by train and then saying, "From my understanding, T should always be a train and cannot be another means of transport, such as a car or bus." Well, yes: it's a train because we defined it to be a train. It makes complete sense to ask about cars and buses and functions that aren't polynomials, but "p" means "polynomial" because that's what we decided it would mean.

> However, my question is if $Y$ or $X$ already has a lower bound that is not polynomial, which is $2^n$ or $3^n$ then can I still say that $Y$ is NP-complete?

This is a different question again. The "p" in $\leq\_p$ refers to a polynomial amount of work done translating between two problems. That concept is independent of the difficulty of solving the problems themselves. For example, SAT and 3-colourability are both quite difficult to solve (nobody knows an efficient algorithm for either) but it's quite easy to translate between them (we make undergraduates do it as an exercise, and most of them survive).

As it stands, we don't have any super-polynomial lower bounds on the complexity of solving any **NP**-complete problem on a deterministic Turing machine. That would prove that **P$\\,\neq\\,$NP** which would be... quite a big deal.

> In other words, does lower bounds for $X$ and $Y$ matter?

**NP**-hardness *is* a lower bound: it says that the problem cannot be (much) easier than any problem in **NP**. More generally, if $Y\leq\_{\mathrm{p}}X$ then a lower bound on $Y$ does translate to a lower bound on $X$. This is because the lower bound on $Y$ says "Every possible way of solving $X$ requires at least this much computational resources", and "any possible way" includes "translate to $X$ and then solve $X$."

In general, a lower bound on $X$ doesn't tell you anything. We just know that $Y$ is at most as hard as something which is at least "this hard", but that doesn't say anything, in the same way that "$x\<y$ and $y\>3$" doesn't restrict the value of $x$ at all.
> 1 votes

---
Tags: np, np-complete
---


# Question
Title: shortest path from start to end in a grid but with a twist
i am trying to solve a graph based problem , this is the statement: i have to find shortest route from position marked (s) to position marked (S) \[**Note** : *i marked S and E just for ease of understanding*\]. here is the catch in problem i can go only through cells marked `0` and cells marked `1` represents walls which are impassable.also i have the option to `remove only one wall` if it fetches me a shorter route to exit. ***Moves can only be made in cardinal directions; no diagonal moves are allowed.***

sample 2d grid:

```
[
    [0(S) 1  1  1  1   ],
    [0    0  1  1  1   ],
    [1    0  1  0  1   ],
    [1    1  0  0  0(E)],
]

```

if the option of removing walls were not present i could use`bfs` or `dijkstra` to find the shortest route. this question has been asked here: here \- they use full exhaustive search which is very bad for large matrices and they focus on language based optimisations which is not a good approach to a problem.

someone asked it here \- the accepted answer has the following approach to it:

* Run a breadth-first search starting at the prison door, to find the distance of each passable space from the prison door.
* Run another breadth-first search starting at the escape pod, to find the distanceof each passable space from the escape pod.
* Now iterate over the walls, and consider removing each wall in turn. You know the distance of each passable space from the prison door and the escape pod, so you can immediately work out the length of the shortest route that passes through the space left by the wall
you just removed.

but i am not clear what does this(***so you can immediately work out the length of the shortest route that passes through the space left by the wall*** ) mean in 3rd step above.

also is there any better way to approach it?

# Answer
> 2 votes
Use any search algorithm, where your state space is the set of tuples $(x,y,d)$ where $(x,y)$ are your co-ordinates and $d$ is a Boolean flag that says whether or not you've already dug through a wall. If $d=\mathrm{true}$, then your available moves are just to move to a vacant adjacent square; if $d=\mathrm{false}$, then your available moves are to move to a vacant adjacent square, or to move into a wall and set $d\leftarrow\mathrm{true}$.

---
Tags: algorithms, graphs
---


# Question
Title: Time complexity of art gallery-like problem
Suppose that $G = (V,E)$ is a directed graph such that each vertex in $V$ is in at least one edge in $E$. We'd like to decide whether or not $w$ watchmen can be placed on $w$ distinct vertices in $G$ such that every vertex in $G$ is being "watched" by some watchman. More formally, we'd like to decide whether there exists a $w$-sized watch set $W \subseteq V$ (with $|W| = w$) such that for any vertex $v \in V$, either $v \in W$ or there exists a (directed) edge in $E$ of the form $(u, v)$, with $u \in W$.

I'd like devise a deterministic polynomial time algorithm for deciding whether, for a given $w \geq n/2$, where $n$ is the number of vertices in $G$, $G$ has a $w$-sized watch set $W \subseteq V$. So the decision problem would be $\\{\langle G, w \rangle : w \geq n/2 \mbox{ and } G \mbox{ has a size } w \mbox{ watch set} \\}$.

One approach I'm considering is finding, in polynomial time, a minimum edge covering for $G$. If the size of this edge covering is strictly larger than $w$, then we know a size-$w$ watch set does not exist; otherwise we can easily construct a watch set from this edge covering. However, the polynomial time edge-covering algorithms I've seen are a bit complicated, so I'm looking for a simpler approach.

# Answer
Your problem is a *special case* of finding a dominating set of size at most $w$ for directed graphs $G$, where we require that there are no isolated vertices in $G=(V,E)$ and that $w\geq |V|/2$.

Unfortunately, this problem is still NP-hard, since there is a polynomial time reduction from the general directed dominating set problem:

Given an arbitrary directed graph $G=(V,E)$ and an integer $w$, construct the instance $(G',w)$ as follows:

1. Set $G\_0 \leftarrow G$ and $w\_0\leftarrow w$.
2. Remove all $i$ isolated vertices from $G\_0$ and 'place guards on them': $w\_0\leftarrow w\_0 - i$. If $w\_0\leq 0$, simply construct some instance that yields NO and we're done.
3. If $w\_0\geq |V|/2$, we are done. Otherwise, 'add two guards' for every cycle we will introduce: $w'\leftarrow w\_0+2\cdot(|V\_0|-2w\_0)$ and add $|V\_0|-2w\_0$ directed 3-cycles to $G\_0$. Set $G'\leftarrow G\_0$.

Observe that now $w'\geq |V|/2$, since if we have added the three-cycles, we get $2w'= 2w\_0+4(|V\_0|-2w\_0) \geq |V\_0| + 3(|V\_0|-2w\_0) = |V'|$. The reduced instance is a YES-instance if and only if the original instance is, since 'disconnected' components do not influence the rest of the graph and at least 2 guards are required to watch a 3-cycle.

So a polynomial time algorithm most likely doesn't exist, even for this special case.
> 3 votes

# Answer
Your problem is equivalent to dominating set for directed graphs. The dominating set problem is known to be NP-hard. The standard proof shows that dominating set is NP-hard for undirected graphs; it follows that it is hard for directed graphs, too, if we simply focus on directed graphs where $(u,v)$ is an edge iff $(v,u)$ is an edge. Consequently, you shouldn't expect an algorithm that will have worst-case polynomial running time and will work on all possible graphs.
> 2 votes

---
Tags: complexity-theory, graphs, polynomial-time
---


# Question
Title: What is the complement of Halting Problem?
I understand that Halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever. That is, there are two options for HP: Halt (accept/reject) OR loop.

With this definition of HP, I am unable to understand what is co-HP, since any program can have only 2 options, Halt or loop, so what is co-HP? How do we even know co-HP exists?

# Answer
The complement of a language $L$ is the language of all strings (over the same alphabet) not in $L$. So the complement of any language exists, by definition. It may be empty, which seems to be the case here.

However, your definition of HP is a bit strange, as every program for a given input either halts after a finite number of steps or does not. So, including both in HP obviously gives you all programs.

It might be more useful to consider something similar to the *halting set* $K := \\{ (i, x) | \text{program $i$ halts when run on input $x$}\\}$ (see wikipedia), i.e. the language of all programs that halt.

The complement of $K$ is then, of course, the set of all programs that do *not* halt.
> 5 votes

---
Tags: formal-languages, computability, turing-machines, halting-problem
---


title: unambiguous grammar but it's not LR(1)

text:
# Question
Title: unambiguous grammar but it's not LR(1)
I have following grammar:

$$A \to a A a \mid \varepsilon$$

This grammar is not ambiguous because it has no more than one parse tree from the any sentence generated by this grammar, but there is a shift-reduce conflict in LR(1) on this grammar.

Why does there exist an conflict even though it is not ambiguous grammar?

# Answer
> 9 votes
All $LR(1)$ grammars -- indeed, all $LR(k)$ grammars -- are unambiguous, by definition. But the converse is not true: the fact that a grammar is unambiguous does not say anything about whether it can be parsed with an $LR(k)$ parser.

The grammar you present is not $LR(1)$, although the language itself is. (In fact, the language is regular: $(aa)^\*$.) But that's not true for the language of even-length palindromes which has a rather similar unambiguous CFG:

$$\begin{align} S &\to \epsilon \\ S &\to a S a \\ S &\to b S b \end{align}$$

Intuitively, the problem with parsing palindromes deterministically is that you have to start popping the stack at the middle of the sentence. But you can't tell where the middle of the sentence is until you reach the end, and since there is no limit on the length of a sentence, the end could be arbitrarily distant from the middle. So no finite lookahead is sufficient to make the decision.

A context-free language is $LR(k)$ precisely if it is deterministic. For the outline of a proof of the non-determinism of the language of even-length palindromes, see: prove no DPDA accepts language of even-lengthed palindromes

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


# Question
Title: What are differences between Static Scope and Dynamic Scope?
My teacher has provided the following pseudo-code, and says that the output using static scope is `1 2 3`, but the output using dynamic scope is `2 3 4`.

```
void fun1(void);
void fun2(void);

int a = 1, b = 2, c = 3;

int main() {
    c = 4;
    fun1();
    return 0;
}

void fun1() {
    int a = 2, b = 3;
    fun2();
}

void fun2(){
    printf("%d %d %d", a, b, c);
}

```

Which variable we use in Static Scope? $c=3$ or $c=4$? (by Static Scope Rule and without considering C Rules).

# Answer
> 4 votes
In static scope the $fun2$ takes the globally scoped $c$ which comes from scope where function is defined (opposite to dynamic, where it traverses scopes of execution), so $c = 3$.
With dynamic scope traverses up the chain of scopes until it finds variable it needs, which reflects the fact that scopes are:
Global($a=1, b=2, c=3$) -\> main($c=4$) -\> fun1 ($a=2, b=3$) -\> fun2.
fun2 in the way up finds $a=2, b=3$ in fun1 and $c=4$ in main.
By the way: C has static scope rules.

# Answer
> 4 votes
Some background, from https://www.youtube.com/watch?v=6m\_RLTfS72c:

> What is static scope ? Static scope refers to scope of a variable is defined at compile time itself that is when the code is compiled a variable to bounded to some block scope if it is local, can be bounded to entire Main block if it is global. examples: C,C++, Java uses static scoping
>
> What is dynamic scope in Programming Languages ? Dynamic scope refers to scope of a variable is defined at run time rather than at compile time. Perl language allows dynamic scoping.

Coming to your question **a=2,b=3** are defined in **fun1()** which is the most recent scope and dynamic scope for **a,b variables** . So, if we use **dynamic scoping** output will be **2,3,4**. For clear information check this link static scope and dynamic scope with examples.

# Answer
> 1 votes
POINT OF CLARIFICATION:

The 'c' referred to in main() IS NOT DECLARED IN main(). Therefore there is *only one* 'c' in the program, the global one. When the program is run, this 'c' is first initialized to 3, then the value 3 *is overwritten in* main() with 4, which is why the output of fun2() is '1 2 4'.

If we alter the statement in main() from 'c = 4' to 'int c = 4', THEN there will be two 'c' variables, one global, the other local to main(). THEN we can say that the output of fun2() should be '1 2 3' under static scoping (as in C) versus '1 2 4' under dynamic scoping.

# Answer
> 0 votes
Each procedure that is invoked contains a link (the dynamic link) to the invoking procedure. When the procedure is finished, this link is used to return to the invoking procedure. In a language using dynamic scoping,the dynamic link is also used to lookup the 'scope' of the variables. That means that in the example fun2 is invoked by fun1. By going back the dynamic link, we find that a=2 and b=3. To find c we follow the dynamic link to main, and c=4.

In a static scoped (also called lexical scoped) language the dynamic link is only used to find the return address when the procedure is finished. A second link (called the static link) is defined to find the scope of the variables. In the example all three functions (fun1, fun2 and main) are defined on the same level. All three of them will have a static link pointing to the global level. So when fun2 is invoked, it will follow the static link to the global level and find a=1, b=2 and c=3.

---
Tags: programming-languages, compilers, functional-programming, variable-binding
---


# Question
Title: An algorithm to find highest lines in at least one point
Suppose we have $n$ lines $L\_1, L\_2, \dots, L\_n$, where $L\_i$ has the equation $y = a\_i x + b\_i$. We call $L\_i$ the highest line at $x\_0$ if for each $j \in \\{1, 2, \dots, n\\}$

$$a\_i x\_0 + b\_i \ge a\_j x\_0 + b\_j.$$

* **Goal:** Find an algorithm in $O(n \log n)$ time to return a set of lines that are the highest lines in at least one point.
* **Hint:** Use the divide and conquer technique.

Since we should use divide and conquer technique, I think I should split the problem into two subproblems with size of $n/2$ and try to solve these two first. I don't know what to do next. Thanks in advance.

# Answer
If the lines are unlimited (as they seem to be) then the way to go seems to divide the lines by their slope.

Preprocessing:

Sort all the lines lexicographically by their slope and constant term. This allows to remove each line which is parallel to some higher-placed line. The ordering is also used to split the lines into subroups depending on their slope later on.

Recursion:

Divide the lines into lines with positive and negative slope. For each group call recursion. From each recursion we get two lists, a list of top-lines (ordered as they appear on top from left to right) and a list of top-intersections of the top-lines (ordered by x-coordinate) corresponding to the points where one line takes over the previous one.

Now we only need to combine the two results we got from recursion. The algorithm passes through the intersection-point lists in parallel, going through positive-slope lines from right to left, and through negative-lines from left to right until the x-coordinates of the intersections meet. To do this properly, we need always make the step on the side with higher y-coordinate.

(I strongly suggest to draw it, it's easier to see in a picture. Imagine bunch of lines forming a "U"-shape and the algorithm descends with equal vertical speed on both sides until it reaches the lowest point of the "U"-shape.)

In this way we found a "middle" point where one positive- and one negative-slope top-line meet in a new top-intersection. From the list of lines we know which lines meet there and we can compute the intersection point they share (the lowest point of the "U"-shape).

We can now construct the total list of intersections of top-lines (all the point we went through + the new intersection point we found in the middle) and the list of the corresponding top lines.

Note that it might happen that all the positive-slope intersection might be too much to the left (so we do not get a "U"-shape). In that case we only get one positive- and one negative-slope line as a result, intersecting in an "V"-shape.

Now, how to split the groups in the recursion? Well, simply realize that by tilting (by less than 90 degrees) what the algorithm understands us "horizontal" none of the necessary properties is violated (within the subgroup). Thus the algorithm can again split the groups into smaller groups, while the left-right orderings remain consistent. So in fact we don't want to split lines into positive and negative slope, but simply split by the median slope each time. (splitting by the horizontal direction just makes it easier to understand)

Complexity:

Each level of recursion is linear-time in respect to the number of lines (going through lists in parallel, concatenation of lists, etc.). Since the lines are already ordered by their slope (from preprocessing), we can always split by the mean slope in linear time. So the total time is O(nlogn).

Hope the description is somewhat clear. I did not go into details as that would be lengthy.
> 0 votes

# Answer
SORRY: I MIS-READ THE PROBLEM AS FIXING THE X COORDINATE FIRST:

Evaluate each line $L\_i$ at $x\_0$, yielding $y\_i$. Collect all ordered pairs ($L\_i$,$y\_i$) and sort on the $y$ values. Top pair yields the desired line. *\[note: there may be more than one 'top line', in which case they will all be at the 'top' with the same $y$ value\]*
> -1 votes

---
Tags: algorithms, computational-geometry, divide-and-conquer
---


# Question
Title: Equivalence between alternative definitions of NP
I'm having some problems in understanding the two alternative definitions of NP. They're presented as equivalent, but to me they seem to define different class of problems. Intuitively, we can think of a non-deterministic TM as branching at every step to check all possible alternatives in parallel. Also, we can see it as guessing the right next state at every stage of the computation. In both cases, if there is a computation path which terminates in an accepting state, the TM is said to accept its input, otherwise it rejects it. On an informal level, we can define NP in two ways.

1. The class of problems solvable in polynomial time by a NTM. That is, given an instance $x$ of the problem, there is a NTM $M$ which accepts $x$.
2. The class of problems which can be verified in polynomial time by a TM. In this case, together with the input we get a *certificate* which provides a *proof* that $x$ is a solution. We can then check if this is the case by some polynomial time procedure.

Now, what baffles me is that taking the first definition, it would seem as if a NTM would always find the accepting computation path and will thus always be able to accept its input (provided this is in the language recognized by the TM). On the other hand, by the second definition, since we're given only one certificate, $x$ could actually be in the language recognized by $M$, but we cannot tell because we've been given the wrong certificate.

On a second thought, the problem here could be that I'm thinking as a NTM as *actually performing* a computation, while it is just a theoretical construct. That is, even if we allow the TM to accept if at least one computation path accepts, no one guarantees that a concrete run of the algorithm will "follow" this computation path. So, in this sense we could see the equivalence by stating that, in the case of a verifier, the TM accept if there is at least one *certificate* which proves that the input is in the language recognized by the TM; this parallels the way in which a NTM needs only to have at least one computation path which accepts the input.

Any deeper insight or also formal derivations would be very appreciated.

# Answer
The definition of $\text{NP}$ in terms of verification can be formally stated as follows:

> A language $L$ is in $\text{NP}$ if there exists a polynomial verifier for $L$ such that for every $x$: $$x \in L \iff \exists u: V(x,u) = 1.$$
>
> Here $u$ serves as a certificate.

To prove that the other definition $\text{NP}$ in terms of NTM implies the one above, you should construct such a polynomial verifier $V$ with the desired property. That is, for every $x \in L$, you need to *find a certificate $u$* (you are not given a certificate $u$) such that $V(x,u) = 1$. Note that for every $x \in L$, there is *a sequence of nondeterministic choices* that makes the NTM $M$ accept $x$. This sequence is the certificate we need. What the polynomial verifier $V$ need to do is just to simulate the action of $M$ using these nondeterministic choices.
> 6 votes

# Answer
This is an informal version of the answer you require I guess.

In this case both(TM and NTM), what they do is verification only. Assume that we have a problem like Sudoku which can be verified on a TM in polynomial time. We are asked to solved that so we can try to brute-force all possible solutions as a worst method to solve.

In a normal CPU you can make loop which checks for a solution in the solution space. But if you have as many number of CPUs as you want working in parallel then you can verify all the possible solutions by the time of a single verification. It is only one difference & that is TM traverse in solution space one after another and NTM traverse all at once.

Theoretically NTM doesn't choose the correct path always. It has non-determinism so it goes on all path at the same time. While processing any input if one of the state you are in is an accepting state then NTM accepts that input.
> 3 votes

# Answer
A non-deterministic turing machine can only find an accepting path if there is one. For example, if you try to solve the Travelling Salesman problem, and you have a configuration where the shortest tour takes 1,272 miles, and you ask if there is a tour taking 1,271 miles or less, then the NTM isn't going to end up in an accepting state.

The easier way to see the equivalence is by using the model that an NTM just magically picks the correct decision at every step where it is allowed to choose. Now in one direction, let an NTM find an accepting path, record all the magically correct decisions, and call that sequence of decisions a "certificate". Now you build a deterministic TM exactly like the NTM, except that where the NTM made a magically correct decision, the deterministic TM consults the next bit of the "certificate" to decide. Obviously the NTM and the DTM make exactly the same decision at every step, so the DTM will also find an accepting state.

The other direction is even easier: Build a TM that takes a problem and a certificate as its input, and which finds an accepting state with the right certificate. Then you can build a NTM by letting it choose which decision to make at every point where the DTM consulted the certificate to make a decision. To find an accepting state, all the NTM has to do is magically guess the decision that the TM would have made based on the certificate.
> 0 votes

---
Tags: complexity-theory, computability, turing-machines, np, nondeterminism
---


# Question
Title: cardinality of recursive/r.e/not r.e languages?
I was just looking into properties of languages and wondered about the cardinality of them

* are all recursive languages countable or can they also be uncountable (can u have a recursive language which is uncountable?)
* can r.e languages be countable and uncountable? (can u have a r.e but not recursive language which is uncountable?)
* are all non r.e languages uncountable? (can u have a non r.e language which is countable?)

an explanation would be nice but i am not necessarily looking for a proof. thanks!

# Answer
> 1 votes
I assume you're talking about the cardinality of the sets $R$, $RE$, and $\overline{RE}$, as the set of all words in a language is always countable.

* $R$ (the family of recursive langauges) is countable, because there the set of Turing Machines is countable, and there is at least one TM for each $R$ language.
* $RE$ is countable, by the same logic, since there is a TM semi-deciding each $RE$ language.
* The set of non-$RE$ languages, $\overline{RE}$, is not countable, then by process of elimination. The set of all languages, $\mathcal{L}$, over an alphabet $\Sigma$ is $\mathcal{P}(\Sigma^\*)$ i.e. the powerset of the set of all words. This set is uncountable, since $\Sigma^\*$ is countable, and the powerset of a set always has higher cardinality.

$\mathcal{L} = RE \cup \overline{RE}$, and $RE$ and its complement are disjoint, so since $RE$ is a countable subset, there must be an uncountable number of words in $\overline{RE}$.

---
Tags: formal-languages, computability, undecidability, sets, semi-decidability
---


# Question
Title: What if there is a polynomial-time algorithm to minimize NFA?
Knowing that NFA-minimization has been proven to be P-SPACE complete, what if there is a polynomial-time algorithm to minimize NFA? Does that imply that P = PSPACE?

# Answer
> 5 votes
If any PSPACE-complete problem is proved to be in P, then that proves that P = PSPACE, i.e., every problem in PSPACE can be solved in polynomial time.

Why? Suppose we have a polynomial time algorithm for NFA minimization. Since NFA minimization is PSPACE-complete, any other problem in PSPACE can be solved by reducing the problem to NFA minimization, then applying the polynomial-time algorithm for NFA minimization. The definition of PSPACE-complete ensures that the reduction step will complete in polynomial time, so solving that problem can be done in polynomial time.

---
Tags: complexity-theory, automata, space-complexity
---


# Question
Title: Counting permutations whose elements are not exactly their index ± 1
This is a special case of the question:
Counting permutations whose elements are not exactly their index ± M

The $M=0$ case has already been solved, but no one was sure how to work out the non-zero cases.

So I decided to try to just brute force some values and search the results for a recursion relation. As a test I first tried $M=0$ and searched for recursion relations that looked like: $$ a\_n = \sum\_{1\le i \le k} (A\_i n + B\_i) a\_{n-i} $$ where $k$ is some cutoff of how far back to search, $A\_i \in \\{-1,0,1\\}$ and $B\_i$ some small integers. It was correctly able to find: $$a\_n= (n-1)a\_{n-1} +(n-1)a\_{n-2}$$

So I then tried for $M=1$ and found: $$ a\_n= (n) a\_{n-1} +(-n+2) a\_{n-3} + (-1)a\_{n-4} $$

It's possible it's just a coincidence, but I ran a brute force approach to calculating the $M=1$ cases overnight to get a couple more values and it still holds. But even with this potential answer in hand, I cannot figure out a reason this recursion would hold.

Is there a simple combinatoric argument I'm missing here?

# Answer
> -3 votes
Checkout Derangements

"Suppose that there are n people who are numbered 1, 2, ..., n. Let there be n hats also numbered 1, 2, ..., n. We have to find the number of ways in which no one gets the hat having same number as their number."

In applying this to your problem, there would be two hats: the element's index +1, the elements index -1.

I'm not certain this solves the problem, but it seems like a step in the right direction.

---
Tags: combinatorics, recurrence-relation, permutations, algorithm-design
---


# Question
Title: Design a turing machine that accepts $L=\{ww^Rw\mid w\in\{0,1\}^*\}$
> I need to design a turing machine that accepts $L=\\{ww^Rw\mid w\in\\{0,1\\}^\*\\}$.
>
> $w^R$ is the reverse of $w$.

I don't have a good idea yet how to do that, I know I should check:

1. the length of the word must be equal $0\mod 3$
2. $ww^R$ is a palindrome
3. the prefix $w$ equal to the suffix $w$.

I thought maybe to divide the word to three parts and use non deterministic TM to move from one part to another. Need help with the algorithm.

# Answer
> 1 votes
Here is an idea for an non-deterministic Turing machine: guess the borders between $w$ resp. $w^R$ non-deterministically and verify that the parts do indeed match.

With a little more detail:

* Mark the first input symbol. Put additional marks on two more arbitrary symbols (choose non-deterministically).
* Consume the word (i.e. overwrite it with blanks) in lock-step starting from each mark; move right from the first and third, and left from the second.
    + If the three marks are on *different* symbols at any step, reject.
    + If they are the same, overwrite with blank and move all marks in their direction by one symbol.
* If all three marks reach blank simultaneously, accept.
* Otherwise, reject.

I'll leave the details and proof of correctness as exercise.

# Answer
> 2 votes
I suggest a deterministic solution using some basic TM trickery.

First you need to identify the parts. Suppose we tag the 0,1 symbols by replacing them by symbols, e.g. A,B (A~0, B~1) - so that we know what we already "tagged" but keep the data "intact". The TM works in a simple loop: move far left, tag the first untagged element, move to far right, tag first two untagged elements. If at some point the tags from left and the tags from right meet, we have found the end of W prefix. If the tags don't meet well, then the length of the input is not divisible by 3 and the TS says NO. Suppose we used A,B tags on left and C,D tags on right (so we can always find the end of W prefix). We split in the C,D part into WR and W in a similar way.

Suppose that the first part now consist of A,B symbols, the middle of C,D symbols and the last of E,F symbols. The TS now reads the three sections in parallel (while the middle one is read in reverse) and compares them in a simple loop, while rewriting the correct parts with some special # symbol. First, move to the left to find the first non-# symbol (which is either A or B). Remember it (use two sets of states, one corresponding to A and one corresponding to B) and replace the symbol by #. Move right until you reach the end of C,D section (the first symbol E,F or # signifies the end), and check if the previous symbol corresponds to the remembered value (A~C, B~D). If it does not, answer NO. Otherwise replace it by # and move to the first E/F-symbol and again check (A~E,B~F) and replace with #. Repeat until there are no non-# symbols left. Once that happens, the answer is YES.

---
Tags: turing-machines
---


# Question
Title: What is the abstract idea of a semaphore and how can we use it to implement mutual exclusion?
So I've got this so far to try and wrap my head around the **abstract idea** of a semaphore:

> A semaphore is a variable or abstract datatype (commonly an integer), used to control access to a common resource by multiple processes in a concurrent system.

I'm not sure that this definition fully encompasses the full idea of semaphores.

As well as this, I'm not sure how we could use them to implement mutual exclusion.

Any notes to help me understand this concept is appreciated!

# Answer
> 5 votes
A semaphore is a counter, that counts the number of processes that have access to a resource. If a resource can service n processes, n is decremented each time a process accesses the resource, and increments it when the process no longer needs the resource. When n reaches zero, the access of the resource is denied.

A real life example will make things clear: imagine a public toilet with 5 toilets (n=5). At the entrance there is a guard (the semaphore). If some one wants to enter the guard looks at n. if n \> 0 the guard let the visitor in and decrements n. If someone comes out n is incremented. Only if n=0 the guard will block the entrance until someone leaves.

Consider a binary semaphore, where `n = 1`. This semaphore works as a flag which is activated when the resource is in use or not, and can be used to protect a critical section. When a process wants to enter the critical section, it first looks at the ‘flag’ to find out if the critical section is being used by another process. If not, the process enters and raises the flag, preventing the other processes to enter. The flag is unset when the process leaves, and therefore ensures mutual exclusion.

---
Tags: concurrency, mutual-exclusion
---


# Question
Title: How can CFGs have epsilon rules if CSG may not have them?
I am new to theory of computer science and I am currently reading about CTF grammars. In our lecture we defined that a Type 1 grammar is context-free if for $w\_1 \to w\_2$, $\vert w\_1 \vert \leq \vert w\_2 \vert$.

I looked on the internet for an example and found this context-free grammar for palindromes: $G = \\{\\{P\\},\\{0,1\\},A,P\\}$ with the production rules: $P \to \epsilon|0|1|0P0|1P1$, but aren't those production rules violating the definition for a CTF? First of all $\vert w\_1 \vert \leq \vert w\_2 \vert$ is violated by $P\to\epsilon$ and secondly in my notes there is mentioned that we can only use an epsilon transition if P isn't on the right site.

# Answer
> 1 votes
The definition you state is for noncontracting grammars, which define the context-sensitive languages (modulo the issue of the empty word). In contrast, context-free grammars define the context-free languages, which are a strict subset of the context-sensitive languages.

So whoever told you that a Type 1 grammar is context-free iff it is noncontracting, used highly idiosyncratic terminology. Or perhaps they just made a mistake.

The Wikipedia article mentions a paper of Chomsky in which noncontracting grammars are called "Type 1". In an earlier paper of Chomsky, he used "Type 1" to mean context-free grammars. This might be the source of the confusion.

Finally, to answer the question in your title: noncontracting grammars only define the context-sensitive languages without $\epsilon$. Conversely, the context-free languages without $\epsilon$ are defined by context-free grammars without $\epsilon$ productions (this follows from Chomsky normal form, for example). In this sense a noncontracting grammar is a generalization of a context-free grammar, in both cases for languages without $\epsilon$. If you want to include also languages with $\epsilon$, you need to consider *essentially* noncontracting grammars instead; these are also allowed to contain the product $S\to\epsilon$, assuming $S$ doesn't appear in the right-hand side of a production.

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


title: Conversion of FA to Regular Expression

text:
# Question
Title: Conversion of FA to Regular Expression
If there is a transition with no input in the FA, when it is converted to a regular expression should it be accepted as ɛ transition? As an example picture shown below, should regular expression showing possible transitions between 1 and 3 (1-2-3 , 1-3) be accepted (ab+ɛ) or just ab?

# Answer
The regular expression is supposed to match (exactly) all of the words that the automaton accepts. If you pretend that some of the transitions of the automaton don't exist, you're effectively converting a different automaton, and that automaton probably accepts different strings from the ones you're supposed to accept.

In this specific case, pretending that there's no $\varepsilon$-transition from the first state to the third one means that the automaton no longer accepts the word $c$.
> 1 votes

# Answer
Any epsilon transition from a start state to state $x$ would mean $x$ is also a start state because you can get to state $x$ with no input (via epsilon transitions). In your image, states 1 and 3 would thus both be valid starting states and you could start accepting input from either. So yes, with no input, not only *can* you be at state 3, but you *are* at state 3. A regular expression representing your FA could be something like `/(ab)?c/`. We can optionally have `ab`, because we start at states 1 and 3, but then we are required to have `c`.

One thing to note, because your FA can be in multiple states at once (e.g. it can be at 1 and 3 before it starts accepting) it is a non-deterministic finite automata. You can get around this by converting it to a deterministic finite automata. A pretty common algorithm for this is the powerset construction. Then you can minimize it if you'd like using DFA minimization algorithms.
> 0 votes

# Answer
We can read the equations of your machine from the diagram: $$\begin{align} S\_1 & = a S\_2 + S\_3 \\ S\_2 & = b S\_3 \\ S\_3 & = c S\_4 \\ S\_4 & = \epsilon \end{align}$$

The equation for $S\_1$ has an epsilon transition to $S\_3$.

We can solve for $S\_1$ bottom up: $$\begin{align} S\_3 & = c \\ S\_2 & = b c \\ S\_1 & = a b c + c \\ \end{align}$$

---

It is always possible to eliminate the other states one by one to get a regular expression for the entry state. Since the equations are right linear, they can be put in the form

$$\mathsf V = \mathcal R + \mathcal S \\; \mathsf V$$

where

* $\mathsf V$ is a non-terminal and
* $\mathcal R$ and $\mathcal S$ are regular expressions free of $\mathsf V$.

The solution to the equation is $$\mathsf V = \mathcal S^\* \mathcal R$$

Note that the right-hand side is free of $\mathsf V$.
> 0 votes

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


# Question
Title: How to extend a hash function to manipulate longer integers?
Carter and Wegman introduced in the paper Universal Classes of Hash Functions the $H\_{1}$ universal class of hash function. This is essentially the function $h\_{a,b}(x) = ((a\cdot x+b)\mod p)\mod m$. *I am using here the more common notation from CLRS book respective description, and not from the paper*.

Some notation:

* $x$ is the input to hash function (the key) and takes values in $\\{0..u-1\\}$
* $p$ is a prime $\geq u-1$
* $a$ is a random number in $\\{1..p-1\\}$
* $b$ is a random number in $\\{0..p-1\\}$
* And obviously the outputs of hash function are in $\\{0..m-1\\}$

The problem is that if key word $x$ is large enough, the multiply and add operation involved in the hash function maybe lead in an overflow. For example if $u= 2^{32}$, $x= 2^{32}-1$, then we cannot hold the outcome of $a\cdot x + b$ in a 32-bit word. But even if we can (using 64 bit word) the least prime $p$ we can use is $4294967311$ which can be represented by 34 bits. In that case $a$ and $b$ will possibly have values of 34 bits long, so a 64 bit word can't hold the outcome of $a\cdot x + b$ leading in an overflow.

The authors of the paper describe a way to manipulate longer integers in proposition 8 and the following paragraph, using hash functions working with shorter integers.

Can anyone please demystify the way we can extend this function to manipulate longer integers and why this is working? The paper can be found here here

# Answer
I believe Schrage's method is exactly what you are looking for.

But for a general method of computing $ax + b \bmod m$ where $a, b, x, m$ all fit in a single CPU word and all are unsigned values I can quickly explain a method. I assume a CPU word has size $2^w$ and overflow is just modulo $2^w$.

First, computing $x + y \mod m$. Reduce $x, y \mod p$ (not necessary if you already know $x, y \< p$). Then, if $y \geq m - x$, overflow would occur. So in that case we compute $x + y - m$, otherwise simply $x+y$. In C++:

```
// Compute (x + y) % m, assumes x, y < m.
uint64_t addmodu64(uint64_t x, uint64_t y, uint64_t m) {
    return x + y - m * (y >= m - x);
}

```

Then, computing $xy \bmod m$ can be done by multiplication through repeated addition in $O(\log x)$ additions. We can repeatedly apply the following identity:

$xy \equiv (2\lfloor{x\over2}\rfloor + (x\bmod 2))y \equiv 2y\lfloor{x\over2}\rfloor + y(x\bmod 2) \mod m$

This gives a recursive function:

```
// Compute (x * y) % m, assumes x, y < m.
uint64_t mulmodu64(uint64_t x, uint64_t y, uint64_t m) {
    if (x == 0) return 0;
    uint64_t y2 = addmodu64(y, y, m);
    uint64_t r = mulmodu64(y2, x/2, m);
    if (x % 2) r = addmodu64(r, y, m);
    return r;
}

```

This is just for demonstration purposes, for a fast implementation you want to convert this to a loop without any calls.

Finally, computing $(ax + b \bmod p) \mod m$ then is as simple as `addmodu64(mulmodu64(a, x, p), b, p) % m`.
> 1 votes

---
Tags: hash, hashing
---