Writing a program to find polynomial $f(x)$ from $f(1)$ and $f(f(1))$ Let $f(x)=a_0+a_1x+a_2x^2+\dots+a_nx^n$, where $a_i\ge0$ and $a_i$ is integer.

Given $f(1)=p$ and $f(f(1))=q$, we have to find $a_0$, $a_1$, $a_2$, $a_3$, $\dots$, $a_n$, where such $f(x)$ exists. Or we have to confirm if such $f(x)$ exists or if the polynomial is ambiguous e.g. for $p=1$ and $q=2$, no such $f(x)$ exists but for $p=1$ and $q=1$, $f(x)=1$, $f(x)=x^2$ both can be solution.

I have to write a program to do that. What should be my procedure?

The conditions $f(1) = p$ and $f(p) = q$ imply the following two equations:
$$
\begin{align}
&\sum_{i=0}^n a_i = p, \\
&\sum_{i=0}^n a_i p^i = q.
\end{align}
$$
When $p < 0$ or $p$ is not an integer, there are no solutions. When $p = 0$, the first equation implies that the polynomial must be $0$ and so $q = 0$.
When $p = 1$, the equations imply that $p = q$, and the first equation implies that the solutions are the polynomials $1,x,\ldots,x^n$. From now on, we assume that $p \geq 2$.

Intuitively, the polynomial minimizing $\sum_i a_i$ under the second constraint above is obtained by writing $q$ in base $p$ notation (first $n$ digits) and putting the rest as a coefficient of $a_n$. Denote this solution by $b_0,\ldots,b_n$. If $\sum_i b_i > p$ then there is no solution. If $\sum_i b_i = p$ then we have found the unique solution. From now on, suppose that $\sum_i b_i < p$; this implies that the base $p$ expansion of $q$ has length at most $n+1$.

The given equations imply more constraints. First of all, $q \geq p$. Second, since $p \equiv 1 \pmod{p-1}$, we must have $q \equiv p \pmod{p-1}$. Starting with the polynomial $g(x) = \sum_{i=0}^n b_i x^i$, we can increase $g(1)$ by applying the update $(b'_{i+1},b'_i) \gets (b_{i+1} - \alpha,b_i + p\alpha)$ (when $b_{i+1} \geq \alpha$); this increases $g(1)$ by $\alpha(p-1)$. We can apply these updates systematically, moving the mass all the way to the polynomial $q$. Since $\sum_i b_i < p \leq q$ and $q \equiv p \pmod{p-1}$, somewhere along the way we will find a (unique) polynomial satisfying both requirements above.

How do we perform this process algorithmically? We go over the indices from $b_n$ to $b_1$ in order. At each point, we subtract from $b_i$ the maximal amount $\alpha$ which keeps the invariant $g(1) \leq p$. After processing $b_1$, we should reach the desired polynomial. (We are basically looking at the base $p-1$ expansion of $p - g(1)$.)


Traversing a graph in finite time, maximizing utility I am working on a problem in robotics, where we have a problem of having finite time horizon T, and a set of actions. Each take some time to perform and each have a utility. We can transition from any action to another after completing that particular action, and each transition takes a unique, finite time. Our goal is maximize the sum of the utilities after the time horizon has ended.

I am currently thinking of this as a graph problem, and have some trouble formalizing it.

Let the nodes be the actions, and the edges be the transition between the actions. Each node have some value, and take some time T. How do I find the path in this graph which maximizes the utility, and takes time less than or equal to T?

I think this is the knapsack problem, with the following correspondences:

item: activity
item weight: activity performance time
item value: activity utility
knapsack maximum weight: finite time horizon T

One solves it using dynamic programming.

(I don't think a graph model would be useful here, as it does not seem easy to encode the problem into a standard graph problem.)


Is there a "natural" undecidable language? Is there any "natural" language which is undecidable?

by "natural" I mean a language defined directly by properties of strings, and not via machines and their equivalent. In other words, if the language looks like
$$ L = \{ \langle M \rangle \mid \ldots \}$$
where $M$ is a TM, DFA (or regular-exp), PDA (or grammar), etc.., then $L$ is not natural. However $L = \{xy \ldots \mid x \text{ is a prefix of y} \ldots \}$ is natural.

Since you wanted "strings", I mention the classic one: Post Correspondence Problem.


Can a finite automaton have more than one regular expression? A finite automaton is a generator for a regular language, and a regular expression represents a regular language. A language can be represented in many forms of regular expressions.
So can a finite automaton have more than one regular expression?

There are multiple ways of writing the same expression, then I guess yes, it can be represented by many expressions.

For example, look at this DFA (with the initial state being final)

-->(a)________
    ^         |
    |         |
    |         V
    '--------(b)

the regular expression for it can take infinite forms, such as

$(ab)^*\;$ or $\;(ab)^*(ab)^*\;$ or $\;(ab)^*(ab)^*(ab)^*\;$ ...

If you consider different forms of the same expression, then it can be represented by lots of regexs, otherwise is just 1.


Big Oh rules - How to argue in case of negative base Let us say you have a function $C_n = (-2)^n + 2^n$.
It would seem that it would be correct to assume that the running time of this algorithm would be $O(2^n)$.
However, how would I go about arguing this? The rule I had in mind would be that $a^n$ is $O(b^n)$ if $0 < a \leq b$. But since $a$ is $< 0$, this rule cannot be applied. How would one argue the relevancy of the roots in cases like this, where the specific conditions do not hold up?

If $C_n = -2^n + 2^n$, then this just simplifies to $C_n = 0$, so I assume that you mean $C_n = (-2)^n + 2^n$. Then:
$$
C_n \le |-2|^n + 2^n = 2^{n+1} = O(2^n).
$$


Recursive Call Inside Argument List (C++) So, my professor asked me to implement recursion in different ways to compute $a^n$ (a and n being integers) and rank them according to their space efficiency. Now, here is one of the methods I came up with:

  int Power (int a, int n)
 { if ( n == 0 )
  return 1;
   if ( n % 2 == 0)
  return Power(Power(a, n/2), 2);
   else return Power(Power(a, n/2), 2)*a;
  }

The code compiles well, but leads to a segmentation fault. On debugging, I came to the conclusion that recursive call within the argument list is not acceptable. That is, something like

  return Power(Power(a, n/2), 2)

or

  int m = Power(a, n/2);
  return Power(m, 2);

is not allowed but

  int m = Power(a, n/2);
  return m*m;

is allowed. Why is this the case? Is this true only in C++, or is it a general phenomenon?

So I did a dry run of the algorithm as suggested by greybeard in the comments. It turns out that for any a and n, after a certain number of recursions, one ends up getting Power(1, 2). This leads to an infinite recursion because Power(1, 2) also leads to Power (1, 2) after a certain number of recursions.


Recurrence relations that do not have a closed form solution A recurrence relation computes value $d_n$ with the $\{d_{i},d_{j}\ldots\}$ previous digits of the sequence

So for example, the Fibonacci sequence is defined as follows:
$$
F_n = F_{n-1}+F_{n-2},\ \ \ F_0=0, F_1=1
$$
The classic closed form solution is given by the Binet formula:
$$
F_n = \frac{\phi^n-\psi^n}{\sqrt{5}}
$$
where $\phi=\frac{1+\sqrt{5}}{2}$ and $\psi=1-\phi$.

The question is: are there such sequence of digits defined through some arbitrary recurrence relation that do not have a closed form solution, that is, that provably do not have a closed form solution?

I am asking this question in CS stack exchange because the context of this question is Random Number Generation... If such iterated sequences exist, this could be (could be) helpful in designing RNG's...

Yes, there are. Consider the recurrence $a_{n+1}=(7a_n/4 + 1/2) - (5a_n/4 + 1/2)(-1)^{a_n}$ where $a_0$ is a given integer value. It is well known that this gives the Collatz sequence. There is no "known" closed form solution to the recurrence (and if you find it, you would be quite famous in mathematical circles). Furthermore, it is also well known that there are recurrent sequences that can't be solved in closed form. For instance, Conway shows that a natural generalization of the Collatz problem is undecidable. On the other hand, there are large classes of recurrence relations for which methods are known to determine closed form solutions in terms of sometimes multiple finite or infinite sums. Hypergeometric functions can be used to solve large classes of them. For instance, in theory, all linear recurrences with polynomial coefficients can be solved. More information can be found in Solving Linear Recurrence Equations with
Polynomial Coefficients by Petkovsek and Zakrajsek (PDF).


Which of the following expressions is TRUE if and only if NOT all three variables a, b, and c have the same value? I am trying to solve this problem and I am stuck. I think it is B, but I think I'm wrong. Thanks.

Which of the following expressions is TRUE if and only if NOT all three variables a, b, and c have the same value?

A.  a != b || b != c

B. (a == b || b == c || a == c)

C. a >=b && b >= c && c >= a

D. a > b || b > c || a > c

E. a != b && b != c

My teacher:

This kind of tricky wording is to be expected the AP Exam. The phrase "have the same value" we can take to mean equal. Now, "not all three equal" does not mean "all three different", it means at least one is different. So let's use the test case {a=0, b=0, c=1}

! (a == b || b == c || a == c)

! (0 == 0 || 0 == 1 || 0 == 1)

! (true or false or false)

! (true)

false

a > b || b > c || a > c

0 > 0 || 0 > 1 || 0 > 1

false || false || false

false

a >=b && b >= c && c >= a

0 >=0 && 0 >= 1 && 1 >= 0

true && false && true

false

a != b && b != c

0 != 0 && 0 != 1

false && true

false

0 != 0 || 0 != 1

false || true

true

When you think about it logically, given three things, one of them has to be not equal to one of the other two in order for all three of them to not be the same.

Thus the correct answer is A.


In an Inverted Page Table, will following chains happen very often for small addresses? I just learned about the Inverted Page Table and immediately thought about the chaining model used.
If two processes use the same virtual address, resolving the address will have to include following the chaining information in the table.

If all memory addresses were used uniformly, that should not be a problem, since address collisions would happen seldomly.

But if many processes use the first page (because they usually start using small addresses) will that not deteriorate performance on a real system a lot?

According to my knowledge, inverted page table has an entry for each physical frame, not for each logical page.

It is usually designed as a Hash table, where the Hash function takes both the task id and the page number as parameters. Thus (task A, address X) and (task B, address X) will not be likely to produce the same Hash value.

Does that answer your question?


RSA Decryption from Simple Public Key Values I'm a little stuck trying to figure out how to decrypt some messages and could use some hints as to what I may be doing wrong.

I was given a series of integer values that make up my cipher text. Here are just a few of them:

6584 15650 16198 11003

I was given the following public key b = 3001 n = 18209

So to encrypt a message M, you would use the formula:

C = M^3001 mod 18209

I understand to encrypt, I need to find a 'd' value that satisfies:

bd = 1 mod 18209

3001d = 1 mod 18209

Any hints on a technique or algorithm to help me find a suitable value for 'd'?

If you want to decode a message encoded with RSA, you need to get the private key. The "simplest" method is to find the primes $p,q$ with $n=p\cdot q$.

In your case, $n=18209$ is the product of the primes $131$ and $139$. Now, you can follow the value of Euler's phi function for $n$, which is $\varphi(18209)=130\cdot138=17940$.

The private key $d$ suffices the following equation

$b\cdot d\equiv 1\mod\varphi(n)$.

To get $d$ with this property, you can use the extended euclidean algorithm for $b$ and $\varphi(n)$, which produces $x$ and $y$ with

$1=x\cdot b+y\cdot\varphi(n)$

Now, the value $x$ is your private key $d$. In your case, I get $d=4621$.
To finally decode the message $m$, you have to compute

$m^d\mod n$


Are there any examples of programming synthesis in vulnerability research? Program Synthesis

To borrow from Microsoft:

  Program synthesis is the task of automatically discovering an executable piece of code given user intent expressed using various forms of constraints such as input-output examples, demonstrations, natural language, etc.

One of the best program synthesis examples I've come across created new authenticated encryption (AE) schemes; the paper also automated the analysis and privacy and authenticity security proofs for the synthesized AE schemes.

The take-away from program synthesis is: (1) it can provide novel solutions to solve a problem through an automated process and (2) it is possible to verify the solution's correctness.

Vulnerability Research & Program Synthesis

There has been a great deal of effort made in recent years in automating vulnerability analysis.  A culmination of this effort was demonstrated this summer at the Cyber Grand Challenge(https:// www. cybergrandchallenge.com/).

It would seem like program synthesis would have great potential in automated vulnerability research.

Perhaps it could derive new exploits
Perhaps it could derive new patches or tests

My question is this: Are there any examples of program synthesis in vulnerability research?

I am having a hard time finding any examples of such and I would like to know if anyone has come across it.

Yes, there's plenty of work on synthesizing exploits using program synthesis.  One of the seminal papers was:

Thanassis Avgerinos, Sang Kil Cha, Alexandre Rebert, Edward J. Schwartz, Maverick Woo, and David Brumley. Automatic Exploit Generation. Communications of the ACM, 57(2):74–84, 2014.

This is a cleaned-up and general-audience version of a paper published at NDSS in 2011.

You should be able to use Google Scholar to find lots of other related work and follow-on work, by finding papers that cite it.  Also, many of the research teams participating in the Cyber Grand Challenge have been publishing on this subject for the past several years; look up each of their web pages and go check out their papers, and you should be able to find more.

Generally speaking, the challenge typically lies more in finding inputs to a vulnerable program that will cause it to do something bad, rather than in finding programs that directly do something bad themselves.  Thus, the techniques tend to be slightly different from standard work on program synthesis, because the challenges are slightly different in this space: here it's often more about synthesizing data rather than code.

There is also plenty of work on automated patch creation.  There, the big challenge is usually identifying which part of the code is vulnerable and what the vulnerability is; once you know that, the patch synthesis is usually rather straightforward.  Consequently, the challenge typically seems to be more about program analysis than synthesis, though of course there are certainly aspects of both that do need to be solved, and different papers have a different focus.


How does the CPU know to get data from or send data to a peripheral device? We were talking today, in Intro to Programming, about machine language. I know it's a bunch of 0's and 1's. Let's say I compile the following C++ program on an x86 machine:

 #include <string>
 #include <iostream>
using namespace std;
int main()
{
cout << "Enter something";
string input;
cin >> input;
return 0;
}

Now, cin - as I understand - is an input stream. The computer gets input from the keyboard and places it in cin to be read by the program. My question is, how does the CPU know it's supposed to get input from the keyboard when, at the end of the day, the program is just 1's and 0's?

My understanding is that the machine code is kind of broken up.

Keyboard input is handled through an interrupt – a signal sent to the CPU by the motherboard in response to your pressing a key. The CPU maintains a table of functions to call for each type of interrupt, and the operating system sets this so that control passes to it whenever a key is pressed.

The operating system maintains a buffer of pressed keys, and passes on this event to the software currently capturing the keyboard (if any), causing the call of an event handler set by the piece of software. If you run your program from a terminal, then the terminal is the relevant piece of software. It stores the keystrokes in its own buffer, which the C standard library has access to. (In terminal-based operating systems such as DOS or a Unix shell, this is handled by a system call, which is a function executed by the operating system.) The C++ iostream library, which is what your program actually uses, is a wrapper of the C standard library.


Context-free Languages closed under Reversal In class this week we've been learning about the CFLs and their closure properties. I've seen proofs for union, intersection and compliment but for reversal my lecturer just said its closed. I wanted to see the proof so I've been searching for the past few days but all I've found is most people just say that to reverse the productions is enough to prove it. Those that do go a little more formal just state there is an easy inductive proof you can give. Can anyone provide me with some more information/hints about the inductive proof? Try as I might I can't come up with it.

Your sources are right, and I am afraid there is only little to add, except formalism. I denote the reverse (mirror) of string $w$ by $w^R$.

If $G$ is a grammar, let $H$ be its reversed, so for production $A\to w$ in $G$ we have $A\to w^R$ in $H$.

Then by induction we show that $A\Rightarrow_G^*w$ iff $A\Rightarrow_H^*w^R$.

(basis) In zero steps we have  $A\Rightarrow_G^0 A$ iff $A\Rightarrow_H^0 A$.
(induction) Assuming
$A\Rightarrow_G^*w_1Bw_2$ iff $A\Rightarrow_H^*w_2^RBw_1^R$ we can apply any production $B\to u$ in $G$ (and in $H$ in reverse) and obtain $A\Rightarrow_G^*w_1uw_2$ and $A\Rightarrow_H^*w_2^Ru^Rw_1^R$ respectively, where indeed $w_2^Ru^Rw_1^R$ is the reverse of $w_1uw_2$.

This is a very condensed proof, but contains all necessary ingredients. Again, a derivation of the reverse grammar is the reverse of the original one. This is especially clear when looking at the two derivation trees.


Finding the dichotomy that maximizes information gain for a classifier? Suppose that $\Omega$ is a finite probability space,with measure $P$ (we can take $P$ uniform). Let $C \in \{\pm 1 \}$ be a random variable on $\Omega$, the classifier. Let

$$H(C) = H(C, \Omega, P) = \sum_{i \in \pm 1} P(C = i) \log P(C = i)$$

be the entropy of $C$.

For a random variable $Y$ on $\Omega$ and $r \in \mathbb{R}$, define the level set $\{Y = r\} = V_r$, and define

$$H(C | Y) = \Sigma_{r \in \mathbb{R}} P(Y = r) H(C|_{V_r}, V_r, P_{V_r})$$

where $P_{V_r}(B) = P(B \cap V_r) / P(V_r)$ is a measure on $V_r$. $H(C|_{V_r}, V_r, P_{V_r})$ is the entropy of the random variable restricted to the the subset $V_r$, with the conditional probability measure.

As in a decision tree classifier, I want to determine the subset $A \subset \Omega$ that maximizes $H(C) - H(C|1_A)$. That is, I want to maximize the information gain. What is the "best" algorithm for doing so? What is the complexity of this question? Are there good probabilistic algorithms ?

Some computation allows one to reformulate this as finding the subset $A$ that maximizes

$$\sum_e \sum_{i = \pm 1} P(C^i \cap A^e) \log(P(C^i \cap A^e)) + \sum_e P(A^e) \log P(A^e),$$

provided we let $A^e$ mean $A$ or $A^c$, and $C^i = \{C = i\}$.

As in the discussion, there are too many "features" for this to be in interesting question. In particular, letting $A = C^{-1}(1)$, the set of positive examples, then $H(C|A) = H(C|C) = 0$ so information gain is $H(C)$, which is maximal.

This is obvious in retrospect, in order to decrease the entropy maximally, make $C$ deterministic on $A$ and $A^c$.

For decision trees, the point is that we have a limited collection of features, specifically excluding C, to split our data set around.


Space complexity of breadth-first search I read that breadth-first search has to store (at most) $1+b+b^2+···+b^d$
nodes in memory ---more than depth-first search---, where $d$ is the depth of a solution, and $b$ is the branching factor.

Why isn't it $b^d$?

Why are $1+b+b^2+···+b^{d-1}$ (the previously searched depths) maintained in memory?

If it's a matter of completeness, then (a complete implementation of) DFS would suffer from the same problem.

That's not entirely correct Tobi. Breadth-First search requires to store in memory only those nodes awaiting for expansion. Thus, it only requires to store in memory $b^d$ nodes in the worst case, i.e., if the solution is found at the rightmost child at depth $d$. That is the number of nodes required to be stored in memory because when the solution is found at depth $d$, that is precisely the number of nodes awaiting for expansion.

Indeed! You could actually remove any node after expanding it. So far, you are correct when you are guessing that you could actually remove all nodes expanded in the previous depths whose sum gets so far as $b^0+b^1+b^2+b^3+...+b^{d-1}$. Now, here comes the question:

Why would you do it? Why would you actually remove those nodes? If you do not remove them, you could easily implement a duplicate detection mechanism: if a node $n$ is found at depth $d_1$ it is stored in memory. If it is found again at depth $d_2$, $d_2>d_1$ then its expansion can be skipped because a shortest path to it was already found ---given that the edge costs are all the same.
Oh yeah! you might be thinking that this idea is not worthy as it requires to store in memory a rather large number of nodes: $b^0+b^1+b^2+...b^{d-1}$, isn't it? So that while duplicate detection seems desirable it might be too costly.

Note however that the sum of the terms of the geometric progression $b^0+b^1+b^2+...+b^{d-1}$ equals $\frac{b^d-1}{b-1}$ so that adding duplicate detection requires only a small fraction ($b-1$) of the nodes actually required to be stored in memory ($b^d$).

In other words, we say that the memory requirements of Breadth-First Search are dominated by the number of nodes awaiting to be expanded, $b^d$. Additional memory can be used as the total number of nodes in memory, $b^d+\frac{b^d-1}{b-1}=\frac{b^{d+1}-1}{b-1}$ (in case that duplicate detection is implemented), is much smaller than the number of nodes required to store the nodes in the subsequent level, $b^{d+1}$.

Test these numbers, even if $b=2$, note that with duplicate detection, the number of nodes in memory is $2^{d+1}-1$ which is smaller than $2^{d+1}$, the number of nodes required to store in memory for exploring an additional level without duplicate detection. The situation worsens significantly if you consider larger branching factors. For example, with $b=10$, the number of nodes required with duplicate detection is $\frac{10^{d+1}-1}{9}$, which is only 11% of the nodes required to be stored in memory for exploring the subsequent depth without duplicate detection, $10^{d+1}$ ...

Hope this helps,


Which Data Structure should I use to store words from a novel? So, I was learning Data Structures in Java on my own. And there was a "challenge question" in the book.
The question basically asked me to make a data structure that could store all the words in a novel, and then it would associate with the word, where it occurs (like line number and character count) and the frequency of the amount of times it occurs.
I was wondering which data structure should I use to store all this while maintaining a relatively Fast look up time and such.

I was thinking either hashmaps or tries, but I don't know which trie to use and how to associate the frequency of the word and stuff

Thanks in advance!

You will probably end up using two nested data structures. I would use a hashmap with the words as keys. The value would be an array/list/set (depending on what you want to do with the occurrence data) containing an item for each occurrence of the word. The item would store whatever you needed (line number, etc). The number of occurrences would just be the size of this array/list/set.


Why is the carry of any n base system equal to the radix in arithmetic? In binary the carry/borrow is 2, in hex the carry is 16. What's the reason for this?

Background
Writing a number in base $r$ means to write it in the form
$$a_0+a_1r+a_2r^2+\ldots+a_nr^n$$
where $0\leq a_i< r$, for all $i=0,1,\ldots,n$. The positional notation that we use consists in just writing the digits $a_i$ from right to left
$$(a_na_{n-1}\ldots a_2a_1a_0)_r$$
Some people write parentheses and maybe the radix as a subscript. Some people write a bar over the digits, and in the decimal positional system, which is the most popular, we just write the digits.
You can think of the digits as buckets that can only be filled up to the value $r-1$.
The carry actually depends on the position of the digit, only that when you compute you imagine that it is the degree zero position, the units. Actually, when you are inside algorithms like adding or converting numbers from one radix to another in each iteration you have already divided enough by $r$ such that the digit that you are treating has become the degree zero position or you are treating it as such.
The carry at the $k$-th position
For example, suppose that you are looking at position $k$ and the digits at that position and the one that follows are
$$a_kr^k+a_{k+1}r^{k+1}$$
You can divide by $r^k$ to get $a_k+a_{k+1}r$, which implicitly is what happened if we just write the two digits $(a_ka_{k+1})_r$.
Now, the maximum carry will happen when $a_k$ is as full as it can be and we add to it the maximum digit that we can add. This is $a_k=r-1$ and we add $r-1$. Then we get
$$\begin{align}
(a_k+a_{k+1}r)+(r-1)&=(r-1)+a_{k+1}r+(r-1)\\
&=(r-2)+\mathbf{r}+a_{k+1}r\\
&=(r-2)+(a_{k+1}+1)r
\end{align}$$
As you can see, it is $\mathbf{r}$ the amount that we have to move out of the $k$-th position to re-write the number as a sum of powers of $r$ in which the coefficients are all between $0$ and $r-1$. Well, it is really $r\cdot r^k$, because we divided by $r^k$. In terms of the contribution to the next ($k+1$-th) digit the carry contributes $1$, when carry over happens. Otherwise it contributes $0$ to the next digit.
Potentially, $a_{k+1}+1$ is larger than $r-1$, so $(a_{k+1}+1)r$ will have to spit out an $r^2$ (actually $r^2\cdot r^k$), but well that's the carry generated by the $(k+1)$-th position.


Is the languague L={, M accepts a finite amount of words} decdidable? Is $L=\{<M> | L(M) \ is \ finite\} $ decidable ? M is a TM.
I think its relative simple to proof with the theorem of rice. But I am interested in a solution which does not use the Rice theorem.
This my try  :
Let f(<m,w>) be a function which works in the following way :

Run w on M
If M accepts Construct a TM Mwhich accepts only the word w and return M
If M rejects Construct a TM Mwhich accepts everything. Return M

So if m is in $A_{TM}= \{<M,w>|M \ accepts \ w\}$ we know that f(<m,w>) is in L. If m is not in A then we know that f(<m,w>) does accept every word and therefore infinity words. So f(<m,w>) not in L.
Is this a correct mapping reduction ?

The function you defined is not a reduction at all - it may not even stop!
The problem is running $m$ on $w$: can you be sure $m$ wont be stuck in an infinite loop on $w$? you can't.
You can define a proper reduction as follows: (on input $<m,w>$)
Create the machine $M_{m,w}$that does the following algorithm, and return in: (on input $s$)

Emulate $m$ on $w$ for $|s|$ steps. If $m$ halted in that time, reject $s$. Otherwise, accept $s$.

I will leave it for you to prove this is a proper reduction from $H_{TM}$ to $L$ (its a good exercise!)


How to find the number of Binary Search Trees with given number of nodes and leaves? With 7 nodes of distinct values (unique), how many Binary search trees (BST) can be formed such that:

Exactly $1$ leaf node(s) present?
Exactly $2$ leaf nodes present?

I was able to solve the first one(and the actual problem was also that, but then I though what if the process can be extended)

  Here's my take on the 1st one

Here the elements are  $1,2,3,4,5,6,7$ (let's assume that for simplicity) and we need only $1$ leaf

So let us fix a root node: To fix the root node we have $2$choice either $1$ or $7$ from  $1,2,3,4,5,6,7$
(if we select any non-extreme elements then only $1$ leaf is not possible)
Let us say we select $1$ as root node
In each and every level we have $2$ different option that is to select i,e; either of extreme elements
So in 2nd level we can select $2,3,4,5,6,7$
Let us say we select $7$ in 2nd level
We still have 2 option to select in $2,3,4,5,6$
So this is true in all levels except last level since only $1$ element is left.
Therefore, total possibilities are : $2 * 2 * 2 * 2 * 2$ = $2^5$

The same condition is true for $7$ as a root

Hence, $2^5* 2$ (1 as root or 7 as root)  =  $2^6$.

(Which comes out as $2^{number of nodes -1}$)

But how can we now approach the second subpart or it can be generalized for let's say (2,3,4) leaf nodes?

Exactly 2 leaf nodes present?

You can compute the numbers with dynamic programming.

Let $c(n,l)$ be the number of BSTs with $n$ nodes and $l$ leaves, where the nodes are selected from a set of $n$ distinct nodes. Then we have the following recurrence relation in general cases,

$$c(n,l) = \sum_{i=0}^{n-1}\sum_{j=0}^l c(i,j)\cdot c(n-i-1, l-j)$$

The outer summation is over $i$, the number of nodes in the left sub-BST of a BST with $n$ nodes and $l$ leaves.
The inner summation is over $j$, the number of leaves in the the left sub-BST of $i$ nodes.
The product $c(i,j)\cdot c(n-i-1, l-j)$ is the number of BSTs whose left sub-BST has $i$ nodes and $j$ leaves and whose right sub-BST has $n-i-1$ nodes and $l-j$ leaves. Please note that the root of such BST has only one choice, namely, the $(i+1)^{th}$ smallest node.

I will let you figure out the boundary values of $c(n,l)$ such as when $n=0$ or $n=1$ or $l=0$. There might be a few different cases. However, this should be enough to point you to the right direction.


Reframing decision, counting, enumeration, and search as optimization The top accepted answers to the questions below allude to two complexity classes of optimization problems:  NPO and PO (in relation to NP and P for decision problems):

Decision problems vs "real" problems that aren't yes-or-no
Optimization version of decision problems
“NP-complete” optimization problems

The way these questions and answers are written, I get the impression that many problems such as counting, enumeration, or searching problems could be framed as general optimization problems even if their formulation does not have an explicit objective function (i.e. mathematical programming problems). Is that correct?

Take decision problems for example, one often casts decisions in machine learning (ML) as those that minimize regret, or e.g. an expected error in the evaluation against a loss function (e.g. 0/1 for decision problems).

These types of decisions or search as-optimization formulations for a wide variety of problems are fairly ubiquitous in ML.

Take some other common examples:

Find the $n$th Fibonacci term
Find the GCD of a set of numbers
Enumerate the subsets for which 3SUM answers "Yes"
Count all hamiltonian cycles in a graph
etc.

Couldn't one easily reframe many of them as optimization problems using a loss function as well? e.g. $\text{argmin}_x f(x)$, where $f$ is a measure of error defined on the solution space of the desired problem? Or is that reduction, despite its prevalence in e.g. ML, not always "easy", feasible or useful?

More generally, how does the family of complexity classes (and their associated types of reductions and definitions) for search, enumeration and counting relate to the family of their "reduction-equivalent" optimization problems?

Search problems are in NP if you can verify a solution in polynomial time.

Counting problems are ♯P if you're counting the number of solutions to an NP search problem.

Enumeration problems are not particularly special.

See https://en.wikipedia.org/wiki/Computational_problem.


Allocating n processes to n servers, counting from the server perspective In this question, I asked about a confusion I had counting the size of the sample space for allocation of n processes to n servers. Bangye gave a simple answer by approaching the counting problem from the perspective of the choice when allocating each process.

I'd like to know -- to expand my understanding of counting -- how we might count in a different way, from the server perspective: assigning each server to some number of processes.

The obvious problem I see is if I have already allocated one process to a server, I then can't allocate it to another, and so the analysis becomes complicated -- each server-based count is dependent on all other server-based counts.

Is this a common problem, and there's actually a heuristic to know which way to count things?

The heuristic is: "try both ways, and see which works".  As you get more practice you might start to develop a sixth sense about which one to try first, but that's the most useful principle I can suggest.

The general mathematical principle is the bijection principle.  If you have two finite sets $S,T$ and you can find a bijection between $S$ and $T$, then they must have the same size.  So, if you can count the number of elements in either of them, you can infer the number of elements in the other one.


Why does linear search have $\frac{n}{2}$ comparisons on average? I'm reading the Wikipedia page on Linear Search and it is mentioned that there are on average $\frac{n}{2}$ comparisons.

I tried working this out on my own.

First I considered the number of cases. There are $n$ cases corresponding to when the target value is the $1$st, $2$nd, ..., $n$th entry of the list. There is also the case where the entry is not in the list at all, so we have $n + 1$ cases.

Next I consider the individual number of comparisons needed per case. For the cases where the target value is in the list, we need $1, 2, \dots, n$ comparisons respectively. For the case where the target value is not in the list, we need $n$ comparisons (after which the search terminates and concludes with a return value of NIL).

Finally, I sum up the individual number of comparisons to get the total number of comparisons, and divide by the number of cases to get average number of comparisons. I get

$$\frac{1 + 2 + \dots + n + n}{n + 1} = \frac{n^2 + 3n}{2n + 2}$$

which is different from $\frac{n}{2}$.

May I where is the fallacy in my reasoning? Thank you!

Let us assume that required element is equally likely to be in any position between $1$ and $n$. Let $x _i $ be a random variable. Random variable $x_i = 1$ means required element is in ith position and vice-versa. Now probability that required element is in position between $1$ and $n$ is $$ Pr[x_i = 1] = \frac{1}{n}$$ Now Expected value is given by $$\mathbb{E}(x) = 1 \times\frac{1}{n} + 2 \times \frac{1}{n} + 3 \times \frac{1}{n} +\cdots + n \times\frac{1}{n} $$ which can be written as
$$\mathbb{E}(x) =  \frac{n(n+1)}{2n} = \frac{(n+1)}{2}$$
which is a required answer

Reference : https://www.macs.hw.ac.uk/~pjbk/pathways/cpp2/node56.html


Finding the shortest path for synchronized pawns in a maze I have been trying to wrap my head around this problem, and I just can't get it.

We have an $a \times b$ matrix where every cell corresponds to either an empty space, denoted with a dot, or a wall, denoted with $X$.
There are two pawns in different locations within the maze, their movements are synchronized and they must leave the maze (it has multiple exits) in the same move.
If one moves and the other is up against a wall, it's a valid move and the other one stays in place.
The goal is to write an algorithm that finds the lowest possible moves to get both out of the maze at the same time, of time complexity $\mathcal O(a^2 b^2)$.

I got some advice to use BFS for this problem, but I don't get how it would deal with all of the backtracking that has to be done. I've included two visualizations with the correct paths labeled to help explain the problem.

Example 1: Pawn starting positions shown as blue squares

Example 2: Pawn starting position shown as blue square and red square

I am going to take a guess that you are having trouble with understanding how BFS will work on this game. First, you may wonder "what is the graph we are searching on?" Let's first start with, you are not searching through the game board. This is not what you are doing at all.

How to represent Game State

You are search through game states. I am using game state to mean:

  Game state - a full and unique description of all pieces/players in the game at the start of any "turn" during the duration of game play. A game state is final when pieces are in a position that satisfies the termination constraint.

Termination constraint as you have define is when two pawns are both able to leave the grid with the same move. You could alternatively define it as a state right after this move has been made.

Here are some examples of game states that can be uniquely describe by a $3 \times 8$ matrix $G$ where we make each entry either: Red, Blue, White, or Black.:

We would have $G_{1,1} = \text{Blue}$ and $G_{1,4} = \text{Red}$ and assign the rest of $G_{i,j}$ appropriately.

We would have $G_{0,1} = \text{Blue}$ and $G_{1,3} = \text{Red}$ and assign the rest of $G_{i,j}$ appropriately.

We would have $G_{0,6} = \text{Blue}$ and $G_{1,1} = \text{Red}$ and assign the rest of $G_{i,j}$ appropriately.

One important thing to note here is that the only thing changing in these game states is the location of Red and Blue, everything else stays the same. This should give you some indication that we only need to maintain the location of Red and Blue to get a unique description of the game state. With this idea, we can represent all three of the prior games states as:

$\text{Blue} = (1,1)$ and $\text{Red} = (1,4)$
$\text{Blue} = (0,1)$ and $\text{Red} = (1,3)$
$\text{Blue} = (0,6)$ and $\text{Red} = (1,1)$

To be concise I will represent them as pairs of coordinates:

State = $[(1,1), (1,4)]$.
State = $[(0,1), (1,3)]$.
State = $[(0,6), (1,1)]$.

Another important thing to note here, is that the states do not need to be "possible" in the sense that we can always reach them from our initial state. The purpose of using these states is so that we can create a graph to BFS.

Graph Representation of Game States

To be able to properly "search" through the game states, we will make each state a node in our abstract graph. We will add an edge from state $s_1$ to state $s_2$ if we can get from state $s_1$ to state $s_2$ by moving both players either Up, Down, Left, or Right. Using our first example:

State $[(1,1), (1,4)]$ can move to:

State $[(0,1), (1,4)]$ via the Up move.
State $[(1,0), (1,3)]$ via the Left move.
State $[(1,1), (1,4)]$ via the Down move.
State $[(1,2), (1,5)]$ via the Right move.

So in a graph it would look like this:

How to BFS Game States

We will be looking for the shortest sequence of moves such that we reach a final state. For instance, $[(0,1), (0,6)]$ would be a final state because they can both move Up to leave the grid. One option would be to create the entire graph, then run the BFS from our start node. However, this can be costly. We can instead generate nodes adjacent to our current node on demand. We can also check if we reach a final state on demand. We need to also make sure we cannot visit "invalid" board states. For instance $[(-1,1),(1,4)]$ would be invalid because "-1" is outside our bounds. $[(0,0), (1,4)]$ would also be invalid because $G_{0,0}$ is a black square and we cannot move there.

This should be enough information to get you started. I will leave the analysis up to you. A hint on the analysis would be to consider how many game states are possible as we know in the worst cases we may visit each and all of them.


Usefulness of Differential Geometry I recently came across these books:

Differential Geometry and Lie Groups: A Computational Perspective
Differential Geometry and Lie Groups: A Second Course

Their subject matter really intrigues me, as I really enjoy topology/geometry/analysis, but had not planned to pursue them since I also want to work in an area with very concrete application. However, I am skeptical. At one point I thought topological data analysis (TDA) was the perfect marriage of my interests, but I have found very little evidence of that field actually being used in computer science, much less in industrial or otherwise more 'practical' settings. It seems like TDA makes mathematicians feel more relevant to the data science world, but I'm not convinced that it makes them so (feel free to contradict me if you think I'm wrong on this point, but note that I want a concrete use case, not an abstract argument about its relevance). I have similar stories about coding theory, certain aspects of set theory, etcetera. They may have theoretical relevance, but is there any situation where, in the process of developing software, one might need to consult theses fields? I don't know of any.
So now my question: is there any practical field of computer science that makes advanced use of differential geometry? Medical imaging, other imaging, computer graphics, virtual reality, and some other fields come to mind as potential application areas. In my (admittedly limited) experience, however, these areas seem to use basic 3D geometry, numerical linear algebra, and sometimes numerical analysis of PDEs. Those are all very nice topics, but they do not require anything as abstract as differential geometry.
Thanks in advance.

If you found Structure and Interpretation of Computer Programs interesting, you might like Functional Differential Geometry (It's from the same authors) .

Differential geometry is deceptively simple. It is surprisingly easy to get the right answer with unclear and informal symbol manipulation.  To address this problem we use computer programs to communicate a precise understanding of the computations in differential geometry.  Expressing the methods of differential geometry in a computer language forces them to be unambiguous and computationally effective. The task of formulating a method as a computer-executable program and debugging that program is a powerful exercise in the learning process.  Also, once formalized procedurally, a mathematical idea becomes a tool that can be used directly to compute results.

Taken from Sussman, Wisdom: Functional Differential Geometry


Algorithm to find all 2-hop neighbors lists in a graph Given a graph $G = (V,E)$, where $|V| = n$. What is a fast algorithm for generating the collection of all 2-hop neighborhood lists of all nodes in $V$.

Naively, you can do that in $O(n^3)$. With power of matrices, you can do that with $O(n^{2.8})$ using Strassen algorithm. You can do better than this using another matrix multiplication algorithm. Any better method ? Any Las Vegas algorithm ?

The question really depends on what is the precise definition of a 2-hop. If by a 2-hop you mean the set $$hp(v) = \{ u \mid \mbox{there is a path of length 2 between u and v}\},$$ then the current answer is no, you cannot do it faster than $O(n^{\omega})$ where $\omega$ is the usual constant associated with the complexity of performing the matrix product.

Why? For every vertex $v$ check if $v$ is adjacent to vertex in $hp(v).$ If this is the case then you have found a triangle in your graph. Moreover the graph is triangle free if you do not find a vertex $v$ with this property.

The currently best known algorithm for testing if a graph is triangle-free has time complexity $O(n^{\omega}).$


Removing Left Recursion from Context-Free Grammars - Ordering of nonterminals I have recently implemented the Paull's algorithm for removing left-recursion from context-free grammars:

Assign an ordering $A_1, \dots, A_n$ to the nonterminals of the grammar.
for $i := 1$ to $n$ do begin
$\quad$ for $j:=1$ to $i-1$ do begin
$\quad\quad$ for each production of the form $A_i \to A_j\alpha$ do begin
$\quad\quad\quad$ remove $A_i \to A_j\alpha$ from the grammar
$\quad\quad\quad$ for each production of the form $A_j \to \beta$ do begin
$\quad\quad\quad\quad$ add $A_i \to \beta\alpha$ to the grammar
$\quad\quad\quad$ end
$\quad\quad$ end
$\quad$ end
$\quad$ transform the $A_i$-productions to eliminate direct left recursion
end

According to this document, the efficiency of the algorithm crucially depends on the ordering of the nonterminals chosen in the beginning; the paper discusses this issue in detail and suggest optimisations.
Some notation:

We will say that a symbol $X$ is a direct left corner of
a nonterminal $A$, if there is an $A$-production with $X$ as the left-most symbol on the right-hand side. We define the left-corner relation to be the reflexive transitive closure of the direct-left-corner relation, and we define the proper-left-corner relation to be the transitive closure of
the direct-left-corner relation. A nonterminal is left recursive if it is a proper left corner of itself; a nonterminal is directly left recursive if it is a direct left corner of itself; and a nonterminal is indirectly left recursive if it is left recursive, but not directly left recursive.

Here is what the authors propose:

In the inner loop of Paull’s algorithm, for nonterminals $A_i$ and $A_j$, such that $i > j$ and $A_j$ is a direct left corner of $A_i$, we replace all occurrences of $A_j$ as a direct left corner of $A_i$ with all possible expansions of $A_j$.
This only contributes to elimination of left recursion from the grammar if $A_i$ is a left-recursive nonterminal, and $A_j$ lies on a path that makes $A_i$ left recursive; that is, if $A_i$ is a left corner of $A_j$ (in addition to $A_j$ being a left corner of $A_i$).
We could eliminate replacements that are useless in removing left recursion if we could order the nonterminals of the grammar so that, if $i > j$ and $A_j$ is a direct left corner of $A_i$, then $A_i$ is also a left corner of $A_j$.
We can achieve this by ordering the nonterminals in decreasing order of the number of distinct left corners they have.
Since the left-corner relation is transitive, if C is a direct left corner of B, every left corner of C is also a left corner of B.
In addition, since we defined the left-corner relation to be reflexive, B is a left corner of itself.
Hence, if C is a direct left corner of B, it must follow B in decreasing order of number of distinct left corners, unless B is a left corner of C.

All I want is to know how to order the nonterminals in the beginning, but I don't get it from the paper. Can someone explain it in a simpler way? Pseudocode would help me to understand it better.

This is actually not very complicated.  I'll assume that epsilon productions have already been eliminated from the language, because that will only obscure the key concept of "left corner".

Form a graph G where the vertices are all the non-terminals of the grammar.  Now draw a directed edge from A to B if there is any production rule that looks like "A -> B[...]".  The paper calls B a "direct left corner" of A.  More generally, some other non-terminal C is called a "left corner" of A if there is some path from A to C along the edges of this graph.  This can be done by computing the transitive closure of G, call it H.

The paper suggests ordering the vertices by counting the number of left corners each vertex A has (i.e. how many other non-terminals you can reach from A, or the out-degree of A in the graph H), then sorting them in decreasing order by this number.

One handwavy motivation for this policy is that if there is an important non-terminal (say the starting symbol S) with connections to many other symbols), then it makes sense to purge left-recursion from S early on, because if you leave it till later there will be more copies of S that you need to expand out.  I think the explanation in the paper is more convincing, but perhaps less obvious.


Prove that Big-O is transitive by relation. What does it mean by 'by relation'? Prove $f(n) = O(g(n))$ and $g(n) = O(h(n))$, then $f(n) = O(h(n))$.

The question is

  Prove that Big-O is transitive by relation.

What does it mean by by relation??

f(n)=O(g(n)) implies f(n) <= c1*g(n)
g(n)=O(h(n)) implies g(n) <= c2*h(n)
therefore,
f(n) <= c1*c2*h(n) = c3*h(n)

f(n) <= c3*h(n) implies f(n)=O(h(n))


Can someone please help with the proof of this? Given an unambiguous context-free language L and an unambiguous regular language L (moreover, every regular language is unambiguous) such that L∩ R = ∅, then prove that L∪ R is also unambiguous.

Take unambiguous grammars for L and R with start symbols $S_L$ and $S_R$. For L union R take a grammar that starts with $S->S_L$, $S->S_R$. Since no string is both in L and R, only one of the initial two rules can succeed, so the grammar is unambiguous.


Recognizability of $\left\{ \left\langle M\right\rangle |M\text{ is a TM and }A_{TM}\leq\mathcal{L}\left(M\right)\right\} $ Determine whether the following language is decidable, recognizable but not decidable, co-recognizable but not decidable or neither recognizable nor co-recognizable. Prove your answer.
  $$L=\left\{ \left\langle M\right\rangle |M\text{ is a TM and }A_{TM}\leq\mathcal{L}\left(M\right)\right\} $$

[Where $\mathcal{L}(M)$ is the set of words accepted by $M$ and $A_{TM}\leq L$ if there is a mapping reduction from $A_{TM}$ to $L$]

So if I understand correctly the question is whether the set of all $\mathcal{RE}$-hard languages is recognizable/co-recognizable. It seems an easy corollary of Rice's theorem that it is not decidable, and my intuition tells me it is neither recognizable nor co-recognizable but I'm having issues contradicting any reductions.

My approach was, to show it is not recognizable, to assume it is and therefore there is a reduction $L\leq A_{TM}$, where given a TM $M$ recognizing it we would run $M(<M>)$ where I hoped to get some diagonalization argument, but I failed.

Edit: I was able to show that $L\not\in co\mathcal{RE}$, using a reduction $A_{TM,\varepsilon}\leq L$. Given an encoding of a Turing machine $\left\langle M\right\rangle$  define $f\left(\left\langle M\right\rangle \right)$ to be the Turing machine which on input $\left\langle M',w\right\rangle$ :

For $i$ from $1$ to $\infty$:

Run $\left\langle M',w\right\rangle$  for $i$ steps.
Run $\left\langle M,\varepsilon\right\rangle$  for $i$ steps.
Accept if both accepted.

I wasn't able to modify this to show $L$ is not recognizable though, wanted to do a similar reduction using $\overline{A_{TM,\varepsilon}}$, but I have issues either getting a recognizable language when $M$ doesn't halt, as the "common" method of running for $|w|$ steps only produces decidable languages.

The reduction you suggest can be a bit simplified, by running the machines serially rather than "in parallel". That is, First check if $M$ accepts $\epsilon$, and if it does, run $M'$ on $w'$.

Your idea is to make sure that if $M$ accepts $\epsilon$, then the language of $f(\langle M\rangle)$ is $A_{TM}$, and otherwise it's empty.

We can do a similar thing to show that the language is not in RE, but it requires a bit more subtlety:

We show that $A_{\overline{TM,\epsilon}}\le_m L$ as follows. Given $\langle M \rangle$, the reduction outputs a machine $f(\langle M \rangle)$, which on input $\langle M',w' \rangle$ works as follows:

Simulate the run of $M$ on $\epsilon$ for $|\langle M',w' \rangle|$ steps.
If $M$ does not accept $\epsilon$ during that simulation, simulate $M'$ on $w'$ and answer whatever it answers.
Otherwise, if $M$ accepts $\epsilon$ during that simulation, reject.

Now, the crux of the construction is in step 1, where we simulate for a finite number of steps, but this number depends on the input, so it can grow arbitrarily large.

What we get is that if $M$ does not accept $\epsilon$, then we'll always get to step 2, so $L(f(\langle M\rangle))=A_{TM}$, and all is well.

However, if $M$ does accept $\epsilon$, then we get something a bit strange - for some small inputs, it may still be the case that we'll get to step 2. But for large enough inputs, we'll get to step 3. This means that $L(f(\langle M\rangle))$, so clearly there is no reduction from $A_{TM}$ to it, and we're done.


Turing machine states, lost in the jungle There is a lengthy discussion going on at the English Language & Usage StackExchange site suggesting various synonyms for dead code, and it got me wondering about an angle that wasn't covered -- inaccessible states in a Turing machine.   These are simply defined (look at page 43 here if you need a source) as states that are never reached.

The definition I linked to is accompanied with a state graph that shows an obviously inaccessible state.  Simplified:

(q0)-1->((q1))<-0,1-(q2)

If q0 is the start state, q2 is obviously inaccessible. This is analogous to the deliberately-disabled code that was the premise of the EL&U discussion.

But I'm wondering about those states that are inaccessible, but you will never know it, because they're just lost in the jungle.

These states all have a path from the start state in the machine's state graph. But no matter how long the machine runs, the particular combination of state and symbol to make the number transition into that state never appears.

For some of these states, static analysis can determine if they're inaccesssible.

For the rest, no analysis will ever be able to determine if the state is ever reached. For example, if you could determine whether every halt state is reached or not, you would have just solved the (unfortunately-named, but don't get me started) Halting Problem.   Let's leave out states that machines reach serendipitously if you run them long enough.

Is there a more specific term than 'inaccessible state' for this?  (It's a shame  'inaccessible states' can't mean specifically this; it would have been a nice parallel with inaccessible sets from set theory.)

The only terms I have seen used with any consistency are "dead" and "unreachable".

There is also the dual, "unproductive" states. This term comes from formal grammars and means that you have a state/non-terminal from which you can not reach a final state/terminal string.


Is Simon's problem a good NP-intermediate candidate? We know that $BPP \subseteq BQP$ but we have no proof $BPP \subset BQP$
(Though we have the proof that BQP $!=$ BPP with an oracle)

Since Simon's problem (as factoring) it's easily solvable by a quantum computer, and in exponential time complexity solvable by a classical computer, that's a hint of the separation between BQP and BPP and therefore this can be a pure NP problem.
Am I right?

Simon's problem is not a pure NP problem, for two reasons:

It is an oracle problem.  We are given an oracle for some function $f$.  That's not something that you can do within the definition of a NP problem.
It is a promise problem.  We are given the promise that $f$ will satisfy a particular property (it is two-to-one, and has a particular structure).  That too is not something you can do within the definition of a NP problem.

So Simon's problem is not a problem in the formal complexity class NP; it's just something different.  For the same reasons, it's not NP-intermediate, either.


Direct conversion from regular expression to MSO A language $L \subseteq \Sigma^*$ can be described by a regular expression iff it can be defined by a formula in monadic second order with words as structure $(\{0, \dots, n-1\}, <, (P_a)_{a \in \Sigma})$. The proof I know is an indirection construction over automata, i.e. we show that DFAs and regular expressions / formulas are equivalently powerful.

However, I am interested in a direct transformation process to make analysis of complexity properties easier. If I remember correctly, there is a construction based on the inductive nature of regular expressions and formulas, but I cannot find it. Just a link to a paper presenting these two algorithms (reg.exp. to MSO and back) would suffice for me.

The direction from regular expressions to MSO is easy, as MSO is versatile. For a regular expressions $R$ let us construct formulae $\varphi_R$.

$\varphi_{\emptyset} := \bot$

$\varphi_{\varepsilon} := \forall x\bot$

$\varphi_a := \exists x(P_a x \wedge \forall y(x=y))$

$\varphi_{R_1 | R_2} := \varphi_{R_1} \vee \varphi_{R_2}$.

$\varphi_{R_1R_2} := \exists X(\forall y\forall z((Xy \wedge \neg Xz)\to y<z) \wedge [\varphi_{R_1}]_{Xx} \wedge [\varphi_{R_2}]_{\neg Xx})$

$\varphi_{R*} := \exists X(\forall y\forall z((\forall x((\neg x<y \wedge \neg z<x)\to(Xx\leftrightarrow Xy))) \wedge \forall x((x<y\wedge(Xx\leftrightarrow Xy))\to\exists x'(x<x'\wedge x'<y\wedge\neg(Xx'\leftrightarrow Xy))) \wedge \forall x((z<x\wedge(Xx\leftrightarrow Xy))\to\exists x'(z<x'\wedge x'<x\wedge\neg(Xx'\leftrightarrow Xy)))) \to [\varphi_R]_{\neg x<y \wedge \neg z<x})$

Here, $[\varphi]_{\psi(x)}$ denotes the relativization of the formula $\varphi$ to the formula $\psi$.

As you can see, the translation is linear.

In the other direction, I suggest to transform MSO to regular expressions in two steps, with NFAs in between. I know this is not what you are asking for. For complexity analysis it should suffice, however: The translation from MSO to NFAs is known not to have any elementary lower bound. And a direct translation to regular expressions cannot be any better, because of the linear translation from regular expressions to NFAs.


K shortest paths - any relation between K and % of graph nodes in discovered paths? Let's say I have a graph with $N$ nodes, $A$ arcs and an average branching factor $b$.  I want to find the $K$ shortest paths between two nodes.

Is there some relation (even approximate is fine) that expresses the dependency between the parameter $K$ and percentage of nodes included in the paths discovered by running the algorithm (Yen's loopless KSP)?

For example, in a graph of 20 nodes, the ($1st$) shortest path from node $1$ to $12$ is $1-4-7-12$, while the $2nd$ shortest path is $1-4-6-9-12$.

So for $K=1$, the discovered path contains $4/20 = 20\%$ of the nodes in the graph. For $K=2$, the two paths contain $6/20 = 30\%$ of the nodes. This relation between $K$ and the percentage is what I'm looking for.

It seems to me the relation depends purely on how the graph is made. Think about a cycle. The shortest path between two adjacent vertices contains 2 vertices while the second contains n vertices


Adapting neural network I have on a few occasions trained neural networks (back propagation networks) with some rather complicated data sets (backgammon positions and OCR). When doing this, it seems that a lot of the work involves trying out different configurations of the networks, in order to find the optimal configuration for learning. Often there is a compromise between small nets that are faster to use/learn, and bigger nets, that are able to represent more knowledge.

Then I wonder if it could be possible to make some networks that are both fast and big. I'm thinking that at network where every neuron ain't fully connected ought to be faster to calculate than nets with full connection on all layers. It could be the training that detected that certain inputs are not needed by certain neurons, and therefore remove those connections. In the same way the training could also involve adding new neurons if some neurons seems to be "overloaded".

Is this something that have been tried out with any success ? Does any classes of networks exists with this kind of behavior ?

This is roughly an open problem subject to ongoing research with various different strategies and heuristics known. A key word is "neural network architecture". The most basic strategy is to iterate through various network topologies and retrain for each one. Another strategy is to start with a relatively larger network and prune connections that have low weight and retrain and look for improvements; years ago this was called "brain damage" in at least one paper [2]. Here are some example references. There are many others. There is also a possibility of using GA-like algorithms to determine the network structure [3]. Here is part of the abstract from [1]:

  The use of ANNs requires some critical decisions on the part of the user, which may affect the accuracy of the resulting classification. In this study, determination of the optimum network structure, which is one of the most important attributes of a network, is investigated. The structure of the network has a direct effect on training time and classification accuracy. Although there is some discussion in the literature of the impact of network structure on the performance of the network, there is no certain method or approach to determine the best structure. Investigations of the relationship between the network structure and the accuracy of the classification are reported here, using a MATLAB tool-kit to take the advantage of scientific visualisation.

[1] Determining Optimum Structure for Artificial Neural Networks by Taskin Kavzoglu

[2] Optimal brain damage Le Cun, Denker, Solla

[3] Finding Optimal Neural Network Architecture Using Genetic Algorithms Britos et al


Proving by induction that a function gets called n-1 times This is the pseudo-code from the problem:

procedure Foo(A,f,L)

   Precondition: A[f..L] is an array of integers, f,L, are
                 two naturals >=1 with f<=L.

   if (f=L) then
     return A[f]
   else
     m <-- [(f+L)/2]
     return min(Foo(A,f,m), Foo(A, m+1,L))
   endif

The Question:

Using induction, argue that Foo invokes min at most $n-1$ times.

I am a little lost on how to continue my proof for part (iii). I have the claim written out as well as the base case. Which I believe it to be $n\geq2$. But how do I do it for $k + 1$ terms? Since this is a proof by induction.

Thanks

Here, I'm going to let $n = L-f$ and let $M(f,L)$ be the number of times min is invoked when calling $Foo(A,f,l)$. Notice when $n=0$, then $L=f$ and clearly Foo invokes the function min $0$ times so the condition is satisfied.

Now suppose that the assertion is satisfied for $n \leq k$. We want to show it holds true for $n=k+1$, i.e., suppose that $L-f = k+1$. Since $Foo(A,f,L)$ has to invoke min once and then invoke it as many times as its invoked in the recursive calls, we get that,

$$M(f,L) = 1 + M(f,m)+M(m+1,L).$$

Now notice that for $M(f,m)$ and $M(m+1,L)$, the quantity $m-f$ and $L-(m+1)$ are both less than $L-f = k+1$ (since $m$ is essentially the midpoint of $L$ and $f$). So by the inductive hypothesis $Foo(A,f,m)$ invokes min at most $m-f-1$ times and $Foo(A,m+1,L)$ invokes min at most $L-(m+1)-1$ times. Plugging these into our equation yields, we get,

$$M(f,L) = 1 + M(f,m)+M(m+1,L) \leq 1 + (m-f-1) + (L-(m+1)-1) = L-f-1 = n-1,$$

as desired.


Is dynamic programming restricted to optimization problems? The usual criteria used to decide if a problem can be solved using dynamic programming is (1) if it has optimal sub-problems and (2) if it has overlapping sub-problems. Does the word "optimal" mean that DP can only be used to solve optimization problems? Otherwise, it would make more sense to write (1) as "if it can be decomposed in sub-problems" (i.e. it is recursive). Obviously, this definition includes optimization problems with optimal sub-problems.

Dynamic Programming can be used to solve a problem as long as the problem has a recursive substructure and the sub-structural problems are overlapping. So, as long as a problem has the two properties, DP can be used for solving it. Problems with these properties are definitely not restricted to only optimization problems. So, yes.

Here are some good examples of non-optimization problems which can be solved quickly using DP:

Coin Change Problem
Counting the number of increasing subsequences in a given sequence
If you forget everything, calculating upto the first $n$ Fibonacci Numbers using its recurrence relation can be done using Dynamic Programming.


Induction rules for reflexive, transitive closure I'm trying to solve an exercise on inductive definitions, the premiss is:

Let $\to$ be a relation on $A$ and $\to^*$ its reflexive, transitive closure, which is defined by following two rules:

$a \to^*a$ (reflexive)
${a \to^*b \quad b \to c \over a \to^*c }$ (step)

The questions are:

What are the induction rules for $\to^*$?
Show that  $\to^*$ is reflexive.
Show that  $\to^*$ is transitive.

The first question startles me, I view ${a \to^*b \quad b \to c \over a \to^*c }$  as the induction rule. Is this the complete answer?

And can I show the reflexivity with ${a \to^*b \quad b \to a \over a \to^*a }$?

Here's a fully formal articulation in the language of Agda.
First, inductive rules correspond to indexed families.

data Star {A : Set}(R : A → A → Set) : A → A → Set where
    Refl : {a : A} → Star R a a
    Trans : {a b c : A} → Star R a b → R b c → Star R a c

Here the Refl data constructor corresponds to your first rule, and the Trans data constructor corresponds to your second rule. R represents $\to$, so Star R corresponds to $\to^*$. The induction rule corresponds to the eliminator for the data type, i.e. roughly the fold on that type (though things are a bit more complicated in a dependently typed language).

ind : {A : Set}{R : A → A → Set}{P : A → A → Set}
    → ({a : A} → P a a) → ({a b c : A} → P a b → R b c → P a c)
    → {a b : A} → Star R a b → P a b
ind r t Refl = r
ind r t (Trans s x) = t (ind r t s) x

This says that if you give me some binary relation $P$ and you show that $\forall a \in A. P(a,a)$ holds and $\forall a,b,c\in A. P(a,b)\land R(b,c) \Rightarrow P(a,c)$ (i.e. when $P(a,b)$ and $R(b,c)$ hold, then $P(a,c)$ holds) then I can provide you a proof of $P(a,c)$ whenever $R^*(a,c)$ holds, where $R^*$ is the reflexive, transitive closure of $R$.

Question 2 is completely trivial. The formal proof of the statement is Refl. Question 3 is not much harder.  It's asking to show that if $a \to^* b$ and $b \to^* c$ then $a \to^* c$, while the inductive rule only gives the case when $b \to c$ in a single step. Obviously, we just need to recursively apply the single-step rule. This leads to the following code:

trans : {A : Set}{R : A → A → Set}{a b c : A} → Star R a b → Star R b c → Star R a c
trans r Refl = r
trans r (Trans s x) = Trans (trans r s) x

For your purposes, you should probably define the equivalent of trans in terms of the induction rule, i.e. in terms of ind. I'll leave that as a very simple exercise.


Who invented the adder, full-adder, half-adder? I didn't find, in the digital design books, who invented the adders.

The same person invented the half-adder and the full-adder?

What's the oldest publication on digital arithmetic design?

In 1966, I was taught by Professor Tom Kilburn at Manchester University.

He said the half adder was sometimes called the Kilburn adder because he invented it!


Prove that every undirected connected graph with $|V | > 2$ results in a connected graph if two vertices removed.. How do I go about proving this?

Prove that every undirected connected graph with $|V | > 2$ has at least two vertices such that if one or both are removed (along with their incident edges) the resulting graph is still connected, and describe an efficient algorithm to find two such vertices.

Hint: Find the connected graph's spanning tree (using an algorithm like breadth-first search). Consider the endpoints of a longest path in this spanning tree.


Why have additional symbols on a Turing machine? What is the point of non-binary printed letters on a turing machine? I understand that these need to be omitted to get a computable number, but why are they used in the first place?

Turing Machines are an abstract model of computation, their purpose is to define in a mathematical way what problems are theoretically computable and which are not.

It is true that a binary alphabet is enough to reach the full expressive power of Turing Machines. However, when playing with them "in practice" to prove theorems and to communicate these proofs, it can be more convenient to use more symbols, instead of encoding everything in binary. We could always go back to binary if it's absolutely needed.

An extreme example of the same sort would be "why are we still using 26 characters to write texts, now that we know that two are enough? It would save time when learning the alphabet!".


How to determine $10^{\log n}$ and $3n^2$ which grows faster asymptotically? My think is pretty easy that $10^{\log n} = n$, which is growing slower than $3n^2$.

However, many tutorial shows that $3n^2$ ranks before $10^{\log n}$.

I'm really confused.

You have to be careful here, since the answer depends on the particular log function you use. As Lieuwe noted if $\log$ in this context means $\log_{10}$ then $10^{\log n}=n$ and certainly $n$ "ranks before" $3n^2$, under any reasonable interpretation of "ranks before". However, if we have a different base for the logarithm, that might not be the case.

It's not hard to show that $10^{\log_b n}=n^{log_b{10}}$ (take the log of both sides) and so $10^{\log_b{n}}$ will be asymptotically larger than $n^2$ as long as $\log_b10>2$, i.e., when $b^2<10$, so when you use logs to base $b$ with, say, $b=3$ you'll have $10^{\log_b n}$ "ranks after" $3n^2$.


Can you do operations on the halt state of a turing machine? As the title says, can operations be performed by a turing machine after it has transitioned to the halt state like shown in the following image.

It may depend on the exact definition you're using for Turing machines, but most reasonable definitions will probably halt at the halt state. Your transition function can include transitions at the halt state, they just won't be executed. It's also possible that your particular definition prohibits such transitions.

In summary, your definition will tell you everything you need to know. Take a look!


a conjunctive normal form that is a tautology Are there any examples of CNF formulas that are tautologies?
Such that every clause contains different variables so phrases like (a or not a) are rejected?

Take any clause in the formula. If all variables in that clause are different, we can always assign $0$ to a non-negated variable and $1$ to a negated variable. This makes that clause $0$. Therefore, it makes the CNF formula $0$. Thus, tautology is not possible unless there is $A \vee \neg A$ in every clause.
This is probably what Kyle Jones stated in his comment.


data structure admitting top items with prefix A trie can answer a query for all items with a certain prefix in $O(m + \log n)$ time, where $m$ is the number of matches and $n$ is the number of items. A trie also supports $O(\log n)$ insertion and deletion and takes $O(n)$ space.

Now suppose each item has a score. I am looking for a data structure that can answer a related query: give me the top $m$ items by score with a certain prefix. Ideally search, insertion, and deletion would have the same time as a trie, up to a constant factor, and space would be $O(n)$ as well. To this end we may assume items are short (of length $O(\log n)$).

This problem can be solved with $O(\log^2 n)$ insertion and deletion and $O(n \log n)$ space by forming a trie where every node contains a sorted set of items with that prefix sorted by score. But this approach uses excess time and space compared to a trie. Can we do better?

You can achieve $O(\log n)$ time insert, $O(\log n)$ time delete, $O(n)$ space,  and $O(m \log m + \log n)$ time search by augmenting the trie.

Store in each leaf the weight of the corresponding item.  Also, at each internal node, add a field with a pointer to the leaf of maximum weight that's reachable from that node.

It's easy to see how to perform insertion in $O(\log n)$ time, and it's easy to see why this still uses only $O(n)$ space.

Search for the top $m$ items with a certain prefix can be done in $O(m \log m + \log n)$ time.  First, find the node $x$ corresponding to that prefix.  Use that node to identify the first item of the output (the highest-weight item with that prefix).  Next, look at the children $y_1,\dots,y_k$ of node $x$, and for each, look at the highest-weight item with that prefix.  Add these $k$ nodes to a priority queue, keyed on the weight of the corresponding item.  Extract the highest-weight item from the queue; that's the second item of the output.  Look at the children of the node you just extracted, and add them to the queue.  Repeat until you have output $m$ items; in each iteration, you extract the node of highest weight from the priority queue, output the corresponding item, and add the children of that node to the priority queue.  Remove duplicates as you go.  Stop once you've output $m$ items.  You do $O(\log n)$ time to find the first node corresponding to the prefix, and then each subsequent iteration takes $O(\log m)$ time (since operations on a priority queue of size $O(m)$ can be done in $O(\log m)$ time), and you do $m$ iterations, for a total running time of $O(\log n + m \log m)$.

Deletion can be done in $O(\log n)$ time.  To delete an item, traverse the trie to find that item.  Then, update each node that you visited during that traversal.  To update a node $x$, if the maximum-weight leaf under $x$ is the the item you're deleting, check the children of $x$ to find the next-highest-weight leaf under $x$, and update $x$.  This does $O(1)$ work per node you traverse, and the traversal visits $O(\log n)$ nodes, so the total time for deletion is $O(\log n)$ time.


How to solve a polynomial of the form y = ax^3 + bx^2 + cx + d using the incremental algorithm in computer graphics I am studying Computer Graphics and need to design an incremental algorithm for solving the polynomial $y = ax^3 + bx^2 + cx + d$, and then implement that in OpenGL. The input will be the values of $a, b,c,d$ and the desired output is a line/curve to be drawn. The values of $x$ would be in the range $1\leq x\leq100$. The algorithm needs to be very efficient hence I am required to use only addition operation, as multiplication is less efficient.

It would be similar to this technique, but here the polynomial to be considered is the one given above. I have searched a lot on the Internet but cannot find the required solution, because most of the examples solve the equation $y = mx+b$.

Can anyone kindly guide me how to solve it or which method should be applied to solve it?

You have f(x). Let g(x) = f(x+1) - f(x). Let h(x) = g(x+1) - g(x). Let k(x) = h(x+1) - h(x). It turns out that k(x) is a constant.

Calculate f(x), g(x), h(x) and k(x) for x = 1. Then you calculate f(x+1) = f(x) + g(x), g(x+1) = g(x) + h(x), h(x+1) = h(x) + k(x), and k(x) is a constant.


Calculating Binet's formula for Fibonacci numbers with arbitrary precision Binet's formula for the nth Fibonacci numbers is remarkable because the equation "converts" via a few arithmetic operations an irrational number $\phi$ into an integer sequence. However, using finite precision arithmetic, one would always have some (small) roundoff error.

  Is there a discussion/description somewhere of how to calculate the Fibonacci sequence using Binet's formula (ie not the recurrence relation) and floating point arithmetic which results in no roundoff error?

As the comments show, roundig is a respected method for Fibonacci computations. See also "Computation by rounding" in the wiki-lemma.

You avoid roundoff by computing exactly, but using numbers of the form $a+b\sqrt5$: $(a+b\sqrt5)(c+d\sqrt5) = (ac+5bd)+(ad+bc)\sqrt5$. Technically that is $Z[\sqrt5]$ I believe. But I now realise that you also have to take into account that $a,b$ are fractions.

But the recursion is so nice, why not use it? Based on the matrix form you can get the $n$-th Fibo number in a logarithmic number of steps.


The bounded halting problem is decidable. Why doesn't this conflict with Rice's theorem? One statement of Rice's theorem is given on page 35 of "Computational Complexity: a Modern Approach" (Arora-Barak):

A partial function from $\{0,1\}^*$ to $\{0,1\}^*$ is a function that is not necessarily defined on all its inputs. We say that a TM $M$ computes a partial function $f$ if for every $x$ on which $f$ is defined, $M(x) = f(x)$ and for every $x$ on which $f$ is not defined $M$ goes into an infinite loop when executed on input $x$. If $S$ is a set of partial functions, we define $f_S$ to be the boolean function that on input $\alpha$ outputs 1 iff $M_\alpha$ computes a partial function in $S$. Rice's theorem says that for every nontrivial $S$, the function $f_S$ is not computable.

Wikipedia states that languages of bounded time turing machines are EXPTIME complete. I expect this language looks something like $\{(\alpha,x,n) : M_\alpha $ accepts $x$ in less than $n$ steps$\}$. So let $M$ be some DTM that decides this bounded language in exponential time. It seems like this DTM is deciding some property for ALL turing machines, so my intuition tells me that Rice's theorem precludes such a decision. But obviously $M$ computes a total function.

What am I missing about the relation between this language and Rice's theorem?

The language

$\qquad \{(α,x,n):M_α \text{ accepts } x \text{ in less than } n \text{ steps}\}$

is not an index set, that is it is not of the form

$\qquad L_P = \{ \langle M \rangle \mid M \text{ is TM},\ \exists\, f \in P.\ f_M = f \}$

for some set of (partial recursive) functions $P$, with $f_M$ the (partial) function computed by TM $M$. Rice's theorem makes statements only about such $L_P$; many "intuitive" rephrasings are not helpful. See also here.

Note that this is not only a technical detail here. Rice's theorem does not apply to

$\qquad L = \{ \langle M \rangle \mid M \text{ accepts } \langle M \rangle \text{ in less than } \langle M \rangle \text{ steps} \}$,

either. Can you see why?

   For every machine in $L$ you can easily construct many machines that accept the same language but run for more than $\langle M \rangle$ steps, and thus are not in $L$. Thus, $L$ is not an index set.

$L$ is decidable, using the same argument as for the original language we're discussing.


Rice's Theorem - usage on $DFA$ or $LBA$ I have read about Rice's Theorem on Sipser's book, and I think I understand it quite well. I understand that it can be used to show that a language is not decidable.

However I am not sure about one question -

Can I use Rice's theorem on languages which are defined on $LBA$ or $DFA$? For example, the following language -

$$ALL_{LBA} = \left \{ \langle M \rangle \mid \text{$M$ is an LBA and $L(M) = \Sigma^*$} \right \}$$

Since an $LBA$ is a "private case" of a turing machine, I am not sure I can use Rice's theorem here to prove the language is undecidable.

If when you say  "$M$ is a $LBA$ (or $DFA$ or $PDA$)" you mean that $M$ has a fixed decidable structure (i.e. some properties of its internal state/transition structure) that forces its behaviour to be like a $LBA$ (or $DFA$ or $PDA$) then Rice's theorem cannot be applied directly.

For example, if "$M$ is a $DFA$", is formally defined as "$M$ has no left moves and always enters a halting state on the first blank symbol whatever the current state is" then

$ALL_{DFA} = \left \{ \langle M \rangle \mid \text{$M$ is a DFA and $L(M) = \Sigma^*$} \right \}$ is decidable

Note that even if "$M$ is a $LBA/PDA$" is formally defined using some decidable properties of the structure of $M$, the sets $ALL_{LBA}$ and $ALL_{PDA}$ are undecidable but the proof cannot rely on Rice's theorem: it must use the LBA/PDA ability to "parse" a valid partial computation trace (tape+state) of an arbitrary Turing machine $M$.


What's the complexity class of determing the halting problem of a finite memory Turing machine? What's the complexity class of determining the halting problem of a finite memory Turing machine?
What is the computational complexity class of determining whether a machine halts on any input if it is allowed to access no more than $n$ bits of memory.

I know this problem is decidable because due to the limited memory, if it runs for longer then $2^n$ it must be caught in a loop.

The problem is PSPACE-complete.

The problem is in PSPACE.  You can test whether such a machine halts in polynomial space, by running the Turing machine for $2^n |Q| n + 1$ steps, where $|Q|$ is the size of the finite control, and checking whether it halts.  Why?  Each configuration of the Turing machine is determined by the values on the tape, the state of the finite control, and the position of the head, so there are at most $2^n |Q| n$ such configurations.

Any PSPACE problem can be reduced to this problem.  In particular, if you have a Turing machine that solves problem $P$ with polynomial space, then you modify $P$ to solve the problem, then if $P$ would accept, halt, and if $P$ would reject, enter an infinite loop.  Now if you could solve the halting problem for polynomial-space Turing machines, you could solve $P$.

So, this completely characterizes the difficulty of the halting problem for polynomial-space Turing machines.


Is P^SAT with only one query equal to the union of NP and coNP? I have a following problem:

Let $P^{SAT[1]}$ be a class of problems decidable by a deterministic polynomial Turing Machines with SAT oracle. (only one question to oracle).

Assume that:
$\mathrm{co}NP \neq NP \neq P$

Decide if $coNP \cup NP \neq P^{SAT[1]}$ or $\mathrm{co}NP \cup NP = P^{SAT[1]}$.

I know how to show that $\mathrm{co}NP \cup NP \subseteq P^{SAT[1]}$.

But I have no idea what about inverse direction. Any tips?

Under the assumption that $NP\neq \mathrm{co}NP$, we have that:

$$P^{SAT[1]}=NP\cup \mathrm{co}NP\implies P^{NP[1]}\neq P^{NP[2]}$$

Proof: Since $D^p\subseteq P^{NP[2]}$, we deduce that $(SAT\dot{\land} UNSAT)\in P^{NP[2]}$.

Meanwhile, $(SAT\dot{\land}UNSAT)\notin NP$ due to $UNSAT\notin NP$ and similarly, $(SAT\dot{\land}UNSAT)\notin \mathrm{co}NP$ due to $SAT\notin \mathrm{co}NP$. So, $(SAT\dot{\land}UNSAT)\notin NP\cup \mathrm{co}NP=P^{NP[1]}$.

We conclude that $P^{NP[1]}\neq P^{NP[2]}$.$\blacksquare$

In the above, $(SAT\dot{\land}UNSAT)=\{(\phi_1,\phi_2)\mid\phi_1\in SAT \land \phi_2\in UNSAT\}$.

So, though it might be tempted to push $P^{NP[1]}$ downto $NP\cup \mathrm{co}NP$, this result (if true) could tell us more about where the polynomial-time hierarchy $PH$ would actually collapse to. And, in this case, your proposition would save $PH$ from collapsing to $P^{NP[1]}$.


Running time of this recursive relation: T(n) = (n/2)T(n/2) + O(n^2) I encountered these few recursive relations:

T(n) = (n/2)T(n/2) + O(n^2)

T(n) = T(n/2) + T(n/2-1) + ... + T(1) + O(n^2)

I do notice that these recursions can be solved faster by DP. I'm just curious as to:

What's the big-O of the running time of these relations, if we follow the resursive formula
How do you analysis recursive relations like these.
Does the trailing term (in this case O(n^2)) matter?

Any help is much appreciated.

You can solve the first recurrence for powers of $2$. The recurrence (without the big O and with an arbitrary base case) reads
$$ T(2^k) = 2^{k-1} T(2^{k-1}) + 4^k, \quad T(2^0) = 4^0. $$
Opening the recurrence, we get
$$
T(2^k) = 4^k + 2^{k-1} \cdot 4^{k-1} + 2^{k-1+k-2} \cdot 4^{k-2} + \cdots + 2^{k-2+\cdots+1} 4^0.
$$
Denote these by $T(2^k) = \alpha_0 + \cdots + \alpha_\ell$. We have
$$
\frac{\alpha_\ell}{\alpha_{\ell-1}} = 2^{k-\ell-1}.
$$
Therefore the largest term is $\alpha_{k-1} = \alpha_{k-2}$, and the rest of the terms decrease geometrically. This shows that
$$ T(2^k) = \Theta(\alpha_{k-1}) = \Theta(2^{k-1+\cdots+1} 4^1) = \Theta(2^{k(k-1)/2}). $$
As you can see, the term $O(n^2)$ in the recurrence isn't important, and you will get similar result for any term $O(n^c)$.

One could guess that the general solution to the first recurrence (with $\lfloor n/2 \rfloor$ replacing $n/2$) is $T(n) \Theta(2^{\log_2 n(\log_2 n - 1)/2})$, and one could further guess that the second recurrence has the same solution (though that's a wilder guess). I'm not sure these guesses are correct. At the very least, the first recurrence should have the solution $T(n) = 2^{\Theta(\log^2 n)}$.


Reducing from NPC to Co-NPC => NP = Co-NP? In my lecture we learned:

If X is NPC and X in Co-NP => NP = Co-NP

Would it be enough to prove NP = Co-NP if I reduce a problem just in one direction (from NPC to Co-NPC) in polynomial time?

Or would it be necessary to show this for both directions?

In short
yes
Proof
Let's assume $X$ is NP-complete and $X$ is in co-NP.
We show that $NP \subseteq coNP$ and viceversa.
[$NP\subseteq coNP$]
Because $X$ is NP-complete
$=>$ for each $L\in NP$ we can found a polytime function $f$ that $s\in L$ iff $f(s)\in X$.
But $X$ is in coNP
$=>$ for the polityme reduction closure of coNP, $L\in coNP$ too
$=>$ $NP\subseteq coNP$
[ $coNP \subseteq NP$ ]
let $B\in coNP$
$=>$ $B^c \in NP$
$=>$ $s\in B^c$iff $f(s)\in X$
$=>$ $s\in B$ iff $f(s) \notin X$
$=>$ $s\in B$ iff $f(s) \in X^c$
but because $X \in coNP$
$=> X^c \in NP$ and for polityme reduction closure of $NP$
$=> B \in NP$
$=>coNP\subseteq NP$
So $NP=coNP$ under this assumptions.


Non-deterministic Turing machine that halts on at least one branches of computation I'm looking at my textbook here from Michael Sipser and he says that a nondeterministic Turing machine is a decider if all its computation branches halt on all inputs. I think I recall seeing somewhere what you'd call a nondeterministic Turing machine that halts on at least one branch for all inputs, but may loop on others. Is there a name for such a thing? I see later in this chapter the word verifier, but that doesn't seem to fit... I think that refers to an algorithm.

  A verifier for a language $A$ is an algorithm $V$, where
  $$A=\{w\mid V\text{ accepts }\langle w,c\rangle\text{ for some string c}\}.$$
  We measure the time of a verifier only in terms of the length of $w$, so a polynomial time verifier runs in polynomial time in the length of $w$. A language $A$ is polynomially verifiable if it has a polynomial time verifier.

The strings accepted by a NTM M is the language of M, noted L(M)

Let us say that M for any input is not guaranteed to halt on all branches.
Then M clearly cannot be a decider, and is thus only a recognizer. M recognizes the language of all strings, for which any branch of M ends in an accepting state.

Since M is a recognizer, it is only guaranteed to accept a string if the string is in L(M).
Given a string, that is not in L(M), it may reject the string, or loop forever.
Any NTM can be simulated by a DTM, but if NTM only recognizes a language L, its equivalent DTM will also only recognize L.

If the NTM halts on all branches for any input it is a decider, then the equivalent DTM will do the same and thus be a decider as well.

A verifier is not the thing you are looking for. In Sipsers book, Introduction to the Theory of Computation, the verifier is introduced when talking about complexity of algorithms and complexity classes, because any language L is in NP if and only if it has a polynomial time verifier.

A verifier for a language L will take as input a string w in L and a certificate c (think of the certificate as a solution to the problem w) and verify that the certificate is in fact a correct solution, which makes w lie in L.

Example:

For the language

L = { w | w is an integer for which the product of some of the digits equals 12000 }

You can make a verifier V, that takes a string w in L, a certificate c, and verifies that w is in fact in L using the certificate c. c could be a binary string indicating the integers in w for which the product of equals 12000.

For example, V must reject the input 1923423343, 0010111011, because 2*4*2*3*4*3 = 576 != 12000

For many problems, we only know an algorithm that can solve them running in exponential time of the input size. This is why verifiers are interesting, because it is often the case, that we given a solution quickly can determine if that solution is correct or wrong.


Flags register in an out-of-order processor LW R2, 0(R1)
CMP R3, R2
CMP R7, R5

the LW instruction stalls the first CMP so the second one will execute first. Wouldn't this cause the flags register to contain the wrong value since it expects the second CMP to be the last one that updates the flags register?

I'm not sure about this one: does an ADD instruction ALWAYS update the overflow flag (1 if overflow and 0 if no overflow).

LW R2, 0(R1)
ADD R4, R3, R2
ADD R7, R5, R6

Same thing here: will the overflow flag be wrong if the first ADD wouldn't overflow but the second one will. The second ADD executes firsts and sets the overflow flag. After that the first ADD executes, doesn't overflow and sets the overflow flag to 0?

The flags register is handled using one of the standard techniques for dealing with dependencies in out-of-order processors.  Either

the registers are renamed (there are multiple physical flags registers, and the renaming and retirement mechanisms make sure the correct physical flags register is being used by each instruction) or
the scheduler respects anti- and output- dependencies, in which case the two CMP instructions execute in-order because the second is output-dependent on the first.

Same thing with ADD instructions.  In a machine with ADDs that set an overflow flag, the overflow flag needs to be handled either by renaming or by stalling on anti- and output- dependencies.


Loop-local variable in Cytron's SSA algorithm I am trying to write a compiler that converts a simple imperative language to SSA form, but I am having trouble with loops. As an example, I have some code that looks like:

fun count() {
    i = 0;
    while(i < 10) {
        x = i + 1
        i = x;
    }
    return i;
}

I then convert it to a control flow graph that looks like this:

0 ->
    predecessors                = []
    successors                  = [1,2]
    dominators                  = [0]
    strict dominators           = []
    dominatees                  = [0,1,2]
    dominance frontier          = []
    inverse dominance frontier  = []
    immediate dominator         = none
    immediate dominatees        = [1,2]
    instructions                =
        r := 0
        i := 0
        if i >= 10 goto 2 else goto 1

1 ->
    predecessors                = [0,1]
    successors                  = [1,2]
    dominators                  = [0,1]
    strict dominators           = [0]
    dominatees                  = [1]
    dominance frontier          = [1,2]
    inverse dominance frontier  = [1]
    immediate dominator         = 0
    immediate dominatees        = []
    instructions                =
        x := i + 1
        i := x
        if i < 10 goto 1 else goto 2

2 ->
    predecessors                = [0,1]
    successors                  = []
    dominators                  = [0,2]
    strict dominators           = [0]
    dominatees                  = [2]
    dominance frontier          = []
    inverse dominance frontier  = [1]
    immediate dominator         = 0
    immediate dominatees        = []
    instructions                =
        r := i
        ret

The issue I'm running into is that when I use the algorithm for placing phi nodes described in section 5.1 of Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, I get something like this:

0 ->
    predecessors                = []
    successors                  = [1,2]
    ...
    instructions                =
        r := 0
        i := 0
        if i >= 10 goto 2 else goto 1

1 ->
    predecessors                = [0,1]
    successors                  = [1,2]
    ...
    instructions                =
        x := phi(x, x)
        i := phi(i, i)
        x := i + 1
        i := x
        if i < 10 goto 1 else goto 2

2 ->
    predecessors                = [0,1]
    successors                  = []
    ...
    instructions                =
        x := phi(x, x)
        i := phi(i, i)
        r := i
        ret

I understand why a phi is necessary for i in basic block #1 and #2, but I don't understand why phis are necessary for x, and in fact they seem to break the renaming algorithm that follows (specifically, at one point where the renaming algorithm tries to pop off the S("x") stack, that stack is empty, because x was not assigned to in basic block #0). Did I somehow incorrectly implement this algorithm, or is there some subtlety I'm not understanding?

Congratulations for implementing Cytron's algorithm! You are one of a select few who have attempted it.

Most compilers these days tend to use a much simplified algorithm which inserts and then removes redundant phi nodes. We will go through that later. Be aware that although it produces minimal SSA form on reducible flow graphs, it sometimes doesn't on irreducible flow graphs. But all in good time.

I'm going to go through a couple of related points, some of which you've probably already noticed, but I'm going to mention anyway to make this answer a bit more self-contained.

First off, the definition of $\mathit{HasAlready}$ in the paper is doesn't make a lot of sense. It is defined as follows:

  $\mathit{HasAlready}(*)$ is an array of flags, one for each node, where $\mathit{HasAlready}(X)$ indicates whether a $\phi$-function for $V$ has already been inserted at $X$.

Already, we see a problem: Where's $V$ in this query? But then, in figure 11, we see this code:

  $\texttt{if}\,\mathit{HasAlready}(X) < \mathit{IterCount}$

  ...

  $\,\,\,\,\,\,\,\,\mathit{HasAlready}(X) \leftarrow \mathit{IterCount}$

So $\mathit{HasAlready}(X)$ should clearly be an integer, not a flag. Its value represents the highest-numbered variable that has had a $\phi$-function introduced for each basic block.

Secondly, if you are constructing SSA form using basic blocks, then Cytron's algorithm as published doesn't deal with multiple assignments to the same variable within a basic block, because the they don't need $\phi$-functions. The set of assignments to a variable $V$ (denoted $\mathcal{A}(V)$ in the paper) only refers to the last assignment in a basic block.

Now what you've identified is the dual of this: the only "uses" which matter are any that occur before the first assignment in a basic block. That also means that no potential reaching definition of a variable is "used" in a basic block if there are no uses before that first assignment in the block.

Now I've forgotten a lot of the details here, but that might explain the pop issue in the renaming algorithm: there isn't an assignment to x in basic block 1 as far as Cytron's algorithm is concerned.

OK, now that's out of the way, here's what most compilers tend to do: insert $\phi$-functions everywhere for everything (using variable scopes so we don't go completely crazy), and then remove the redundant ones.

In your case, let's suppose that x is declared outside the loop and initialised with 0. We rename every assignment, then insert a $\phi$ at the start of every block (except the start block) with the incoming values from the last assignment in all predecessors:

0 ->
    r_0 := 0
    i_0 := 0
    x_0 := 0
    if i_0 >= 10 goto 2 else goto 1

1 ->
    i_1 := Phi(i_0, i_2)
    x_1 := Phi(x_0, x_2)
    r_1 := Phi(r_0, r_1)
    x_2 := i_1 + 1
    i_2 := x_2
    if i_2 < 10 goto 1 else goto 2

2 ->
    i_3 := Phi(i_0, i_2)
    x_3 := Phi(x_0, x_2)
    r_3 := Phi(r_0, r_1)
    r := i_3
    ret

This is already valid SSA form, it is just not minimal SSA form.

Now we iteratively apply two transformations:

If there is a Phi assignmment whose value is unused, remove it.
If there is a Phi assignment whose arguments are the returned value
of the assignment and one other value, remove it and rename the assigned variable to that other value.

An example of the first rule is in block 2, with r_3. That is unused, so we remove it.

An example of the second rule is in block 1, with r_1. Here, r_1 can be replaced with r_0 everywhere. In general, you might find something like this:

v_1 := Phi(v_1, v_2, v_2, v_1, v_2)

In that case, remove the Phi and replace v_1 with v_2 everywhere.

It should be clear why these two simplifications are valid transformations. What's interesting is that if you apply these two rules until none apply any more, you get minimal SSA form if the flow graph is reducible.

In your case, you get this:

0 ->
    r_0 := 0
    i_0 := 0
    x_0 := 0
    if i_0 >= 10 goto 2 else goto 1

1 ->
    i_1 := Phi(i_0, i_2)
    x_2 := i_1 + 1
    i_2 := x_2
    if i_2 < 10 goto 1 else goto 2

2 ->
    i_3 := Phi(i_0, i_2)
    r := i_3
    ret

Now you can see that all of the Phi nodes for x have been eliminated, as we would hope. Also, x_0 and r_0 are dead definitions, but they can be removed later.

Just as a last comment, the very notion of a "basic block" isn't necessarily that important in modern compilers any more, after you have resolved scopes and before you generate assembly language.

The "sea of nodes" representation is a case in point. Many modern IRs tend to think in terms of sequencing constraints instead of linear blocks of code. That way, you don't have to deal with basic blocks specially as in this example.

If you think of each instruction as its own "basic block", then Cytron's algorithm should work perfectly!