Fitting a regular grammar to strings from a PCFG: how big does it get? Let $G=(V, \Sigma, R, S)$ be a (non regular) probabilistic context-free grammar, and $u_1, \ldots, u_n$ a set of $n$ strings generated by $G$.

For finite $n$, it is always possible to find a regular grammar $\hat G=(\hat V, \Sigma, \hat R, S)$ which generates the strings $u_1, \ldots, u_n$.

Intuitively, as $n$ goes to infinity, we expect $\hat G$ to get larger: my guess is that the cardinal of $\hat R$ (and maybe also the cardinal of $\hat V$?) would need to go to infinity.

Are there results which formalize this, e.g. by giving a lower bound on these cardinals as a function of $n$?

The question, if understood in the simplest naive way, might be uninteresting.

Here is a simple example. Let $G$ be the regular language $\{a^n\mid n\ge0\}$ over the alphabet $\{a\}$.

Consider the strings $\epsilon, a, a^2, \cdots, a^n$ in $G$. What are the regular languages that contains those strings?

The minimal such language, i.e., which contains no other strings, will need $n+1$ generation rules $S\to a^i$ for $0\le i\le n$.
The language with the least generation rules is $G$ itself, which has two generations rules $S\to \epsilon$ and $S\to aS$.

However, once we start to twiddle with the ways how to approximate context-free grammar by regular grammar, there are tons of research.

Here is a related question that links to many related stuff, Is there a known method for constructing a grammar given a finite set of finite strings?.

This paper considers approximating CFG from above by a regular
grammar.

You can browse the google search result for approximate context-free grammar by regular grammar or the google scholar.


Correct term for a priority queue with unique elements Is there a standard term for a priority queue which can only hold a single occurrence of any element?  This would be a priority queue for which operations such as "raise the priority of element x to the new value p" would make sense.

In this kind of an abstract container, if you insert some element ("key", but not in the sense of "priority key") with some priority, you cannot insert it again until it is extracted, but you can update its priority.

I would also like to know if there is some established interface for this kind of a priority queues.

I don't know of a name for the abstract data structure.

There is a well-established implementation of what you describe, though: treaps, a combination of BST and heap (i.e. priority queue). This is with priority and value/key being different things, though.

If priority and value are the same, use any priority queue and add uniqueness, i.e. by combining it with a set/dictionary data structure. (Treaps degenerate to sorted lists in this case.)


Why is SAT not in P? I'm studing P and NP complexity classes. I like know, why is SAT not in P? Is it because I can not determine if any Boolean expression is satisfiable?

It is possible to determine whether a boolean expression is satisfiable, the question is how quickly it can be done.

If there are $n$ variables, then we can try all $2^{n}$ possible truth assignments, and eventually we'll find if there is a satisfying one, but this is not polynomial time with respect to the size of the input.

There might be some polynomial time algorithm that does solve SAT, we don't know, however SAT is NP-complete, which gives strong evidence that there isn't a polynomial time algorithm. It all comes down to whether P=NP or not.


What kind of Neural Network (if any) could fit two sets of data points? I have two datasets, one of animal migration patterns (collected over the course of a couple years) that consists of many points on an x, y plane (latitude, longitude), and the other of ocean surface temperatures (also a set of lat, long points). What kind of neural network can be used, if any, to see some pattern, or correlate the two sets, so that I could alter the temperature data and have the network predict how the migration pattern changes? Is this a feasible use of an artificial neural network?

Try a common feed-forward neural network with one hidden layer and train it with error backpropagatin to find a coherence between your input (temperature values) and output (migration patterns). In order to train a neural network, you have to have pairs of input and output vecors, i.e. in your case, one temperature measurement position corresponds to one migration position. If you cannot assign single input-output pairs, you might do some preprocessing (for example, simply grouping your data into a grid on the x-/y- plane and taking the mean of each grid). The question to find a suitable number of neurons in the hidden layer is discussed here.

Note that there exist many machine learning techniques to learn relations between input and output data. Furthermore, there exists a notable variety of artificial neural networks in structure as well as in training algorithms. As your question explicitly demands a neural network, this answer tries to provide a rather straightforward standard method.

For pattern analysis (in order to understand and/or visualize the patterns/correlations) some statistical approaches might be more suitable, e.g. clustering the data with k-means/EM-algorithm.


Repeated addition and comparisons of floating point numbers In the following program where I repeatedly half an integer, it takes until i = 1074 for my integer to be equal to zero (I know that ideally the while loop shouldn't have ended, and the reason why it stopped was because of the memory limit of the computer).

a = 1.0
i = 0
while a != 0:
    a = a / 2
    i = i + 1
    print(a, i)

However, the next program, where I compare the halved integer using addition ends at i = 53.

a = 1.0
b = 1.0
i = 0
while a + b != b:
    a = a / 2
    i = i + 1
    print(a, i)

My question is why is there a big difference here?   Why does the first program go up to 1075 iterations, while the latter goes up to 53?

Also, when I tried a + b + c != b + c, it went up to just 52, furthermore

a + b + c + d != b + c + d

only went up to 51.  Why isn't there a big difference here?

The reason you are seeing these results are not due to the memory limits of your computer, but rather of the limits of the encoding of "floating point" numbers.  Python uses 64 bit floats (aka double precision floating point numbers), which are well described on wikipedia: https://en.wikipedia.org/wiki/Double-precision_floating-point_format

In short, there are only 52 bits for the significand and 11 bits for the exponent.  $2^{1023}$ is the highest exponent that can be represented.


Is recomnder systems part of computer science? I want to work on a paper with one of my friends in Recommender systems. My field is programming, and I favourite part is to be more technical.
I want to know that, is field of Recommender systems a part of Computer science or field in Information technology?

The algorithmic part of the  recommendation systems is more closely related to the computer science, the theoretical part of recommendation systems is mostly combination of statistics and linear algebra, thus we can think of recommendation systems as the combination of statistics and computer science, and the data science is the field that one would actually call the combination of statistics and computer science.
Thus my take on to answer the question is that the data science is the field you are looking for.


Parameters of a linear code Consider the code $C=\{c=(c_1...c_n): c \in \Bbb F_q^n, c_1=c_n\} \subset \Bbb F_q^n$.

I was able to prove that the code is a linear code because it is closed under addition and scalar multiplication.
Also, it is clear that the length is n.

However I am having a hard time with minimum distance, dimension, and size.

For minimum distance: I know that for a linear code the minimum distance is equal to the minimum weight, or number of places with nonzero entries, of all nonzero codewords in C. However, I think the minimum weight can range between 1 to n entries, so does this mean that the minimum distance is 1?

For dimension and size: I know that the dimension is the order of the basis for C. I think that the basis is $B=\{10...01, 010...0, 001...0, ... , 0...010\}$, and so the dimension would be $n-1$, but I am unsure on this.
If the dimension is $n-1$, then the size would be $q^{n-1}$.

Any help is appreciated, thank you in advanced. Please also let me know if this post does not belong to this stack exchange.

You're right, minimum distance is the minimal nonzero weight, thus 1.

A basis is what you gave. There are many bases. And youre right on size and dimension as well.

Edit: As pointed out in the other answer the distance is 2 if $n=2.$


A language which is neither r.e. nor co-r.e First, consider $$L_\exists=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts some input}\}$$
is RE. I tried to construct a Turing machine:

Input: Code(M);
L_e_TM(Code(M))
    for all words w of binary strings
        simulate M on w,
            if M accept w then return true;
    end for
end

Since we do not have to care about whether it halts or not, so we can use it to recognize $L_1$. But surely, this is language is not recursive which can be shown by reduction from the halting problem or by Rice's theorem.
But when we consider the complement of this language (for simplicity, we think all binary strings are valid Turing machine codes, otherwise we can just add a decider to check whether it is one recursively which will not affect the main result),
$$L_{\emptyset}:=L_\exists^\complement=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts no input}\}.$$
Similar we can just change the code above inside the for-loop:if M accept w then return false. Then both are in RE. Then they are in R? What was wrong? I thought there must be something wrong with the Turing machine code, but we are not talking about recursiveness, so I don't think the machine will not do the job to check whether it is in $L_\exists$ or not.
Somewhere, I have seen $L_\exists$ is RE. Hence,

Furthermore, consider

$$L_\forall=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts all inputs}\}$$
and
$$L_\forall^\complement=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts not all inputs}\}.$$
Are they both non-RE or one is RE and the other not?

Recall that a language is r.e. iff its complement is co-r.e. It follows that a language is neither r.e. nor co-r.e. iff its complement is neither r.e nor co-r.e., just like a language is recursive iff its complement is.

The language $L_{\exists}$ is recursively enumerable, though not recursive. To enumerate it, simulate all Turing machines on all possible inputs, and output a Turing machine whenever it halts on some inputs. To see that it's not recursive, reduce the halting problem to it.

Your other example $L_{\forall}$, usually known as TOT, is indeed neither r.e. nor co-r.e. In fact, it is $\Pi_2$-complete. You can prove that it is neither r.e. nor co-r.e. directly, by finding appropriate reductions from the halting problem.


How can i solve the recurrence $T(n)=2T(n-2)+n\log n$ What would be the solution of the following recurrence?
$$T(n) = 2T(n-2) + n\log n.$$

I've managed to get:

$$T(n) = 2^{n/2}T(0)+\sum_{i=0}^{n/2} 2^i (n-2i) \log(n-2i). $$

The sum cannot be easily bounded for estimating the recurrence, because part of it increases while the other part decreases as the index grows.

Hint:

Let $n=2m$.

$$T(2m)=2T(2m-2)+2m\log(2m)$$

or

$$T'(m)=2T'(m-1)+2m\log(2m)$$

which has the classical form.


How can encryption involve randomness? If an encryption algorithm is meant to convert a string to another string which can then be decrypted back to the original, how could this process involve any randomness?

Surely it has to be deterministic, otherwise how could the decryption function know what factors were involved in creating the encrypted string?

There can be more than one ciphertext that maps back to the same plaintext. In mathematical terms, the encryption algorithm must be injective so that you can recover the plaintext for the ciphertext, but this does not prevent the ciphertext from encoding more information than the plaintext.

As a concrete example, consider modes of block cipher operation such as CBC, CTR or OFB. All these modes involve an IV (initialization vector) in addition to the plaintext, the block cipher algorithm and its key. (For CTR, the IV is called a nonce, but it plays a similar role.) The encryption function is deterministic for a given IV. The IV, on the other hand, may be chosen randomly (for CTR, it must be chosen randomly). Thus, unless the protocol specifies a deterministic method of choosing the IV (such as an agreed-upon constant), the IV is sent alongside the ciphertext. In fact, the output of the encryption software often consists of the IV followed by the cipher text stricto sensu. The IV itself is sent in plaintext; it does not (must not) contain any confidential information.

As another example, consider the PKCS1.5 mode (“padding scheme”) of RSA (defined in PKCS#1 version 1.5 — see p.22–25 of PKCS#1 v2.1). Simplifying a bit, this mode consists of concatenating a random string with the message, then applying the exponentiation operation. The ciphertext is $(P \mathbin\Vert M)^e \mod{n}$ where $\Vert$ is concatenation, $M$ is the message and $P$ is a padding string most of whose bits are random. To recover the message from the ciphertext $C$, apply the raw decryption operation $C^d \mod{n}$ and break up $C$ into padding (which is discarded) and message.


RMQ with $O(\sqrt{n})$ space? I'm asked to design an RMQ data structure (Range Minimum Query: return index of $min$ in a range $[i,j]$) for an array that has $<=\log(n)$ local minimums (a local minimum is an index $i$ such that $A[i-1]>A[i]<A[i+1]$).

There are 2 restrictions:

Only $O(\sqrt{n})$ additional space (rather than $O(n)$ which is used for the regular RMQ d.s. Also see here)
Only a constant number of entry readings from the original array while answering a query

I thought of a solution that uses $\log(n)\log\log(n)$ space. Which is $< \sqrt{n}$ for $n>1165$ according to wolframalpha. (as @jbapple said, $\log(n)\log\log(n)=O(\sqrt{n})$ so that's fine)

edit: i found an error in the solution: in part 3, each item needs to know which section it belongs to (or at least the closest local min to it) - that's already $O(n)$ additional space.

However, i won't delete it so maybe it can be modified to a correct solution

My solution:

Find all local minimums and save pointers to them in $O(n)$ time, $O(\log n)$ space $(<\sqrt{n}\space)$ .

Apply regular RMQ on $\log(n)$ local minimums (powers of $2$ technique - section 3.3 page 5 in this paper). This takes $n\log(n)$ space, but $n$ in my case is $\log(n)$ (number of "representatives"), so it'll cost $\log(n)\log\log(n)$ space only. This is for part 3 - see ahead.

Answering a query:

There are 3 types of queries:

Range begins just after a local minimum and ends just after the next one:

This is easily solved in $O(1)$ since it's either the leftmost or rightmost entry
Range between 2 local mins (not including):

Also easy (same method)
Overlapping range:

This always overlaps complete sections of "local min to local min" and exactly 2 small sections from the right and left sides (see picture).

Sections of "local min to local min" can be solved in $O(1)$ using the regular RMQ we built above.
Regarding the other 2 sections, for each of them we can determine the min in $O(1)$ (must be either leftmost or rightmost item).
Finally we're left with exactly 3 numbers. Get their min in $O(1)$

Here's how it works:

I'll provide 2 solutions:

$O(\log{n})$ space and $O(\log{\log{n}})$ query.
$O(\log{n})$ space and $O(\log{\log{\log{n}}})$ query.

1) Using binary search on local mins.

Find all local minimums and store them in an array $B$ in their original order - $O(n)$ time, $O(\log{n})$ space ($<O(\sqrt{n})$). Also, let each item remember its original index. Now apply regular $RMQ<O(n),O(1)>$ structure on $\log{n}$ local minimums ($\log{n}$ space.)
To answer a query, each item must know its block’s beginning and ending points. But that would cost $O(n)$ additional space so we can’t afford it. Instead, given an interval $[i,j]$, we binary-search the array $B$ for indices $i$ and $j$ to find the closest index which has a local_min.

Answering a query:

There are 3 types of queries:

Range begins just after a local minimum and ends just after the next one:

First, we need to recognize we’re in this case. Perform a binary search on array $B$ for index $j$ or the smallest index larger than $j$. And symmetrically for $i$. In this case we’ll find exactly $i-1$ and $j$. That indicates the interval covers exactly 1 block. Therefor the answer is either $i$ or $j$ (proof below). Time: $O(\log{\log{n}})$.

Range between 2 local mins (not including):

Same method as above, but this time we’ll find  $i-2$  and  $j+2$ . That means we’re inside a block. The min must be either $i$ or $j$ (proof below) – Check that in $O(1)$. Time: $O(loglogn)$.

Overlapping range:

This always overlaps complete sections of "local min to local min" and exactly 2 small sections from the right and left sides (see picture).
Again, to recognize the case, binary-search for $i,j$ in $B$. Obviously, we’ll find $i$ and $j-1$ . This means $j$ overpasses the end of a block, and i overpasses a beginning of a block. Therefore, the min is: either one of the local minimums at that range, or one of the 2 edges (leftmost or rightmost – i.e $A[i]$ or $A[j]$). Solve query $[i,j-1]$ by RMQ, compare the returned min with $A[i]$ and $A[j]$ in $O(1)$, one of those 3 is the min. Time: $O(\log{\log{n}})$.

2) Using y-fast trie on local mins.

Find all local minimums and store them in a y-fast trie structure (call it $Y$) and let the keys be the original indices - $O(n)$ time, $O(\log{n})$ space. Now apply regular $RMQ<O(n),O(1)>$ structure on $\log{n}$ local minimums ($\log{n}$ space.)
To answer a query, each item must know its block’s beginning and ending points. But that would cost $O(n)$ additional space so we can’t afford it. Instead, given an interval $[i,j]$, we search $Y$ for indices $i$ and $j$ (or their pred and succ) to find the closest index which has a local_min. Search of pred/succ in a y-fast-trie of $n$ elements takes $O(\log{\log{n}})$.

Answering a query:

There are 3 types of queries:

Range begins just after a local minimum and ends just after the next one:

First, we need to recognize we’re in this case. Search for index $j$ or its successor in $Y$. And symmetrically for $i$. In this case we’ll find exactly $i-1$ and $j$. That indicates the interval covers exactly 1 block. Therefor the answer is either $i$ or $j$ (proof below). Time: $O(\log{\log{\log{n}}})$.

Range between 2 local mins (not including):

Same method as above, but this time we’ll find  $i-2$  and  $j+2$ . That means we’re inside a block. The min must be either $i$ or $j$ (proof below) – Check that in $O(1)$. Time: $O(\log{\log{\log{n}}})$.

Overlapping range:

This always overlaps complete sections of "local min to local min" and exactly 2 small sections from the right and left sides (see picture).

Again, to recognize the case, search for $i,j$ in $Y$. Obviously, we’ll find $i$ and $j-1$ . This means $j$ overpasses the end of a block, and $i$ overpasses a beginning of a block. Therefore, the min is: either one of the local minimums at that range, or one of the 2 edges (leftmost or rightmost – i.e $A[i]$ or $A[j]$). Solve query $[i,j-1]$ by RMQ , compare the returned min with $A[i]$ and $A[j]$ in $O(1)$, one of those 3 is the min. Time: $O(\log{\log{\log{n}}})$.

Proof for cases 1&2:

Theorem: in this type of ranges, the min is either the leftmost or rightmost entry.
Proof by contradiction: Suppose the min is somewhere inside the block, and not at the edges.
If it’s the min then it’s smaller than both its left and right neighbors. Thus it’s a local_min by definition. This is a contradiction because we assumed we have a block from a local_min to the next local_min (no local_mins’s in between).


avl trees rotations question As you can see in this tree its unbalanced at the root with a balanced factor of $-2$. You can also perform a Right left rotation or a Right Right rotation. Which do you have to pick in this case?

Apparently, you want to rebalance the AVL tree.

You can either do a simple left rotation or a right-left rotation.

I prefer not to mention right-right rotation since that term is misleading and ambiguous.

You can visualize what is happening. Go to AVL tree visualization, a page created by David Galles. Insert 2, 1, 4, 3, 5 in that order. Now look closely when you delete 1.


How $N$ qubits correspond to $2^N$ bits? I read everywhere that $N$ qubits correspond to $2^N$ bits. Let's start with 1 qubit, which is commonly represented by $\alpha |0\rangle + \beta |1\rangle$ where alpha and beta are complex numbers. This looks to me like infinite bits. How do they choose alpha and beta so that it becomes 2 bits?

Edit: Why is it commonly said that $N$ qubits correspond to $2^N$ bits?

Despite what badly written pop-science explanations of quantum computation may tell you, a qubit is not two classical bits and $N$ qubits is not $2^N$ bits. Qubits are fundamentally different from bits, pairs of bits or anything else (except for a representation of $\alpha$ and $\beta$ in binary to precision sufficient to classically simulate the computation to whatever precision is required).

As for why people talk about $N$ qubits being equivalent to $N$ bits, it's hard to say. To paraphrase Tolstoy, all correct explanations are alike but all incorrect explanations are incorrect in their own particular way. Perhaps it comes from the widespread mistaken belief that quantum computers somehow try all the options in parallel; perhaps it's a mistranslation of the fact that quantum computers offer exponential speedup over some classical algorithms. Scott Aaronson has some thoughts along these lines.


Difficulty understanding the solution of heap problem in CLRS book? I am reading the solution of this problem in CLRS:

Show that there are at most $\lceil {n/2^{h+1}} \rceil$ nodes of height $h$ in any $n$-element heap.
Solution: All the nodes of height $h$ partition the set of leaves into sets of size between $2^{h-1}$ and $2^h$, where all but one is size $2^h$. Just by putting all the children of each in their own part of the partition. Recal from 6.1-2 that the heap has height $\lfloor\lg(n)\rfloor$, so, by looking at the one element of this height (the root), we get that there are at most $2^{\lfloor\lg(n)\rfloor}$ leaves. Since each of the vertices of height $h$ partitions this into parts of size at least $2^{h-1}+1$, and all but one corresponds to a part of size $2^h$, we can let $k$ denote the quantity we wish to bound,  so,
$$(k-1)2^h + k(2^{h-1}+1) \leq 2^{\lfloor\lg (n)\rfloor}$$
so
$$k\leq \frac{n+2^h}{2^{h+1}+2^h+1} \leq \frac{n}{2^{h+1}}\leq \left\lceil\frac{n}{2^{h+1}}\right\rceil$$

But I don't understand how to come up with the fact that $(k-1)2^h + k(2^{h-1} + 1)$ is less than the number of leaves.

But I don't understand the how to come up with the fact that $(k−1)2^h+k(2^{h−1}+1)$ is less than the number of leaves.

It is quite straightforward from the very first statement of the solution which says there are all but one set of size $2^{h}$. Where $k$ is total number of sets of nodes at height $h$.

Therefore, total number of nodes at $h$ height is:
$$\begin{align*}
s &= (\text{total sets} \times \text{size of each sets})\\
 &= k(2^{h}+2^{h-1}+1)-1 \cdot 2^{h}\\
 &= (k−1)2^h+k(2^{h−1}+1)
\end{align*}$$

Another way to solve this is here.


AVL Rotations Abbreviations I read that there are 4 types of rotations:

Left rotation
Right rotation
Left-Right rotation
Right-Left rotation

What are the corresponding abbreviations: RL,LR,RR,LL? Is there a reference how to rebalance AVL trees?

Please skip that article at tutorialspoint. Instead, read this article at GeekforGeeks, which is much better. You may want to check my answer to another question.

The common abbreviations for Left rotation, Right rotation, Left-Right rotation, Right-Left rotation are L, R, LR and RL respectively, as expected. These rotations can be applied to all kinds of binary search trees. For example, they are applicable to red-black trees, too.

Please note that there is minor confusion about the terminologies. However, I would say that more than 9 out of 10 times, you will encounter the mainstream terminologies as explained in that GeekForGeeks article.

A common reference to rebalance AVL trees is the Wikipedia entry on AVL trees.


Quick and space-efficient way to find whether two sets intersect I hope you can help me -

Given a lot of sets containing integers,
I'd like for any two sets, to quickly (i.e. O(1)) ask whether they intersect.
Note that I don't need the exact intersection, rather just a yes/no answer.
Also, I am fine with some false-positives.
Also, the representation of the sets should be space-efficient (i.e. less than the set-size).

Ideally, I'd also like to (infrequently) update the sets.

My requirements make me think of Bloom Filters, which 1)represent sets efficiently, 2)allow O(1) containment-test and 3) have some false-positives. Unfortunately it they don't apply to two-set-intersection.

Any ideas? Thanks!

(Just FYI, the sets are subsets of ids of adjacent edges from a huge graph)

Build a $k \times k$ table $ans$ of answers, storing in each entry the smallest (according to some total order) element in that intersection or a sentinel value (e.g. -1) if the intersection is empty, and also maintain a mapping from each element to the set of all sets that contains it (e.g. using a hashtable of hashtables).

When you add an element $x$ to a set $i$, you can efficiently find all other sets $j$ for which $ans[i][j]$ might need to change, and the change itself is also simple: set $ans[i][j] = \min(ans[i][j], x)$.  Removing an element will also be efficient, except in the rare case when you remove that minimum shared element, which requires fully recomputing (just) $ans[i][j]$.


Is there any model of Game of Life compatible with hypercomputation? I found a question in Mathematics Stack Exchange which asks a very similar question

(https://math.stackexchange.com/questions/1023812/hypercomputation-higher-dimensional-variants-of-conways-game-of-life)

It asks whether there are Game of Life models with 3 or more dimensions and if there are Game of Life models related to hypercomputation, but the answers seem to refer to the first question and ignore the second.

So, if I am not wrong, and that is the case, then:

Is there any specific model of Game of Life (Or Cellular Automata in general) that can perform hypercomputation (i.e a Hypercomputational model of Game of Life and/or Cellular Automata)?

And also, Is there any specific model of a hypercomputational Game of Life/Cellular automata that has been applied to physics? That has proposed a cosmological/physical model of the universe based on these Cellular Automata? (Like some sort of Zuse's thesis: https://en.wikipedia.org/wiki/Calculating_Space)

Cellular automata can be simulated with an ordinary Turing machine, so they don't have any more power than an ordinary Turing machine -- they can't perform "hypercomputation".


P, NP and specialised Turing Machines I'm sort of new, but very interested to the field of computing and complexity theory, and I want to clarify my understanding about how to class problems, and how strongly the problems relate to the machine being used to solve them.

My Understanding

Standard Turing Machine - a Turing Machine which has a finite alphabet, finite number of states and a single right-infinite tape
Turing-Equivalent Machine - a Turing Machine which, can emulate, and be emulated by, a Standard Turing Machine (quite often with some trade-off between space and time achieved by the emulation)
P - the class of problems which can be solved in polynomial time using a Standard Turing Machine (defined above)
NP - the class of problems which can be verified in polynomial time using a Standard Turing Machine
NP-complete - the hardest problems which are still in NP, which all NP problems can be converted to in polynomial time

My Question

Are the complexity classes (P, NP, NP-complete, etc) related to the algorithm, or the algorithm and the machine?

Said in another way, if you could create a Turing Equivalent Machine (that can solve all the problems that a Standard TM can, but in a different amount of time/space) and this new machine could solve an NP-complete problem in time which grows as a polynomial with respect to the input, would that imply P=NP?

Or must the NP-complete problem be solvable on all possible Turing Machines in polynomial time to be considered in P?

Or do I mis-understand something fundamental above?

I have had a look (maybe not with the correct search terms, I don't know all the jargon quite well) but it seems most lectures/notes etc. focus on standard machines but say that custom machines often have some time/space speed up at the expense of space/time, without saying how that bears on complexity classes. I'm not really familiar enough with the jargon in this field yet to find papers which explain this.

Algorithms and machines are not defined in your question and I don't think they are needed to ask what you want to ask.

Complexity classes are defined using Turing machines. That is their definition. If you want to prove anything you have to use these definitions. Anything about any other model is unrelated unless you prove some correspondence between that model and Turing machines.

Let me add that there is a hypothesis that says that "efficient" "computation" in any "reasonable" "machine" will capture the same number theoretic functions. However it is not a provable statement unless one defines the quoted terms. We can prove it for many machines but not all machines. Being Turing machine equivalent is not sufficient, we want them to be Strongly so, i.e. we should be able to simulate those machines with Turing machines and vice versa efficiently. The nice thing about $\mathsf{P}$ and $\mathsf{NP}$ is that they are very robust classes, i.e. small and big differences in machine models does not change the class. However it is true all the time. For example, I can define a simple new model of computation where I have an basic operation that in constant time solves a problem that is unsolvable in $\mathsf{P}$. Then it is obvious that this model will not be strongly equivalent to Turing machines.

The example above was an artificial one. However right now we have a model of computation that seems closer to efficient computation in practice than polynomial-time Turing machines: bounded-error probabilistic/randomized Turing machines, efficient algorithms in that model are referred to as $\mathsf{BPP}$.

Many experts believe that $\mathsf{BPP}=\mathsf{P}$ but we are far from proving it.

We have another model of computation which some experts expect to become practicable in future: quantum Turing machines, efficient algorithms in that model are referred to  as $\mathsf{BQP}$. We don't know if it is different from $\mathsf{P}$ but some experts conjecture that it is different and more powerful than $\mathsf{P}$.

In short, if you want to prove a complexity theory result about $\mathsf{P}$ and $\mathsf{NP}$, you have to use either the original definitions using Turing machines, or first prove a correspondence between them and the classes you are using based on some other model of computation. As I mentioned above it is quite easy to create machine models where polynomial "time" in them can solve an $\mathsf{NP}$ (or even arbitrarily more difficult) problem: just add a basic operation to your machine model that solves that problem and let the "time" that operation takes to be one unit of time.


Finite automaton whose alphabet is $\mathbb{N}$ Is it possible to have a finite automaton where $\Sigma = \mathbb{N}$? Why or why not?

I think it is possible to have a set of all natural numbers, however I'm not sure why.

In the standard definition of a finite automaton (say a DFA or an NFA), the alphabet is a non-empty finite set (perhaps the empty set is allowed by some definitions). The reason we insist that the alphabet be finite is that otherwise the description of the automaton would potentially not be finite.
For example, in one common definition of DFAs, the transition function is a function from $Q \times \Sigma$ to $Q$, where $Q$ is the set of states. If $\Sigma$ is infinite, then describing the transition function would require us to list infinitely many values of the transition function.
Some definitions of DFA allow the transition function to be partial, and in that case, we could have an automaton with a finite description even when the alphabet is infinite; and the same always holds for NFAs. However, in such cases all words accepted by the automaton belong to $\Delta^*$ for some finite $\Delta$, and so the effective alphabet is finite.

While the usual definition requires $\Sigma$ to be finite, the definitions of DFA and NFA still make sense even for infinite alphabets. However, if you keep the set of states finite, then you can find a partition of the alphabet into finitely many subsets $\{\Sigma_\sigma : \sigma \in \Delta\}$ so that the language accepted by the automaton behaves as a language over $\Delta$, in the sense that whether a word is accepted or not depends only on which partitions $\Sigma_\sigma$ its letters belong to (that is, it is obtained from a language over $\Delta$ by applying the inverse of the homomorphism mapping all letters in $\Sigma_\sigma$ to $\sigma$).
Allowing infinitely many states doesn't really change the picture: if the set of states is allowed to have the same cardinality as the alphabet, then all languages are regular, and otherwise the "effective alphabet" has the same cardinality as the set of states (as in the case considered above), and all languages over that alphabet can be accepted.
This shows that even from a theoretical perspective, the most interesting case is that of finitely many states and ("without loss of generality") finite alphabet.


Hilbert's 10th Problem and Chaitin's Diophantine Equation "Computer"? In Chaitin's Meta Math! The Quest For Omega, he briefly talks about Hilbert's 10th Problem. He then says that any Diophantine Equation $p=0$ can be changed into two equal polynomials with positive integer coefficients: $p=0 \iff p_1 = p_2$.

Then he says that we can think of these equations like a "computer":

  Diophantine Equation Computer:
  $$L(k,n,x,y,z,...)=R(k,n,x,y,z,...)$$
  Program: $k$, Output: $n$, Time: $x,y,z,...$

With left side $L$, right side $R$. He says $k$ is the program of this computer, which outputs $n$. He also says that the unknowns are a multi-dimensional time variable.

What confuses me is that he then says that Hilbert's 10th Problem is clearly not solvable when viewed in this way. He basically says "because of Turing's Halting Problem". But I don't see the connection (I'm just beginning to learn the theory). I was hoping someone could more clearly explain what Chaitin's point is here.

I know that Turing's Halting Problem basically states that you cannot predict when a program will halt before it actually halts (given a finite amount of time). What is the application to Hilbert's 10th Problem, using the notation laid out by Chaitin?

Good question.  It sounds like you might need some additional background on Hilbert's 10th Problem.  I hope this isn't overkill.
The problem asks:

Is there an algorithm that, given a Diophantine polynomial, decides whether or not there is a setting of its variables that makes it equal to $0$?

This was resolved in the 70's as a consequence of the MRDP (also called Matiyasevich's theorem, if you feel like searching it) which states:

Define: A set $D \subset \mathbb{N}$ is Diophantine if there is a Diophantine polynomial $p$ on $k+1$ inputs such that $D = \{ x \, | \, \exists y \in \mathbb{R}_+^k \, p(x, y) = 0\}$.
The Diophantine sets are precisely those that are recognizable by Turing machines.

This theorem is obvious in one direction (every Diophantine set is recognizable by a Turing Machine -- on input $x$, simply have your machine start guessing vectors $y \in \mathbb{R}_+^k$, evaluate $p(x, y)$, and halt if/when you find that $p(x, y) = 0$).  It is very non-obvious in the other direction -- why is it true that every Turing recognizable set is Diophantine?  The encoding schemes are disgusting, but trust me, it can be done.
Anyways, how does the MRDP theorem resolve Hilbert's 10th problem?  Well...
For the sake of contradiction, let's pretend we have an algorithm that, given a Diophantine polynomial $p(y)$, decides whether or not there is an input vector $y$ that causes $p(y) = 0$.
Now I'm going to use this magical algorithm to solve the halting problem.  Given a machine, I will use the disgusting encoding of Diophantine equations to convert the problem "Does $M$ halt on input $x$?" into the problem "Does the Diophantine polynomial $p(y | x)$ have a set of inputs that make it equal to $0$?"  Then I will use my magical algorithm to solve this problem, and now I have solved the halting problem.
Of course, this is impossible, so in reality there can't be a magical algorithm that searches for an input vector that causes $p(y) = 0$.  Similarly, there can't be an algorithm that looks at two Diophantine polynomials and decides if they're ever equal.  That's what Chaitin is saying.


Average number of comparisons in sorted insertion The questions is pretty simple: Given a sorted array of N elements, what is the average number of comparisons made in order to add a new element (let's call it x) in its correct position?
I am using linear search for that task.

So far, I've tried to solve it this way:

# of Comparisons     Probability of A[i] > x (Not sure if correct)
     1                         1/n
     2                         1/n
     3                         1/n
     4                         1/n
    ...                        ...
     n                         1/n

Hence, the expected value would be:

$$E[x] = \sum_{x=1}^{n}x \cdot Pr(X=x)$$
$$E[x] = 1 \cdot Pr(X=1) + 2 \cdot Pr(X=2) + 3 \cdot Pr(X=3) + ... + n \cdot Pr(X=n)$$

Using $$Pr(X = n) = \frac{1}{n} $$ for all n,

$$E[x] = \frac{1}{n} \cdot \sum^{n}_{i=1}{i}$$

and finally
$$E[x] = \frac{n+1}{2}$$

Still, I'm not sure if this is the correct way to solve it, since I'm not sure about my 1/n assumption.

Any insights would be helpful!

Well, that would strongly depend on the algorithm that you use to find out where to insert the new element, and on the distribution of new elements.

Assuming that you do a linear search, and the new element could go to any position with the same probability, your result is close, but not quite exact. The new element can go into one of (n + 1) positions, not n. There may be up to n comparisons needed; n comparisons are needed both if the new element goes into the first array position, and if it goes into the second array position. So the result is

(1 + 2 + 3 + ... + (n-1) + n + n) / (n + 1) =

= (n (n+1) / 2 + n) / (n + 1)

= n (n + 3) / 2 / (n + 1)

= (n + 2 - 2 / (n + 1)) / 2 ≈ (n + 2) / 2,

which is just a tiny bit more than your answer (n + 1) / 2.


"Grammar inference" for 2-D images Others have studied the following question: given a set of words $w_1,w_2,\dots \in \Sigma^*$, find a regular grammar (or a context-free grammar) that generates all of those words, is "natural" in some sense, and is as small as possible.  In the special case where we have a single word $w \in \Sigma^*$, if the grammar generates exactly the word $w$, we can think of this as a compression algorithm that compresses the word $w$ to the grammar produced by this inference algorithm.  Of course, each word is a one-dimensional sequence of symbols.

Now consider a two-dimensional array of symbols, say an array $A[1\ldots m, 1\ldots n]$ where each $A[i,j] \in \Sigma$.  Is there any corresponding algorithm that could be used to find a grammar of some sort that generates $A$?  Could this be used as a compression algorithm for compressing images, i.e., one that compresses a two-dimensional image to its corresponding grammar?

I'm not even sure what kind of grammar would be suitable.  Is there an analog of regular or context-free grammars that generates a two-dimensional output instead of a one-dimensional output?  I've done some searching, and haven't found anything obvious.

Of course we could linearize the image, by concatenating the rows of the array, to get a one-dimensional sequence, and then apply any of the above techniques -- but this does not preserve locality.  In other words, elements that are vertically adjacent will no longer be near each other after this transformation.  So this transformation does not seem useful.
Perhaps we could build a quad-tree over the array and then consider tree automata over that quad-tree?  Is there a grammar inference algorithm for such tree automata over quad-trees?
Alternatively, it seems like there might be a natural extension of context-free grammars to two-dimensional output: just make the right-hand side of each rule be a two-dimensional array of terminals and non-terminals of arbitrary size, and then apply the obvious generation algorithm.  Do such grammars have a standard name?  Is there a grammar inference algorithm for such grammars?

I'm researching related ideas using context-free grammars at the moment, so I might be able to give you some things to think about by describing the approach I've taken (which is just one approach).

Firstly, I use rules that describe the production of multisets and not sequences (or trees in fact). So whereas a conventional production rule:

$s \rightarrow abc$

would produce the (ordered) string 'abc', the rule below would produce an unordered set of the same symbols

$s \rightarrow \{a, b, c\}$

In such a grammar non-terminal symbols can operate as variables in the same way as sequential grammars, e.g.:

$
s \rightarrow \{X, c\}\\
X \rightarrow \{b, a\}
$

Now, going back to 2D images. Perhaps surprisingly, it turns out you can encode an image as an (unordered) collection of non-terminal symbols, each producing a (unordered) multi set that describes each pixel. In your question you describe a set of terminal symbols that describes that possible values of each pixel, let's say $\Sigma=\{0,1\}$. I'm going to add to that 2 terminal symbols $x$ and $y$, each of which representing an offset of 1 pixel from the origin on each axis, so  $\Sigma=\{0,1, x, y\}$.

Now consider the pixel $A[2,2] = 1$. This can be encoded in the grammar scheme I describe using a multi set production:

$p \rightarrow \{x, x, y, y, 1\}$

So, you could encode a whole image this way. It's easy to imagine the amount of bloat you'd get in such a grammar. However, it is possible to compress the whole grammar by using a hierarchy of production rules that can be inferred. For example, take the derivation of the point $A[18, 9]=1$

Instead of:

$p \rightarrow \{x, \text{(repeat 17 more times)}, y, \text{(repeat 8 more times)}, 1\}$

you can have:

$p \rightarrow \{D, A, G, y, 1\}\\
A \rightarrow \{x, x\}\\
B \rightarrow \{A, A\}\\
C \rightarrow \{B, B\}\\
D \rightarrow \{C, C\}\\
E \rightarrow \{y, y\}\\
F \rightarrow \{E, E\}\\
G \rightarrow \{F, F\}\\
$

With of course the non-terminals $A$ to $G$ being reused to describe multiple points. So actually something that looks like it would be hideously inefficient can be compressed very efficiently. It is possible to easily infer such a grammar from a series of points (this is the subject of my research), using similar techniques as normal sequential grammar inference.

The cool feature of this type of grammar is it is possible for the grammar to encode complex patterns that are non-sequential (in this case graphical) in nature.

This is all a work in progress but it might help you with your problem.


DFA, lower bound on number of states, language with primes and remainders This is an exercise from old exam on formal languages that I don't know how to solve:

Let $p \ge 5$ be a prime number and $L_p$ be a language of words over $\{0,1\}$ that read in binary from right (i.e. from least significant bit) give a number that gives remainder modulo $p$ from the set $\{1,2, \ldots, \frac{p-1}{2}\}$.

How to show that:

  Every DFA recognizing $L_p$ has at least $2p$ states.

?

One fact that I know of and is somehow related (has DFA and primes in the statement) is:

  Any DFA recognizing language $\{0^n : n \text{ is not divisible by } p\}$ has at least $p$ states.

This can be seen by observing that the language is infinite, hence any DFA must have a reachable cycle, from which some accepting state is reachable. And if that cycle had less than $p$ states, then because any number smaller than $p$ is coprime with $p$, we could loop sufficiently many times in that cycle and arrive at the aforementioned accepted state with a word $0^{kp}$ for some natural $k$ - a contradiction.

Maybe it's possible to use this fact, or alter this proof somehow to make it fit for the theorem with $L_p$?

--EDIT

I'm trying to solve it by Myhill-Nerode theorem, as Yuval Filmus suggested.
So, the goal is to find $2p$ words $w_1, \ldots, w_{2p}$ that will be pairwise distinguishable. I don't have a good intuition here but let's define $w_i$ to be $rev(bin(i))$ for $i = 1, \ldots, 2p$ ($bin(a)$ gives a binary representation of number $a$, and $rev(w)$ reverses the word $w$). Let's take any $i \neq j$ that both belong to $L_p$, or both don't. Now the task becomes a bit number-theoretic -- adding a common suffix $x$ to these words changes their values such that $val(w_ix) = val(w_i) + 2^{length(w_i)-1}val(x)$ (and similarly for $j$), where $val(\cdot)$ gives value of binary string reading from LSB (so e.g. $val(01) = 2$).
Now the question is: can we always find an appropriate $x$ that makes one of $w_ix, w_jx$ belong to $L_p$, and the other not? I don't know the answer to this question. Maybe I should use the fact, that $2$ is a multiplicative generator modulo $p$?

For a binary string $x$, let $N(x)$ be the value of the number when read LSB first. Then $N(xy) = N(x) + 2^{|x|} N(y)$.

Now consider any $P \subseteq \mathbb{Z}_p$. For any $x$, $N(xy) \bmod p \in P$ iff $N(x) + 2^{|x|} N(y) \bmod p \in P$. This condition depends only on $N(x) \bmod p$ and $2^{|x|} \bmod p$, i.e. on $N(x) \bmod p$ and $|x| \bmod \operatorname{ord}_p(2)$ (here $\operatorname{ord}_p(2)$ is the smallest exponent such that $2^o \equiv 1 \pmod{p}$).

As $x$ goes over all binary strings, $(N(x) \bmod{p}, |x| \bmod\operatorname{ord}_p(2))$ goes over all possible $p \cdot \operatorname{ord}_p(2)$ values. One way to see this is to take zero paddings of strings representing $0,\ldots,p-1$.

Let us now consider the particular $P$ stated in the question. Since $p \geq 5$, $2^2 \not\equiv 1 \pmod{p}$, and so to prove the claim, it suffices to show that the equivalence classes $\{(a,1),(a,2) : a \in \mathbb{Z}_p\}$ are all different.

Consider any two equivalence classes $(a_1,b_1),(a_2,b_2)$. If exactly one of $a_1,a_2$ is in $P$, then there is nothing to do. Suppose first that $a_1,a_2 \in \{1,\ldots,\frac{p-1}{2}\}$. If $b_1 = b_2$ then $a_1 \neq a_2$. Without loss of generality, $a_1 < a_2$. Therefore we can find $n$ such that $a_1 + nb_1 = \frac{p-1}{2}$ while $a_2 + nb_2 \notin P$. If $b_1 = 1$ and $b_2 = 2$ then there is a range of $\frac{p-1}{2}$ consecutive values of $n$ such that $a_1 + nb_1$ goes over all of $1,\ldots,\frac{p-1}{2}$. For the same values of $n$, the expression $a_2 + nb_2$ goes over $\frac{p-1}{2}$ values in jumps of $2$; it is not hard to check that not all of them can belong to $P$.

We leave the case $a_1,a_2 \notin P$ to the reader.


Median of Medians Recurrence Relation for 3-grouping So I am trying to figure out the recurrence relation for the median of medians algorithm using groups of 3 instead of groups of 5. Per CLRS's method, my recurrence relation looks like

$$
T(n) = T(\lceil \frac{n}{3} \rceil) + T(\frac{2n}{3} + 4) + c_1n
$$

And I want to show $T(n) = O(n \lg n)$

Via substition, I assume inductively that

$T(n') = cn' \lg n'$

So by substition

$$T(n') \leq c\lceil \frac{n'}{3} \rceil \lg \lceil \frac{n'}{3} \rceil + c(\frac{2n'}{3} + 4) \lg (\frac{2n'}{3} + 4) + c_1n' $$

$$ \leq c (\frac{n'}{3} + 1) \lg (\frac{n'}{3} + 1) + c(\frac{2n'}{3} + 4) \lg (\frac{2n'}{3} + 4) + c_1n'$$

aaand now im stuck. Is there anyway i can drop the +1 and +4 from this expression to make it simpler?

You can use the inequality $\log (1+x) < x$ (valid for $x > 0$, where $\log$ is the natural logarithm), which follows from a Taylor expansion, to reason as follows:
$$
\log \left(\frac{n'}{3} + 1\right) =
\log \left(\frac{n'}{3} \cdot \left(1 + \frac{3}{n'}\right)\right) = \log \frac{n'}{3} + \log \left(1 + \frac{3}{n'}\right) < \log \frac{n'}{3} + \frac{3}{n'}.
$$
This shows (after some calculation) that you can remove the $+1$ and $+4$ in return for an additional constant additive term, that is, you can estimate your final line by
$$
c \left(\frac{n'}{3}+1\right) \lg \frac{n'}{3} + c\left(\frac{2n'}{3}+4\right) \lg \frac{2n'}{3} + M + c_1 n',
$$
where $M>0$ is some constant.


Determining if a digraph has any vertex-disjoint cycle cover Given a digraph, determine if the graph has any vertex-disjoint cycle cover.

I understand that the permanent of the adjacency matrix will give me the number of cycle covers for the graph, which is 0 if there are no cycle covers. But is it possible to check the above condition directly?

Your problem is answered in the Wikipedia article on vertex-disjoint cycle covers. According to the article, you can reduce this problem to that of finding whether a related graph contains a perfect matching. Details can be found in a paper of Tutte or in recitation notes of a course given by Avrim Blum.

As a comment, in the graph-theoretic literature a vertex-disjoint cycle cover is known as a 2-factor.


Correct way to implement linked list I'm doing this challenge on Hacker Rank that wants me to implement a linked list.

It seems to want me to find the last-added instance of node and change its head to link to my new instance of node. Therefore the last instance added would have head=None (I'm using Python).

This is the pic they provide -

Wouldn't it make more sense to create a node instance with its head linked to the previous node? That way the only node with head=None would be the first node created.

I've seen conflicting suggestions so far. I'm not a CS student or developer.

EDIT -

This example from Youtube (1.36) suggests the second method.

EDIT -

Sorry if this seemed like a programming question. I'm trying to see if there's a logical way to set up linked lists for my own benefit... solving the HackerRank challenge is not the issue.

First of all, don't have a head pointer in your structure that doesn't point to the head of the list: it will confuse everyone. Call the pointer in your structure next or something!

You are right that in a singly-linked list (one with a next pointer but no pre pointer) it is illogical and inefficient to add new items to the end of the list. Singly-linked lists work best when you add each new item to the beginning of the list. Then all you need to do is:

Create a new item and fill in its data.
Set its next pointer to the value stored in the global head variable.
Set the global head variable to point to the new item.

Thus, as you say, only the first item to be added to the list will have next=null.

Adding items to the end of the list involves walking through the whole of the list every time, which is not efficient or sensible.

If you wanted a singly linked list to which you could add items at the end, you would have a second global variable (call it tail) pointing to the last item in the list. This makes for inelegant code, since you now have different kinds of behaviour when tail is null (which it will be at the beginning) and when tail is not null. In fact, a good way of handling matters in this case is to create the list with one fictional item in it already, and tail pointing to that item. This saves a lot of tests, but you will of course have to remember, when walking through the list, not to pay attention to that fictional item.


Is there any polynomial time algorithm for a restricted EXP-time problem? Let we fix $<T>$ and $w$, where $<T>$ is its binary representation of a Turing machine and $w$ is input.

We want to check if $T$ doesn't halt over $w$ before $2^{|w|}$ steps. A trivial solution is to use a universal Turing machine which simulates $T$ on $w$ and counts its steps, but this method uses exponential time.

I wish to know do we have any polynomial time algorithm to check this for the fixed Turing machine and input?

If we had a high-level program or pseudo code, then we had the possibility to analyze it and figure out the time complexity without simulation. But by Rice theorem, we know that it is not possible to understand the behaviour of a Turing machine using its binary representation string. So it seems impossible to have a Turing machine which runs in polynomial time and understand that $T$ doesn't halt less than $2^{|w|}$ steps even for a fixed $T$ and $w$. I don't know how to prove it.

Edit (In order to be more clear about inputs and outputs):

There are two possible ways to think of it:

We want a Turing machine $M$ that runs in polynomial time over its empty tape and outputs 0 if $T$ halts over $w$ before $2^{|w|}$ steps and outputs 1 otherwise.
We want a Turing machine $M$ that runs in polynomial time over input $<T>w$ and outputs 0 if $T$ halts over $w$ before $2^{|w|}$ steps and outputs 1 otherwise. It's not important for us that what is $M$ output for other inputs.

I believe there is no such $M$ since it is not possible to understand what is a Turing machine doing without simulation of its steps. If such $M$ exists, then it is understanding somehow how $T$ acts on $w$ without simulation of $T$ on $w$. Of course for special cases like pseudo-code, we can estimate the running time. But the $T$ which we fix is not always a pseudo-code.

Edit 2: In order to fix the point Ariel mentioned in his answer,

We want a Turing machine $M$ with the second formulation that works correctly as we stated (it understand T takes exponential time running its input) for two inputs $<T>w_1$ and $<T>w_2$.

Your first formulation isn't very useful, as either the machine which simply writes $0$ on its tape (without putting in any effort) or the one which writes $1$, satisfy your condition. Fixing both $T,w$ means you have only one question at hand, and not a computational task we can reason about in terms of the amount of resources require to handle it. In that case, a simple yes or no consists as a valid answer, and we can output it in constant time.

In your second formulation, you're asking whether the language

$L=\{(\langle M \rangle,w)| \text{$M$ halts on $w$ within $2^{|w|} steps$}\}$

is decidable in polynomial time? The answer is no, since $L$ is hard (under polynomial time reductions) for the class $\mathsf{DTIME\left(2^n\right)}$. This means that if $L\in P$ then $\mathsf{P=DTIME\left(2^n\right)}$, contradicting the time hierarchy theorem.


Theta bound of the following function Suppose the function $f(n)$ is defined as the number of $\ast$ printed in the following code

for(int i = 0; i<n; i++) {
    for(int j = i; j<n; j++) {
        for(int k = j + 200; k<2n; k++) {
            for( int r = k^2; r<n; r++) {
                print(*);
            }
        }
    }
}

I suspect the answer is $\Theta(n^{2.5})$, by running the code at $n=5000$ and $n=50000$, but I do not have a rigid proof.

Can anyone enlighten me? Thank you!

First, note that  we print a * for every tuple $(i,j,k,r)$ such that
$0 \leq  i \leq j \leq k-200 \leq \sqrt{r}-200\leq \sqrt{n}-200$

For every $i$ and $j$ there are at most $(\sqrt{n}-200)$ options, for $k$ it is $\sqrt{n}$ and for $r$ it is $n$. Thus the upper bound for the number of * is $(\sqrt{n}-200)\cdot (\sqrt{n}-200) \cdot \sqrt{n} \cdot  n\in O(n^{2.5})$.

To compute the lower bound, we can take $i$'s in the range between $0$ and $\frac{\sqrt{0.5n}-200}{2}$, $j's$  between $\frac{\sqrt{0.5n}-200}{2}+1$ and $\sqrt{0.5n}$, $k$'s between $\sqrt{0.5n}+1$ and $\sqrt{0.75n}$, and finally, $r's$ between $0.75n+1$ to $n$. Thus the number of options for a tuple $(i,j,k,r)$ is more than $(\frac{\sqrt{0.5n}-200}{2})^2 \cdot (\sqrt{0.75n}-\sqrt{0.5n})\cdot 0.25n \in \Omega(n^{2.5})$.

Thus the answer is $\Theta(n^{2.5})$


Are there any PSPACE problems that don't exist in NP-Hard? The question is in the title, I suppose. I am studying complexity classes, and I understand that NP-Hard is the set of problems that are at least as hard as the hardest problems in NP. Therefore, it will naturally contain PSPACE problems.

However, I was specifically wondering if there were any PSPACE problems that were not in NP-Hard? (from my understanding, implying that they are easier than the hardest problems in NP).

Assuming we use polytime reductions in both, all PSPACE-hard problems are NP-hard, which follows directly from the definition and from the easy fact NP$\subseteq$PSPACE: a languages $L$ is PSPACE-hard if all languages in PSPACE polytime-reduce to $L$. If $L$ is PSPACE-hard then in particular, all languages in NP polytime-reduce to $L$, and so $L$ is also NP-hard.

On the other hand, there are problems in PSPACE which are not NP-hard, for example $\emptyset$ and $\Sigma^*$. If P=NP then all other problems in PSPACE are NP-hard, since every non-trivial language (a language different from $\emptyset,\Sigma^*$) is NP-hard in this case. If P$\neq$NP then every problem in P also belongs to PSPACE and is not NP-hard.


Question about time-complexity for MST-like algorithm I have got a problem with an excercise about graphs:

Your friend has been hired by a brewery to work out the most efficient
delivery route for the beer-delivery truck drivers. A typical delivery has about 50 stops and the company wants to save money by driving the
shortest possible distance. Your friend ignores your advice and decides on an algorithm, as follows:

Start at the depot,
Go to the nearest location that has not yet been
delivered to:

Deliver
Repeat until you have delivered all the beer

Return to depot

And the quesiton is:
What is the Big-O complexity of this approach? Why?

I do not think this way of solving problem is any algorithm like Prim's algorithm, and I have no clue what can be a complexity. Could anyone explain me?

This problem looks variant of TSP problem(more precisely metric TSP). As you want to traverse all node with the minimum distance.

TSP is one of the classical NP-Hard problem.

What your friend did is a Greedy approach making minimum Spanning tree Which is 2-Approx(metric-TSP) of the minimum distance.

This greedy approach generally works in E log V time but does not have guarantee for exact solution.

By using graph structure we can implement in linear time also.


Find all $k$ local maximums in an array of length $n$ in $O(n \log k)$ time Given a sequence of numbers $a_1, a_2, ..., a_n$, a number $a_i$ is called the $k$ local maximum $\iff i > k$ and $a_i$ is the largest number among the $(k+1)$ numbers $a_{i-k}, a_{i-k+1}, ..., a_i$. Given a sequence of $n$ numbers $a_1, a_2, ..., a_n$, and an integer $k$, I am requested to find all $k$ local maximums in $O(n \log k)$ time.

At first, this seems like a dynamic programming problem, where I first calculate the solution for $k'=1$, and goes from there to $k'=k$, but this approach seems to take $O(nk)$ time.

I have found a possible solution to my problem here
, but this also seems to take $O(nk)$ time for my problem, as

Build a Cartesian tree of the first $k$ elements. $O(k)$
Insert and check whether the $(k+1)$th element is the $k$ local maximum (also remove the leftmost element). $O(k)$
Repeat step two until reaching the end of the sequence.

The overall complexity seems to be $O(k) + O((n-k)k) = O(nk)$.

Any help is appreciated. Many thanks.

Hint: Use some data structure that allows insertion, deletion, and search in logarithmic time to maintain a snapshot of the $k$ preceding elements, and use it to determine whether the next element is a $k$-maximum in time $O(\log k)$.


Is the P vs NP problem, an NP or co-NP problem? A few years ago, a youtube channel named hackerdashery, made an extraordinary youtube video explaining P vs NP, in a semi-vulgarized way  :
https://www.youtube.com/watch?v=YX40hbAHx3s

At 7 minutes and 56 seconds however, he talks about why it is so hard to prove that P $=$ NP or that P $\neq$ NP, and states that proving things is in fact an NP problem (in the video however, he writes down that it is actually a co-NP problem).

Thus, is proving things, in particular P $=$ NP or P $\neq$ NP, an NP or co-NP problem? If so, why? And where could I find more on this?

It isn't meaningful to say that a single specific question is in NP or any other complexity class. In order to classify things as being in P, or NP, or co-NP, etc. they need to be sets of problems with some parameter. So for example, the problem "Is the positive integer n prime" is a question where we can discuss this sort of thing.

In a certain overly pedantic sense, the correct answer to your question is that the problem you care about is in P, since there's an algorithm which will answer every question of your form in polynomial (in fact constant time). But we don't know if that algorithm is just "Return  TRUE" or is "Return False."

The idea that the video may be touching on is the idea that if P != NP, then in general, finding proofs is hard. In fact, "Is statement S provable in formal system A with a proof of length at most x" is an NP-hard problem" (Questions in this are things like "Is there a proof of Fermat's Last Theorem that's shorter than 5 pages.") . And we also expect that if P != NP, for most "natural" NP-complete problems, random instances will often not be easy. So if P != NP, then searching for proofs should often be difficult, and thus we shouldn't be surprised that the proof that P != NP would itself be one of those. This may be what they were trying to say.


Decidable language: set of context-free langauges containing 1 string ONE = {(G) : G is a CFG such that L(G) contains exactly one string} .

I know to prove this is decidable I need to create a DTM that would recognize it and HALT on all input.
I am struggling at coming up with a high level definition.

My Possible Solution:

On input G, where G is a Context-free grammar,
If non-terminal has more then one option that it can lead to, reject.
Else accept.

Hint: The point of this exercise is that it is decidable whether a context-free grammar generates the empty language. Using this as a black box, you can proceed as follows. On input $G$:

Check if $L(G)$ is empty, and if so, reject.
Find a word $w \in L(G)$.
Check whether $L(G) \cap (\Sigma^* \setminus w)$ is empty.

I'll let you figure out how to implement the latter two steps; step 2 uses the fact that it is decidable whether a grammar $G$ generates a given word $x$, and step 3 uses the fact that the intersection of a context-free language and a regular language is context-free (constructively).

The same idea can be used to calculate $L(G)$ given that we know that $L(G)$ is finite.


Backward data-flow: post-order or RPO on reverse CFG? When solving backward data-flow problems, many resources (Wikipedia and many presentations found online) recommend traversing the control-flow graph (CFG) in post-order for fastest convergence, which makes sense.

Other resources (such as the "Engineering a Compiler" book) suggest to use reverse post-order (RPO) on the reversed CFG instead.

... and PO(graph) != RPO(rev(graph)) in some cases involving cycles.

My question is: which resource is right? Post-order makes sense, so why not just use that and save the CFG inversion? Why would I use RPO on reversed CFG instead?

It is mostly due to the speed of convergence. To clarify, RPO visits as many predecessors possible before visiting a node so in case of forward data flow problems (like Dominator computation) this would help to converge faster. You can find more details in Engineering a compiler book (which you already know!)


Recurrence relations and the Master Theorem Although it might be a bit of newbie question, my question is, How can I apply the Master theorem to the following relation:
T(n) = 99T(n/100) + log(n!)

I'm trying to learn about algorithms, but I'm not really comfortable with logarithms(haven't studied in school yet), so I'd really appreciate a bit of help.
Thanks.

We know that $n! \le n^n$, therefore $\log n! \le n \log n$. Then
$$
T(n) \le 99T( \frac{n}{100} ) + n \log n
$$
Let $c=\log_{100} 99 < 1$ and notice that $n \log n$ is polynomially larger than $n^c$. Indeed:
$n \log n \in \Omega(n) \subset \Omega(n^c).$ By the master theorem we have $T(n) = O(n \log n)$.
This is tight because $\Omega(n \log n)$ is also a lower bound since:
$$
T(n) \ge \log n! \ge \log ( \lfloor n/2 \rfloor^{(n/2)} )
=  (n/2) \log ( \lfloor n/2 \rfloor)  = \Omega(n \log n).
$$
To summarize, you have $T(n) = \Theta(n \log n)$.


Simplifying regular expressions This is the homework question:

  $ \{w \in \{a, b, c\}^* : \text{(no symbol occurs twice in succession in w)}\} $

This is my answer:

  $$\{((abc)^*| (acb)^*| (ab)^* | (ac)^*)^* | (bac)^* | (bca)^* | (ba)^* | (bc)^*)^* | ((cab)^* | (cba)^* | (ca)^* | (cb)^*)^* | ((\epsilon +a) | (\epsilon + b) | (\epsilon+c)) \}
 $$

Is there a way to simplify this expression?

Let's solve this exercise "by induction". Suppose first that the alphabet is only $a,b$. In this case, the only possible words are $ababab\ldots$ and $bababa\ldots$, and you can write a simple regular expressions for them. Now take such a word over the alphabet $a,b,c$. You can break it apart as $w_1 c w_2 c w_3 c \ldots$, in which $w_i \in \{a,b\}^*$. We already have a regular expression describing the $w_i$, so we can write one for the language in question. This approach is general, and you can apply it to any alphabet size.


How to find the big o running time if the recursion function have different cases of recursion with different fraction of n? How to find the big o running time if the recursion function have different cases of recursion with different fraction of n?

If I have a recursive function like this for example (This is just an example, its not a real thing, it just demonstrates my question):

someFunction(n){
  base case:
    return 0
  if (some case)
    return someFunction(3n/4)
  else if (some other cases)
    return someFunction(n/4)
}

As we can see, the recursion calls itself in different cases and in different cases, the n is fractioned by different value, how can I write down the recursive formula for finding out the run time?

Is the formula something like:

T(n) = T(3n/4)?
T(n) = T(n/4)?
T(n) = T(3n/4) + T(n/4)?
T(n) = (Probability of first case)*T(3n/4) + (Probability of first case)*T(n/4)?

What if I have no idea what is my probability for each case?

If you want to find the worst-case asymptotic running time, then you can't use probabilities; you have to assume that at each branch, it takes the slower path.  Thus you get a recurrence relation

$$T(n) = \max(T(3n/4), T(n/4)) + O(1).$$

If you want to find the expected running time, then you can use probabilities:

$$T(n) = p_0(n) T(3n/4) + p_1(n) T(n/4) + O(1)$$

where $p_0(n)$ is the probability of taking the "then" branch and $p_1(n)$ is the probability of taking the "else" branch.  If you don't know the probabilities, this kind of analysis won't be useful and you presumably won't be able to calculate the expected running time.  There are some important caveats here as well; the random choice must depend only on internal random choices of the algorithm, not on $n$, or else funny things can happen.

Solving the recurrence relations above is a separate matter.  Often it suffices to apply the master theorem.

Normally, in theoretical computer science, if we are talking about asymptotic running time, the default assumption is that you are talking about worst-case running time.  If you want to focus on something else (e.g., expected running time), it's important to state that explicitly, otherwise you might cause confusion among readers.

Since you seem to lack some basic understanding of running time analysis, I suggest studying big-O notation, running time analysis, and recurrence relations.  This is a slightly tricky example, and it's not the simplest one to start with to start learning the subject.  We do have some resources on that subject here; see, e.g., How to come up with the runtime of algorithms?, How does one know which notation of time complexity analysis to use?, Sorting functions by asymptotic growth, Is there a system behind the magic of algorithm analysis?, Solving or approximating recurrence relations for sequences of numbers, and a good algorithms textbook.


Is there an algorithm that can solve any two-player game? Note: this is basically a more precise restatement of this question, which didn't get proper answers because it was vague.

Most two-player perfect information games can be represented as a finite directed graph, because although the games could theoretically go on forever, there are only finitely many possible states for the game. Chess fits into this category, for instance. Here we'll consider states to be distinct even if the only difference between them is whose turn it is, thus our directed graph is always two-colorable with the colors "White's turn" and "Black's turn".

Given a directed graph $G$ with such a two-coloring, with one priveleged node called the "initial node", a strategy for a player $P$ is a partial function $s:N(G)\to N(G)$ such that:

$s$ is defined only on nodes at which it is $P$'s turn.
If $s$ is defined at a node $A$, then $s(A)$ is a child of $A$.
If $s$ is defined at a node $A$, it is defined at all children of $s(A)$.
$s$ is defined on the initial node, or on all children of the initial node if $P$ goes second.

Now, I'll call a complete path through $G$ a path through $G$ starting at the initial node which either goes on forever or ends at a node with $0$ out-degree, such nodes are called endstates. If $S$ is some set of complete paths, we will say that player $P$ can force $S$ iff there exists a strategy for $P$ such that any complete path which obeys that strategy (I think it's obvious what this means) is in $S$.

Some endstates are marked as victories for White, some are marked as victories for Black, some are marked as draws. Let $W$ be the set of all complete paths ending in a victory for White, $B$ be the set of all complete paths ending in a victory for Black, and $D$ the set of complete paths ending in a draw. Let $I$ be the set of all infinite complete paths, which we will also conceptually think of as draws.

It is then a theorem that either White has a strategy that forces $W\cup D \cup I$, or Black has a strategy that forces $B\cup D \cup I$, or both.

Is there an algorithm which, given such a description of a game, outputs which players have such a strategy, along with the strategy itself?

I don't mind if no such algorithm is actually known, but is there an existence or impossibility proof?

(Note that you're excluding games with randomness, such as backgammon.)

Yes. In particular, endgame tablebases use most of such an algorithm.

Wbool,Wfull,Bbool,Bfull = set(),set(),set(),set()
keep_going = False
for v in nondraw_endstates:
 keep_going = True
 if is_a_victory_for_white_(v):
  Wbool.insert(v)
  Wfull.insert([v,0])
 else:
  Bbool.insert(v)
  Bfull.insert([v,0])
n = 1
while keep_going:
 keep_going = False
 for v in Wbool:
  for u in nodes_with_an_edge_to_(v):
   if u in Wbool:
    continue
   if white's_turn_(u):
    Wbool.insert(u)
    Wfull.insert([u,n,v])
    keep_going = True
    continue
   avoidable = False
   for x in nodes_with_an_edge_from_(u):
    if x not in Wbool:
     avoidable = True
     break
   if not avoidable:
    Wbool.insert(u)
    Wfull.insert([u,n,v])
    keep_going = True
 for v in Bbool:
  for u in nodes_with_an_edge_to_(v):
   if u in Bbool:
    continue
   if not white's_turn(u):
    Bbool.insert(u)
    Bfull.insert([u,n,v])
    keep_going = True
    continue
   avoidable = False
   for x in nodes_with_an_edge_from_(u):
    if x not in Bbool:
     avoidable = True
     break
    if not avoidable:
     Bbool.insert(u)
     Bfull.insert([u,n,v])
     keep_going = True
     continue
 if (initial_node in Wbool) or (inital_node in Bbool):
  keep_going = False
 else:
  n = n+1

Suppose the game is locally finite. If white has a winning strategy then the while loop will terminate and every extension of the result of removing the middle entries from Wfull's triples to all non-endstate white nodes is a winning strategy for white.  If black has a winning strategy then the while loop will terminate and every extension of the result of removing the middle entries from Bfull's triples to all non-endstate black nodes is a winning strategy for black. If only finitely many nodes can reach the non-draw endstates and neither side has a winning strategy then the while loop will terminate and white can always stay out of Bbool and white doing so guarantees that white won't lose. Bblack can always stay out of Wbool and black doing so guarantees that black won't lose.

If the while loop terminates, then it does so in an amount of time that's bounded above by a polynomial in (the number of nodes that can reach the non-draw endstates). Furthermore, by reduction from the circuit value problem, deciding who has a winning strategy is P-complete even when $G$ is (finite and) acyclic and there are no draw states.


Doubt over the index value used in dynamic programming I was going through Count All Palindromic Subsequence in a given String where I've to count all the palindromic subsequence of a given string.

After seeing the brute force(recursive solution), I went through the dynamic programming technique but the index values used surprised me.

for (int L=2; L<=N; L++)
{
    for (int i=0; i<N; i++)
    {
        int k = L+i-1;
        if (str[i] == str[k])
            cps[i][k] = cps[i][k-1] +
                        cps[i+1][k] + 1;
        else
            cps[i][k] = cps[i][k-1] +
                        cps[i+1][k] -
                        cps[i+1][k-1];
    }
}

In the above code snippet,

if(str[i] == str[k])
    cps[i][k] = cps[i][k-1] + cps[i+1][k] + 1;

whereas in the code for brute force approach the same thing works using:

Else if (str[i] == str[j])
    return   countPS(i+1, j) + countPS(i, j-1) + 1;

I agree with what has been used in the brute force but Shouldn't the code following the DP approach be written as:

if(str[i] == str[k])
    cps[i][k] = cps[i-1][k] + cps[i][k+1] + 1;

because in the brute-force approach if we are computing for CountPS(i,j) then for str[i]==str[j] case, we need to compute countPS(i+1,j) and countPS(i,j-1) which in on translating to DP approach should mean that
we need to compute cps[i-1][j] and cps[i][j+1].

But, it isn't like what I'm thinking.

Where am I going wrong in understanding the code?

The code there is not optimal in terms of space as you can reduce the space complexity to n.

In any case I would recommend thinking as follows when you are trying to convert a brute force recursive solution to dynamic programming.

First look at the recurrence.

f(i,j) = 1                                   if i==j
f(i,j) = f(i+1,j) + f(i,j-1) +1              if str[i] == str[j)
f(i,j) = f(i+1,j) + f(i,j-1) - f(i+1,j-1)    otherwise

Here each i,j pair is a 'state' and each state depends on other states. Dynamic programming stores previously computed states into an array/hashmap/whatever hence allowing us to reuse previously computed states to make the program run faster.

If we are using a 2d array to store the states then state (i,j) is stored in dp[i][j]. State  (i-1,j) is stored in dp[i-1][j] and so on.

In any case look at the recurrence relation of the brute force solution. You can see that:

For any given state, i depends on the values of i+1 and i
For any given state, j depends on the values of j and j-1

Thus we can make the following inference:

Since i depends on i, i+1 values, i+1 must be filled before i. Hence i loops from n to 0.
Since j depends on j, j-1 values, j-1 must be filled before j. Hence j loops from 0 to n.

So we know the direction of our loops and we can just fill in values accordingly like so:

private int count(String s) {
    int[][] dp = new int [s.length()+1][s.length()+1];
    for(int i=s.length()-1; i>=0; i--) {
        for(int j = i; j<s.length(); j++) {
            if(i==j)
                dp[i][j] = 1;
            else if(s.charAt(i) == s.charAt(j))
                dp[i][j] = dp[i+1][j] + dp[i][j-1] +1;
            else
                dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];
        }
    }
    return dp[0][s.length()-1];
}

And this is basically what is in the link that you posted. f(i, string.length-1)'s state contains the result which is why we return  dp[0][s.length()-1].

Time complexity: n^2; Space complexity: n^2

However this is not optimal. Optimal solution below:

Like I mentioned earlier we can make an optimization in terms of space to give us a better solution. This is not done in the link that you posted.

Notice that i depends on values of only i and i+1. This means states containing i+2, i+3, ... i+n is useless.
Similarly j depends on values of only j and j-1. This means states containing j-2, j-3, ... j-j is useless.

If something like this happens for any parameter of the recurrence, it means that we can reduce the dimension of the array by 1. We can either reduce the dimension i or we can reduce the dimension j (since either i or j can be reduced). Just make sure that the dimension you are reducing is the outer loop.

Here i represents the rows and j represents the columns of the array. Below I will show you how to reduce the i dimension. You can do the same with j but just make sure that if you reduce j, j is in the outer loop.

We are reducing dimension i, we need only 2 rows: row i and row 1+1. We dont need the other rows in the matrix. So let row 1 be row1, let row i+1 be row2.

private int count2(String s) {
    int[] row1 = new int[s.length()+1];
    int[] row2 = new int[s.length()+1];

    for(int i=s.length()-1; i>=0; i--) {
        for(int j = i; j<s.length(); j++) {
            if(i==j)
                row1[j] = 1;
            else if(s.charAt(i) == s.charAt(j))
                row1[j] = row2[j] + row1[j-1] + 1;
            else
                row1[j] = row2[j] + row1[j-1] - row2[j-1];
        }
        // copy row1 into row2
        for(int j=0; j<row1.length; j++)
            row2[j] = row1[j];
    }
    return row1[s.length()-1];
}

The time/space analysis is:

Time complexity: n^2; Space complexity: n

So the general pattern to convert recursion to bottom up dp is:

Look at the recurrence relation
Figure out the order of the loops
Check to see if any variable x depends on x+-c where c is a constant. If that is the case, we can reduce the space complexity
Compute and store state i,j using previously computed states (unless it is the base case)
Return the result.

Hope this helps.


In what sense are dataflow architectures non-deterministic? The Wikipedia article mentions non-determinism in the context of dataflow architectures. Arthur Veen's paper mentions non-determinism when it elaborates on MERGE nodes as conditional constructs.

Are dataflow architectures non-deterministic in the sense of Non-Deterministic Turing Machine?

For any program which deterministically runs on a von Neumann architecture, can we guarantee that it runs deterministically on a data flow architecture?

Are dataflow architectures non-deterministic in the sense of Non-Deterministic Turing Machine?

In principle one could create a non-deterministic dataflow architecture, but that would be a bit odd.  There is nothing about dataflow that fundamentally requires determinism or non-determinism.

Normally I'd expect that a dataflow architecture would be deterministic in the sense that the result of the computation is a deterministic function of the inputs (in principle it doesn't have to be that way, but that's probably the common case for a dataflow architecture).  Of course, the order in which intermediate values are computed might not be deterministic, even though the result is.  See Why doesn't parallelism necessarily imply non-determinism? for a detailed explanation of that point.

Beware that there are multiple meanings of the word "non-determinism".  One meaning is non-determinism in the sense of a non-deterministic Turing machine, i.e., there can be a choice of transitions and the machine magically makes the best choice at every step; this is not implementable directly in real-world machines, so is purely a theoretical nothing.  Another meaning is that the system is not deterministic, e.g., there are aspects of its behavior that are not specified or random; those are resolved somehow but not necessarily by choosing the best choice.  Occasionally I've seen people use the word "indeterminism" for the latter notion, but that seems to be pretty rare.  See also  Differences and relationships between randomized and nondeterministic algorithms?, https://cs.stackexchange.com/a/38158/755, https://en.wikipedia.org/wiki/Nondeterministic_algorithm, https://en.wikipedia.org/wiki/Indeterminacy_in_computation.


Proving calculating Minhash I'm reading about MinHash technique to estimate the similarity between 2 sets: Given set A and B, h is the hash function and $h_\min(S)$ is the minimum hash of set S, i.e. $h_\min(S) = \min(h(s))$ for s in S. We have the equation:
$$
p(h_\min(A) = h_\min(B)) = \frac{|A \cap B|}{|A \cup B|}
$$
Which means the probability that minimum hash of A equals to minimum hash of B is the Jaccard similarity of $A$ and $B$.

I am trying to prove above equation and come up with a proof, which is:
for $a \in A$ and $b \in B$ such that $h(a) = h_\min(A)$ and $h(b) = h_\min(B)$. So, if $h_\min(A) = h_\min(B)$ then $h(a) = h(b)$. Assume that hash function h can hash keys to distinct hash value, so $h(a) = h(b)$ if and only if $a = b$, which means the probability is $\frac{|A \cap B|}{|A \cup B|}$. However, my proof is not complete since hash function can return the same value for different keys. So, I'm asking for your help to find a proof which can be applied regardless the hash function.

Min-hash are not just (standard) hash functions, but a family of functions $\cal H$, such that if you randomly pick one function $h\leftarrow \mathcal{H}$ out of the family, it will satisfy the requirement you have in your question.

Check
"Min-wise independent permutations"
by Broder, Charikar, Frieze and Mitzenmacher, 2000. They define this notion and analyze it in a very simple way to follow.

From a practical point of view, you usually have a bound on the size of the sets you use (say $2^{256}$, probably more than the number of atoms in the universe).
Then, a 256bits output is enough to have hash-functions that are permutations (and clearly, the set of all the permutations is a good family of min-hash functions..)
So the problem is not the output length, but how many functions are there in the min-hash family, so that if you pick one at random, you get the probability that any element is the minimum exactly $1/2^{256}$.

To overcome the huge set of hash-functions (there are $256! \gg 2^{256}$ permutations of 256 bits..),
they relax the requirements on the probability of the min-hash and get an approximated notion of $\epsilon$-min-hash, which guarantees that
$$\Pr_{h\leftarrow {\cal H}}[h(A)=h(B)] = \frac{|A\cap B|}{|A\cup B|}\pm \epsilon$$
which is more useful from efficiency perspective (the set $\mathcal{H}$ is smaller and easier to get).


What is wrong with this reasoning that finding the genus of a degree 3 bipartite graph is NP-complete? Finding genus of a biparite graph is $NP$-complete and finding genus of a degree $3$ graph is $NP$-complete and so finding genus of a degree $3$ bipartite graph is $NP$-complete.

Though implication could be right is there any harm in reasoning this way on $NP$-completeness?

You cannot reason in this way. Try proving it formally to see what goes wrong.

Also, consider the following example (which is admittedly slightly different than yours). Chromatic number is NP-complete, even for planar graphs. The 4-coloring problem (i.e., the chromatic number problem with the number of colors fixed at 4) is NP-complete. However, the 4-coloring problem for planar graphs is in P.


Interpreting a Language I'm having trouble understanding some language notation, primarily what rules I can take away from it. The language is as follows:

$\qquad L = \{a^n b^m b^p c^p b^{n-m} \mid n > 0, m < n, p > 2\}$

My goal is to create a context free grammar from this, but I can't get my ahead around the rules in place here. In plain English, it's clear that any string for this language must have a positive number of a's in it, but what is going on with the multiple b's? Do I take this as the string must be in some form like so:

$\qquad aaa-b-bbb-ccc-bb$  (n=3, m=1, p=3)

where the bunches of b's are just distinct sequences? Or is there something else I should be doing in order to satisfy this?

First of all, note that your quest for "rules in place" is probably doomed. This looks pretty much like an exercise problem you would pose in class; there is not necessarily an intuitive rule or semantics. It's just a playground for developing your skills. Therefore, it may be more helpful to strap on theory glasses and just look at the formal object given to you.

Now, for your problem. In order to get to a context-free grammar, it can be useful to identify "phases" a grammar can work through. A good first step is to identify which parts of the word are "connected" by the restrictions in place and which are independent of each other. If you find intersecting dependency arcs, you either have a non-context-free language (which you can check) or you need to represent your language differently (sometimes restrictions are redundant or seem to imply dependencies that are not really there¹).

   Here, note that your words have the form

 $\qquad a^n b^m \dots b^{n-m}$.

 Why can I remove a part for an intuitive look? Because I cut away $b^p c^p$ which can clearly by generated by a standard grammar and independently of the rest. Now, the above is just

 $\qquad a^n b^n$

 if you remember to insert $b^p c^p$ at some point in $b^n$.

  Try to come up with a grammar along these lines. Take care about corner cases and the exact restrictions on $m,n,p$! And, of course, prove correctness.

Another strategy that can sometimes work better is to build a PDA and convert it into a(n ugly) grammar by the standard construction.

A simple example: $a^nb^nc^n$ is not context-free, so $a^na^na^n$ is not. Right? Wrong: $a^na^na^n = a^{3n}$ is clearly regular.


Remove range of keys from Binary Search Tree in O(s+h) I have a binary search tree with integer keys. I have to remove a range (m, n]eZ of keys from the BST in O(s + h)

where s is the number of keys to remove and h is the height of the tree.

Attempted solution:

The naive solution is just to find nodes in range and delete them and fix the tree one-by-one, but that doesn't meet the time complexity requirement as it would be O(s * h).

I have considered the fact that if a node is within the range and its left child is in range, all of the left child's right children are in range as well as if the right child of the node is in range, the left children of the right child are also in range. Both of these facts allow you to delete the entire subtree below those children by simply unlinking it. I'm having trouble converting this information into a useful algorithm.

It sounds like you almost have an algorithm.
Find the vertex $u$ where the successor of $m$ is stored. Similarly, find the vertex $v$ where $n$ is stored (or its predecessor if $n$ is not in the BST).

Suppose that the range of vertices to delete is not empty (that is, the key of $u$ is smaller than, or equal to, the key of $v$) and let $w$ be the lowest common ancestor of $u$ and $v$.

Proceed as follows:

Walk from $u$ to $w$ (excluded). Let $z$ be the current vertex of the walk. At the very beginning of the walk ($z=u$) and whenever $z$ is reached from its left child, delete $z$ and its right subtree. The left subtree of $z$ takes $z$'s place in the tree (continue the walk from the former parent of $z$). The deleted vertices are shown in red in the left figure. This takes time $O(h + d_u)$, where $d_u$ is the number of deleted vertices.
Walk from $v$ to $w$ (excluded). Let $z$ be the current vertex of the walk. At the very beginning of the walk ($z=v$) and whenever $z$ is reached from its right child, delete $z$ and its left subtree. The right subtree of $z$ takes $z$'s place in the tree (continue the walk from the former parent of $z$). The deleted vertices are shown in blue in the left figure. This takes time $O(h + d_v)$, where $d_v$ is the number of deleted vertices.
You are now left with the task of deleting $w$ (see the figure on the right), which can be done in $O(h)$ time using the standard deletion algorithm (if $w$ is a leaf, delete it immediately, otherwise swap $w$ with its predecessor/successor and then delete it).

The overall time required is then $O(h + d_u + d_v) = O(h + s)$.


If Then Constraint Linear Programming I want to write the following constraint:
If A=1 and B <= m then C=1 ( where A and C are binary, m is a constant and B is continuous).

My solution requires some kind of hack in the model, a Big-$M$ value, which is pretty common, but also a tolerance $\varepsilon$, which is not very desirable. I hope that I do not miss something easy here but reckon there is no way around it.

To model a condition of the form $(X \wedge Y) \to Z$ for binary $X, Y, Z$, you can use $$\tfrac12(X + Y) \leq Z + \tfrac12.$$
We can verify this by inserting: $X=Y=1$ yields to $1$ on the left hand side, thus, $Z$ has to be at least $\frac12$, and since it is binary, it must be $1$. If either $X$ or $Y$ is $0$ (or both), we have at most $\frac12$ on the left hand side and in this case $Z$ might be either $0$ or $1$.

We also need to transform the constraint $B \leq m$ as a binary variable in order to use the template above. This can be done by introducing a new binary variable $B'$ which must assume the vaue $1$ iff $B \leq m$. We also need a Big-$M$ value which must be greater than any value that $B$ can assume (note that for numerical reasons in practice, $M$ should be not too large). Moreover, we have $\varepsilon$, a small tolerance value to get a strict $>$-inequality (in practice you would choose the difference to the next greater number from $m$ that can be represented exactly on your machine). We now add the constraints $$B \leq m + (1-B')M\tag{1}$$ $$B \geq m + \varepsilon - B'M\tag{2}$$
$(1)$ guarantees that $B' = 0$ if $B > m$, $(2)$ guarantees that $B' = 1$ if $B \leq m$. We verify this again: If $B \leq M$, $(1)$ and $(2)$ can be satisfied with $B' = 1$, but not with $0$. If $B > m$, we need $B' = 0$ to satisfy $(1)$ and then $(2)$ is satisfied since $B$ is at least $\varepsilon$ larger than $m$.

Putting it all together, we obtain your constraint
$$
\tfrac12(A + B') \leq C + \tfrac12,\\
B \leq m + (1-B')M,\\
B \geq m + \varepsilon - B'M.
$$


Double, down facing arrow in operational semantics What is the meaning of the double, down facing arrow $\Downarrow$ in the context of operational semantics? Here's the example formula that uses it:

$$\frac{s_0 \vdash M_1 \Downarrow P_1, s_1 \; ... \; s_{n-1} \vdash M_n \Downarrow P_n, s_n}{s_0 \vdash M \Downarrow P, s_n}$$

It would be also beyond priceless if you could explain in words what do other pictograms of this formula mean. I feel that $\vdash$ here doesn't mean what it usually means in logic (is provable from). However the general form of this formula is the derivation rule (I can understand it from the context). It is a rather general derivation rule though (it is followed by few other more specific examples which use all the same pictograms).

The source of the formula: On Exceptions versus Continuation in the Presence of State by Hayo Thielecke. It cites several other sources, but I couldn't find the explanation of the symbols used.

The language of inference rules are much more general than what is usually given in Logic. Indeed you can look at systems with rules of the shape

$$ \frac{\Theta_1\ldots \Theta_n}{\Theta}$$

Where the $\Theta_i, \Theta$ are some kind of statement and ask: what are all the possible $\Theta$ I can get by repeated application of these rules?

In the above case, $s \vdash M \Downarrow P, s'$ expresses the statement:

  With starting state $s$, program $M$ evaluates to $P$ and the resulting state is $s'$.

This is a very general framework for expressing the operational semantics of a program, and it means that if you can build a finite derivation tree with $s \vdash M\Downarrow P, s'$ at the base, then you have shown that the program $M$ is well-defined and evaluates to $P$.

Let's give an example. Say $s$ is the state in which variable $b$ is sent to true and $n$ is sent to $2$, which I will write $\{b\mapsto \mathrm{true}, n\mapsto 2 \}$. Then the following should be derivable:

$$\{b\mapsto \mathrm{true}, n\mapsto 2 \}\vdash \mathrm{if}\ b\ \mathrm{then}\ n+1\ \mathrm{else}\ 0 \Downarrow 3, \{b\mapsto \mathrm{true}, n\mapsto 2 \}$$

Note that in your question, the rule:

$$\frac{s_0 \vdash M_1 \Downarrow P_1, s_1 \; ... \; s_{n-1} \vdash M_n \Downarrow P_n, s_n}{s_0 \vdash M \Downarrow P, s_n}$$

Means:

  If, starting from state $s_0$, $M_1$ reduces to $P_1$ and new state $s_1$, and starting with state $s_1$ $M_2$ reduces to $P_2$ and new state $s_2$ etc. then starting from state $s_0$, $M$ reduces to $P$ with new state $s_n$.

In particular, the order in which you do the reduction is important: the state may change after the evaluation of $M_1$, which in turn will influence the evaluation of $M_2$, etc. This is why in a language with state (side-effects), the order of evaluation of arguments passed to a function is important: we may get a different result depending on which argument we evaluate first.

In Haskell, laziness makes it impossible to know which arguments will be evaluated first (or at all!), so having side effects is pretty much out of the question.

I suggest reading the classic Types and Programming Languages, by Benjamin Pierce, which treats all of this in much detail.


Reversing a List from a Context-Free Grammar Let's say I have a struct_declaration_list of the following type. How do I reverse it?

struct_declaration_list
    : struct_declaration
    | struct_declaration_list struct_declaration
    ;

P.S. Sorry I don't know the exact name of this kind of list so I can't search. I just have this grammar.

Your question is not very precise. I assume you want the list of struct_declaration to start from the other end in the parse tree.

Your grammar gives you a struct_declaration_list that looks like

         SDL
        /   \
      SDL    SD
     /   \
   SDL   SD
  /   \
SDL   SD
 |
SD

If you reverse the order in the second part of the rule, you reverse "the pointers" in the list, which may be understood as reversing the order.

struct_declaration_list
    : struct_declaration
    | struct_declaration struct_declaration_list
    ;

Then the parse tree  looks like:

   SDL
  /   \
 SD   SDL
     /   \
    SD   SDL
        /   \
       SD   SDL
             |
            SD

The left-to-right order of SD is in both cases that of their occurrence in the input string (the program).


Karnaugh map simplification I'm working through an example that looks like a fairly simple Karnaugh map and simplification, but I feel stupid that I can't seem to understand the correct answer.

This is the map:

My groupings:

This is the equation:

But I don't know how it simplifies to the correct answer here:

I understand why the NOT A goes outside of the bracket, but I don't see how the C OR NOT C just becomes a C inside the bracket?

Check for solution. Grouping should be done using 2 quads


Where is PCP(1,1) located? The PCP-Theorem states that $PCP(log(n), 1) = NP$. So can anyone explain, where $PCP(1,1)$ is located in relation to other classes?
My thoughts:

$P \subseteq PCP(1,1) \subseteq PCP(log(n)) = NP$
Is there some theorem like "$P \neq NP \implies PCP(1,1) ...$"
What is the relation to the probabilistic classes like $BPP$ and $RP$?

$PCP\left(O(1),O(1)\right)=P$.

Suppose you are allowed to toss at most $r$ coins, and that the proof length is bounded by $l\in\mathbb{N}$. Given input $x$, you can compute the acceptance probability of the verifier relative to any proof in $\{0,1\}^{\le l}$. To do this, for every proof $\pi\in\{0,1\}^{\le l}$ and every possible outcome of the random coins $w\in\{0,1\}^r$, simulate $V^{\pi}(x,w)$ and count the number of $w$'s who caused $V^\pi$ to accept. Note that this requires only polynomial time in $|x|$. Now, accept $x$ iff during this process you have found a proof $\pi$ which causes $V$ to accept $x$ with probability $1$.

Note that the constant bound on the proof length does not immediately follow from the definition (in the above you only have a constant bound on the number of queries), but follows from the fact that if $L\in PCP(r(n),q(n))$, then $L$ has proofs of length $\le 2^{r(n)}q(n)$. See this question for details.


How to prove that this defined language is regular? Suppose that $L$ is a regular language and $0<\alpha<1$ and $\alpha \in Q$. Define $L_\alpha$ as

$$L_\alpha = \{\omega \in \Sigma^* \mid \exists \omega_1 \in  \Sigma^* .\omega\omega_1 \in L,\frac{|\omega|}{|\omega\omega_1|}=\alpha\}$$

How do I prove that $L_\alpha$ is regular?

Here is my attempt. If we assume that $D$ is the automaton that recognize $L$ with $Q=\{q_0,...,q_n\}$, if $\delta(q_0,\omega\omega_1)\in F$ and $\delta(q_0,\omega)=q_i$  we can define  $D_1$ such that $\delta_1(q_0,\omega)=r_{i-1}$ (for $r_i \in F_1)$, but the problem is I can't define $\delta_1(q_0,a) $for $a\in \Sigma$.

Try proving it for $\alpha = 1/2$ first.  Construct a non-deterministic automaton that recognizes $L_\alpha$.  Before you start reading in the string $w$, guess something about where you will be in the future.  What would you like to guess?  What would help you?