About a symmetric rank decomposition of a SYM◦SYM circuit's truth table matrix New algorithms and lower bounds for circuits with linear threshold gates.
Ryan Williams. Submitted, 2013.

I study this paper and have difficulty with understanding the proof of Lemma 2.2 in section 2.
My questions are the three below.

① In the proof, we can find this sentence.

  Let f : {0,1,...,s} → {0,1} be the symmetric function of gate g′: for all a ∈ {0,1,...,s}, f(a) = b if and only if a true inputs make g′ output b.

Since f : {0,1,...,s} → {0,1} and f(a) = b, I thought b ∈ {0,1}.
Is my assumption correct?

② We can find the constants a and b also in the next paragraph.

  For every pair (a,b)∈{0,1,...,t}2 such that a+b ≤ t, let Sa,b ⊆ {g1,...,gs} denote the subset of gates gj such that a+b true inputs makes gate gj output 1.

Do these a and b correspond to the previous ones?

③ To understand how every pair (a,b) is constructed, I made a simple SYM◦SYM circuit and tried to enumerate every pair.

In this example, I know the constants below will be
n = 2, s = 2, a ∈ {0,1,2},
but I'm not sure about the value of t(the number of wires), b and the subset Sa,b.
So, please tell me the value of constant t, every pair (a,b) and its Sa,b in this example.

P.S.(2019/05/03)

The concept of the pair (a,b) and the subset Sa,b are used in the following context to construct the truth table of a symmetric circuit.

(Since I'm not so good at English and not an expert of this field, I'd be sorry if there's any inappropriate expressions or mistakes.)

The fact that the same letter is used twice doesn't mean that it signifies the same thing. In particular, in your first question, clearly $a \in \{0,\ldots,s\}$ and $b \in \{0,1\}$, whereas in the second question, it is explicitly stated that $a,b \in \{0,\ldots,t\}$. From your excerpts, it seems that the second $a,b$ are of the same "type" as the $a$ in your first question.

Your third question is unanswerable given your excerpts. It could be that the construction is instantiated with several different values of $t$. In any case, I would look at the place in which the construction is invoked to find out what the value of $t$ should be.


complexity classes defined as limits or "globally"? As far as I understand correctly, to say that a decision problem $X$ is in P means that there exists a polynomial $c\cdot n^p$ such that as $n$ goes to $\infty$, the steps required to solve $X$ is bounded by $c\cdot n^p$.

But strictly speaking, this doesn't restrict the complexity for finite $n$ in any way. Strictly speaking if $X$ is in P, it could be that for all $n$ between $0$ and Ackermann function $A(300,300)$, the complexity of $X$ grows according to $e^n$, and then only from $A(300,300)$ onwards it starts being bounded by $c\cdot n^p$.

Am I right that if a problem is in the complexity class P this strictly speaking doesn't say anything about its complexity for finite $n$? Is there a way to talk about complexity for finite $n$?

Complexity classes are (usually) expressed using Landau notation, which makes precise what you state. See also our reference questions.

Yes, by definition (usual) complexity classes don't say anything about the real world per se. That is by design; complexity is a model for classifying the inherent hardness problems, not a tool to design or analyse algorithms.
See also here for some related thoughts.

  Is there a way to talk about complexity for finite n?

"Complexity" and "finite" are mutually exclusive. Of course you can study, say, the (relative) performance of algorithms on real(istic) data. The machinery of complexity theory and, sadly, "Big-Oh"-driven algorithm analysis will be mostly useless then.


How to generate an LL(2) parse table? The algorithms I've seen for building an LL(1) parse table involve calculating first and follow sets such that:

predict(nonterminal, production) ==
     if epsilon in FIRST(production):
         first(production) union follow(nonterminal)
     else:
         first(production)

where production is a sequence of symbols which can include nonterminals, terminals, and epsilon.

what's the algorithm for an LL(2) parse table?

There is a pretty reasonable discussion in this essay from the SLK parser generator.

Basically, you just need to extend $FIRST$ and $FOLLOW$ to be $FIRST_k$ and $FOLLOW_k$, meaning the first / following $k$ symbols. The basic principle is the same, but when $k > 1$ there is a complication, leading to the distinction between "strong" and regular grammars.

The naming is a bit counterintuitive; the parsing table for a strong grammar can be generated by an easier but less powerful algorithm, so the strong grammars are in a sense weaker; they make a stronger guarantee about predictability.


Is my algorithm to find the median of 2 sorted arrays O(log(m + n))? I came up with a solution for LeetCode Problem 4:
Median of Two Sorted Arrays
The expected efficiency of this should be $O(\log(m+n))$, where $m$ and $n$ are the lengths of nums1 and nums2.
For my solution I decided only to process only the first half of nums1 and nums2.
Does that count as logarithmic time, or is it still linear time?
My Java code:
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Don't need the entire array - only the first half
        int maxSize = nums1.length + nums2.length;
        int size = maxSize / 2 + 1;

        // Merged array and its index
        int[] merged = new int[size];
        int m = 0;

        // Left index, right index
        int l = 0;
        int r = 0;

        // Build the merged array
        while (m < merged.length) {
            if (l >= nums1.length) {
                // Left array exhausted - just add the right array
                merged[m] = nums2[r];
                m++;
                r++;
            } else if (r >= nums2.length) {
                // Vice versa
                merged[m] = nums1[l];
                m++;
                l++;
            } else {
                // Compare left and right
                int a = nums1[l];
                int b = nums2[r];

                if (a > b) {
                    merged[m] = b;
                    m++;
                    r++;
                } else {
                    merged[m] = a;
                    m++;
                    l++;
                }
            }
        }

        // Debug
        // for (int x : merged) {
        //     System.out.print(x + ", ");
        // }
        // System.out.println();

        // Find median based on the first half
        if (maxSize % 2 == 0) {
            // Divide with 2.0 instead of 2: important!
            return (merged[size-1] + merged[size-2]) / 2.0;
        } else {
            return merged[size-1];
        }
    }
}

Pseudocode:

Make a new array $m$, which is the size of the first half of both arrays combined

Merge both arrays together in the correct order into the array $m$
(note that this will not fully iterate the first or second array, since $m$ is only the size of the first half of both combined arrays)

Return the last element of 'm', or the average of the 2 last elements of $m$ (the median of both sorted arrays)

Leetcode result:
Runtime: 2 ms, faster than 99.75% of Java online submissions for Median of Two Sorted Arrays.
Memory Usage: 40.1 MB, less than 81.65% of Java online submissions for Median of Two Sorted Arrays.

Judging from your description and your code, you are basically doing a merge of the two array but stop at the median. This means that your main loop (body) is executed $(m + n) / 2 \in O(m + n)$ times, which is linear in $m + n$. You could also figure that one out experimentally by trying your algorithm on a range of different inputs and plotting the time taken against $m + n$, I guess.
If you want to find a solution which takes $O(\log (m + n))$ time you could try working backwards: A binary search over a (sorted) array of length $n$ takes $O(\log(n))$ time.


What are some comparative studies on program termination verification tools? Comparative studies of tools like AProver, 2LS

As mentioned by nekketsuuu, SV-COMP has a termination category, and the Termination Competition has been going on for quite some time (there is some overlap).

It depends on what kind of termination you are interested in. This paper on AProVE gives an overview of that tool, which covers many of the techniques involved in general program termination analysis and types of programs that can be handled, though it does not really analyze the comparative strengths of different tools.

Sadly, I'm not aware of any modern overview paper that does this, which is unfortunate. The tool description papers of the competition participants for your category of choice would be a good place to start.


Any Non-trivial Logic System Defined with only Equality Preface
We can define a system of logic by conjunctions of rules that system must follow. For example, if we wanted to define transitivity of numbers:
$$F_1: \forall a,b,c. a < b \land b < c \rightarrow a < c$$
We could similarly define associativity:
$$F_2: \forall d,e,f. (d + e) + f = d + (e + f)$$
Then we could define a system that follows these rules by the conjunction of all these rules:
$$F : F_1 \land F_2$$
Then if we wanted to check if a statement is satisfiable, say $S: c + 2 = b \land b = 1 \land c = 0$, we could take the conjunction of $S \land F$ and then calculating their congruences classes to see if any contradictions arise.
Question
I am curious: Can any valid non-trivial systems of logic be describe only using equalities ($=$) and conjunctions ($\land$)?
What I mean by non-trivial is that for the logical system in question, $F$, there exists some statements $S$, only using conjunction and equality for both $F$ and $S$, such that:
$$SAT(S \land F) \neq SAT(S)$$
Where $SAT$ evaluates to $\top$ or $\bot$ if the logic is satisfiable or not.
This is to say, the conjunction of $F$ with $S$ changes the satisfiability of $S$. If $S$ were already satisfiable, $F$ may define a system where $S$ is in fact a contradiction.
Example 1
As an example say:
$$S: x = 1 \land x = 0$$
This is satisfiable by $x = 1 = 0$, because we haven't defined what the relation of 1 and 0 are. If we introduce a system of logic:
$$F: 1 \neq 0$$
Then take their conjunction:
$$1 \neq 0 \land x = 1 \land x = 0$$
This is no longer satisfiable. You can see this is mainly because we introduced an inequality from $F$. I am wondering if you could define such an $F$ only using equality and conjunction that changes the satisfiability of an $S$.
Example 2
I don't think this is possible. Let's say, for instance we define a system of logic $I$ that defines a set of integers and the addition operation ($+$), conjunctions of associativity, transitivity, reflexivity, axioms, etc. Let's assume we do this only using equality and conjunctions.
Then we describe a statement:
$$S: a = b \land a = b + 1$$
$S$ is perfectly satisfiable on it's own because they would all be in the same congruence class, and because $+$ is not defined we have $a = b = b + 1$. Then introduce $I$:
$$I \land S$$
Clearly this should not be satisfiable. However, if we have only used equality then there is nothing to let us know that any particular congruence class will have a conflict and thus it is still satisfiable (I think). Thus resulting in a contradiction that we have not actually define the logic system of integers. From this, I would conjecture that this is not possible, as you would need some inequality ($<, \neq, >$) to refute or at least discover a contradiction.

If all you have is equalities and uninterpreted function symbols, then you have an algebraic theory a la universal algebra. A singleton set (or a collection of them in the multi-sorted case) is always a model of an algebraic theory. That is, every algebraic theory is, at least, trivially satisfiable. So if both $S$ and $F$ are required to simply be conjunctions of equations, then $SAT(S)=SAT(F)=SAT(S\land F)=\top$.


Determine image of hypercube under linear map Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb R^N$ with each entry of $w$ in the range $[0,1]$. In other words I'd like to find the image of the unit hypercube in $\Bbb R^N$ under the map represented by $A$. Does there exist an algorithm that runs in time polynomial in $N$?

Everything I've thought of so far is exponential, basically looping over the $2^N$ vertices of the hypercube. The problem is similar to that of determining the convex hull of a given set of points, except that the entries in $w$ needn't sum to $1$. Obviously taking the convex hull of all $2^N$ points would work, but it's exponential again.

My motivation is that I want to determine the range of colours that can be seen under a given light source, based on the spectral power distribution of the light source and the responsivity curves of the three cone cells in the eye.

I eventually found an answer. The image of a hypercube in $\Bbb R^3$ under a linear map is called a zonohedron. They can be calculated efficiently, for example using the algorithm in An Efficient Algorithm for Generating Zonohedra (PostScript file) by Paul Heckbert.


Djikstra's shortest path vs Brandes algorithm for betweeness centrality I have a couple of Python scripts that calculate various network measures.

Given a graph (G), the first script calculates the average shortest path from each node to all other nodes and stores this in an Nx1 matrix (L). An implemntation of Djikstra's algorithm from the NetworkX Python library is used for this:

for i in range(num_nodes):
    for j in range(num_nodes):
        dj_path_matrix[i,j] = nx.dijkstra_path_length(G, i, j)

L = np.sum(dj_path_matrix, axis=0)/(num_nodes - 1)

Given the same graph (G), the second script uses an implementation of Brande's algorithm in the NetworkX library to calculate betweenness centrality and stores this in an Nx1 matrix (BC):

BC = nx.betweenness_centrality(G, normalized=True)

My question is: why does it take so much longer to calculate L compared to BC?

The way I understand it, BC of a node is a measure of how often a shortest path travels through that node. As such, to calculate BC, surely you would need to calculate all possible shortest paths in the graph. And surely then, BC should take at least as long as L? Using my scripts, given the same graph, it will take a couple of seconds to calculate BC, but up to half an hour to calculate L.

The way I understand it, BC of a node is a measure of how often a shortest path travels through that node. As such, to calculate BC, surely you would need to calculate all possible shortest paths in the graph.

This isn't necessarily true. Perhaps there is a different algorithm that is faster than what you outline. One possible explanation for the discrepancy in running times is that the NetworkX library uses a smarter algorithm. However, it's hard to know because you haven't told us how the function betweenness_centrality is implemented in NetworkX. It is also possible that it uses an algorithm along similar lines, but employs some optimizations that don't affect the asymptotic running time (big O) but does save a large constant factor.


Is radix sort a greedy algorithm? I was thinking of radix sort, and at a sudden thought that it uses de facto the paradigm  of dynamic programming, but I soon changed my mind to greedy algorithm. Is it really a greedy algorithm?

Personally, I would not call it a greedy algorithm. I'm not sure that's a useful way to think about it.

A greedy algorithm optimizes some global objective function by making small choices, where at each step we make a locally optimal choice (among all the choices at each step, we choose the one that best improves our objective function).  In a greedy algorithm, the objective function monotonically increases at each step of the algorithm.  I don't see any sense in which radix sort has this form.

This becomes clearest if we look at the version of radix sort that starts by sorting on the least significant digit, then the next-least significant digit, etc.  Here the objective function does not monotonically increase.  The first step can take you further away from being sorted, but then later steps bring you back.

For instance, consider the list $[0101, 0010, 0001]$.  Let's look at what happens if we apply radix sort to this list.  The first pass will transform this to $[0010, 0101, 0001]$: it got further away from being sorted.  After the second pass, we get $[0101, 0001, 0010]$, then after the third pass we get $[0001, 0010, 0101]$: it is finally sorted.  So, we started out being close to sorted, then we got farther away from being sorted, then we got closer -- not exactly the characteristic of a greedy algorithm.

For an even better example, consider the list $[0001, 0010, 0101]$.  Let's look at what happens if we apply radix sort to this list, even though it happens to already be sorted.  The first pass will transform this to $[0010, 0001, 0101]$.  I don't care what your global objective function is; this has certainly made the global objective function worse, because it changed the list from being completely-sorted to being not-sorted.  So, this shows that radix sort doesn't seem to be a greedy algorithm (at least if you start by sorting on the least significant bit).

There's an alternative version of radix sort where we sort first by sorting on the most significant digit, then the next-most significant digit, etc.  This does feel closer to a greedy algorithm, though I'm not sure that viewpoint is really useful in any practical way.

It is definitely not a dynamic programming algorithm.

I'm not sure that trying to classify it in this way is useful or helpful.  I don't think it'll help you, e.g., understand how greedy algorithms work, or help you design better greedy algorithms in the future in other settings.  I'd suggest you think about radix sort on its own terms: it just is what it is.


Converting a context free grammar to a PDA -- is my solution correct? I'm reviewing for my midterm and wanted to post this to see if anyone can spot any errors. Im supposed to make a PDA that recognizes this CFG:

$\qquad\begin{align}
  S &\to R1R1R1 \\
  R &\to 0R \mid 1R \mid \varepsilon
\end{align}$

Here is my solution; I'm aware that I forgot to draw the second circle around my accepting state.

Doesn't that language simply recognize any string in $\{0,1\}^*$ that has at least three $1$s in it?

If so, you just need a regular finite deterministic automaton with that can count up to three in order to recognize it.

This is because I'm not on the mood to do a direct translation of that grammar, if that is what you really wanted to check :P


Can't see how this can be true: any connected undirected graph $G$ contains vertex v such that removing v results in another connected Graph $G'$ I am attempting to prove this result but I found a case where I can easily disprove this statement.

  Suppose $G$ is a graph with two nodes u, v and an edge (u,v) and respective self edges, then removing the edge u,v results in two nodes left, therefore leaving the resulting graph disconnected.

Can someone show me why I am approaching this question incorrectly?

Suppose to the contrary that removing any vertex of a finite graph $G$ would disconnect it. Then $G$ could not contain any cycles (else we'd have an immediate contradiction) and so $G$ would have to be a tree. However, removing a leaf vertex of $G$ wouldn't disconnect it, contrary again to our assumption.


Strassen's matrix multiplication algorithm when $n$ is not a power of 2 The above image, describing Strassen's matrix multiplication algorithm, is from the book Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein.
The algorithm multiplies two square matrices of order $n$, where $n$ is a power of $2$, i.e., $n=2,4,8,16,32,\dots$ and so on.

  Can this algorithm be modified so that we can multiply two square matrices of order $n$, for all $n$?

The solution is to pad the matrices with zeroes, using the block matrix identity
$$
\begin{bmatrix}
A & 0 \\
0 & 0
\end{bmatrix}
\begin{bmatrix}
B & 0 \\
0 & 0
\end{bmatrix}
=
\begin{bmatrix}
AB & 0 \\
0 & 0
\end{bmatrix}
.
$$

Here $A,B$ are $n\times n$ matrices, and the big matrices are $N\times N$ for some $N > n$. In other words, we add $N-n$ rows and $N-n$ columns of zeroes.

You can do this in two ways:

Pad the original $n \times n$ matrices to $N \times N$ matrices, where $N$ is the closest power of 2. Note that $N < 2n$, so this doesn't affect the asymptotic complexity.
Pad the matrices recursively. Whenever a recursive call gets $m \times m$ matrices with $m > 1$ odd, we pad them to $(m+1) \times (m+1)$ matrices by adding a single row and a single column of zeroes. This also doesn't affect the asymptotic complexity.

A third option is to make use of, say, a 3x3 matrix multiplication algorithm if the dimension is odd but divisible by 3. Laderman found such an algorithm which uses 23 multiplications (instead of the trivial 27).


How to find a basis which is guaranteed to need 9 or less characters to represent a 12 digits number? I'm trying to map a 12 digit number into a fixed width file.  For a number of reasons, it must be compressed in such a way that it is guaranteed to be less than or equal to 9 characters (alpha numeric is fine).  My first thought was a change of base, but I can't find an equation which gives an upper bound the number of characters needed for a given base.

For example, transforming into base 32

123456789101 -> 3IV9I6JD

Which is 8 digits.  How to find a basis which is guaranteed to need 9 or less characters to represent a 12 digits number?

The largest 12 digit number in base 10 is $10^{12} - 1$.  In general the largest $n$ position number in a base $b$ is $b^{n} - 1$.  So in your case you need a base large enough that $b^{9} - 1 > 999,999,999,999$ $(10^{12} - 1).$  Solving for $b$:

$$b^{9} - 1 > 10^{12} - 1$$
$$b^{9} > 10^{12}$$
$$b^{9/9} > 10^{12/9}$$
$$b > 10^{12/9}$$
$$b > \sqrt[9]{10^{12}}$$
$$b > 21.54$$

So make your base 22 and your numeric data will fit in 9 positions.


Are there any context-free languages that are not known to be in $\mathrm{DTIME}(O(n))$? The problem of determining, given a string $x$ and a context-free grammar $G$, whether $x \in L(G)$ is conjectured to take more than linear time in the length of $x$. Currently the best known algorithm is Valiant's which takes $\Theta(|G||x|^\omega)$.

On the other hand, for a fixed $G$ there may be a specialized recognition algorithm which is faster, and indeed linear-time algorithms have been developed for many grammars and classes of grammars of interest. In fact, I can't think of any example of a language which doesn't have a linear-time recognition algorithm.

Is there any example of a context-free language that is not known to be recognizable in linear time?

Theorem 1 in "If the Current Clique Algorithms are Optimal,
so is Valiant’s Parser" shows an explicit context-free grammar $G$ such that if $G$ can be parsed in linear time (or even a bit slower), then there's a surprisingly fast algorithm for the $k$-clique problem. As the paper says, no such algorithm for $k$-clique is known to exist and it would be a breakthrough if it was discovered; therefore, there's no known linear-time algorithm for this grammar $G$.


Which of these properties hold for all FO theories? (but not regarding fragments thereof) Which of these properties hold for all FO theories? (but not regarding fragments thereof)
a. Decidable
b. At least expressive as propositional logic
c. NP-complete
a) Decidable: no, some first order theories are not decidable.
b) Propositional logic lacks expressiveness, so possibly yes. However, are hence all FO theories more expressive than propositional logic?
c) NP-complete: An undecidable FO-theory is not NP-complete
Are a) and c) correct? How about b), is there a counter example?

Your answers to (a) and (c) are correct. To tell whether (b) is correct we need a precise notion of expressiveness.
The issue is that propositional logic and first-order logic have totally different semantics: their notions of "model" are valuation and structure respectively. When two logics use the same notion of "model" we can straightforwardly compare their expressive powers by looking at what sets of models their sentences can pin down respectively. For example, SOL is strictly more expressive than FOL since there is an SOL-sentence whose class of models is not the class of models of any FOL-sentence (e.g. take an SOL-sentence whose models are exactly the finite structures, and observe via compactness that no FOL-sentence can do this). But this direct comparison idea doesn't even make sense for FOL vs. propositional logic.
Now for the specific question you ask, due to the fact that you look at all FOL theories this is arguably a moot point since there is a particular FOL-theory which is extremely simple, namely it only has two formulas up to semantic equivalence and it is linear-time decidable:

 Take the theory in the empty language of a one-element pure set.

(Of course if you allow inconsistent theories this is even easier, but that seems silly. Incidentally note that $(i)$ the example above really does have to be that "small" per here and here, and $(ii)$ this also addresses (c).)
Since propositional logic isn't that simple, it's pretty clear that this is an FOL-theory which is not as expressive as propositional logic in any meaningful sense. But I think it's still worth highlighting this ambiguity, since there will be less trivial situations where we want to compare very different logics and there we will absolutely need a precise definition to say anything.


Is it possible to entangle more than 2 qubits? If so, is it useful? With 2 qubits, there are 4 ways to entangle the qubits - the four maximally entangled two-qubit Bell states, of which one is $1/\sqrt{2}(|00\rangle + |11\rangle)$.

Is it possible to entangle more than two qubits together?  If so, is there any practical use to doing so?

Ok, entanglement just clicked for me and totally makes sense.

Yes it is completely possible to entangle more than two qubits!

Entanglement is a fancy word with a really simple meaning.

In quantum computing, you can modify the probabilities of values being read.

If you have two qubits, normally there is some probability for each of the possible states: reading a 0 for each qubit, reading a 1 for each qubit, reading a 0 for qubit a and a 1 for qubit b, and reading a 1 for qubit a and a 0 for qubit b.

When you modify probabilities such that any of these probabilities drop to zero, it limits the possibilities of what can happen when you measure the qubits.

Most specifically, in the two qubit case, you could eliminate the situations where they disagree (states $|01\rangle$ and $|10\rangle$), and make it a 50/50 chance between the states of them both being on, or both being off.

Now, they have NO CHANCE of disagreeing when you read their values.

Who knows how reality "implements" this situation, since distance doesn't matter, but there you go... it's pretty darn simple.

A very simple 3 qubit entanglement would be this: $|000\rangle$, or this: $1/\sqrt{2}(|000\rangle + |111\rangle)$


A canonical representative, for this equivalence relation on matrices This question is inspired by Constructing inequivalent binary matrices.

Define the equivalence relation $\sim$ as follows: If $M,N$ are two $8\times 8$ binary matrices (all elements are $0$ or $1$), say that $M \sim N$ if you can transform $M$ into $N$ by a sequence of moves, where each move picks some pair $(i,j)$ and swaps rows $i$ and $j$ and then swaps columns $i$ and $j$.  For example,
\begin{equation}
\left( \begin{array}{ccc}
0 & 0 & 0 \\
0 & 1 & 1 \\
1 & 0 & 0 \end{array} \right) \sim
\left( \begin{array}{ccc}
1 & 0 & 1 \\
0 & 0 & 0 \\
0 & 1 & 0 \end{array} \right).
\end{equation}
This equivalence relation induces a set of equivalence classes.

Is there a way to define a canonical representative for each equivalence class, so that given any matrix $M$, we can efficiently compute the canonical representative $M^*$ corresponding to the equivalence class containing $M$?  I'm hoping for a simple and efficient algorithm to compute the canonical representative.

For instance, one way to define a canonical representative for matrix $M$ would be as follows: among all matrices $N$ that are equivalent to $M$, choose the one that is lexicographically first.  However, I don't know of any fast way to compute the canonical representative corresponding to a given matrix $M$.  (One could enumerate all matrices that are equivalent to $M$ by trying all $8!$ possible permutations, and then check which one is lexicographically first, but this is inefficient: it requires $8! \approx 2^{15.3}$ steps of computation, which is too much.)  Is there a better approach?

Alternatively, is there a way to define a canonical representative for each equivalence class, so that we can quickly test any given matrix $M$ to determine whether it is in canonical form?  (i.e., there is an efficient algorithm to check this)

A good answer to this question might help solve Constructing inequivalent binary matrices.

Here are some ideas to get started. First, we can arrange that the diagonal is of the form $0 \cdots 0 1 \cdots 1$. This breaks the original problem into two new problems which are equivalent to each other. Let's concentrate on the part with zeroes on the diagonal. We can sort the rows according to Hamming weight, and can arrange the first row to be of the form $0\cdots 0 1\cdots 1$, say the one with minimal weight. If it is the only row having the same weight, then again we have broken the problem into two parts, and can continue recursively. If there are several rows with the same minimal weight, we can try tie-breaking using column weights, but this is not always enough. That's where this approach gets stuck, though perhaps one could be more creative and extract a normal form from these ideas.


Solve the worst case of this recurrence equation I am trying to find the worst case $Θ$ bound for the following recurrence equation:
$$
T(n)=\sum_{i=1}^kT(a_i)+n+\lg k\sum_{i=1}^ka_i\quad
where\quad n=1+\sum_{i=0}^ka_i\quad and\quad
a_0\ge a_1, a_2, \dots,a_k\ge 1
$$
By master theorem, with $k=a_0=a_1=n/3$ and $a_2=a_3=\dots =a_k=1$, $T(n)=Θ(n\lg n)$. Now my freind and I guessed that the worst case of $T(n)$ is also $Θ(n\lg n)$, but we are not able to prove it.

My question is, what is the worst case bound of $T(n)$ and how to prove it?

Edit: By worst case I mean that $T(n)$ to be the maximum of the expression I wrote over all $k\ge1$ and $a_0\ge a_1,a_2,\dots,a_k\ge1$ such that $n=1+a_0+\dots+a_k$.

For starters, let's rewrite the recurrence as
$$ T(n) \leq \max \sum_{i>0} T(a_i) + O(n\log n). $$
Suppose now that we could show that $T(m+1) - T(m)$ is increasing in $m$. In this case, it follows that we can assume that $a_2 = \cdots = a_k = 1$, and so
$$ T(n) \leq \max T(a_1) + O(n\log n). $$
The largest that $a_1$ can get is $n/2$ (well, $(n-1)/2$), and so
$$ T(n) \leq T(n/2) + O(n\log n). $$
Expanding this, we get $T(n) = O(n\log n)$.

Showing that $T(m+1) - T(m)$ (if this is indeed true) looks a bit messy, but potentially could be done in the spirit of the following lemma.

Lemma For all $a,b \geq 1$, we have $T(a+b) > T(a) + T(b)$.

Proof. Choose the $a_i,b_j$ for which
$$
\begin{align*}
T(a) &= \sum_{i=1}^k T(a_i) + a + \log k \sum_{i=1}^k a_i, \\
T(b) &= \sum_{j=1}^\ell T(b_j) + b + \log l \sum_{j=1}^\ell b_j.
\end{align*}
$$
Consider the sequence $c_0 = a_0+b_0$, $c_1,\ldots,c_t = a_1,\ldots,a_k,b_1,\ldots,b_\ell,1$, where $t = k+\ell+1$. This sequence sums to $a+b-1$ and satisfies $c_0 \geq c_r \geq 1$ for all $r > 0$, and so
$$
\begin{align*}
T(a+b) &\geq \sum_{i=1}^k T(a_i) + \sum_{j=1}^\ell T(b_j) + T(1) + a+b + \log(k+\ell+1) \left(\sum_{i=1}^k a_i + \sum_{j=1}^\ell b_j + 1\right) \\
&> T(a) + T(b).
\end{align*}
$$


Bipartite Graph Game So say we have a bipartite graph G=(X,Y,E). Let's make a game out of it.

I go first. I pick a node in X. You go next. You pick a node in Y that is connected by an edge to the node I picked. Next it's my turn. I pick another node in X (must be a new one that hasn't been used before) that is also connected to the node in Y you just picked. We continue playing in this manner, until someone cannot pick a node (i.e. all edges out of the current node have already been used). When that happens, the person who cannot pick a next node loses.

I'm supposed to find a polynomial time algorithm to decide which of the two players (you or me) can force a "win" for a given bipartite graph.

I'm stumped. I've approached this in many different ways, including the following two:

1) 1) each node in the xy "path" played will use two edges, except for the first and last nodes which will only use one edge. Idea: add one new node on each side of the bipartite graph, and connect to all opposite nodes. Then check for a perfect (or maximal) matching twice, removing the edges used in the first perfect (maximal) matching when finding the second one. I don't think this really helps us with the problem, though, as there are many different nodes you could visit next given a current node.

2) A second idea was to work with alternating/augmenting paths (as we "zig-zag" between the two sides). I again got stuck since at any given node there are many possible nodes to visit next.

Does anyone have any suggestions for this problem? I'm thinking it has to do with matching, but I could be wrong.

Thanks in advance!

Let me spell out the solution.

We first show that Player 2 wins if there is a perfect matching $\pi$. Player 2's strategy is very simple: if the current path ends at a vertex $v$, she choose $\pi(v)$. Induction shows that $\pi(v)$ is never taken, since the edges chosen by Player 1 never belong to the perfect matching. Player 2 never gets stuck, and so wins.

The more complicated case is when there is no perfect matching. Let $\pi$ be a maximal matching, and let $x \in X$ be a vertex not in $\pi$. Since $x \notin \pi$, the edge $(x,y)$ chosen by Player 2 is not in $\pi$. If he can, Player 1 now choose $\pi(x)$, and induction again shows that Player 2 never chooses edges in $\pi$, and so Player 1 can choose an edge in $\pi$ as long as there is one adjacent to the vertex that Player 2 chose. If Player 1 gets stuck then the edges chosen by the players trace out an alternating path with Player 2 having one extra edge, showing that $\pi$ wasn't a maximal matching.


What is a swap-with-memory instruction? I am reading an article on algorithms for parallel computing and came across the following sentence.  What do they mean by a swap-with-memory instruction?

  Our algorithm provides reasonable latency in the absence of contention, requires only a constant amount of space per lock, and requires no hardware support other than a swap-with-memory instruction.

J. M. Mellor-Crummey and M. L. Scott, Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. ACM Transactions on Computer Systems, 9(1):21–65, 1991. (PDF)

I would assume the fetch_and_store instruction is meant. Look at the footnotes on page 2:

  1) Fetch-and-store exchanges a register with memory.

Keep in mind that this paper is over 20 years old, so the terminology can seem unfamiliar. However, often the semantic of the operations/instructions used in such papers are described in detail somewhere in the text.


Can BPP be bounded around any constant other than 1/2? A language $L$ is in BPP if there exists a randomised TM such that it outputs a correct answer with probability at least $1/2+1/p(n)$ for some polynomial $p(n)$, where $n$ is the length of the input. This probability can be amplified to $1-2^{q(n)}$, for some polynomial $q(n)$ by repeating the algorithm polynomially many times and taking the majority.

I was wondering if it is necessary to have this bound around the constant $1/2$? Can we have a randomised algorithm that answers correctly with probability $c+1/p(n)$ for some $c<1/2$ and still amplify the probability in polynomial time?

The proof for the case of $1/2 + 1/p(n)$ uses Chernoff bound on lower tail that requires $0 < \delta <1$. $\delta= 1-1/2p$ in that case which means $p$ should be greater than $1/2$. Proof here.

However here is a proof that weak BPP = Strong BPP where strong BPP is BPP as we know it and weak BPP is when if $x\in L,$ $P(TM\ accepts\  x) \geq s(n)+1/p(n)$, and if $x \not\in L, P(TM\ accepts\ x ) \leq s(n)$, where $p(n)$ is any polynomial and $s(n)$ is any polynomial time computable function.

If $c < 1/2$ then for any problem there is an algorithm that answers correctly with probability at least $c+1/n$, say. For small $n$, the algorithm just outputs the hardwired correct answer. When $n$ is large enough so that $c + 1/n \leq 1/2$, the algorithm just tosses a coin.

What went wrong? For BPP amplification to work, we need a gap between the promise for a Yes instance and the promise for a No instance. In your definition of "weak BPP" (not a standard term), you are given an algorithm such that:

On a Yes instance, accepts with probability at least $s(n) + 1/p(n)$.
On a No instance, accepts with probability at most $s(n)$.

In contrast, in your suggested definition, we have the following promise:

On a Yes instance, accepts with probability at least $c + 1/p(n)$.
On a No instance, accepts with probability at most $1 - c - 1/p(n)$.

If $c < 1/2$ then for large enough $n$, the two acceptance intervals overlap (at acceptance probability $1/2$), and so the definition is meaningless. When $c = 1/2$, there is an inverse polynomial gap, which can be amplified to a constant gap, to match the standard definition of BPP.


Cases where string concatenation is commutative Strings are known to not satisfy the commutative property.
pq is not equal qp unless p is empty string. Is there a case where pq can be qp where both are non empty strings and p and q are distinct

Simple solution: $a\cdot aa = aa \cdot a$?

In general there is a characterization due to Lyndon and Schützenberger.
For nonempty words $x,y\in \Sigma^+$ the following are equivalent:

$xy=yx$
there exists $z\in \Sigma^+$ such that $x=z^k$ and $y=z^\ell$ for some $k,\ell >0$.
there exist $i,j>0$ such that $x^i = y^j$.

This means that $x$ and $y$ commute ($xy=yx$) iff they are powers of the same string, like $bbabba\cdot bbabbabba = bbabbabba \cdot bbabba$. So, basically the examples will not get more complicated than the proposal $a\cdot aa = aa \cdot a$ above.


Calculate the effective access time This question seems to be causing a lot of debate and I'm wondering whether my working is correct.

A computer with a single cache (access time 20ns) and main memory (access
time 500ns) also uses the hard disk (average access time 0.01ms) for virtual
memory using paging. If it is found that the cache hit rate is 95% and the page
fault rate is 1%
Calculate the effective (average) access time (EAT) of this system for a
sequential access system.  (a) 73.5ns. (b) 55ns. (c) 50ns. (d) 74.75ns.

My working was as follows: (0.95x20) + 0.05 (0.01(10000+500+20) + 0.99(500+20))
Leading me to an answer of 50 being C), however others have seem to have chosen D) as their answer
Any help would be appreciated.

Seems correct , cache hit gives you 0.95*20 ns if it misses then 0.05 or 5% of the time you consult memory that is 0.05*( no page fault hence 0.99*( 500 from mem to cache + 20 from cache to cpu) else if page fault occurs then 1% or 0.01 *( 10000 ns from disk to mem +  500 ns from mem to cache + 20 ns from cache to cpu))
Should be 45.5 ns which I would give as C


Are there search problems that cannot be written as decision problems? I'm not sure whether the distinction between decision and search problems has a deeper significance or if it is just concerns the immediate answer to the problem.
Of course, if you have a finite solution space then you can easily turn a search problem into a decision problem by assigning a 'yes' to whichever output satisfies your conditions. Even if you are searching for the object which maximises some function on the solution space, you can pairwise compare the evaluations of the function to assign 'no' values and be left with the 'yes' solutions.
Perhaps there are search problems cannot be turned into decision problems if we are unable to enumerate the solution space and assign a 'yes' or 'no' to every value?

In terms of decidability, they are equivalent. Indeed, in order to turn a decision problem into a search problem we do the following:

Run the decision algorithm
If it outputted "no", return "no solution exists"
Else, create a list called $Active$, and a counter $w\in\Sigma^*$.
Until you find a solution, repeat the following 5-6 steps:
Create a new instance of an algorithm that checks whether $w$ is a valid solution, and add this instance to $Active$.
For every instance in $Active$, run the algorithm one more step. If any one of them returned "true", return the $w$ associated with it. Otherwise, increase the counter $w$ by one.

Intuitively, the word $w$ enumerates over all $\Sigma^*$, and for each one we check wether it is a valid solution. Since the decision algorithm must have returned "true", there is a valid solution, say $w^*$. Since $w$ enumerates over all $\Sigma^*$, then it will also go through $w^*$ and thus will find the valid solution.

In terms of computation time, the two might differ. It depends on the language itself, and on the granularity of the time complexity you are trying to achieve. For example, $SAT$ has a known search to decision reduction that runs in polynomial time. This means that you can solve the search problem by a polynomial factor of the decision problem. But it wont help you if you are looking for a sub-polynomial factor instead.


counterexample for this graph isomorphism algorithm I'm trying to learn about graph isomorphism and I stumbled upon coloring. When given 2 graphs, you give each vertex a color according to properties of their neighbors and any vertex on graph 1 can only map to any vertex on graph 2 with the same color. This way you cannot have false negatives (if the algorithm says there's no mapping, it is so) but you may have false positives. So now I'm looking for a false positive of my particular graph isomorphism coloring algorithm.

We're going to assign each vertex a "breadth" and a "color", which are both strings. Assume both graphs have n vertices.

Step 1: we assign depth=0. We pick a starting vertex and assign it
(breadth, color) = ("0;","0;").
We assign a set S={that vertex}.

    Step 2: depth++;
    set T=[all neighbors that don't have a color yet of all vertices in S].

        Step 2.A: for each vertex in T, name it t and set t.breadth = depth + ";"

        Step 2.B: for each t in T:
        t.breadth += '[' + (concatenate all colors of all
        neighbours of t that are in S, in lexicographically sorted order) + '];'

        Step 2.C: for each t in T:
        t.color = t.breadth + '{'+(all breadths of all neighbours
        of t that are in T, concatenated in lexicographically sorted order)+'}'

    Step 2.D: S=T; goto step 2 unless T is empty.

Step 3: Save the resulting coloring, clear S and T and the coloring and
repeat from step 1 for *each possible starting vertex for both graphs*.

Step 4: We now have n colorings for both graphs. Deduce if this leads to a
negative. If not, for now assume that the graphs are isomorphic.

A bit of explanation on step 4: Suppose I pick a starting vertex for graph 1, we need to look at each starting vertex for graph 2. If a starting vertex for graph 2 then leads the exact same number of colors for each color of graph 1, we have possible vertex mappings from graph 1 to graph 2. If this is also the case for another starting vertex of graph 2, we have extra mapping possibilities. with 1 starting vertex for graph 1, we look at all starting vertices from graph 2 and union the results together.

When looking at another starting vertex for graph 1, we get another set of mappings. Each starting vertex of graph 1 leads to a set of mappings, and we're looking at the interesection of those sets. If that intersection is empty, the graphs are not isomorphic.

Now, I'm looking for two graphs for which this algorithm says they're isomorphic, while they're not.

I'm assuming that the graphs are connected.

Note that the colors might grow exponentially large this way, but we can avoid that by replacing parts with placeholders.

I've not looked closely at your algorithm so I'm not sure exactly what it does. However, it sounds quite a lot like colour refinement (also known as the 1-dimensional Weisfeiler-Lehman method). I suggest you look at the following paper, which will both explain that method and show a class of graphs whose isomorphism problem it cannot solve, even though graph isomorphism on those specific graphs is in P.  Even if your algorithm turns out to be different from colour refinement, a similar construction might give some graphs it doesn't work on.

J.-Y. Cai, M. Fürer and N. Immerman, An Optimal Lower Bound on the Number of Variables for Graph Identification.  Combinatorica, 12(4):389–410, 1992. (Free PDF)

By the way, one thing you can (probably) do to avoid the labels your algorithm assigns from becoming exponentially long is to just replace them with 1, 2, ... at each round.  You (probably) don't need to know exactly what label each vertex has; rather, you (probably) just need to know whether two vertices have the same label or not.


How does a computer "wait" time? Me and a friend were discussing how programming languages can perform asynchronous tasks, like waiting 15 seconds before performing another task, and we started a debate.

I know that computers have an internal clock that uses the CMOS battery that can keep track of time, but how does it know it has been 15 seconds since right now and since when I told it to wait 15 seconds without looping infinitely and performing conditional operations, or does it do that?

In their most basic form, computers use electrical signals that are represented as 1's or 0's. A 1 meaning that there is an electrical signal and a zero meaning that there isn't an electrical signal.

A computer keeps track of time using a vibrating crystal oscillator. This crystal oscillator gives off a constant and precise frequency. The oscillator is powered by a small and weak CMOS battery on your motherboard that provides a constant electrical signal for up to three years.

So how can a computer use this oscillator along with binary (1s and 0s) to keep track of timers?

When an interval is set, a value of zero is given to the computer along with a threshold based on the length of the interval and the frequency of the oscillator.

threshold = length of interval in ms / 1000 * frequency of crystal in MHz

When the oscillator vibrates, it puts off an electrical signal (1) and triggers a binary calculation that adds 1 to to the initial binary number (the one that started at 0). Once the initial value passes the threshold, the binary function puts off a 1 indicating that the interval has been fulfilled. Depending on the operations that are done after the threshold is met, the interval may be reset, saved, altered, or deleted.

Helpful links:

https://www.youtube.com/watch?v=1gyCZIBk_88

https://www.computerhope.com/jargon/q/quartz.htm


Pushdown automaton accepting $\{a,b\}^*$ with twice as many $a$s as $b$s Design a pushdown automaton that can accept

  $$\{w|w\in\{a,b\}^*\text{ and $w$ has twice as many $a$s as $b$s}\} \, .$$

I have a solution as the following. The notation seems to follow "An Introduction to Formal Languages and Automaton" by  Peter Linz, where $\delta$ is the transition function with three arguments: current state, input, current stack top; $\lambda$ as the second argument of $\delta$ means empty string $\epsilon$ in some other textbooks, and $\lambda$ as the third argument of $\delta$ means the transition ignores the current stack top. The $\lambda$ on the right hand side means "pop the top element of the stack".

I have several confusions,

1) I am not sure what the right-hand side notation means. For example, does the right hand side of $\delta(q_1,a,A)=\{[q_2，A]\}$ means pushing an $A$ into the stack? Or it means the stack top stays $A$ without a new $A$ pushed to it?

If this means "push", then what about $\delta(q_1,a,C)=\{[q_2，C]\}$? $C$ seems to mark the bottom of the stack. We push another $C$ to the stack when there is already a $C$ in it?

2) I think the solution might be wrong. I don't see why it accepts $aab$. Tracing this string, I think the transition is the following based on the design (if the big letter at the right-hand side means pushing a new symbol),

$q_0,\lambda \to_\lambda q_1,C\to_a q_2,CC \to_\lambda q_1,ACC \to_a q_2,AACC \to_\lambda q_1,AAACC \to_b q_1,AACC$

It is very strange and I feel very confused. Hope someone can help! Thank you!

When in doubt, one should always consult the definitions.

In this case, this is Definition 7.1 of the book by Peter Linz.

It states that $$\delta : Q \times (\Sigma \cup \{ \lambda \}) \times \Gamma \rightarrow \textrm{finite subsets of } Q \times \Gamma^*$$
Thus, $\delta(q,a,A) = \{[q_1,w_1], \ldots, [q_k,w_k\}$ means that when a pushdown automaton is in state $q$ and sees an $a$ on input (where $a$ may be an input or the empty string $\lambda$), then it can enter any one of the states $q_1$ to $q_k$ and replace $A$ by the corresponding string of stack symbols $w_i$.

Therefore, a pushdown automaton can push a string $w$ to the stack by reading $\lambda$ and replacing it by $w$. Or it can pop the top symbol $b$ by seeing $b$ on the stack and replacing it by $\lambda$.


Witness for the $EU(\phi_1,\phi_2)$ using BDDs I wanted ask if you know an algorithm to find the witness for $EU(\phi_1,\phi_2)$ (CTL formula "Exist Until")  using BDDs (Binary Decision Diagram). In pratice you should use the fixed point for calculating $EU(\phi_1,\phi_2)$, that is:

$\qquad \displaystyle EU(\phi_1,\phi_2)=\mu.Q (\phi_2 \vee (\phi_1 \wedge EX Q)) $

Unwinding the recursion, we get:

$\qquad \displaystyle \begin{align}
  Q_0 &= \textrm{false} \\
  Q_1 &= \phi_2 \\
  Q_2 &= \phi_2 \vee (\phi_1 \wedge EX \phi_2) \\
  \ \vdots
\end{align}$

and so on.

To generate a witness (path) we can do a forward reachability check within the sequence of $Q_i’s$, that is find a path

$\qquad \displaystyle \pi= s_1 \rightarrow s_2 \rightarrow \cdots \rightarrow s_n$

such that $s_i \in Q_{n-i} \cap R(s_{i-1})$ (where $R(s_{i-1})= \{ s \mid R(s_{i-1},s) \}$ and $R(s_{i-1},s$) is the transition from $s_{i-1}$ to $s$ ) where $s_0 \in Q_n $ and $s_n \in Q_1=\phi_2$.

How you can do this with BDDs?

What you describe is symbolic model checking, and it is treated in this set of slides, using reduced ordered BDDs.

In a nutshell, you still do the fixpoint iteration, the main issue being how to do the transformation $Q\mapsto \phi_2\vee(\phi_1\wedge EXQ)$ on BDDs. The elementary operations you need are renaming (to replace unprimed by primed variables in $Q$, obtaining $Q'$), boolean operations (to form $\phi_2\vee(\phi_1\wedge R\wedge Q')$) and abstraction (to do existential quantifier elimination on the primed variables). The witness generation can then be done similarly forwards from the initial states, requiring at step $i$ that $s_i$ is in $Q_{n-i}$ as you did above.


Finding a O(n) solution to: max difference of pairs array question I don't know an O(n) solution to the following:

Given an array of n integers, find the largest difference between any two pairs in the array: however, the larger integer must have a higher index in the array than the other.

Ex: alg({9, 2, 6, 7}) = 5

It seems straightforward, yet it eludes me.

Create an array considering the minimum value seen so far in the array (in O(n)).

Ex. (9, 2, 2, 2)

Create an array containing the differences between the previous array and the original array (again, in O(n)).

Ex. (0, 0, 4, 5)

Find the maximum value in the array (O(n)). In this case, the answer is 5 as required.

This can be done in O(1) memory and only one pass if a few optimizations are made.


Understanding definition of NP In my lecture notes, the definition of the class NP is given as:

A language $L$ is in the class NP, if there exists a turing machine $M$ and polynomials $T$ and $p$ such that:

For every input $x$, $M$ terminates after at most $T(|x|)$ steps
If $x\in L$, then there is a "proof"(or certificate) $t\in\{0,1\}^{p(|x|)}$ such that $M$ accepts the string $\langle x,t \rangle$
If $x\notin L$, then for any string $t\in\{0,1\}^{p(|x|)}$, $M$ rejects $\langle x,t \rangle$

Firstly, are we saying that $M$ here is a universal turing machine, i.e. $M(\langle x,t\rangle)=M_x(t)$, also is it necessary to use the same $t$ for all $x$.
Also $M$ is checking whether or not $x$ lies in the $L$, so shouldn't we run just input $x$ on $M$, why is the $t$ necessary. Is there any particular reason why $t$ is called a certificate? Any help with understanding this definition would be greatly appreciated.

Here is an example that will hopefully make things clearer. Consider the problem 3COL, which is the set of all graphs that can be legally colored using 3 colors. It is conjectured that no polynomial time algorithm can determine whether a graph belongs to 3COL (i.e., can be legally colored using 3 colors). However, given a 3-coloring of the graph, it is easy to check whether it is legal (that is, you can do it in polynomial time). In this case:

$L$ is 3COL.
$x$ is a graph.
$t$ is a 3-coloring of $x$.
$M$ is a machine that checks that $t$ is a valid 3-coloring of $x$.

If a graph $x$ is 3-colorable, then some witness $t$, namely a valid 3-coloring, will convince $M$ that $x$ is in 3COL. Conversely, if a graph $x$ is not 3-colorable, then no 3-coloring $t$ would be valid, and so $M$ will always reject given inputs $x$ and $t$ (for any $t$). This shows that 3COL is in NP.

What happens if $t$ is the same for all $x$? In this case we can hard-code $t$ into the algorithm, and do away with the witness. Under such a definition we get P rather than NP.

What if $t$ is allowed to depend only on the size of $x$? The corresponding class is known as P/poly, and is important in computational complexity. It is more generally known as the class of (languages accepted by) polysize circuits. If you find this interesting, many advanced textbooks discuss this topic.


Algorithm to solve $L_1$ optimization of $\sum_i ||\mathbf{A_i x} - \mathbf{b_i}||_1$ Is there is an efficient algorithm to solve the following optimization:

$\mathbf{x}^* = \arg\min_\mathbf{x}\sum_i ||\mathbf{A_i x} - \mathbf{b_i}||_1$

for given $\mathbf{b_i}, \mathbf{A_i}\ \forall i$, where $|| \mathbf{y} ||_1$ is the $L_1$ norm (i.e. $\sum_j |y_j|$) and $\mathbf{A_i}$ are big matrices which we don't have their explicit representations, only access to operations $\mathbf{A_i y}$ and $\mathbf{A_i^T z}$?

I can solve the problem for small matrices $\mathbf{A_i}$ using linear programming using the same trick from here, but if the matrices are large, there is no obvious way (at least for me) to solve it using linear programming.

Any ideas and suggestions are welcome.

I have found the answer for this problem. One way is, as suggested in the comment, to stack the matrix $\mathbf{A_i}$ and $\mathbf{b_i}$ together and apply first-order convex optimization algorithm, such as Primal-Dual Hybrid Gradient (PDHG), inexact ADMM, or their variants.
For PDHG, the problem to solve is
\begin{align}
\mathrm{min}_{\mathbf{x},\mathbf{y}} &~ F(\mathbf{y}) + G(\mathbf{x}) \\
\mathrm{s.t.} & ~ \mathbf{Ax} = \mathbf{y}
\end{align}
where
\begin{align}
F(\mathbf{y}) &= ||\mathbf{y} - \mathbf{b}||_1 \\
G(\mathbf{x}) &= 0 \\
\mathbf{A} &= [\mathbf{A_1}^T, \mathbf{A_2}^T, ..., \mathbf{A_n}^T]^T \\
\mathbf{b} &= [\mathbf{b_1}^T, \mathbf{b_2}^T, ..., \mathbf{b_n}^T]^T. \\
\end{align}
Thus, the convex conjugate of $F(\mathbf{y})$ is
\begin{align}
F^*(\mathbf{y}^*) &= \mathrm{sup}_{\mathbf{y}} \left[\left<\mathbf{y},\mathbf{y}^*\right> - F(\mathbf{y})\right] \\
F^*(\mathbf{y}^*) &= \left<\mathbf{b},\mathbf{y^*}\right> + \mathcal{I}_{\mathbf{y^*}<\mathbf{b}}
\end{align}
where $\mathcal{I}_\mathcal{C}$ is an indicator function with value $0$ if the condition $\mathcal{C}$ fulfilled, otherwise $\infty$.
As the algorithm uses proximal operator, we need to get the proximal operator for $F$ and $G$,
\begin{align}
\mathrm{prox}_{F^*\sigma}(\mathbf{y}^*) &= \arg\min_{\mathbf{y}'}\left\{\frac{||\mathbf{y}'-\mathbf{y}^*||^2}{2\sigma} + F^*(\mathbf{y}^*)\right\} \\
\mathrm{prox}_{F^*\sigma}(\mathbf{y}^*) &= \max(\mathbf{y}^* + \sigma \mathbf{b}, \mathbf{b}) \\
\mathrm{prox}_{G\tau}(\mathbf{x}) &= \mathbf{x} \\
\end{align}
Thus, the algorithm in this case reads
\begin{align}
\mathbf{y}^{n+1} &= \max(\mathbf{y}^n + \sigma \mathbf{A} \mathbf{w}^n + \sigma \mathbf{b}, \mathbf{b}) \\
\mathbf{x}^{n+1} &= \mathbf{x}^n - \tau \mathbf{A}^T \mathbf{y}^{n+1} \\
\mathbf{w}^{n+1} &= \mathbf{x}^{n+1} + \theta (\mathbf{x}^{n+1} - \mathbf{x}^n),
\end{align}
with $\theta = 1$, and $\sigma \tau ||A||^2 < 1$.
All the operations do not need the direct access to the element of the matrix $\mathbf{A}$ and only require the operation of $\mathbf{A} \cdot$ and $\mathbf{A}^T \cdot$.


Design a Turing machine that accepts L={ww^r | w:(0,1)*}? Can anyone help :(

L = {ww^r | w element of (0,1)*}

Would it be like in :pseudo code, check if the string is equal to itself in reverse?

This can be done with a PDA or a TM. I'll assume you need a deterministic TM, for what I'm assuming is homework.

The strategy is to find the length of the string to determine where the middle is, then treat the tape as a stack to see if all of the characters match before and after that midpoint.

Here's an algorithm that can do it:

For every two input characters you read until you hit #, write a 0 after the last #. This will keep track of where the "middle" is. Mark the inputs as you read them.
If you hit # where you expected to find a number, the string length is odd, and so the machine can halt and reject.
Otherwise, write another # after your string of zeros.
Unmark all inputs and move the read head to the second #.
Using the number of zeros you have, mark the right half of the input.
Starting in the middle, working your way out, mark the left character and unmark the right if they match.
If you encounter a pair that doesn't match, halt and reject.
If you get all of the way to the #s, halt and accept.

For example, let's look at input #101100# (# here means the edges of the input). The read head is at the first #.

Input starts as # 1 0 1 1 0 0 # (leaving room for markers)
Mark the first two inputs, write a 0 at the end: # 1'0'1 1 0 0 # 0
Mark the next two inputs, write a 0 at the end: # 1'0'1'1'0 0 # 0 0
Mark the next two inputs, write a 0 at the end: # 1'0'1'1'0'0'# 0 0 0
You've found the second #, so the string is of even length. Write a # at the end: # 1'0'1'1'0'0'# 0 0 0 #
Unmark everything: # 1 0 1 1 0 0 # 0 0 0 #
Now, starting from the second #, mark the inputs from the right, and the 0s from the left until all of the 0s are marked:
First iteration: # 1 0 1 1 0 0'# 0'0 0 #
Second: # 1 0 1 1 0'0'# 0'0'0 #
Third: # 1 0 1 1'0'0'# 0'0'0'#
You now know the midpoint of the string (it's where an unmarked input is to the left of a marked input).
Starting from that midpoint, mark the left and unmark the right if they match:  # 1 0 1'1 0'0'# 0'0'0'#
Continue working outward, comparing in this way: # 1 0'1'1 0 0'# 0'0'0'#
On the third step, we find that 1 and 0 don't match. Halt and reject.

I'll leave it as an exercise to you to determine how to convert this algorithm into a TM.


Language of all even-length words with no 1's in left half Consider the following language:
$$L=\{w \in \textstyle\Sigma_1 ^*\mid|w| \text{ is even and 1's can only occur in the second half of $w$}\},$$
where $\Sigma_1 = \{0,1\}$.
I need to show that this is not regular. I tried to prove this with the pumping lemma.
Imagine that there exists a pumping length $d$, and consider the string $s=0^d1^d$. If we choose $s=xyz$ arbitrarily with $|y| > 0$, we will have three options.

$y$ can be in the first half of the string.

$y$ can be in the second half of the string.

$y$ can contain the first and second half of the string.

In the last option, $y$ can only be in the following form: $0(0)^+$ or $(0)^+(1)^+$. (Here $^+$ means Kleene plus.)
For the last form ($(0)^+(1)^+$), we see that $xyyz$ will have a $1$ in the first half, which is not in $L$.
Consequently, $L$ cannot be regular.

Two points:

the reasoning is incomplete: you need to show that pumping $y$ in the two first cases also leads to elements outside $L$
the reasoning does not use $ |xy|<d$ which entails that only the first case occurs.

But it is not wrong. If you want to ignore $|xy|<d $ then you need to argue the three cases. The first case holds because deleting $y$ creates a string of odd length or one in which a $1$ appears in the first half. The second case holds because if we pump $y$ $ n >1$ times a $1$ will flow into the first part.


shortest cycle passing through vertices a and b with changeable edge weights given a weighted undirected graph with $N$ vertices $(N \leqslant 500)$ we start from vertex $S$ and wo go to $M$  and then we go to $T$ and then we return to $S$.

each edge in graph has weight $a_i$ at the beginning but after the first time we pass any edge that edge weight will become $b_i$. ($b_i \leqslant a_i$)

the task is to find the minimum sum of edges for this traverse.

time limit : 2 sec.

This is from Iran's IO, a contest that is finished.  Source: https://quera.ir/course/assignments/4573/problems

This solution assumes all weights are non-negative.

  Lemma. There exists an optimal traverse with the following shape ($A, B,C$ may be the same vertex and may coincide with $S,M,T$), where each arrow represents a simple path, and paths represented by different arrows are edge-disjoint.

The strict proof of this lemma is somewhat tedious, so I omit it here. If I have time in the future, I'll add it into this answer.

Let $d_a(x,y), d_{a+b}(x,y)$ respectively denote the shortest distance between vertexes $x$ and $y$ when edges have weights $a_i$'s and when edges have weights $(a_i+b_i)$'s. Let $\mathrm{opt}$ denote the value of optimal solution, then by this lemma we have

$$
\begin{align*}
\mathrm{opt}\ge\ & d_a(A, B)+d_a(B,C)+d_a(C,A)\\
&+d_{a+b}(B,M)+d_{a+b}(C,T)+d_{a+b}(A,S).
\end{align*}
$$

On the other hand, following the shortest path (with weights $a_i$'s or $(a_i+b_i)$'s accordingly) from $S$ to $A$, then from $A$ to $B$, and so on, constitutes a valid traverse. Easy to see the cost of this traverse is no more than

$$
\begin{align*}
d_a(A, B)+d_a(B,C)+d_a(C,A)+d_{a+b}(B,M)+d_{a+b}(C,T)+d_{a+b}(A,S),
\end{align*}
$$

so

$$
\begin{align*}
\mathrm{opt}\le\ & d_a(A, B)+d_a(B,C)+d_a(C,A)\\
&+d_{a+b}(B,M)+d_{a+b}(C,T)+d_{a+b}(A,S).
\end{align*}
$$

As a result,

$$
\begin{align*}
\mathrm{opt}=\ & d_a(A, B)+d_a(B,C)+d_a(C,A)\\
&+d_{a+b}(B,M)+d_{a+b}(C,T)+d_{a+b}(A,S).
\end{align*}
$$

So one can pre-compute the all-pair shortest paths using Floyd–Warshall algorithm, then exhaust all posible $(A,B,C)$'s to find $\mathrm{opt}$. This algorithm costs $O(N^3)$.


Possible to construct a probabilistic halting problem solver? I'm a CS undergrad so my math/CS knowledge is not that deep so please correct me if my premise is flawed or I have made some incorrect assumptions.

So I was thinking, much in the way that some primality testers are probabilistic(they give you yes or no but have a chance to be wrong). Would it be possible to build a probabilistic halting problem solver? One that reports within a certain degree of error, whether a problem halts or not?

It depends what you mean by "probabilistic". There are at least two interpretations. First, the algorithm has some probability of success for every input. Second, the algorithm succeeds on a certain fraction of inputs.

For the first interpretation, it is easy to rule out such an algorithm: probabilistic computation can be simulated (inefficiently but effectively) using deterministic computation, by trying all possible coin tosses.

For the second interpretation, we will have to work a bit harder. Suppose that your algorithm is guaranteed to work with an asymptotic success probability of $2/3$. That means that the fraction of inputs in $[1,N]$ for which it gives the correct answer is some $p_N \to 2/3$. Now suppose you're interested in a certain program $P$. It seems that under a reasonable encoding of programs, you would be able to come up with a long stretch $[M,10M]$ (say) of programs equivalent to $P$. By taking $M$ large enough, it should be the case that by taking the majority vote on the answer of a "probabilistic" algorithm on all of these equivalent programs, you will be able to ascertain whether $P$ halts or not. This rules out even this interpretation of a "probabilistic" algorithm.


Equivalence relations with $\cap$, $\cup$ and $\circ$ I have the relations $E_1$ and $E_2$.

A reflexive, symmetric and transitive property shows that two relations are equivalent to each other. I need to prove if this is true for the following

a) $E_1 ∩ E_2$

b) $E_1 ∪ E_2$

c) $E_1 ∘ E_2$

I found out that a) is true, but I am not sure about it.
This is my proof for transitivity:

$E_1 ∩ E_2 ⇒ (a, b, c) ∈ E_1 ∧ (a, b, c) ∈ E_2 ⇒ \\((a, b) ∈ E_1 ∧ (b, c) ∈ E_1 → (a, c) ∈ E_1) ∧
((a, b) ∈ E_2 ∧ (b, c) ∈ E_2 → (a, c) ∈ E_2)$

Also I found different arguments on the internet, so I'm pretty unsure about this.

Regarding b) $E_1 ∪ E_2$ a friend found out that this is not transitive and they wanted to prove it with an example.
The example is the following:

$A = \{1,2,3\}$

$E_1 = \{(1,2), (2,1), (2,2)\}$

$E_2= \{(1,3), (3,1), (3,3)\}$

$E_1 ∪ E_2 = \{(1,2), (2,1), (2,2), (1,3), (3,1), (3,3)\}$

This is transitive, isn't it? If not, what is it what I did not understand?

And maybe you can help me with with c), as well.

Here are some hints:

a) If $E_1,E_2$ are equivalence relations then so is $E_1 \cap E_2$. The proof is just by "unpacking" the definitions. (More generally, every class defined by universal statements – those of the form $\forall x_1,\ldots,x_n \phi(x_1,\ldots,x_n)$ – is closed under intersection.)

b) When trying to prove that $E_1 \cup E_2$ is transitive, we get stuck in the following case: if $a E_1 b$ and $b E_2 c$ then we have to show that $a E_1 c$ or $a E_2 c$, though there is no reason to believe that this must be the case. This helps you construct a counterexample.

c) When trying to prove that $E_1 \circ E_2$ is symmetric, we get stuck: if $a E_1 x E_2 b$ then there is no particular reason that $b E_1 y E_2 a$ for some $y$. This helps you construct a counterexample.


Matching vertex values with sum of edge weights on bipartite graph Earlier this week I asked this question (please review):

  Imagine StackOverflow started offering a subscription where companies
  could buy X number of impressions per month for a set of tags.

  For example, you might be interested in running an ad with 50000
  impressions on the following tags: javascipt, typescript, react,
  nextjs, nodejs, webpack.

  StackOverflow "promises" you will get 50000 impressions, but they are
  free to distribute them across the above tags however they desire
  (could even be 100% to one tag).

One of the solutions provided suggested using the Hopcroft-Karp algorithm, which I have since been able to successfully implement.

However, I'm having trouble scaling this solution to work for my use case.  The bottle neck is actually in the setup of the graph more-so than the algorithm performance.

The problem is the massive number of edges that must be initialized.  Take the example below:

==Inventory==

Tag          Units

javascipt    2
typescript   4
react        3
nextjs       3

== Subscriptions ==

Account  Units   Tags
Acme     7       javacript, typescript, react, nextjs

Stark    4       javacript, typescript

If we create a vertex to represent every unit, then we would end up with a graph that has 101 edges (7*11 + 4*6)!

The problem I'm working on is orders of magnitude larger, so this quickly becomes unrealistic.

As suggest, I can reduce the number of vertex by scaling the units, but I lose resolution and that's actually somewhat important in this case (I can maybe scale by 100x max).

I was thinking there must be a more efficient way to do this, since I'm essentially duplicating vertex for every unit.  I came up with the following bipartite graph with weighted edges and vertex values:

The goal would be to to adjust the weights of the edges so that:

On the left, the sum of edges is equal the value of the vertex
On the right, the sum of edges is less than or equal to value of the vertex

Below is an example of one of the solutions:

I'm guessing (hoping) this is already a well known problem, for which there is also a well documented solution (ideally one that's not NP-hard)!

Maybe it's even possible to modify the Hopcroft-Karp algorithm to work for this?

I've got bad news.  There's no hope for an algorithm whose worst-case running time is polynomial in the size of the weighted graph (unless P = NP, which seems unlikely).

Your problem is as hard as the knapsack problem, which has no polynomial-time algorithm (unless P = NP) when the input is represented in binary.  The knapsack problem has a pseudopolynomial time algorithm, which means that there is an algorithm whose running time is polynomial in the numbers (but not polynomial-time in the size of the input).  In your setting, that turns into an algorithm whose running time is polynomial in the size of the unweighted graph (with a massive number of edges) but not polynomial in the size of the weighted graph (with a small number of edges).

You could try expressing this as an integer linear programming (ILP) instance, and then solve with an ILP solver.  It's possible that might yield a more efficient solution.  The core idea is to introduce an integer variable $x_{i,j}$ that counts the number of impressions provided to company $i$ in tag $j$; then you can introduce a few linear inequalities to capture the problem's requirements.


Understanding the definition of a language Could you please help me understand the following Language
$L = \{ a | a ∈ \{0, 1\}^∗, |a| = k ≥ 4, a = a_1a_2...a_{k−1}a_k, ∃i ∈ N, 1 ≤ i < k : a_i = a_{i+1} \}$
what does $a_i = a_{i+1}$ mean? Could you please give me an example of word in $L$?

The expression "$a_i = a_{i+1}$" means "$a_i$ and $a_{i+1}$ are equal".
Presumably $a_i$ is a symbol, that is, $a_i \in \{0,1\}$. Therefore the condition states that $a$ contains at least four symbols, and there are two adjacent symbols which are equal, that is $a$ contains either $00$ or $11$ as a substring. Stated differently, $a$ contains at least four symbols and it doesn't consist of alternating zeroes and ones (i.e. you are not allowing 0101, 01010, ... or 1010, 10101, ...).


Weak NP-completeness I know that the Knapsack problem is weakly NP-complete. I also notice that on Wikipedia:

  "A problem is said to be strongly NP-hard if a strongly NP-complete problem has a polynomial reduction to it [...]"

The way I prove the NP-hardness is by a reduction chain: SAT $\leq$ 3SAT $\leq$ Tripartite Matching $\leq$ Exact cover by 3-sets $\leq$ Subset sum $\leq$ Knapsack.

Does it mean all these problems are weakly NP-complete? Because it seems that according to Wikipedia if one of them is strongly NP-complete, Knapsack will be strongly NP-complete.

As is often the case, the Wikipedia article is misleading.

A problem involving integers parameters is:

Strongly NP-complete if the problem is NP-complete when the parameters are encoded in unary (i.e., $n$ is encoded as $0^n$).
Weakly NP-complete if the problem is NP-complete when the parameters are encoded in binary (which is the usual encoding).

In other words, there is only one notion of NP-completeness, and the confusing terms strongly and weakly NP-complete simply refer to different encodings of problems.

For a problem like SAT, these terms are simply inapplicable, since SAT has no integer parameters. The terms do apply to the related problem of weighted MAX-SAT, in which the input is a set of weighted clauses and a target, and the problem is to determine whether there is an assignment which satisfies clauses whose total weight exceeds the target.


Find cut vertex in tree with constraint on the size of largest component I have a connected and undirected graph without cycles (i.e. a tree), and I am trying to find a single cut vertex that, when removed, disconnects the graph into a set of connected components. The largest of these components should not have size greater than some threshold. So if one such cut vertex exists, I need to find an algorithm that returns it (possibly in linear time). The only approach I could think of is the following:

remove from the graph all vertices that have only one outgoing edge (i.e. one neighbour); these are the leaves of the tree
on the resulting graph, repeat the process until only one vertex remains; this should be the cut vertex
take back the original graph and remove the cut vertex. Check the size of the largest connected component

This algorithm should run in linear time, but I am not sure it will work in any situation. What's your opinion? The other thing I could think of is that the cut vertex should always be in the minimum vertex cover of the graph, although I don't really know where to go from here...

Your algorithm may not work. What you describe, in fact, is an algorithm for computing the center of the tree. The following is a brief theory behind this algorithm.
The distance, denoted by $dist(v,u)$, between two vertices $u$ and $v$ is defined as the shortest path between $u$ and $v$. The eccentricity of a vertex $v$ is defined as
$$ \epsilon(v)=\max_{u \in V}\{dist(v,u)\}$$
In simple words $\epsilon(v)$ is the maximum among all distances from the $v$ to a vertex $u$.
We define the center of a graph $G$ is the set of vertices with minimum eccentricity. Observe that step-by-step leaf removal in your algorithm does not change the eccentricity of the center.
Your algorithm essentially computes the center of the tree but the following is a counterexample. This tree

has the center $v_c$. Your algorithm will return $v_c$ as the cut vertex. But if your threshold is $3$ then the optimal cut vertex would be the vertex $u$.


Showing that $\{ c^n a^m b^{n+m} : n+m \geq 6\}$ is not regular I'm trying to show that $L_6=\{c^n a^m b^p : n+m=p,p \geq 6\}$ is not regular.
I need a little help, I was practicing the pumping lemma, and I encountered this language, I saw these conditions and got totally confused, what to do now?

Earlier I showed that $L_5=\{a^n b^n : n≥0\}$ is not regular.
In this Language it was very simple to choose $w$, namely $w= a^pb^p$, where $p$ is the pumping length. But this new Language is complicated, so I thought you guys could help me out.

If $L_6$ were regular, then so would the following language be:
$$ (L_6 \cap a^* b^*) \cup \{ \epsilon, ab, a^2b^2, a^3b^3, a^4b^4, a^5b^5 \}. $$
However, this language is none other than $L_5$.

You can also use the pumping lemma. Try to pump the word $c^qa^qb^{2q}$ for large enough $q$.


Is the problem of traversing every vertex of a graph (not necessarily once) without crossing an edge more than once in P? I know that finding a Hamiltonian circuit is in NP and I know that finding an Eulerian circuit is in P. However, what about the following problem:

Must leave the starting vertex and visit every other vertex;
You may only return to the start after visiting every other vertex;
You can visit the same vertex multiple times, as long as it's not the starting vertex;
You don't have to use every edge in the graph, but each edge can only be used once.

Is that in P or NP-hard? I tried different approaches to this but now I don't know if I'm wasting my time in case this problem doesn't have an efficient solution.

This problem is NP-hard.

Consider the following variants:

Variant 1: given a graph where each vertex has degree at most three, determine if there is a Hamiltonian path.

Variant 2: given a graph, determine if there is a trail (a path without repeated edges) that visits every vertex at least once.

Variant 1 is NP-hard [1].

Variant 1 can be reduced to variant 2 by mapping to the same graph.

If there is a Hamiltonian path on the graph, the Hamiltonian path is certainly a trail that visits every vertex at least once.

On the other hand, if there is a trail from $u$ to $v$ that visits every vertex at least once, since every vertex in the graph has degree at most three, every vertex except $u$ and $v$ must appear exactly once on the trail. If every vertex appears exactly once, the trail itself is a Hamiltonian path. If $u$ and/or $v$ appear twice, remove the first and/or the last edges on the trail respectively, then the trail becomes a Hamiltonian path. Anyway there is a Hamiltonian path in the graph.

So variant 2 is NP-hard.

Suppose the problem in OP is in P. Given an instance of variant 2, construct a new graph for every pair of vertexes $(u,v)$ by adding a new vertex $s$ and new edges $(s,u)$ and $(v,s)$. Now there is a trail that visits every vertex at least once in the original graph if and only if the answer to the problem in OP on at least one of these new graphs is "yes". So one can solve variant 2 in polynomial time by solving the problem in OP on these new graphs. So the problem in OP is NP-hard.

[1] Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), "Some simplified NP-complete problems", Proc. 6th ACM Symposium on Theory of Computing (STOC '74), pp. 47–63, doi:10.1145/800119.803884.


How to construct a CFG which generates {0, 1, #}⁺ - {b_1#b_2#b_3#… #b_n | n is a whole number} where b_i is i in binary without leading zeros? This problem was originally given in "Introduction to Automata Theory, Languages and Computation" by John E. Hopcroft and Jeffrey D. Ullman as Exercise 4.3.

$$ \text {Let }b_i \text{ denote } i \text{ in binary without leading zeros.}$$ We need to construct a CFG which generates the following language: $$
\{0, 1, 2\}⁺ - \{b_12b_22...2b_n | \text{n is a whole number}\} \text{.}
$$

Firstly, I considered implementing such non-terminal
$$
U \mid \forall \text{whole n}. S \Rightarrow^+ U \Rightarrow^+ b_12b_22...2b_n\text{.}
$$
I believe that even if this could be done, it would have a fairly cumbersome structure:
$$
\{b_12b_22...2b_n | \text{n is a whole number}\}
$$
does not satisfy the Pumping lemma, therefore, is not a CFL. For the same reason, I can't see any way to apply any neat theorems like $$CFL - RL = CFL\text{.}$$

How could one construct such a grammar? I would really appreciate some hints, which could help me solve the problem, instead of a complete solution.

Here is the idea. We can always write the string in the form $w_1\#\cdots\#w_n$, for some strings $w_i \in \{0,1\}^*$. If the input string is not of the form $b_1\#\cdots\#b_n$, then one of the following must happen:

$w_1 \neq 1$.
One of the $w_i$'s is empty.
One of the $w_i$'s has a leading $0$.
For some $i$, $w_i+1 \neq w_{i+1}$.

The first three cases are easy. In the first case, the string is empty or starts with $\#,0,10,11$. In the second case, there is a substring $\#\#$. In the third case, there is a substring $\#0$.

For the fourth case, let $x = w_i$ and $y = w_{i+1}$. Here are some things which are not supposed to happen:

$x$ ends with $1^m$ and $y$ ends with $10^{m-1}$.
$x$ ends with $01^m$ and $y$ ends with $0^{m+1}$.
$x = 1^m$ and $y = 0^m$. (Actually this is ruled out by requiring no leading zeroes.)
$x$ starts $\{0,1\}^ib\{0,1\}^*0$ and $y$ starts $\{0,1\}^i \overline{b}$.

Unless I missed some case, if none of these things happen, then $y$ is the encoding of $x+1$. Indeed, the first two constraints guarantee that if $x=z01^m$ then $y=w10^m$ (the third constraint takes care of the corner case $x=1^m$, in which case $y=10^m$), and the fourth constraint guarantees that $z=w$.

Each of these subcases corresponds to a context-free language – once again, there are some corner cases to consider (if $x = w_1$ and if $y = w_n$).


A sufficient and necessary condition about regularity of a language Which of the following statements is correct?

  sufficient and necessary conditions about regularity of a language exist but not discovered yet.
  There's no sufficient and necessary condition about regularity of a
  language.
  Pumping lemma is a necessary condition for non-regularity of a
      language.
  Pumping lemma is a sufficient condition for non-regularity of a
  language.

I know #(4) is correct and #(3) is false because "the converse of this statement is not true: a language that satisfies these conditions may still be non-regular", but what can be said about (1) and (2)?

Here are some necessary and sufficient conditions for a language to be regular.

Theorem. Let $L\subseteq\Sigma^*$. The following conditions are equivalent:

$L$ is generated by a regular expression (i.e., the definition of regular language).
$L$ is recognized by a nondeterministic finite automaton (Kleene).
$L$ is recognized by a nondeterministic finite automaton without $\varepsilon$-transitions.
$L$ is recognized by a deterministic finite automaton (Scott and Rabin).
$L$ is generated by a grammar $(N,\Sigma,P,S)$, where $N$ is a finite subset of $\Sigma^*$ (Frazier and Page).
$L$ is generated by a left (resp. right) regular context-free grammar.
The index of the Nerode relation $\equiv_L$ is finite (Anil Nerode, Linear automaton transformations, 1958). This is widely (and incorrectly) known as the Myhill-Nerode theorem. $\equiv_L$ is the relation used to build the minimal DFA of a regular language.
The index of the Myhill relation $\sim_L$ is finite (John Myhill, Finite Automata and the Representation of Events, 1957). $\sim_L$ is the relation used to build the syntactic monoid of an arbitrary language.
The syntactic monoid of $L$ is finite (consequence of Myhill's result). We note here that the syntactic monoid, apart from being defined by using relation $\sim_L$, can be defined as a minimal monoid (in size) that recognizes $L$ as a preimage of a homomorphism.
$L$ can be recognized by a read-only Turing Machine (trivial).
$L$ can be defined by a formula in Monadic second-order logic over strings (Büchi).

If a language does not satisfy the conditions of the pumping lemma for regular languages, then it is not regular. This means pumping lemma is a sufficient condition for the non-regularity of a language.

In summary, statements 1, 2 and 3 are false, while statement 4 is true, as you mentioned.


Rice's Theorem for Turing machine with fixed output So I was supposed to prove with the help of Rice's Theorem whether the language:
$L_{5} = \{w \in \{0,1\}^{*}|\forall x \in \{0,1\}^{*}, M_{w}(w) =x\}$ is decidable.
First of all: I don't understand, why we can use Rice's Theorem in the first place: If I would chose two Turingmachines $M_{w}$ and $M_{w'}$ with $w \neq w'$   then I would get $M_{w}(w) =  M_{w'}(w) = x$. But this would lead to $w'$ not being in $L_{5}$ and $w \in L_{5}$. Or am I misunderstanding something?
Second: The solution says, that the Language $L_{5}$ is decidable as $L_{5} = \emptyset$ because the output is clearly determined with a fixed input.
But why is that so? I thought that $L_{5}$ is not empty because there are TM which output x on their own input and there are some which do not.

A word $w$ belongs to $L_5$ if for all $x \in \{0,1\}^*$ it is the case that $M_w(w) = x$. In particular, if $w \in L_5$ then $M_w(w) = 0$ and $M_w(w) = 1$, which can't both be true. So no word belongs to $L_5$.


Polylogarithm growth rate proof using Polynomial growth equation In the CLRS, there's this part, where it's shown that $$\lim_{n\to\infty}\frac{(n^b)}{(a^n)} = 0$$ In the same chapter, it uses the aforementioned equation to prove that any polylogarithm function grows slower than any polynomial one, thus, $$\lim_{n\to\infty}\frac{\log b^n}{ n^a}$$ It does that by substituting lgn for n and 2^a for a in the first equation. How is it allowed to substitute the terms and prove the latter equation.

Here is the starting point. For all real constants $a$ and $b$ such that $a > 1$,
$$\lim_{n\to\infty}\frac{n^b}{a^n} = 0\,.\tag{3.10}$$

Let $c=\log_2 a$, i.e, $a=2^c$. Since $a>1$, we have $c>0$. Equation (3.10) becomes
$$\lim_{n\to\infty}\frac{n^b}{a^n} = \lim_{n\to\infty}\frac{n^b}{2^{cn}}= 0\,.\tag{cs.1}$$

Let $m=2^n$, i.e, $n=\log_2 m$. Then equation (cs.1)
becomes
$$ \lim_{n\to\infty}\frac{n^b}{2^{cn}} = \lim_{m\to\infty}\frac{(\log_2 m)^b}{2^{c\log_2 m}} = \lim_{m\to\infty}\frac{(\log_2m)^b}{m^{c}}= 0\,.\tag{cs.2}$$

Note that equation (cs.2) is, after $m$ is renamed to $n$ and $c$ is renamed to $a$,
$$\lim_{n\to\infty}\frac{(\log_2 n)^b}{ n^a}=\lim_{n\to\infty}\frac{{\lg}^b n}{ n^a}=0\tag{cs.3}$$
where $a>0$.

What is done in CLRS is a shortened version of above transformations.

Be careful. $(\log_2n)^b={\lg}^bn\not=\log_2n^b=\log_2(n^b)$, where each of two equalities is just a change of notation. $\log_2 (b^n)$, which is equal to $n\log_2 b$, is a linear function of variable $n$ while $(\log_2 n)^b$ is a polylogarithm function of variable $n$.


If you have a Cook reduction in both directions, do you also have a Karp reduction? If there exists a Cook reduction of a decision problem $\mathcal{P}_1$ into another decision problem $\mathcal{P}_2$ and also a Cook reduction of $\mathcal{P}_2$ into $\mathcal{P}_1$, then is there also a Karp reduction (a polynomial transformation) between $\mathcal{P}_1$ and $\mathcal{P}_2$ (in both directions)?
These are the definitions I use:

Cook reduction
$\mathcal{P}_1$ polynomially reduces to $\mathcal{P}_2$ if there is a polynomial-time oracle algorithm for $\mathcal{P}_1$ using an oracle for $\mathcal{P}_2$.
Karp reduction
$\mathcal{P}_1=(X_1,Y_1)$ polynomially transforms to $\mathcal{P}_2=(X_2,Y_2)$ if there is a function $f:X_1\rightarrow X_2$ computable in polynomial time such that for all $x\in X_1$, $x\in Y_1$ if and only if $f(x)\in X_2$.

The answer depends on whether you require both of $\mathcal{P}_1,\mathcal{P}_2$ to be in NP or not.

If the problems need not be in NP

Then the answer to your question is "No".  There exist problems $\mathcal{P}_1,\mathcal{P}_2$ that are Cook-reducible (in both directions) but not Karp-reducible (in either direction)

In particular, consider $\mathcal{P}_1 = $ HALT (the Halting problem) and $\mathcal{P}_2 = \overline{\mathcal{P}_1}$ (its complement).  They are Cook-reducible (you just invoke the oracle and complement its answer), but not Karp-reducible.

(Similarly, if $\textsf{NP} \ne \textsf{coNP}$, then the answer is No: take $\mathcal{P}_1 = $ SAT and $\mathcal{P}_2 = $ TAUTOLOGY, so that $\mathcal{P}_1$ is NP-complete and $\mathcal{P}_2$ is coNP-complete.  They're Cook-reducible, but a Karp reduction would prove that $\textsf{NP} = \textsf{coNP}$ via a standard argument.)

If the question is restricted to require both problems to be in NP

Then it's an open question; no one knows whether the answer is "Yes" or "No".  See https://en.wikipedia.org/wiki/NP-completeness#Completeness_under_different_types_of_reduction and

https://cstheory.stackexchange.com/q/686/5038 and
https://cstheory.stackexchange.com/q/138/5038 and
https://cstheory.stackexchange.com/q/3435/5038 and
https://cstheory.stackexchange.com/q/14379/5038 and
https://cstheory.stackexchange.com/q/16983/5038.


Confirmation of Dijsktra application explanation Please can someone confirm that my description of the application of Dijkstra's algorithm is correct for this graph?

    1   3
 A -- B -- C
  \      /
 2 \    / 1
    \  /
     D

Step   Current Node

                       B        C        D
1      A               1(A)     -        2(A)
2      B               1(A)     4(B)     2(A)
3      D               1(A)     3(D)     2(A)
4      C               1(A)     3(D)     2(A)

Description:

Tentative distances to B and D determined. C not yet visible.
Shortest distance from previous step taken. No new information on shortest path to B. Tentative distance to C now known. No new information on D.
We choose to backtrack to A, and then move to D because the distance to D (2) is smaller than that to C (4). We update the tentative distance to C because via D it is shorter than via B.
We choose to move to C directly from D because it is shorter (3) than backtracking and going via A (4). Moving to C gives us no new shorter distances. All nodes visited, so end.

It's more traditional to describe dijkstra with the open and closed sets:

You start with an empty closed set and an open set containing $ \{ (A,0) \}$

You select the node with the lowest cost and remove it from the open set, then you expand the neighbours and add them to the open set $ \{ \{B,1\}  \{D,2\} \}$ or update the elements in the open set and Add the selected node to the closed set

step1:
open = $ \{ (B,1, A),  (D,2, A) \}$
closed = $\{(A)\}$

step2:
open = $ \{ (C,4, B),  (D,2, A) \}$
closed = $\{(A),(B,A)\}$

step3:
open = $ \{ (C,3, D)  \}$
closed = $\{(A),(B,A),(D,A)\}$

There is no actual sense of "backtracking" because you are considering all the open nodes in parallel.

Many other search algorithms work in the same way with the only difference in how a node is selected from the open set. Breadth-first takes the oldest node in the set, depth-first takes the youngest, Dijkstra takes the node with the lowest cost, A* takes the node with the lowest cost+heuristic.


Can you reduce a precedence graph or do *all* relevant nodes need to be connected Let's say we have the following simple transaction-schedule:

 T1  |  T2  |  T3
-----+------+-----
 w(x)|      |
     | w(x) |
     |      | w(x)

T1 comes before T2, so in the precedence graph, we draw an arrow from T1 to T2. T2 comes before T3, so we draw an arrow from T2 to T3.

My question is: is it also necessary to draw an arrow from T1 to T3? T1 comes before T3, and the definition of a precedence graph says nothing about not drawing a line from Tx to Ty if there is some arbitrary Tz inbetween.

On the other hand, T1 -> T2 -> T3 implies T1 -> T3, and as the graph gets larger things will get a bit messy. Is it okay to 'reduce' a precedence graph?

If the answer to the above question is yes, here is a follow up - consider the following schedule:

 T1  |  T2  |  T3
-----+------+-----
 w(x)|      |
 w(y)|      |
     | w(x) |
     | w(z) |
     |      | w(y)
     |      | w(z)

In the precedence graph, for the operations on x we draw an arrow from T1 to T2, for y an arrow from T1 to T3, and for z an arrow from T2 to T3. Would you be allowed to omit the arrow 'caused' by element z?

Yes it is necessary.

According to the definition of precedence graph, a directed edge $T_i \longrightarrow T_j$  is created if one of the operations in $T_i$ appears in the schedule before some conflicting operation  in $T_j$.

It is clear from the definition that we have to consider every two transactions separately : $T_1$and $T_2$, $T_1$and $T_3$ and $T_2$ and $T_3$.

 T1  |  T2  |  T3
-----+------+-----
 w(x)|      |
     | w(x) |
     |      | w(x)

So an edge $T_1 \longrightarrow T_3$ is necessary because w(x) in $T_1$ and w(x) in $T_3$ are two conflicting¹ operations.

 T1  |  T2  |  T3
-----+------+-----
 w(x)|      |
 w(y)|      |
     | w(x) |
     | w(z) |
     |      | w(y)
     |      | w(z)

For this schedule there will be three edges in the precedence graph:$T_1 \longrightarrow T_2$, $T_1 \longrightarrow T_3$ and $T_2 \longrightarrow T_3$.

1.Two operations are conflicting, if they are of different transactions, upon the same datum (data item), and at least one of them is write.


How large would a database containing perfect knowledge of chess be? Assuming that a database entry schema contains two 64-bit hash IDs generated via the algorithm explained here, in the section "Generating Hash Keys for Chess Boards", and simply a score that's a 32-bit integer, how many bytes would the database need to be to guarantee that it can store every possible game state of chess?

Claude Shannon indicated that the State Space Complexity (number of legal positions reachable from the initial position in chess) has a lower bound of approximately $10^{43}$. If each entry consists of $20$ bytes, as indicated in your question. The total number of bytes for your database would have a lower bound of $2 * 10^{44}$ which is a very large number indeed.

I would suggest reading Section 2: General Considerations of Shannon's paper, Relevant quote:

  Another (equally impractical) method is to have a "dictionary" of all possible positions of
  the chess pieces. For each possible position there is an entry giving the correct move
  (either calculated by the above process or supplied by a chess master.) At the machine's
  turn to move it merely looks up the position and makes the indicated move. The number of
  possible positions, of the general order of $64! / 32!(8!)^2(2!)^6$
  , or roughly $10^{43}$, naturally
  makes such a design unfeasible.

References:

https://en.wikipedia.org/wiki/Game_complexity
Programming a Computer for Playing Chess - Shannon


Is zero allowed as an edge's weight, in a weighted graph? I am trying to write a script that generates random graphs and I need to know if an edge in a weighted graph can have the 0 value.

actually it makes sense that 0 could be used as an edge's weight, but I've been working with graphs in last few days and I have never seen an example of it.

Allowed by whom? There is no Central Graph Administration that decides what you can and cannot do. You can define objects in any way that's convenient for you, as long as you're clear about what the definition is. If zero-weighted edges are useful to you, then use them; just make sure your readers know that's what you're doing.

The reason you don't usually see zero-weight edges is that, in most contexts, an edge with weight zero is exactly equivalent to the absence of an edge. For example, if your graph represents countries and the amount of trade done between them, a zero-weight edge would mean no trade, which is the same as having no edge at all. If your graph represents distances, a zero-weight edge would correspond to two places at distance zero from each other, which would mean they'd actually be the same place, so should both be represented by the same vertex. However, in other contexts, zero-weight edges could make sense. For example, if your graph represents a road network and edge weights represent the amount of traffic, there's a big difference between a road that nobody uses (zero-weight edge) and no road at all (no edge).


Modelling a basic sequential circuit as a transition system? I'm going through Dr Joost-Pieter Katoen's slides and stumbled upon this:

For some reason I can't quite make out how the transition system relates to the sequential circuit. If I had a question for instance that asked me to convert the circuit into a TS, what steps should I take to approach it (using this one as an example).

Grateful for any help.

How does the transition system (denoted by $\texttt{TS}$) relate to the sequential circuit (denoted by $\texttt{SC}$)?

The states of $\texttt{TS}$ are all possible combinations of values of variable $x$ and register $r$ (no output variable $y$) in $\texttt{SC}$.
The label of each state in $\texttt{TS}$ consists of all the variables (including the register) which are evaluated true given the valuations in $\texttt{SC}$.
For example, $\{x, r, y \}$ for state $(x = 1, r = 1)$ means that all variables are true according to $\lambda_y = \lnot (x \oplus r)$ and $\delta_r = x \lor r$ given $x = 1, r = 1$.
The transitions (arcs with arrow) between states in $\texttt{TS}$ result from the functions $\lambda_y$ and $\delta_r$.
For example, $(x = 0,r = 1) \to (x = 0,r = 1)$ if the next input bit equals 0.

For more details and a general recipe for modeling sequential hardware circuits as transition systems, please refer to the book "Principles of Model Checking" (Section 2.1.2) by Christel Baier and Joost-Pieter Katoen. The MIT Press.


Is this problem hard? Finding all the subsets of size k from a sequence of n numbers I want to know the hardness of finding all subsets of size k from a sequence of n numbers. There is an algorithm based on recursion: Print all possible combinations of r elements in a given array of size n.

However, I am not sure whether this can be done in polynomial time or not.

For fixed $k$, the running time is polynomial, but if $k$ is part of the input, the running time is not polynomial. The number of such subsets is ${n \choose k}$, which is very roughly like $n^k$.  Thus, if $k$ is fixed to something like 3, this becomes $O(n^3)$ -- polynomial.  However, if $k$ is part of the input, the running time is exponential in $k$.


Proof of the undecidability of compiler code optimization While reading Compilers by Alfred Aho, I came across this statement:

The problem of generating the
optimal target code from a source program is undecidable in general.

The Wikipedia entry on optimizing compilers reiterates the same without a proof.
Here's my question: Is there a proof (formal or informal) of why this statement is true? If so, please provide it.

Optimized program must have the same behavior as the original program. Consider the following program:
int main() {
    f();
    g();
}

, where it's guaranteed that $f$ is pure function. The only question is: does it finish its execution? If it does, then we can replace main()'s body with g(). Otherwise, we should replace it with an infinite loop. Unfortunately, verifying whether f() finishes its execution is undecidable.
Another example is the program with body print(f(42)), where f is pure. The optimal program would just replace f(42) with its value. However, there is no algorithm that does this. We may try to compute it in compile-time, but it may never finish.
Another example (now without infinite loops). Assume that your program defines a context-free grammar and $f(x)$ checks whether string $x$ belongs to the language defined by this grammar (for any CFG we can build such $f$ automatically). Then if $f$ is a constant "true", then
if (f(x)) {
    g()
}

can be optimized to g(). Unfortunately, checking that grammar accepts all strings is called a universality problem and is known to be undecidable.