title: Algorithm to find "truncatable words"?

text:
# Question
Title: Algorithm to find "truncatable words"?
My son who is just learning to read loves the concept of hiding one letter of a word with his finger and asking what the rest of the word spells. His favorite is turning "her" into "he" and "then" into "the."

As he's starting to learn bigger words I want to find some words for him that are "truncatable," similar to the concept of a truncatable prime. These would be dictionary words that are also dictionary words when a character is removed from either the left or the right side. A properly "truncatable" word would continue to be a word down to 1 character, but I would be really only looking for those that are truncatable down to three letters:

```
 Browser
 Browse
 Brows
 Rows
 Row

```

What is the best algorithm to do this? My initial naive approaches are proving quite horribly inefficient for the dictionary file that I am using. I am currently literally testing every word in the dictionary, recursively, and the running time and space are intractable and the methodology ends up testing each word many times.

Is there an efficient memoized or otherwise optimized way of finding truncatable words?

Edit: Thank you to https://cs.stackexchange.com/users/755/d-w who provided guidance, this is the code I ended up coming up with which works:

```
# find list of truncatable words in English
# truncatable words are those where a word
# can be dropped from the beginning or end
# to form a new valid word, all the way down
# to three letters or fewer!

def main():
    # Find the truncatable words

    # read dictionary into a list
    f = open("english3.txt","r")
    wordlist = []
    for line in f:
        wordlist.append(line.strip().lower())

    # sort by length

    wordlist2=sorted(wordlist,key=len)
    max_word_length = len(wordlist2[-1])

    # set up list of dictionaries for truncatable words
    Truncatables = []
    for filler in range (max_word_length+1):
        Truncatables.append({})

    # iterate through dictionary and test for truncatability
    for word in wordlist2:
        if len(word)<=3:
            Truncatables[len(word)][word]='default'
        else:
            front = word[1:] in Truncatables[len(word)-1]
            back = word[:-1] in Truncatables[len(word)-1]
            if front and back:
                Truncatables[len(word)][word]='both'
            elif front:
                Truncatables[len(word)][word]='front'
            elif back:
                Truncatables[len(word)][word]='back'
            else:
                pass
    print(Truncatables)

    # Define a function that recursively prints out a truncatable chain

    def printTruncatable(word):
        if word in Truncatables[len(word)] and word in wordlist2:
            print(word," ",end="")
        TruncType = Truncatables[len(word)][word]
        if TruncType == "back" or TruncType == "both":
            printTruncatable(word[:-1])
        elif TruncType == "front":
            printTruncatable(word[1:])
        elif TruncType == "default":
            print("\n")
        else:
            print("ERROR")

    # print the top truncatables
    for wordlength in range(max_word_length,7,-1):
        for key in Truncatables[wordlength]:
            print(wordlength,": ", end="")
            printTruncatable(key)

if __name__ == "__main__" :
    main()

```

# Answer
> 2 votes
Here is a simple implementation strategy.

Find all three-letter truncatable words. Every three-letter word is truncatable, so this is a linear scan through the dictionary to find the three-letter words. Store them in a hashtable.

Find all four-letter truncatable words. You can check whether a four-letter word wxyz is truncatable by checking whether wxy is a truncatable word; the latter can be checked by looking it up in the previous hashtable. So, this can be done with a linear scan through the dictionary. Store all four-letter truncatable words in a hashtable.

Find all five-letter truncatable words, by a linear scan plus a lookup in the hashtable for four-letter truncatable words. Note that given a word vwxyz, it suffices to check whether vwxy is truncatable (you don't need to check vwx).

Find all six-letter truncatable words.

And so on. Finish when you've exhausted the length of words in the dictionary.

# Answer
> -1 votes
Never done it, but this might work for you. I'm using 2 characters as my threshold to generate my example because its easier cognitively, but maybe something along the lines?

1. Run through the dictionary and discard any word less than 3 characters as 2 letter-strings are non-truncatable; then organize by size from largest to smallest by length and alphabetize each subset; this subset of the dictionary is D'.

> {a, aa, aardvark, ..., an, ant, anteater, ...} -\>
> {aardvark, ..., ant, anteater, ...} -\>
> {aardvark, ..., anteater, ..., ant, ...}

2. Use recursion and a binary tree to move through D' to generate a candidate list L from word W. Your base case would be a two-letter string. You can discard two-letter results. For example:

> "that" -\>
> (that (hat,tha)) -\>
> (that (hat (at, ha)),(tha (ha, th))) -\>
> {(that, hat, at), (that, hat, ha), (that, tha, ha), (that, tha, th)}

Note that this would generate combinations that have non-words, so at each level of recursion, you can check D with a regex for membership. In python, this is easier with an is-in call.

> with is-in check : {(that, hat, at), (that, hat, ha)}

3. Concatenate your tuples into new dictionary of results R.
4. Remove all entries in tuples of R from D' so you don't duplicate your work. For instance, this algorithm checks "that" before "at", "ha", and "hat", so eliminate "hat" AND "that" from D'. (D' has already been stripped of "at" and "ha".)
5. Reiterate steps through revised D' until D' is exhausted.

R should now contain tuples of various lengths without redundancy. I'd alphabetize R because that's my nature.

---
Tags: algorithms, memoization
---


title: General resolution in first order logic

text:
# Question
Title: General resolution in first order logic
Assuming you have a formula in first order logic like

> > $$(\forall\_x p(x) \land \forall\_x q(x)) \rightarrow \forall\_x(p(x) \land q(x))$$ (which seems valid?)

Converting the formula to CNF:

> $$(\neg p(x) \vee \neg q(y) \vee p(z)) \land (\neg p(x) \vee \neg q(y) \vee q(z)) $$

I don't see how I can apply general resolution to get the empty clause in this case which puzzles me since I believe the formula is valid.

# Answer
> 2 votes
As you correctly point out, the original formula is valid (in every model either there is some element for which p or q doesn't hold, or p and q hold for all elements).

To prove that your formula is valid, you cannot use resolution directly. Recall that with resolution, you can derive the empty clause from a clause set iff the clause set is unsatisfiable. **Your formula is valid iff its negation is unsatisfiable**. So to prove your formula is valid, you have to derive the empty clause from the clause set corresponding to the negation of your formula.

Let $\varphi$ be your original formula. $$\lnot \varphi \equiv \forall\_x \forall\_y \exists\_z (px \land qy \land (\lnot pz \lor \lnot qz))$$ Skolemization replaces $z$ by a function symbol $f(x,y)$: $$\lnot \varphi \equiv\_{SAT} \forall\_x \forall\_y (px \land qy \land (\lnot pfxy \lor \lnot qfxy))$$ The corresponding clause set: $$\\{\\{px\\},\\{qy\\},\\{\lnot pfxy, \lnot qfxy\\}\\}$$ From there it should be straight-forward to derive the empty clause:

* Apply renaming $\nu\_1 = \\{x/x\_1\\}$ to $\\{px\\}$, yielding $\\{px\_1\\}$, then resolve $\\{p x\_1 \\}$ with $\\{ \lnot pfxy, \lnot qfxy\\}$ by $\sigma\_1 = \\{ x\_1 / fxy\\}$, yielding $\\{\lnot q fxy\\}$
* Apply renaming $\nu\_2 = \\{y / y\_1\\}$ to $\\{qy\\}$, yielding $\\{qy\_1\\}$, then resolve $\\{qy\_1\\}$ with $\\{ \lnot qfxy \\}$ by $\sigma\_2 = \\{y\_1/fxy\\}$, yielding the empty clause $\Box$

In conclusion, we have shown by resolution that $\lnot \varphi$ is unsatisfiable. Therefore $\varphi$ is valid.

---
Tags: logic, artificial-intelligence, first-order-logic
---


title: Finding minimum in PRAM model

text:
# Question
Title: Finding minimum in PRAM model
Show that the minimum of $n$ elements stored in an array can be found in a time in $O(\log(n))$ using $O(n/\log(n))$ processors assuming an EREW-PRAM machine is given.

# Answer
> 2 votes
Let us start with a solution using $n$ processors and then we optimize the solution to use $O(n/\log n)$ of them. Assume first that $n$ is a power of $2$, i.e. $2^k$ for some $k \in \mathbb{Z}$. Imagine a perfect binary tree where the leaves are the elements of the array. In each step we will process one level of the tree in a bottom up manner, where for each node in the tree we will compute the minimum of all elements contained in the leaves of its subtree and write this minimum in the node.

In the first step each node represent one element and hence is the minimum of it self. Now in each further step we go one level up in the tree, half of the processors retire and the other half, each will be responsible for one node. Note that the minimum of leaves in a subtree rooted at some node, is the minimum between the minimum of elements in its right subtree and the minimum of elements in its left subtree. Hence, a processor responsible for a node $M$, it only compares the numbers written on the left child and the right child of this node and write the minimum between them in this node. When we reach the top of the tree, we will have exactly one processor that will compare the values written in both children of the root and write the minimum of them in the root.

Since the depth of a perfect binary tree of $2^k$ leaves is exactly $k$, the algorithm finishes in $\log n$ steps. Since we started with $n$ processors and the number of used processors kept cutting down, $n$ processors are enough for the whole job.

Now assuming $n$ is not a power of two, then there is a $k$ such that $n \< 2^k \< 2n$. Try to prove this claim as an exercise. Now using this claim, given an array of $n$ elements, we can use $2n$ processors to build an array of $2^k$ elements in constant time by adding very large numbers to the array (adding numbers equal to the first number of the array suffice since we are looking for the minimum) and run the algorithm as described above.

Now we optimize the number of processors using a preprocessing technique. Assuming we started with $c \cdot n/ \log n$ processors for some constant $c$ (2 is enough here). Let us start by completing the array into a power of two as above and cut the array into chunks, each of size $\log n$. We will have at most $O(n / \log n)$ of them. Each processor can find the minimum in a chunk sequentially in $O(\log n)$ time. Let us build a new array $A'$ of length $O(n / \log n)$, where the processor responsible for the $i$-th chunk writes the minimum in the $i$-th position of the array. We end up with an array of size $O(n / \log n)$ and with $c \cdot n / \log n$ processors we can proceed as above in $O(\log(n/\log n) = O(\log n)$ steps.

In total we get an algorithm with $O(\log n)$ time and $O(n / \log n)$ processors.

---
Tags: algorithms, time-complexity, parallel-computing
---


# Question
Title: How to find number of combinations of choosing one from k subsets
Consider we have set S:

S = {1,2,3,4,5,6}

and 3 (say k) subsets of S:

S\_1 = {1,2,3}

S\_2 = {2,3,4,5}

S\_3 = {1,3,6}

What is the total number of cases choosing one element from each subsets?

Same element cannot picked from different subset, and the order is not considered.

For example,

S\_1 = {2}, S\_2 = {3}, S\_3 = {6}

and

S\_1 = {3}, S\_2 = {2}, S\_3 = {6}

considered as same. And

S\_1 = {3}, S\_2 = {3}, S\_3 = {1}

is invalid since S\_1 and S\_2 choose the same element.

How can I formulate this?

# Answer
> 1 votes
You can solve this problem with the inclusion exclusion principle.

Assume you have two subsets $S\_1, S\_2$, then the number of ways to choose two elements is the number of ways to choose a number from $S\_1$ multiplied by the number of ways of choosing an element from $S\_2$ minus the number of ways of choosing the same number from $S\_1$ and $S\_2$.

Now given three sets $S\_1, S\_2, S\_3$, the number of ways of choosing one element from each such that all elements are different is $$|S\_1||S\_2||S\_3| - |S\_1 \cap S\_2| |S\_3| - |S\_1 \cap S\_3||S-2| - |S\_2 \cap S\_3| |S\_1| + |S\_1 \cap S\_2 \cap S\_3|.$$

Now given a family of $k$ subsets, you can use the inclusion-exclusion principle to prove that the count can be given by the formula $$ \prod\limits\_{i \in \[k\]}|S\_i| + \sum\limits\_{I \subseteq \[k\], |I|\geq 2}(-1)^{|I|} \left|\bigcap\limits\_{i \in I}S\_i\right|\prod\limits\_{i \notin I}|S\_i| $$

---
Tags: algorithms, sets
---


# Question
Title: Conditions under which the 3-partition problem is not strongly NP-complete?
I'm a bit confused about the 3-partition problem. More specifically I'm confused about this from the Wikipedia article:

> Let B denote the (desired) sum of each subset Si, or equivalently, let the total sum of the numbers in S be m B. The 3-partition problem remains strongly NP-complete when every integer in S is strictly between B/4 and B/2.

Does this mean that if the multiset contains elements that fall outside the range B/4-B/2 the problem is no longer strongly NP-complete and admits heuristics or other optimizations? Am I interpreting that right?

Also am I correct in assuming that this problem (at least when it is strongly NP-complete) pretty much requires an exhaustive search (unless P=NP)?

I've sifted through some papers but haven't been able to figure this out.

# Answer
> 2 votes
No. Intuitively, the problem gets harder if we take out the restrictions on the input values, since the restricted instances are a subset of the instances of the general problem. However, the article says, even if you introduce this restriction the problem does not get easier and it is still strongly NP-complete.

On the other hand, exhaustive search is not always the best approach for hard problems. Parameterized algorithm introduce methods usually to restrict the area where the exhaustive search must happen. Randomized algorithm offer methods where a greedy algorithm or a heuristic looking among bounded number of solutions gives an optimal answer with some probability. repeating the method enough number of times yield an answer with high probability. So no it does not mean that an exponential exhaustive method on the whole input is the best we can do. It only means unless $P = NP$, no polynomial time deterministic non-randomized algorithm can be designed for this problem.

---
Tags: time-complexity, np-complete, combinatorics, partitions
---


title: Why Rice theorem work for decidability?

text:
# Question
Title: Why Rice theorem work for decidability?
Rice's theorem states:

> Every nontrivial property of recursively enumerable language is undecidable.

I came across following problems, which Ullman's books say both are undecidable:

> 1. Turing machine accepts nothing. (empty language)
> 2. Turing machine accepts something. (non empty language)

# Doubt

Consider we have given following TM (this I took from Mark's answer):

I want to decide whether the language of above TM is empty or non empty without actually running TM on any string, but "purely" by looking at TM description (consider above TM graph is input to below pseudo code in some encoded format. The encoded string contains information of everything: states, alphabet, allowed moves and transitions something like described in section 9.2.2 (page 63) of this pdf).

**Step 1:** Start from accept state and prepare breadth first tree (goal is to find all reachable nodes from accept state) rooted at accept state. It will look something like this:

```
         --> q4 --> R   --> q1
        /              /
A --> q3 ----------> q2 --> q0

```

Now I know start state is contained in this tree. So, I know there is path from start state `q0` to accept state `A`.

**Step 2:** Read labels of edges on path in any order, from `A` to `q0` or `q0` to `A` and come up with string that will be accepted by TM. Say we start from `A`.

* **`q3 --[b/b,R]--> A`**
We reach `A`, reading `b`. So last symbol of string will be `b` (denote it as `b1` as we will have more `b`'s in future).
Since this is acceptance state, ignore `R`.
* **`q2 --[b/b,R]--> q3`**
We reach q3, reading `b`. So second last symbol of string will be `b`. (denote it as `b2`). `R` means this second last symbol will be on left of last symbol: `b2b1`
* **`q0 --[b/b,L]--> q2`**
We reach q2, reading `b`. So third last symbol of string will be `b`. (denote it as `b3`). (Now lets assume algorithms do not allow moving to the left of first symbol of input string.) `L` and start state `q0` means dont do any movement of TM's read write head on tape. So, `b3=b2`.
* Reached start state. So print the string which will be accepted by TM. So the string accepted will be `b2b1`. Getting rid of symbol indices: `bb`
* Since TM accepts some string, its language is non empty.

**Step 3:** Try all paths between accept state `A` and start state `q0`, till we get at least one string accepted by given TM or till all paths are exhausted, in which case TM language will be empty.
We can run breadth first search to get all such paths.

I dont know if I am correct with above TM accepts string `bb`, with assumption that we cannot move left to left most symbol of input string. But. I feel, below is instantaneous description of parsing `bb` by this TM:

```
q0bb ⊢ q2bb ⊢ bq3b ⊢ bbA

```

Also I dont know if I am correct with above steps.

What I am trying to do is to come up with "generalized" steps which can be run on any TM description (not on tape content) to decide whether that TM accepts any string or not. This is because, if we can come up with such steps, then above two problems will turn decidable. I feel I am missing something in all these efforts which is preventing me from realizing why these languages cannot be turned decidable by any such reverse engineering efforts.

---

**Earlier doubt which is currently more refined / rephrased / reworded above, but kept below for reference:**

Consider we have given description of TM in encoded format. The encoded string contains information of everything: states, alphabet, allowed moves and transitions something like described in section 9.2.2 (page 63) of this pdf). Then cant we have a Turing Machine which will parse the code describing TM and decide whether it accepts anything or nothing. For example, find final state in the code and then go through all encoded transitions in reverse order starting from final state and check if we reach starting state. This can be done by forming MST rooted at final state. If MST contains starting state, then TM accepts something else it does not accept anything.

**Note** that I am talking about parsing TM description not tape content and since TM description (and number of transitions) is finite (correct me if TM description can be infinite) we can form MST in finite time.

I feel I am missing something stupid here, since if this proves its decidable whether TM accepts nothing or something, then I believe, it will be really a big thing in computer science (may be it will imply some problems previously believed to be undecidable to be decidable). What is that thing which I am missing?

# Answer
You said in a comment:

> I am talking to process this encoding, not the tape content.

But the tape content affects the behavior of the TM, including whether it would enter an accepting state. The exact same TM in the exact same state might later accept, or not accept, depending only on what is on the tape.

You want to "go through all encoded transitions in reverse order", but the behavior of the transition function depends on what is on the tape. You can't run the transition function, either forward or backward, without keeping track of what is on the tape. But you say you're not keeping track of that.

---

I am not able to convince you in the comments that you need to keep track of the tape, so perhaps you can convince yourself. Here are four Turing machines. Their tapes should initially contain sequences of `a` and `b` with only a finite number of `a`, because `b` represents blank.

In each machine, the initial state is $q\_0$, state $A$ is an accepting state, and all the other states are rejecting states. To help you, I will point out that the machines differ *only* in what they print on the tape in the transitions $q\_0\to q\_2$ and $q\_1\to q\_2$. They are otherwise identical.

Each of these machines will either accept every input, reject every input, or accept some inputs and reject some inputs. I will not tell you which is which, but I assure you that not all four machines are of the same type.

Your job is to use your static MST method to decide which is which, without considering the possible contents of the tapes.

Good luck.
> 4 votes

# Answer
Because this process doesn't necessarily end; you can end up discovering more and more possible configurations (state+tape) which would lead to accepting if they were ever reached, but never a legal initial configuration.
> 2 votes

---
Tags: formal-languages, turing-machines, formal-grammars, undecidability, rice-theorem
---


# Question
Title: Calculate the number of combinations of a sequence of numbers in a particular order
I have a problem solving coding challenge when I have to calculate the number of combinations, numbers from **0** to **9**, with the length **n**, with **2** rules -

**-** The first number cannot be **0**

**-** Every other number can be **0** or must be divisible by the previous number (number **1** can not be used as divisor), for example **\[5.0\], \[1,0\]** or **\[2,8\], \[4,8\], \[3,6\]**

For example, if the length **n** were **2**, number of combinations would be **23 - \[1,0\]...\[9,0\] + \[2,4\], \[2,6\], \[2,8\], \[3,6\], \[3,9\], \[4,8\] + \[2,2\]...\[9,9\]**

---

The resulting response can be code in some programming language or a formula to calculate answer

# Answer
> 0 votes
There is a neat way to solve this problem using graph theory.

First of all you need to decide the states and their transitions.

Example:-

```
2 ->[2,4,6,8]
3 ->[3,6,9] and so on.

```

Imagine each state to be a vertex in a graph and each transition to be a directed edge.

Now construct the adjacency matrix.

In your case it may look like:-

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

```

Note that over here the `1s` represent that you can transition from the current state to that state.

Thus, if the `5th` element of the `3rd` row is `1` it means that you can go from `2`to`4`.

Finding all permissible combinations of length `n` is equivalent to finding all the walks of length `n` in this graph.

`(Adjacency_Matrix)^n` results in a matrix of the same dimension where (i,j) denotes number of unique walks of length `n` between vertex i and j.

Since first element cannot be `0`, you can sum up the values of this matrix for all `(i,j)` where `i!=0`. This would be your answer.

Matrix Exponentiation takes O(d^3 log(n)) time. d-\> DImension of matrix(10).

The DP approach would take too much time for n\>10^4. Since this approach is `log(n)` it will perform better for large values of n.

# Answer
> 0 votes
Can you solve the problem for $n=1$?
Can you deduce the answer for $k+1$, if you know the answer for $k$?
(hint: you need an $n\times 10$ table, the $k$-th row devoted for problem size $k$, the columns for partial answers...)

ps: I think that the answer is $9+0+1+1+2+1+3+1+3+2=23$ for n=2 (and 125 for $n=3$)

```
0: 10,...,90
1: -
2: 22
3: 33
4: 24,44
5: 55
6: 26,36,66
7: 77
8: 28,48,88
9: 39,99

```

---
Tags: algorithms
---


# Question
Title: Is it common in the literature to define regular languages and serialization languages as programming languages?
Often when I create programs I use operating-programming language such as Bash for automating OS operations, structure ("markup") language such as HTML to define structures, styling language such as CSS to style structures, and programming (behavior defining) language such as JavaScript, to define the "nature of interaction" with programming by user interface.

But there are two other types of languages I sometimes use when creating programs:
Regular languages such as POSIX basic regular extensions or PERL compatible regular extensions, and Serialization languages such as JSON or YAML;
from my experience, it is reasonable to assume that the former type can be combined with generally all operating-programming languages and behavior defining languages, while the latter type I usually combined with JavaScript.

Is it common in the (Computer Science) literature to define regular languages and serialization languages as programming languages (as sharpening the behavior of a program)?

# Answer
> 2 votes
No. In formal language theory, a language is just a set of strings, and it has nothing to do with programming. Note also that the things that programming languages such as Perl call "regular expressions" are more powerful than the regular expressions used in computer science and can define some non-regular languages.

---
Tags: terminology
---


# Question
Title: Implement heap using stack data structure
I want to implement a heap using the stack data structure. I have searched a lot on the internet. But I do not get any clue how to implement it.

Can you please help me to implement a heap using the stack data structure? The pseudo-code is well enough. I can implement the rest.

# Answer
> 0 votes
The question is a bit vague on the meaning of "using the stack data structure" but I'm going to take an educated guess on a possible implementation. I'll also be assuming that we are interested in a min-heap, that the stack support the push, pop, and top operations, and that the min-heap should support the make-heap, push, pop, and top operations.

The data structure consists of single stack $S$ that will contain the elements of the heap.

**Make-heap$(A)$**: To build a heap from a set of elements $A$, sort $A$ in *nonincreasing* order and push the elements one by one into $S$ (according to their order). In this way the last element to be pushed into the stack will be one of the minimums of $A$. This requires $O(|A| \log |A|)$ time.

**Top**: Return the top element of $S$ (in $O(1)$ time).

**Pop**: Pop the top element $x$ from $S$ (in $O(1)$ time). Return $x$.

**Push$(x)$:** To push a new element $x$ into the min-heap proceed as follows: create a new temporary stack $T$; while the top element $y$ of $S$ is smaller than $x$, pop $y$ from $S$ and push it into $T$; Finally, push $x$ into $S$ and iteratively pop the elements from $T$ while pushing them into $S$. When $T$ is empty you are done. Sadly, this requires $O(|S|)$ time in the worst case.

---
Tags: algorithms, heaps, stacks
---


# Question
Title: Determining key from plaintext and ciphertext (Vigenère)
I was wondering why mathematically we can know the key in the Vigenère cipher if we know in advance a message and its encryption.

# Answer
> 1 votes
A Vigenère cypher on an alphabet of size $M$, which we identify with the integers modulo $M$, works as follows.

The key is an arbitrary word, $k\_0 \ldots k\_{\ell-1}$.

Given a plaintext $p\_0 \ldots p\_{n-1}$, the ciphertext $c\_0 \ldots c\_{n-1}$ is given by $$ c\_i = p\_i + k\_{i \bmod \ell} \bmod M. $$ For example, suppose that we are trying to encipher decimal digits, and use as key the word 2019. If we want to encrypt the plaintext 18446744073709551616, then we form the following table:

```
plain  18446744073709551616
key    20192019201920192019
cipher 38538753274629643625

```

(In this case $n$ was divisible by $\ell$, but that need not be the case.)

In this table, the key repeats enough times, and each digit of the cipher is just the sum of the digits above it, throwing away the carry (for example, from 4 and 9 we get 3 rather than 13).

To decipher a ciphertext $c\_0 \ldots c\_{n-1}$, we simply reverse the process: $$ p\_i = c\_i - k\_{i \bmod \ell} \bmod M. $$ In the table above, given the cipher and the key, we just need to subtract the key from the cipher, borrowing if necessary (so 3-9=4 since 13-9=4).

Similarly, given a plaintext/ciphertext pair, we can recover the key in the sense of constructing the sequence $$ k\_i = c\_i - p\_i \bmod M. $$ This recovers the key up to its length $\ell$, which need not be known in advance.

In the table above, given the ciphertext and the plaintext, we subtract the latter from the former to obtain

```
201920192019201920192019

```

Out of which we can guess that the key is 2019.

---
Tags: cryptography, encoding-scheme, encryption
---


# Question
Title: Intuition behind min cut in a flow network? Whether it's baseball elimination or project selection
I was wondering if someone can give me a general definition of a min-cut besides it being the max flow of a network.

For example, in the baseball elimination problem, if we wanted to find out if team z is eliminated, the min cut represents the team(s) that will beat team z out of the 1st place if the edges aren't full saturated. If the edges are fully saturated, then min-cut is everything except t, and team z still has a chance.

For the project selection, the min cut contains the projects you should do to maximize your return.

How do people figure out that min-cut can be applied to these problems? What is it about min-cut that gives it such power?

Thank you!

# Answer
Given a weighted directed graph and two nodes $s,t$, an $s$-$t$ cut is a set of edges, upon whose removal $t$ is not reachable from $s$. The weight of the cut is the total weight of edges removed. A minimum $s$-$t$ cut is one of minimum weight.

A similar definition works for undirected graphs and in the special case in which the graph is unweighted, in which all edges have unit weight.

If we think of a weighted digraph as a flow network with source $s$ and sink $t$, then any $s$-$t$ cut gives a restriction on the weight of any flow in the network, which must be at most the weight of the cut. The min cut max flow theorems states that the weight of a minimum $s$-$t$ cut coincides with the weight of the maximum flow. However, a cut and a flow are two very different things.

There's a related definition of cut which works just for undirected graphs. A cut in an undirected graph is a set of edges whose removal disconnects the graph. (Any $s$-$t$ cut is a cut.) A minimum cut is one of minimum total weight (or, in the unweighted case, of minimum cardinality).

One reason that cuts are so powerful is that they can be found efficiently.
> 2 votes

---
Tags: algorithms, graphs, network-flow
---


title: Equal partition up to one integer

text:
# Question
Title: Equal partition up to one integer
In the partition problem, the task is to partition $n$ given integers into two subsets $A$ and $B$ with equal sum. This problem is known to be NP-hard, but it becomes easy if the "equal sum" requirement is replaced with the following:

> The difference $|\sum\_A - \sum\_B|$ should be at most the largest integer in the set with the larger sum.

A solution always exists, and can be found using the following algorithm:

* Order the integers by descending value.
* Put the largest integer in subset A, the second in subset B, the third in subset A, etc.

The sum in subset A is always at least as large as the sum in subset B, but if we remove the largest integer from subset A, then the sum in subset B is at least as large as the remainder. Hence, the partition is equal up to one integer.

MY QUESTION IS: what happens when there are cardinality constraints on the subsets? Formally, the task is to partition $n$ given integers into two subsets $A$ and $B$ that have sizes $a$ and $b$, with $a+b = n$ and $a \le b$. The algorithm above does not work, and indeed an equal partition up-to-one-integer may not exist. What is an algorithm to decide whether such a partition exists?

# Answer
There is an $O(n \log n)$ algorithm for this problem.

To formalize, lets say that the task is to partition $n$ given integers into two partitions $A$ and $B$ that have sizes $a$ and $b$, with $a+b = n$ and $a \le b$. Denote the maximum integer with $M$ and the sums of integers in $A$ and $B$ with $\sum\_A$ and $\sum\_B$. The partitions should satisfy that $|\sum\_A - \sum\_B| \le M$.

Start by putting the $a$ largest integers into $A$ and the $b$ smallest to $B$. Now, if $\sum\_A \< \sum\_B - M$, there is no solution because we cannot make the sum of $A$ any larger. If $\sum\_B - M \le \sum\_A \le \sum\_B + M$, the partition $(A, B)$ is a solution and we are ready. The case that is left is $\sum\_B + M \< \sum\_A$. In this case, we can repeatedly choose the largest element of $A$ and the smallest element of $B$ and swap them. The difference $\sum\_A - \sum\_B$ changes by at most $2M$, so either we find a solution or maintain the invariant $\sum\_B + M \< \sum\_A$. At some point we must find a solution, because $a$ is smaller than $b$, and thus $\sum\_A$ will become smaller than $\sum\_B$ by repeating this operation. This can be implemented in $O(n \log n)$ with sorting and two pointers.
> 3 votes

# Answer
W.l.o.g. assume the integers are ordered such that $x\_1 \geq \cdots \geq x\_n$.

@Laakeri presented an algorithm for finding a partition $(A,B)$ that satisfies:

* $\sum\_B + x\_1 \geq \sum\_A \geq \sum\_B - x\_1$

His algorithm can be used to finding a partition that satisfies the stronger condition:

* $\sum\_B + \max\_{A} \geq \sum\_A \geq \sum\_B - \max\_{B}$

The idea is to run his algorithm once for each combination of $\max{A},\max{B}$. The number of such combinations is linear in $n$, so the run-time of the algorithm will be $O(n^2)$.

First, assume that $x\_1\in A$, so that $\max\_{A}=x\_1$. Now, $\max\_B = x\_k$ for some $k\in\\{2,\ldots, a+1\\}$ (since $x\_1,\ldots, x\_{k-1}$ are all in $A$). For each such $k$, we start with a partition in which $\sum\_A$ is maximized (subject to the constraints), and proceed towards a partition in which $\sum\_B$ is maximized (subject to the constraints). The goal is to find a partition that satisfies:

* $\sum\_B + x\_1 \geq \sum\_A \geq \sum\_B - x\_k$

If in the initial partition $\sum\_A \< \sum\_B - x\_k$, then no solution exists for this $k$. If $\sum\_B + x\_1 \geq \sum\_A \geq \sum\_B - x\_k$, we are done. If $\sum\_B + x\_1 \< \sum\_A$, then we start switching integers between A and B such that $\sum\_A$ decreases and $\sum\_B$ increases. Since the location of $x\_1,\ldots,x\_k$ is fixed, the switches involve only integers weakly smaller than $x\_k$. So at each step, the difference between the sums changes by at most $2 x\_k$. Since the "allowed range" for the difference has a size of $x\_1 + k\_x \geq 2 x\_k$, the switch either brings us into the allowed range, or keeps the invariant $\sum\_B + x\_1 \< \sum\_A$. If we arrive at the final partition and still have $\sum\_B + x\_1 \< \sum\_A$, then a solution does not exist for this $k$ and we can move to the next $k$.

The case that $x\_1\in B$ is handled analogously.
> 1 votes

---
Tags: algorithms, discrete-mathematics, partitions
---


# Question
Title: Decide whether an $n$-bit positive integer is composite
**Question:**

Given an $n$-bit positive integer. A decision problem is to decide whether it is composite. Is this problem in NP?

I know that for every composite number, a factor of the number is a certificate. Verification proceeds by dividing the number by the factor and checking if the reminder is zero. My question is whether the verification can be done in polynomial time of $n$? it seems that we need to use at most $2^n/2 = 2^{n-1}$ factors to test, does that mean we should use exponential time to verify?

# Answer
NP doesn’t look at how hard it is to find a certificate (in this case a factor), just at how hard it is to test a certificate that claims to prove the answer is “yes”.

So it doesn’t matter how hard it is to find a factor, just that given a factor of an n-bit number, you can easily verify that it is a factor in $O(n^2)$. Or a bit faster with more effort. So “is x composite” is quite obviously in NP.

The opposite, “is x a prime”, has been shown to be in NP, but that is absolutely not easy to show. Basically you have to show that for any n-bit prime p, there is a certificate that allows us to *verify* in polynomial time time that p is prime.
> 1 votes

# Answer
It's almost always the case that problem sizes are expressed as a function of the *length* of the input, so a number *n* would be taken to be $\log n$ in length. For example, your verification would be in poly time if it ran in $O(\log^k n)$ time for some integer $k$.
> 0 votes

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


title: Reductions from non decision problems

text:
# Question
Title: Reductions from non decision problems
I want to show a minimization problem $Y$ has no approximation factor of 1.36. To be more specific the problem $Y$ is the exemplar distance problem between two genomes. Could I reduce from the min vertex cover problem instead of the decision version of the vertex cover problem. The problem I am having with reducing from the decision version is that a vertex cover of size k maps to the $Y$ of size $ \leq ck$, where $c$ is a constant. A decision version for problem $Y$ for me makes no sense, as there will always be a brekpoint distance between two genomes. I tried to research on the internet but I always only find reductions from decision problems. Could we reduce from non-decision problems.

Also when doing reductions from the vertex cover problem. I can't assume the given instance $G,k$ is such that k is the size of the optimal vertex cover right? $k$ is just any size of a Vertex cover.

# Answer
> 2 votes
Yes. See the notion of an approximation-preserving reduction.

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


title: Time Complexity: Big-O

text:
# Question
Title: Time Complexity: Big-O
What is the time complexity of this loop?

```
k=1
for(j=0;j<=n;j+=k)
    k++;

```

Is it $O(n)$ as we are increasing $j$ linearly?

# Answer
Here are the values of $j$ at the end of each iteration: $$ 1,3,6,10,15,21,28,36,45,55,\ldots $$ More generally, after $t$ iterations, $j = 1 + \cdots + t = \binom{t+1}{2} = \Theta(t^2)$. Therefore the loop halts after $\Theta(\sqrt{n})$ iterations.
> 4 votes

---
Tags: time-complexity
---


# Question
Title: Removing recursion from a function with multiple params
I am given the following function as a brain teaser:

```
def t(x, y, z):
    if x <= z:
        return y
    else:
        return t(t(x  - 1 , y  , z ) , t(y  - 1 , z  , x ) , t (z  - 1 , x  , y ))

```

the task is to remove the recursion in the else-branch. the only allowed expressions are of type arithmetic (+,-,\*,/,%), logical (&&,||,!), relational (\<,\<=,==,\>=,\>,!=) and if-else.

My first approach was to order the input in lexicographical order and trying to deduce a relationship which seemed to look like like this initially:

```
else:
    if y > x
        return x
    else:
        return z

```

but that does not work, a counterexample is `t(20, 7, 18)=8`. So the underlying relationship seems to be a bit more complex. I have also tried to formally infer the solution by differentiating the cases for the '\>'-relation between the variables but I did not get far with that either.

# Answer
> 2 votes
Here is an equivalent way to calculate $t(x,y,z)$.

We distinguish between three cases:

1. $x \leq z$: the answer is $y$.
2. $x = z + 1$: the answer is $z$ if $y \leq x$, and $x$ otherwise.
3. $x-z \geq 2$: the answer is $z$ (if $x-z$ is odd) or $\min(y+1,z)$ (if $x-z$ is even) if $y \leq x+1$, and $x$ (if $y-x$ is even) or $z+1$ (if $y-x$ is odd) otherwise.

You should be able to prove this characterization by induction. The second case is identical to the third case, except that the condition $y \leq x$ is replaced by the condition $y \leq x+1$.

---
Tags: algorithms, recursion
---


# Question
Title: Compiler - Why is the grammar not suitable for shift-reduce
Consider this example:

```
stmt => if (expr) stmt | if (expr) stmt else stmt | other

```

Why can't we use shift-reduce on this?

This is a compiler homework and I really need to answer it.

# Answer
> 1 votes
The grammar is ambiguous, so no deterministic parsing technique will be able to handle it. The parsing techniques called "shift-reduce" are all deterministic.

# Answer
> 1 votes
Expanding on @vonbran's answer, here is why the grammar is mbiguous. Say you have a statement of the form

```
if (expr)  if (expr) stmt else stmt

```

, then the else can belong to either ifs.

---
Tags: compilers
---


# Question
Title: The space complexity of a function that allocates space based on the input value and not size
What is the space complexity of the following hyphotetical function:

```
void function(int n) {
  int[] array = new int[n]; // allocate array of size n
  return;
}

```

My intuition tells me that it is not O(n). Because the function will allocate an array of size n where n is the **value** of the input and not the size. The input size is constant because it is a single integer.

# Answer
> 2 votes
It is $O(n)$ and, more precisely, $\Theta(n)$. What might be confusing you is the fact that the length of the encoding of the parameter $n$ will only be $\Theta(\log n)$, meaning that the **value** of $n$ (and hence the space required by the function) is exponentially larger than the size of the input to `function` (i.e., the number of bits needed to represent $n$).

To summarize both the following statements are true:

* `function(n)` requires linear space w.r.t. **the value of** its parameter $n$, i.e., the asymptotic space complexity of `function(n)` is $O(n)$;
* `function(n)` requires an exponential amount of space w.r.t. the length of the encoding of its input.

---
Tags: complexity-theory, asymptotics, space-complexity, space-analysis
---


# Question
Title: Can I apply Rice's theorem to decide decidability status of these languages?
I came across these languages:

1. A Turing machine prints a specific letter.
2. A Turing machine computes the products of two numbers

I was guessing whether I can apply Rice's theorem to decide upon above are decidable or undecidable, something like this:

1. Not all turing machine languages have specific letter, hence the property is non trivial and hence undecidable.
2. Not all turing machine languages deal with performing product of two numbers, hence this property is non trivial and hence undecidable.

**Doubt 1**

Doubt is that, Rice theorem can be applied when we are talking about languages of Turing machines, not about Turing machine behavior or characteristics themselves or anything else which is not related to "only" languages they accept. I tried to interpret given problems as if they are talking about the languages accepted by those Turing machines, so that I can apply Rice's theorem to decide their decidability status. Am I correct with this?

**Doubt 2**

If we have specification of TM along with its transition functions, in some encoded format, cant we prepare an algorithm to parse that encoding and tell whether the TM ever prints specific letter? The encoding must contain a transition which prints desired letter. We then can define algorithm to check if transition is reachable from the start state. If yes, then TM prints desired letter, and hence decidable. But this contradicts with earlier answers that "whether TM prints a specific letter" is undecidable. What is correct here?

**Update**

After a lot of thinking, I feel we cant apply Rice's theorem here, since both problems put describe nature of output produced by TM, that is on content of tape after TM has processed original content of tape. But the language accepted by TM is content of tape, before TM starts processing. So both problems dont talk about language of TM and hence we cannot apply Rice's theorem to both problems. Am I correct with this?

# Answer
> 1 votes
> Rice theorem can be applied when we are talking about languages of Turing machines, not about Turing machine behavior or characteristics themselves or anything else which is not related to "only" languages they accept.

You are talking about a narrow Rice's theorem. In Wikipedia, it states that

> Rice's theorem can also be put in terms of functions: for any non-trivial property of partial functions, no general and effective method can decide whether an algorithm computes a partial function with that property.

So the 2nd language is indeed undecidable by Rice's theorem. For your first language, there are two interpretations:

1. A Turing machine that when it halts, the tape content is exactly a specific letter (say $s$). In this case, the Turing machine exactly computes a function $f$ where $f(w)=s$ for any $w$, so Rice's theorem applies.
2. A Turing machine **ever** prints a specific letter. In this case, Rice's theorem does not apply, while the language is still undecidable.

> We then can define algorithm to check if transition is reachable from the start state.

No, you can't. There being a path from the start state to the transition does not mean the transition is reachable. For example, consider the following Turing machine:

```
  Read a; Move right    Read a; Move left    Read a; Move right
S ------------------> A -----------------> B -----------------> C
       Write b                                    Write s

```

There is a path from the start state $S$ to the transition that writes $s$, but this transition is not reachable because the Turing machine writes a $b$ at the first position when switching from state $S$ to state $A$, so it will never read an $a$ at state $B$.

Hence, you have to check every path to verify if a specific transition is reachable, but that is impossible because there are infinite many paths (when cycles are involved).

# Answer
> 0 votes
You're right that both of these are non-trivial properties. The key is, Rice's theorem applies only to non-trivial *semantic* properties.

So what defines a semantic property?

Intuitively, a "semantic" property is a property of *what the machine does*, rather than *how the machine works*. If you treat the machine as a black box that takes input and gives output, with all the internal mechanisms hidden, semantic properties are the ones you can still measure.

Applying this rule of thumb, we see that printing letters and multiplying numbers are both semantic actions (they're things a program does rather than mechanisms by which the program does it), so yes, Rice's Theorem applies, and these properties are undecidable.

---
Tags: formal-languages, turing-machines, automata, undecidability
---


# Question
Title: Making a CFG for a^i b^j c^k such that i+k < 3j
I have the language $L = \\{ a^ib^jc^k \mid i + k \< 3j \\}$, however I am struggling to convert it to a CFG.

I have thought about solving this for a long time but but this still hasn't gotten me very far

Any help would be appreciated Thanks

# Answer
> 0 votes
$$ \begin{align\*} S \to & AbBC \mid AbBCc \mid AbBCcc \\; \mid \\ & aAbBC \mid aAbBCc \mid aAbbBCcc \\; \mid \\ & aaAbBC \mid aaAbbBCc \mid aaAbbBCcc \\ B \to & bB \mid \epsilon \\ A \to & aaaAb \mid \epsilon \\ C \to & bCccc \mid \epsilon \end{align\*} $$

The intuition is as follows:

The nonterminal $B$ encodes the fact that we can have any number (possibly 0) of extra occurrences of $b$s in addition to those strictly needed to satisfy $i+k \< 3j$.

For every $3$ occurences of a $a$s or $c$s we have to "pay" by adding one $b$ to our word. The nonterminal $A$ (resp. $C$) represents a triplet of $a$s (resp. $c$s) along with the occurrence of $b$ that is used to "pay" for the triplet.

Clearly, our word might have a number of $a$s (resp. $c$s) that is not a multiple of $3$, however there are only $9$ possible cases for the combinations of the remainders $i \bmod 3$ and $k \bmod 3$. These cases are explicitly handled in productions from the axiom $S$, in which we make sure to add at least $\left\lceil 1+\frac{(i \bmod 3) + (k \bmod 3)}{3} \right\rceil$ additional "b"s to "pay" for the $(i \bmod 3) + (k \bmod 3)$ extra characters (the $+1$ ensures that the "greater than" in the inequality $i+k \< 3j$ is satisfied).

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


# Question
Title: Asymptotics of $\frac{1}{\log(\frac{2^n}{2^n-1})}$
I am trying to understand the asymptotics of

\begin{equation} f(n) = \frac{1}{\log(\frac{2^n}{2^n-1})} \end{equation} In particular, is there some $c \geq 1$ such that $f(n) = O(n^c)$?

# Answer
> 5 votes
From this post, you can approximate $\log(1+x)$ with $x$ for little values of $x$. Hence,

$$ f(n) \sim \frac{1}{\frac{1}{2^n-1}} = 2^n-1 $$

Therefore, you can't find any constant $c$, such that $f(n) = O(n^c)$, as it is $\Theta(2^n)$.

---
Tags: asymptotics, big-o-notation
---


# Question
Title: Is this statement of P = NP in Agda correct?
Looking for a self-contained statement of P = NP in type theory, I stumbled upon this short Agda formalization (a cleaned up version is reproduced below).

The statement here does seem to express the problem correctly but I'm not entirely sure as the code is not well-commented. So my question is: is this an accurate statement of P = NP and if not how would one fix it?

open import Data.Nat                              using    (ℕ; suc; zero; _+_; _*_; _≤_; _^_)
open import Data.Bool                             using    (Bool; true; false; if_then_else_; _∨_)
open import Data.List                             using    (List; _∷_; []; length)
open import Data.Vec                              using    (Vec; _∷_; [])
open import Data.Product                          using    (Σ-syntax; _,_)
open import Data.Sum                              using    (_⊎_; inj₁; inj₂)
open import Data.Empty                            using    (⊥)
open import Relation.Binary.PropositionalEquality using    (_≡_; refl)

iterate : {A : Set} → ℕ → A → (A → A) → A
iterate zero    z s = z
iterate (suc n) z s = s (iterate n z s)

is-poly : (ℕ → ℕ) → Set
is-poly f = Σ[ m ∈ ℕ ] ((n : ℕ) → f n ≤ 2 ^ m)

is-inj₂ : {A B : Set} → A ⊎ B → Bool
is-inj₂ (inj₁  _) = false
is-inj₂ (inj₂ _) = true

data fn : ℕ → Set where
    fz : {n : ℕ} → fn (suc n)
    fs : {n : ℕ} → fn n → fn (suc n)

ref : {A : Set} {n : ℕ} → fn n → Vec A n → A
ref fz (a ∷ _) = a
ref (fs m) (_ ∷ rest) = ref m rest

subs : {A : Set} {n : ℕ} → fn n → A → Vec A n → Vec A n
subs fz a (_ ∷ rest) = a ∷ rest
subs (fs m) a (b ∷ rest) = b ∷ subs m a rest

replicate : {A : Set} → (n : ℕ) → A → Vec A n
replicate zero a = []
replicate (suc n) a = a ∷ replicate n a

data command (stacks : ℕ) (states : ℕ) : Set where
  push   : fn stacks → Bool → fn states → command stacks states
  pop    : fn stacks → fn states → fn states → fn states
         → command stacks states
  return : Bool → command stacks states

record machine : Set where
  field
    stacks : ℕ
    states : ℕ
    commands : Vec (command stacks states) states
    initial-command : fn states

command-mach : machine → Set
command-mach m = command (machine.stacks m) (machine.states m)

record state (m : machine) : Set where
  constructor mkState
  field
    stacks : Vec (List Bool) (machine.stacks m)
    current : fn (machine.states m)

step : (m : machine) → state m → (state m) ⊎ Bool
exec : {m : machine} → command-mach m → state m → (state m) ⊎ Bool

step m s = exec (ref (state.current s) (machine.commands m)) s
exec (return b) _ = inj₂ b
exec (push i b c) s =
  let
    prev-stack : List Bool
    prev-stack = ref i (state.stacks s)
  in
    inj₁ (mkState (subs i (b ∷ prev-stack) (state.stacks s)) c)

exec (pop i ct cf ce) s with ref i (state.stacks s)
... | []           = inj₁ (mkState (state.stacks s) ce)
... | true  ∷ rest = inj₁ (mkState (subs i rest (state.stacks s)) ct)
... | false ∷ rest = inj₁ (mkState (subs i rest (state.stacks s)) cf)

step-or-halted : (m : machine) → (state m) ⊎ Bool → (state m) ⊎ Bool
step-or-halted m (inj₂ b) = inj₂ b
step-or-halted m (inj₁ s) = step m s

nsteps : {m : machine} → ℕ → state m → (state m) ⊎ Bool
nsteps {m} n s = iterate n (inj₁ s) (step-or-halted m)

initial-state : (m : machine) → List Bool → state m
initial-state m l =
  mkState (replicate (machine.stacks m) l) (machine.initial-command m)

record poly-time-machine : Set where
  inductive
  field
    m : machine
    runtime : ℕ → ℕ
    poly : is-poly runtime
    is-runtime : (l : List Bool)
               → (is-inj₂ (nsteps (runtime (length l)) (initial-state m l))) ≡ true

get-inj₂ : {A B : Set} → (e : A ⊎ B) → is-inj₂ e ≡ true → B
get-inj₂ (inj₁ x) ()
get-inj₂ (inj₂ x) _ = x

run-poly-time-machine : poly-time-machine → List Bool → Bool
run-poly-time-machine m inp = get-inj₂ _ (poly-time-machine.is-runtime m inp)

np-machine : Set
np-machine = poly-time-machine

search : ℕ → poly-time-machine → List Bool → Bool
search zero    m inp = run-poly-time-machine m inp
search (suc n) m inp = search n m (false ∷ inp) ∨ search n m (true ∷ inp)

run-np-machine : np-machine → List Bool → Bool
run-np-machine m inp = search (length inp) m inp

P=NP : Set
P=NP =
  (m-np : np-machine) →
    Σ[ m-p ∈ poly-time-machine ]
      (((inp : List Bool) → run-poly-time-machine m-p inp ≡ run-np-machine m-np inp))
```

# Answer
The definition is not correct. It states that a machine is polynomial time (the field `poly` in `poly-time-machine`) when its running time is below the exponential function $n \mapsto 2^n$ (the definition `is-poly`). This would allow, for example, a running time $n \mapsto 1.5^n$, which isn not poly-time according to the accepted definition.
> 5 votes

---
Tags: complexity-theory, type-theory, p-vs-np, dependent-types, agda
---


# Question
Title: Is automata concept theorized in computer science and what would be a simple example?
I understand the terms *automata* or *automaton* to mean "self operating machine".

I can't think of any such "machine" besides maybe (if it is even a machine and even exits) **cyclic universe** of a big-bang--big-crunch phenomena;
either in sequence ("finite automata"), or in eternal occurrence ("infinite automata").

**Is automata concept theorized in computer science and what would be a simple example?**

# Answer
> 6 votes
In computer science, "automaton" refers to some kind of finite state machine. This is a basic and fundamental model of computation, and automata are widely used in implementing simple electronic devices and in writing parsers, e.g., for programming languages.

# Answer
> 5 votes
The automaton is mainly used as a simple model of computation to check input strings on some defined conditions by reading the string and giving out whether the string is accepted in a defined language or not.

There are a lot of examples. A really crucial for example in terms of computing are the RegEx-expressions, if you heard of that. There are some languages which can be checked, and for some of the languages you just can't find any automaton to check, whether an string is in this language or not (for example the language of unlimited correct balanced parentheses). Those that can be checked are the so called regular expressions.

A simple example would be a drinks machine, which is accepting inputs depending on the current state (coins, pressing buttons, ...).

---
Tags: automata, terminology
---


# Question
Title: Determine if an NFA accepts infinite language in polynomial time
**Question Statement**: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite. (Note that converting NFA to DFA is exponential time).

For any DFA, By pumping lemma, I am very sure that the following algorithm works:

```
T = Upon input <M> (a DFA)
  Accept if any state q in DFA has the property:
    1. There is a path from starting state to some final state through q
    2. There is a (directed) cycle that loops from q back to q.
  (Reject if neither property is satisfied)

```

I intend to prove that this algorithm can be directly applied to NFA. After all, if there is no loop in this NFA, then every accepted string is bounded by the number of states (by pumping lemma). Therefore to make sure the NFA accepts infinite language, a loop is necessary.

Is the thinking correct? Further, what would be the optimal algorithm to see if an NFA generates infinite language?

# Answer
Your algorithm is incorrect. Think about the minimal DFA for $ab^\*c$.

Related: Do self-loops in DFA cause infinite languages?, Do all DFA's containing an "accepting path containing a cycle" accept infinite languages?.
> 0 votes

---
Tags: time-complexity, regular-languages, finite-automata
---


# Question
Title: How to determine if a language is deterministic context-free language?
I have the following question to solve : DCFL means Deterministic Context-Free Language.

> Let $L$ be a DCFL over an alphabet $\Sigma$. For each of the following functions of $L$, determine whether $f(L)$ is a DCFL. Explain your answers.
>
> (a) $f\_1(L) = \\{u\in\Sigma^\*: ua\in L\text{ for some }a\in\Sigma\\}$ (that is, $f\_1(L)$ is the set of strings obtained by dropping the last symbol of strings in $L$.)
>
> (b) $f\_2(L) = \\{v\in\Sigma^\*: av\in L\text{ for some }a\in\Sigma\\}$ (that is, $f\_2(L)$ is the set of strings obtained by dropping the first symbol of strings in $L$.)

I tried to find a counterexample to the problem, however I didn't find anything. So I am thinking that it is deterministic. I am wondering how I should approach these kind of questions? and how to determine a language is deterministic?

# Answer
> 2 votes
Here $L$ is DCFL.

> (a) $f\_1(L) = \\{u\in\Sigma^\*: ua\in L\text{ for some }a\in\Sigma\\}$ (that is, $f\_1(L)$ is the set of strings obtained by dropping the last symbol of strings in $L$.)

Let's define homomorphism $h$ as follow:

$h(a) = a, \space a\in\Sigma$

$h(\epsilon)= c$

$L' = h^{-1}(L) \cap (\Sigma^\*c\Sigma), c\notin\Sigma$. (note that $L'$ is DCFL.)

Now start with DPDA of $L'$ and whenever you find $c$ in input make transition to final state.

---

> (b) $f\_2(L) = \\{v\in\Sigma^\*: av\in L\text{ for some }a\in\Sigma\\}$ (that is, $f\_2(L)$ is the set of strings obtained by dropping the first symbol of strings in $L$.)

Consider $L=\\{a^nb^{2n}\\} \cup \\{ca^nb^n\\}$ Now $f\_2(L) = \\{a^{n-1}b^{2n}\\} \cup \\{a^nb^n\\}$ Which is not DCFL.

---
Tags: context-free, nondeterminism
---


# Question
Title: In information theory, why is the entropy measured in units of bits?
In information theory, we have the quantity "information".

Suppose we have some discrete random variable $X$, that can take values $\\{{a,b,c\\}}$ with corresponding probability distribution $\\{{\frac{1}{2},\frac{1}{4},\frac{1}{4}\\}}$. Then, information, $h$, is measured as $h(x) = -\log\_{2}P(x)$.

So now we can say: $$h(a) = -\log\_2 \bigg(\frac{1}{2}\bigg) = 1 \text{ bit}$$ $$h(b) = -\log\_2 \bigg(\frac{1}{4}\bigg) = 2 \text{ bits}$$.

My question is, why does that computation result in a quantity measured in bits?

Explanations I've seen all say something along the lines of: "this quantity is measured in units of bits because of the log base 2" with no further explanation as to why. So why does taking the log (base 2) of a probability result in a quantity measured in units of bits?

Is it somehow related to the idea that if a system can be in $N$ states, then we can encode those $N$ states using $log\_2 N$ bits? E.g. if a system can be in 4 states, we can encode those 4 states in binary with $log\_2 4 = 2 \text{ bits}$: $00, 01, 10, 11$.

# Answer
> 3 votes
Here is a simple intuition. Suppose we consider a random value that takes the values 0 or 1 with equal probability. Then this value can be represented in a single bit. Moreover, its Shannon entropy is $1$. Therefore, it is natural to say that its entropy is 1 bit. More generally, consider a random value that is distributed uniformly on the set of $n$-bit strings. Then this can be represented in $n$ bits; and the Shannon entropy is $n$, so it is natural to say that its entropy is $n$ bits.

Yes, it's definitely related to the fact that if the system has $N$ different possible states, its state can be represented in $\lg N$ bits. If the state is uniformly distributed over these $N$ different possibilities, a little bit of calculation will show that its Shannon entropy is $\lg N$. So, it makes a lot of sense to call its entropy $\lg N$ bits.

# Answer
> 1 votes
The entropy of a random variable $X$ can be described in terms of prefix-free binary encodings. Let $T(X)$ be the minimal average codeword length of a binary prefix code for $X$, and let $X^{\otimes n}$ be the random variable corresponding to $n$ independent samples of $X$. Then $$ \lim\_{n\to\infty} \frac{T(X^{\otimes n})}{n}. $$

Shannon's source coding theorem allows a similar description. An *encoding scheme* for a variable $X$ over an alphabet $\Sigma$ is a pair of mappings $E\colon \Sigma^n \to \\{0,1\\}^{\ell(n)}$ and $D\colon \\{0,1\\}^{\ell(n)} \to \Sigma^n$. The entropy is the infimum of $H$ such that there are encoding schemes with $\ell(n) = Hn$ such that as $n\to\infty$, $$ \Pr\_{x \sim X^{\otimes n}}\[D(E(x))=x\] \to 1. $$ In words, there is an encoding at rate $H$ if we can encoded $n$-tuples of samples of $\Sigma$ using $Hn$ bits in such a way that most of the time, we can decode the original sample from its encoding.

Both of these characterizations show that when encoding a large number of samples of $X$, each sample of $X$ takes $H(X)$ bits to encode.

Another characterization is the *asymptotic equipartition* (AEP) theorem, which states that $X^{\otimes n}$ consists, up to some small error, of roughly $2^{nH(x)}$ points whose probability is roughly $2^{-nH(x)}$.

---
Tags: probability-theory, information-theory, entropy, decision-tree
---


# Question
Title: Why not to take the unary representation of numbers in numeric algorithms?
A pseudo-polynomial time algorithm is an algorithm that has polynomial running time on input value (magnitude) but exponential running time on input size(number of bits).

For example testing whether a number $n$ is prime or not, requires a loop through numbers from 2 to $n-1$ and check if $n$ *mod* $i$ is zero or not. If the *mod* takes O(1) time, the overall time complexity will be O(n).

But if we let $x$ to be the number of required bits to write the input then $x = \log n$ (binary) so $n = 2^x$ and the running time of the problem will be O($2^x$) which is exponential.

My question is, if we consider the unary representation of input $n$, then always $x=n$ and then pseudo-polynomial time will be equal to polynomial time complexity. So why we never do this?

Furtheremore since there is a pseudo-polynomial time algorithm for knapsack, by taking $x=n$, the knapsack will be polynomial as a result P=NP

# Answer
What this means is that *unary knapsack* is in P. It does not mean that *knapsack* (with binary-encoded numbers) is in P.

Knapsack is known to be NP-complete. If you showed that knapsack is in P, that would show that P = NP.

But you haven't shown that knapsack is in P. You've shown that unary knapsack is in P. However, unary knapsack is not known to be NP-complete (indeed, the standard suspicion is that it's most likely not NP-complete). Therefore, putting unary knapsack in P does not imply that P = NP.

---

So which problem should we care more about, knapsack or unary knapsack? If your motivation is based upon practical concerns, then the answer will depend on the size of the numbers you want to solve the knapsack problem for: if they're large, then you certainly care more about knapsack than unary knapsack. If your motivation is based upon theoretical concerns, then knapsack is arguably more interesting, because it allows us to get a deeper understanding -- it allows us to make the distinction between size vs magnitude -- whereas unary knapsack prevents us from making that distinction.

---

To answer the follow-up question about the dynamic programming algorithm for the knapsack problem:

Yes, the same dynamic programming algorithm *can* be applied to both knapsacks and to the unary knapsack. Its running time is polynomial in the magnitude of the numbers, but exponential (not polynomial) in the length of the numbers when encoded in binary. Thus, its running time *is* polynomial in the length of the input when the input is encoded in unary but is *not* polynomial in the length of the input when the input is encoded in binary. That's why we *do* consider this dynamic programming algorithm to be a polynomial-time algorithm for unary knapsack, but *don't* consider it to be a polynomial-time algorithm for (binary-encoded) knapsack.

Recall that we say an algorithm runs in polynomial time if its running time is at most some polynomial of *the length of the input, in bits*.
> 18 votes

# Answer
I would add one small thing to D.W.'s answer:

I have seen people who think that because unary Knapsack is in P therefore we can use it in place of Knapsack which best current algorithms have exponential time.

Let the input be $W=\\{w\_1, \ldots, w\_n\\}$ and $k$ and consider the dynamic programming algorithm for Knapsack and unary Knapsack. The running time for both of them are $O(nk)$. It is the same running time. I.e. if you have an input it will not matter if you use the dynamic programming for unary Knapsack or dynamic programming for Knapsack. Both of them will take (roughly) the same amount of time to solve the problem instance. Theoretically anywhere you use one you can use the other as well. You just need to convert numbers from unary to binary and vice versa.

So what is the point of defining complexity of algorithms w.r.t. to the size of the inputs? Why not always state them in terms of the parameters as $O(nk)$?

If you care about a problem in isolation you can do so. Actually that is what people in algorithms often do. The complexity of graph algorithms are often express in terms of the number vertices and the number of edges, not the size of the string that codes them.

But this is only when we are dealing with an isolated problem. It is not useful when we are dealing with problems with different kinds of inputs. For graphs we can talk about running time w.r.t. to number of vertices and edges. For Knapsack we can talk about the number of items and the size of the Knapsack. But what if we want to talk about both? E.g. when we want to reductions between problems, or discuss class of problems which includes arbitrary problems, not just those with a graph as input. We need a universal parameter of inputs. An input in general is just a string, it is us who interpret its symbols as unary numbers, binary numbers, graphs, etc. To develop a general theory of complexity of algorithm and problems we need a general parameter of inputs. The size of the input is an obvious choice and it turns out to be robust enough that we can build a reasonable theory on top of it. It is not the only possibility. For an artificial one we can build a theory based on $2$ to the size of the input. It will work fine.

Now we decide to use size as our universal parameter of inputs it enforces us to think about the encoding of objects in terms of strings. There are various way to encode them and they can different sizes. (They also make different things easy/hard.) In terms of a general theory of algorithms, whether we encode the input number in unary or binary becomes important. If we are using unary and the size of $k$ is $100$ the largest number we will get is $100$. If we are using binary $k$ can be as large as $2^{100}-1$. So when we are talking about the running time of solving Knapsack problems where the size of $k$ is 100 we get two very different situation: In one case we care about only inputs where $k$ is at most 100. In the other we care about inputs that can be as large as $2^{100}-1$.

Let's say I want to see if I can reduce SAT to Knapsack in polynomial time. Let's say the input formula for SAT has size $n$. Then I will be able to build only an input for Knapsack which has size polynomial in $n$. Let's say $p(n)$ is the size of the input for Knapsack that I build. If I use unary I can only put $k$ to be at most $p(n)$. If I use binary I can put $k$ to be as large as $2^{p(n)}-1$. It turns out I need to put $k$ quite large to be able to reduce SAT to Knapsack. So unary Knapsack will not work for reducing SAT to it. Binary Knapsack would however work. We will be able to create a Knapsack instance with much larger $k$ if we use binary.

Another way to think about this: Assume that you have a black box that solves unary Knapsack and another one which solves Knapsack. Assume that you have time to write an $n$ bit input for the black box. Which one of the black boxes is more powerful? Obviously the one which uses binary encoding. We can use it to solve Knapsack problems which have exponentially larger $k$ compare to problems that the unary Knapsack black box can solve.
> 6 votes

# Answer
In short and simple, I will show you why.

Suppose, you have a factorization algorithm. Except for the small difference that one accepts integers for input and the other $Tally$. As you can see both code snippets are similar.

```
x = input integer

factors = [];

for i in range(1, x + 1):
    if x % i == 0:
     factors.append(i)

 print(factors)

```

Notice that the above algorithm is polynomial of the numeric value of $x$. It will take $x$ amount of steps in the loop. But when it comes to bit-size its actually $O(2^n)$.

Suppose, I make a small edit to the code that will take in $Tally/Unary$. It will now be $O(n)$ time in both value and length of the input $x$.

```
x = input tallies

factors = [];

for i in range(1, x + 1):
    if x % i == 0:
     factors.append(i)

 print(factors)

```

The input representation does not make the code run faster. Even though the 2nd algorithm is truly poly-time. Its not very practical in finding the factors for RSA.
> 2 votes

---
Tags: complexity-theory, algorithm-analysis, time-complexity, polynomial-time, pseudo-polynomial
---


# Question
Title: What is the name of the variant of ICP where the correspondence of the points are known?
Traditional ICP assumes that the inputs are point clouds with no predefined correspondences between the clouds.

If I know before hand that some / all points in one point cloud corresponds to some / all points in the other point cloud, I assume this becomes an easier problem to solve.

What is the name of this modified version of point set registration and what are some algorithms that solves this?

# Answer
> 1 votes
This problem is called "rigid registration", the correspondences being the "rigid" part.

As D.W. pointed out, you can do a least squares fit (or use something like RANSAC to find the correspondences and then do a least squares fit). In the absence of noise, the least squares fit has a particularly nice formulation which has been known for a long time.

If $\mathbf{x}\_i$ and $\mathbf{y}\_i$ are the two corresponding sets of coordinates (there are $n$ points), we want to find the rotation matrix $R$ and translation vector $\mathbf{t}$ which minimises:

$$\hbox{arg min} \frac{1}{n}\sum\_i \left\Vert \mathbf{y}\_i - R \mathbf{x}\_i - \mathbf{t}\right\Vert^2 $$

Calculate the covariance matrix:

$$\mathbf{\mu}\_x = \frac{1}{n} \sum\_i \mathbf{x}\_i$$ $$\mathbf{\mu}\_y = \frac{1}{n} \sum\_i \mathbf{y}\_i$$ $$\Sigma\_{xy} = \frac{1}{n} \sum\_i (\mathbf{y}\_i - \mathbf{\mu}\_y) (\mathbf{x}\_i - \mathbf{\mu}\_x)^\intercal$$

Compute the singular value decomposition of the covariance matrix:

$$\Sigma\_{xy} = U S V^\intercal$$

Then:

$$R = V U^\intercal$$

This algorithm can be made more robust in the presence of noise. There are also more recent algorithms which are competitive.

# Answer
> 0 votes
If you have know the correspondence between all points, the problem becomes much easier. You can find a homography using least squares, or a robust version such as RANSAC. See, e.g., https://stackoverflow.com/q/10441104/781723, https://math.stackexchange.com/q/494238/14578.

If you know the correspondence for some points, you could derive a homography using just those points. Or, you could modify an existing algorithm that assumes no correspondence to hard-code in that correspondence. Usually existing algorithms first try to find a few candidate correspondences, then estimate a homography for each, then take the best. When inferring a candidate correspondence, you can just force the known points to correspond to each other and infer only the rest.

---
Tags: algorithms
---


title: What is a symbol code?

text:
# Question
Title: What is a symbol code?
I am a physicist learning a bit of information theory.

I have encountered a term ("symbol codes") on Wikipedia, and cannot find what it means:

> **Source coding theorem for symbol codes**
>
> Let $\Sigma\_1,\Sigma\_2$ denote two finite alphabets and let $\Sigma\_1^\*$ and $\Sigma\_2^\*$ denote the set of all finite words over those alphabets (respectively).
>
> Suppose that $X$ is a random variable taking values in $\Sigma\_1$, and let $f$ be a uniquely decodable code from $\Sigma\_1^\*$ to $\Sigma\_2^\*$, where $|\Sigma\_2| = a$. Let $S$ denote the random variable given by the length of the codeword $f(X)$.
>
> If $f$ is optimal in the sense that it has the minimal expected word length for $X$, then (Shannon 1948): $$ \frac{H(X)}{\log\_2 a} \leq \mathbb{E}\[S\] \< \frac{H(X)}{\log\_2 a} + 1, $$ where $\mathbb{E}$ denotes the expected value operator.

Please let me know what does *symbol code* mean.

# Answer
> 2 votes
"Symbol Codes" means codes that work over a (finite) alphabet with an arbitrary size. Many times people focus only on binary codes, and Shannon Thm says that the minimal code length of some random variable $X$ is between $H(X)$ and $H(X)+1$ **bits**.

But what if, instead of bits, you use trits, or symbols from a larger alphabet of size, say, $a$? Then, the length of $X$'s coding needs to be adjusted since every symbol of the codeword now "contains" $\log\_2 a$ bits. Then, the wikipedia page says, the minimal code length will be between $H(x)/\log\_2(a)$ and $H(x)/\log\_2(a)+1$ **symbols**.

Multiply the equation by $\log\_2 a$ to convert into information bits: the codeword will have $S$ symbols, hence $S\log\_2 a$ bits, and this amount, by Shannon's coding theorem, can be minimized so that it is almost $H(X)$ (maybe up to one additional symbol, i.e., additional $\log\_2 a$ bits).

# Answer
> 1 votes
I hadn't heard that term before, but from context, I believe it is talking about codes over a finite alphabet (i.e., discrete random variables as opposed to continuous random variables).

---
Tags: information-theory, coding-theory
---


# Question
Title: Interactive proof system for graph nonisomorphism
> $\mathit{GNI} \in \mathrm{PCP}(\mathit{poly}(n),1)$
>
> *GNI* is the language of nonisomorphic graphs. Given two grapsh $G\_0$ and $G\_1$ with $n$ vertices, a verifier expects $\pi$ to contain, for each labeled graph $H$ with $n$ vertices, a bit $\pi\[H\] \in \\{0,1\\}$ corresponding to whether $H \equiv G\_0$ or $H \equiv G\_1$ (arbitrary if neither case holds). Then the verifier can pick a random bit $b \in \\{0,1\\}$ and a random permutation of $G\_b$, $H$. The verifier accepts iff the corresponding bit of $\pi\[H\]$ is $b$. If $G\_0 \not\equiv G\_1$ then the verifier accepts with probability $1$ while if $G\_0 \equiv G\_1$, then the probability of accepting is at most $1/2$.

I was reading this slide and got confused about the following part:

> A bit $\pi\[H\]\in\\{0,1\\}$ corresponding to whether $H=G\_0$ or $H=G\_1$ (arbitrary if neither case holds)

But what if both cases hold? In that case, $G\_0$ and $G\_1$ are isomorphic, and how should we assign the bit? I hope that there's an example.

# Answer
> 4 votes
The slide describes a proof system for graph *non*-isomorphism. This is a way for the prover to convince the verifier that the two graphs are non-isormorphic. The soundness of this proof system derives from the fact that it *cannot* work if the graphs are isomorphic. If $G\_0 \equiv G\_1$ then no matter what the prover does, the acceptance probability is only $1/2$.

*How should we assign the bit?* Proof systems don't work in this way. A proof system has two guarantees:

* Completeness: if the input belongs to the language (in this case, the two graphs are not isomorphic), then there is a proof that convinces the verifier.
* Soundness: if the input doesn't belong to the language (in this case, the two graphs are isomorphic), then no proof convinces the verifier.

When proving these two properties of the proof system, we specify a proof only in the first case. In the second case we have to show, instead, that *no* proof works. It's a different quantifier:

* Completeness: if $G\_0 \not\equiv G\_1$ then there *exists* a proof which convinces the verifier with probability 1. (When proving completeness, we need to specify the proof that convinces the verifier.)
* Soundness: if $G\_0 \equiv G\_1$ then *all* proofs convince the verifier with probability 1/2. (When proving soundness, we don't need to specify a proof. Indeed, we need to show that *all* proofs perform badly. In a sense, a proof is given to us, and we have to show that it doesn't convince the verifier.)

---
Tags: complexity-theory, interactive-proof-systems
---


title: variable in turing machine

text:
# Question
Title: variable in turing machine
Here is a simple turing machine, that accepts only $0$.

For this, it read $0$, write it with $x$, then move to right and checks end, if it is end it accepts.

With that logic, I can also add this `1->x,R`, then it accepts all strings of length 1, {'0','1'}.

What I want to do is, instead of writing to logic I want to write one, `$anything$ -> $another_thing$,R`.

Can I do it?

# Answer
A Turing machine diagram is a form of communication. Its goal is to describe a Turing machine — usually defined as a tuple with a specific format — in a form which is easier to grasp. As such, you can use whatever shortcut you want, as long as everybody understands what you mean. This might entail your explaining some non-standard notation which you invented as shorthand.

Your professor might have different ideas about this, but the answer I gave is valid for the working mathematician.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: Do all programming languages adhere to the IEEE 754-2008 standard?
I am well aware that the `float` data type's maximum value is approximately `1.8E308`, which means that across the various programming languages such as dearly beloved Java, the maximum factorial we can compute with this primitive data type is that of 170. Trying to compute the factorial of 171 and beyond gives errors. Here, PHP behaves the same way. In one of the answers from here, JavaScript also poses problems with factorials greater than 170. I understand that all this happens because that is what the de facto standard defines. My question is, are there non-esoteric programming languages that don't adhere to the IEEE 754-2008 standard? If there are, it would be interesting to see how they deal with factorials.

# Answer
For example, C and C++ don’t adhere to it. They don’t define the details of floating point arithmetic. An implementation *may* adhere to that standard, and there is a standard way to inform the user about it.

I used one compiler with ieee compliant 32 and 64 bit floating point, and totally non-compliant 128 bit fp with roughly 105 bit mantissa.
> 1 votes

---
Tags: floating-point
---


title: Wrong proof about maximum matching

text:
# Question
Title: Wrong proof about maximum matching
Given a bipartite graph $G=(U,V,E)$, find a maximum matching.

Algorithm G:

* Let $S\gets\emptyset$
* Mark all edges unmatched
* For $i\gets1$ to $|E|$
    + If $i$ is unmatched
        - $S\gets S\cup\\{i\\}$
    + End If
* End For

**Proposition:** Algorithm G is optimal.

**Proof:** Feasibility is easy by induction. We prove that $|S|$ is maximum. By contradiction. Assume that there exists a set $S'$ of edges that has more edges than $S$. Since $S$ is maximal, then no edge could have been added to it without violating its feasibility. Thus, $|S|$ cannot be increased. Since $|S'|\>|S|$, we reach a contradiction.

This is, of course, wrong, but I cannot find the error?

# Answer
Consider the path graph of length 3: $x-y-z-w$.

Take $S$ to be $y-z$, and $S'$ to be $x-y,z-w$.

---

A set of constraints for which your kind of argument does work is known as a *matroid*. The greedy algorithm that you describe does work for matroids (and, more generally, for *greedoids*). Your set of constraints satisfies a weaker condition: it is *2-extendible*, meaning that in order to add a new element (in this case, an edge), you need to throw out at most two existing elements. The greedy algorithm always gives a 2-approximation for such systems of constraints.
> 2 votes

# Answer
There is a difference between a maximal matching and a maximum matching. A maximal matching is a matching that is not a proper subset of any other matching. Hence, it is not possible to add another edge to a maximal matching (we can say a maximal matching can't be augmented). A maximum matching is a matching of maximal cardinality. Every maximum matching is also a maximal matching, but the converse is not necessarily true. Your statement "$|S|$ cannot be increased" is not true. There can exist other matchings having larger size, and the correct version would be that "$S$ cannot be augmented".

For example, let $G = (V,E)$ be a bipartite graph with bipartition $V=X \cup Y$, vertex sets $X = \\{x\_1,x\_2\\}, Y = \\{y\_1,y\_2\\}$ and edge set $\\{x\_1 y\_1, x\_1 y\_2, x\_2 y\_1\\}$. A greedy algorithm that first chooses $S = \\{x\_1 y\_1\\}$ cannot augment $S$ because it is maximal. However, there exists another matching $S' = \\{x\_1 y\_2, x\_2 y\_1\\}$ which has a larger cardinality than $S$.

Note that if both the subsets $S$ and $S'$ are maximal and $|S'| \> |S|$ (or just $S \ne S'$), then $S$ is not a subset of $S'$, and each subset contains an element not in the other subset.
> 1 votes

---
Tags: algorithms
---


# Question
Title: $L_1 ∩ L_2$ is not regular while $L_1$ is regular and $L_2$ is not regular language
Could you give me an example of languages $L\_1$ (regular) and $L\_2$ (not regular) where $L\_1 \cap L\_2$ is not regular?

# Answer
> 2 votes
Take $L\_2$ to be any nonregular language, say $\\{0^n 1^n: n \ge 1\\}$ and let $L\_1 = (0+1)^\*$ be the set of all strings over the alphabet $\\{0,1\\}$. Then $L\_2$ is a subset of $L\_1$, and their intersection is $L\_2$, which is nonregular.

# Answer
> 1 votes
Suppose $\Sigma = \\{a\\}$. A straighforward example is $L\_1= a^\*$, $L\_2 = \\{a^p| \text{p is prime}\\}$. So, $L\_2 \cap L\_1 = L\_2$ and it is not regular.

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


# Question
Title: Prove or disprove - graph doesn't exists
So, we have a directed graph G whose basis graph is connective. I was asked to prove or disprove If its possible that for every DFS run on G, the output will be two trees containing all G vertices . The only thing I could think of Is that graph like this cannon have a root (otherwise we could use DFS on the root and the output will be just one tree containing all G vertices).

Any Ideas?

thanks.

# Answer
If the question is - "Does there exists a directed graph $G=(V,E)$ (whose undirected version is connected) such that each DFS run on $G$ (preferably with different choices of root) always return exactly two trees?", then the answer is No.

Compress all SCCs into supernode, and let $G^\*=(V^\*, E^\*)$ be resulting graph with $V^\*=\\{S\_1,S\_2,\ldots, S\_k\\}$. Each SCC ($S\_i$'s) must have either an incoming edge or an outgoing edge. Now,

* At least one SCC must have a zero incoming edge (say it is $S\_1$).
* At least one SCC must have a zero outgoing edge (say it is $S\_k$).

If you take a root in SCC $S\_k$ as compared to $S\_1$, then DFS will give one more tree for sure.
> 1 votes

# Answer
Consider a digraph with vertex set $\\{a,b,c,d\\}$ and arc set $\\{ad, bd, cd\\}$. The underlying undirected graph is connected (it's a star with vertex $d$ as its center). Running DFS on the digraph gives at least three edge-disjoint trees.
> 1 votes

---
Tags: graphs
---


title: Oracle separation P and BPP

text:
# Question
Title: Oracle separation P and BPP
I'm reading (with much pleasure) the book Quantum Computing Since Democritus by Scott Aaronson. At some point the author claims that, while most most people believe that $\mathbf{P} = \mathbf{BPP}$ in real life, it is very easy to construct an oracle $O$ such that $\mathbf{P}^O \neq \mathbf{BPP}^O$. Frankly I don't find this easy at all. Even more so I find it implausible sounding. I will explain my reasoning here.

My understanding from earlier parts of the book is that the *reason* people believe that $\mathbf{P} = \mathbf{BPP}$ is that we believe in the existence of good pseudo-random generators (i.e. deterministic processes that generate random looking strings) and even have some plausible looking candidate pseudo-random generators. Now whenever we want to run a $\mathbf{BPP}$ algorithm on a $\mathbf{P}$-machine we just run the algorithm as written, but replace every random bit the $\mathbf{BPP}$-machine would use by a pseudo-random bit generated by our pseudo-random generator.

You can see my problem now: we can just apply the same strategy in presence of the oracle. Whenever the $\mathbf{BPP}^O$-algorithm makes an 'ordinary' deterministic step we do the same thing in our $\mathbf{P}^O$ algorithm. Whenever the $\mathbf{BPP}^O$-algorithm queries the oracle, we query the same oracle in our $\mathbf{P}^O$ algorithm and whenever the $\mathbf{BPP}^O$-algorithm uses a random bit we use a bit from our pseudo-randomgenarator. What could go wrong, short of the oracle magically coming to life, taking physical form and smashing our pseudo-random generator with an axe? So my question is:

> What is an example of an oracle $O$ such that $\mathbf{BPP}^O \neq \mathbf{P}^O$ and what problem is in the former but not the latter class?

**Update:** while typing a link to the following question showed up that is essentially asking the same: Existence of suitable pseudo-random number generators to derandomize BPP to P

However I don't see how the accepted answer answers my question. It seems to say that there are oracles that can distinguish the output of a *given* pseudo-random-generator from actually random data but

a) I can't think of a problem where having access to truly random data would give an advantage over having access to only outputs of $G$ to solve it and

b) What if the $\mathbf{P}$-machine fools the oracle by using a PRG *other* than $G$?

# Answer
I'm not sure what's the simplest way, but you can use diagonalization. We will construct an oracle for the following problem: $$ L = \\{ x : O(y) = 0 \text{ for all } |y|=|x| \\}, $$ where $O$ is some oracle that we construct by diagonalization. The same oracle will also be used to solve $L$ in randomized polynomial time, but we will ensure that it doesn't suffice to solve $L$ in deterministic polynomial time.

Let $M\_i$ be an enumeration of timed oracle Turing machines running in polytime (that is, $M\_i$ runs some other machine $M'\_i$ for $p\_i$ time steps, where $M'\_j,p\_k$ go over all oracle machines and polynomials).

We construct $O$ in stages. Initially, $O$ is empty (none of its values are decided).

In stage $i$, we handle $M\_i$. We pick some length $n$ on which $O$ is completely empty, and furthermore the running time of $M\_i$ on $0^n$ is at most $2^{n-1}$ (this will hold for all large enough $n$), and run $M\_i$ on $0^n$. Whenever $M\_i$ queries an undecided value of $O$, we set the value to $0$. If the machine $M\_i$ says that $0^n \notin L$, then we set all other values of $O$ of length $n$ to $0$. If it says that $0^n \in L$, then we set the other values of $O$ of length $n$ so that exactly half of them are $0$ and half of them are $1$.

Finally, we set all undecided value of $O$ (after going through the entire enumeration) to $0$.

Our construction guarantees the following properties:

* $M\_i^O$ fails to compute $L$. Consequently, $L \notin \mathsf{P}^O$.
* For each length $n$, if we choose a random $y$ of length $n$ then $\Pr\[O(y) = 0\] \in \\{1/2,1\\}$. This gives a trivial random sampling algorithm for $L$, showing that $L \in \mathsf{BPP}^O$. (In fact, the algorithm has *one-sided* error, so $L \in \mathsf{RP}^O$.)
> 3 votes

---
Tags: complexity-theory, oracle-machines, pseudo-random-generators
---


title: NP-hard problems but only for n≥3

text:
# Question
Title: NP-hard problems but only for n≥3
* 2-SAT is in P; 3-SAT is NP-complete.
* Exact cover by 2-sets is in P; exact cover by 3-sets is NP-complete
* Two-dimensional matching is in P; three-dimensional matching is NP-complete
* Graph 2-coloring is trivially in P; graph 3-coloring is NP-complete

Are there other well-known or important examples that are similar, in that there is a family of problems with a natural parameter $n$, where the problem is known to be in P when $n\<3$ and known to be NP-hard when $n≥3$?

# Answer
In graph coloring you are looking for a partitioning of the vertex set into independent sets. Now, there are many arguably well-known similarly behaving (i.e., easy for $k=2$, hard for $k \geq 3$) problems where instead you want to find a partition into $k$ sets which could be (i) independent dominating, (ii) dominating, (iii) total nearly perfect, (iv) weakly perfect dominating, or (v) total perfect dominating, to name a few. Many of these problems also appear under different shorter names like "domatic number", "total domatic number", and so on. For more details, see e.g., the work of Heggernes and Telle \[1, Table 1\] (there's quite a bit of follow-up work as well).

Also, graph coloring is naturally linked to the classical and heavily-studied chromatic index (i.e., edge coloring) via the line graph. Further, deciding if a $k$-regular graph can be edge $k$-colored properly is NPC for every $k \geq 3$.

---

\[1\] Heggernes, Pinar, and Jan Arne Telle. "Partitioning graphs into generalized dominating sets." Nord. J. Comput. 5.2 (1998): 128-142.
> 5 votes

# Answer
There are many problems like this listed in Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael Garey and David S. Johnson. For instance,

* \[ND14\] Graph Partitioning: NP-hard for $K\geq3$ and in P for $K=2$.
* \[SP3\] Set Packing: NP- hard even for all $c\in C$ with $|c|\leq 3$ but in P if for all $c\in C$ have $|c|\leq 2$.
* \[SP4\] Set Splitting and \[SP5\] Minimum Cover: same constraints as in \[SP3\].

You can see the cited textbook for a much longer list of problems.
> 5 votes

# Answer
One more example is $k$-partitioning problem, where given a set $A$ of $n$ numbers where $n$ is a multiple of $k$, the goal is to find a partition of $A$ into $k$-tuples, such that the numbers in each tuple sum up to zero.

More specifically, given a set $A$ of $m \cdot k$ elements. The goal is to partition $A$ into $m$ tuples $(a\_{i1}, \dots a\_{ik})$ for $i \in \[m\]$ each of size $k$, such that the sum of the numbers in each tuple $a\_{i1} + a\_{i2} \dots + a\_{ik}$ is equal to zero.

The problem is hard for $k \geq 3$. However, for $k = 2$ the problem turns to find if for each value $x \in A$, whether $-x$ is also in $A$ which is doable in linear/almost-linear time. You can also define the problem on multisets and hence the positive-instance condition in case of $k = 2$ turns into $\\#\_A(x) = \\#\_A(-x)$ for all $x \in A$.

**Note** This problem differs from the set partitioning problem, where we are given a set $A$ and the goal is to find a partition of $A$ into $A\_1$ and $A\_2$ such that $\sum\_{x \in A\_1} x = \sum\_{y \in A\_2}y.$

The set partitioning problem admits a psudo-polynomial algorithm and hence is weakly NP-hard meanwhile $k$-partitioning for $k \geq 3$ is a strongly NP-hard problem. Assuming $P \neq NP$, strongly NP-hard problem are strictly harder than weakly NP-hard problem. (For instance, a pseudo polynomial algorithm for the 3-partitioning problem implies a polynomial time algorithm for the 3d-Matching problem which is an NP-hard problem).

**Side note.** The parameter $n$ is usually used to represent the size of the input. In Graphs it is used as the number of vertices and in sets as the number of elements. Try to avoid using $n$ to name other parameters since that might create confusion. Usually $k$ and $r$ are used for other parameters. Quite often in parameterized complexity $k$ is used as the parameter representing the size of the output (In the running time of output sensitive algorithms). For example, the independence number in the maximum independent set problem and the minimum feedback vertex number in the feedback vertex set problem.
> 4 votes

# Answer
Let $d\_1,\ldots,d\_n\geq 2$ be positive integers and let $T \in \Bbb R^{d\_1\times \ldots \times d\_n}$ be a tensor (hypermatrix) of order $n$.

---

**SVD:** The singular value decomposition (understood as canonical polyadic decomposition for $n\geq 3$) is NP-hard for $n\geq 3$ (see \[1\]). Similarly computing the **rank** of $T$ over any finite field is NP-complete, and it is NP-hard over the reals.

---

**The spectral norm** of $T$ is the quantity: $$\\|T\\| = \sup\_{x\_1\in\Bbb R^{d\_1}\setminus\\{0\\},\ldots,x\_n\in\Bbb R^{d\_n}\setminus\\{0\\}} \frac{\sum\_{j\_1=1}^{d\_1}\cdots \sum\_{j\_n=1}^{d\_n}T\_{j\_1,\ldots,j\_n}x\_{1,j\_1}\cdots x\_{n,j\_n}}{\\|x\_1\\|\_2\cdots\\|x\_n\\|\_{2}}$$ If $n=2$, then this is just the spectral norm of the matrix $T$ whose computation is well-known and can be done in polynomial time (just do an SVD of $T$ and $\\|T\\|$ is the maximal singular value). However, if $n\geq 3$, then the problem is NP-hard (see \[1\]). Actually, in the mentioned reference, you will find plenty of problems whith the same flavor (NP-hard for tensors of order $n\geq 3$ and "easy" for matrices $n=2$).

\[1\] *Tensor rank is NP-complete*, Johan Håstad, J. of Algorithms 11.4 (1990), https://link.springer.com/chapter/10.1007/BFb0035776

\[2\] *Most Tensor Problems Are NP-Hard*, Hillar, Christopher J. and Lim, Lek-Heng, J. ACM (2013), https://dl.acm.org/citation.cfm?id=2512329
> 3 votes

# Answer
Can you color a planar graph with k colours?

k = 0, k = 1: Trivial.

k = 2: Easy peasy.

k = 3: NP-complete.

k = 4: Very, very hard proof that the answer is always "Yes".

k = 5, 6, 7, etc. : Easy proof that the answer is always "Yes".
> 2 votes

---
Tags: np-complete
---


# Question
Title: Minimum words in a string given a dictionary
The question is: Given a dictionary consisting of a set of words and a string: find the minimum number of words the string can be split into. If the string can not be decomposed into a list of words return -1.

I tried finding the longest prefix and proceeding but that doesn't seem to work. I searched this question online and found a similar stack exchange question but I believe that the solution provided is wrong. It looks like this person is finding the longest suffix and proceeding but this approach doesn't work. Link to similar question

The reason this doesn't work is because: Suppose the dictionary is:{i,iiiiface,facebook,book} and input instance is 'iiiiifacebook'. The given solution would select 'facebook' and then continue to select 5 'i's' making a total of 6 words when infact the optimal solution is: (book,iiiiface,i) which is just 3 words. Please correct me if I'm wrong.

Please help me find the optimal (DP) solution to this problem.

# Answer
> 1 votes
One possible approach to solve this problem is as follows:-

(1) Create a trie of the dictionary for fast matching.

(2) Create a recursive function that does the following:-

(a) Finds all possible prefixes of the current string that are present in the dictionary.

(b) Calls itself recursively with those prefixes removed

```
Example:-

Word:- keyboardrocks
Dictionary:- {key,keyboard,keyboardrock,s,board}

f(keyboardrocks)->f(boardrocks)
                ->f(rocks)
                ->f(s)

```

(c) Recurse until the string is reduced to an empty string.

(d) The minimum recursion depth will be the required answer.

What can be done to better the runtime complexity?

You can use memoization to remember the minimum number of words that were needed to construct a prefix of length `m` of the string in an array.

```
So now, MinWord[1,n]=MinWord[1,x]+findMinWord[x,n]

```

# Answer
> 0 votes
Let the string be $S\_1,\ldots,S\_n$. For every $m$, find the minimum number of words that $S\_1,\ldots,S\_m$ can be split into. I'll let you work out the remaining details.

---
Tags: algorithms, data-structures, dynamic-programming, performance, java
---


# Question
Title: Modified Linear Bounded Automata Language
We know that linear bounded automatons accept context-sensitive grammars.

> Now suppose that we modify the LBA such that any location of the tape except the input part can be changed.What language does this automaton accept?

I think it is as strong as the standard Turing machine because we can copy the input part somewhere else and work with it like a semi-infinite Turing machine so that its tape is limited from the first symbol of the input that we copied.So it accepts recursively enumerable languages.Is this correct?

# Answer
any location except i/p part means

(total unbounded tape area - tape area that includes i/p string)

= (infinity length - finite length) as we know i/p string length is always finite

= infinity length

in the definition of linear bounded automata it is stated that the tape can be used as a function of the input string length.but here the portion that can be used is of infinite length which is obviously not a function of the input string length.So it acts as a turing machine.
> 1 votes

---
Tags: computability, automata, computation-models, linear-bounded-automata
---


# Question
Title: turing machine logic instead of something
Lets assume I have this turing machine:

And I have a $\Sigma = \\{0,1,2,3,4,5\\}$.

Now my question is can I simplify the transaction from $A$ to $B$ ?

Is there any way so I can write - when the read **value is not $2$**, write $x$ and move to right?

# Answer
> 1 votes
You could write $\neq 2 \to x,R$, but you might have to explain somewhere that by that you mean that the transition is taken as long as the symbol read is not $2$.

More generally, you can use whatever notation you want as long as you explain it and it's unambiguous.

This is the answer of a practical mathematician. Your professor could have different ideas.

# Answer
> 1 votes
Maybe you can write sth like "Σ\2 → x, R" on the transition. But as Yuval Filmus mentioned, the notations always depend on the lecturer.

---
Tags: turing-machines
---