What doest it mean: "computer is an intelligence amplifier"? There is one example in Kolmogorov complexity books and related articles:

Consider we have a monkey at a typewriter and a monkey at a computer keyboard.

If the monkey types at random on a typewriter, the probability that it types out all the works of Shakespeare (assuming that the text is 1 million bits long) is about

p_typewriter (works of Shakespeare) ≈ 2^−1000000

If the monkey sits at a computer terminal, however, the probability that it types out Shakespeare is now related to the Kolmogorov complexity of the works of Shakespeare, which can be approximated by

K(works of Shakespeare) ≈ 250000 bits

using a program that compacts these works using 250000 bits.
Then:

p_computer(works of Shakespeare)≈2^−K(works of Shakespeare) ≈2^−250000

The example indicates that a random input to a computer is much more likely to produce “interesting” outputs than a random input to a typewriter.

We all know that a computer is an intelligence amplifier...

What actually the computer does?

Let's first clarify the scenario. What you're basically asking is why it is more likely to randomly write a computer program that outputs the works of Shakespeare than writing the works of Shakespeare directly.

The simple answer to this is that there are many ways to write a program that outputs a fixed string, but only one way to directly write this string. This may sound a bit strange, because there is clearly a mapping from strings that describe a computer program that outputs a string to another string (that is, the string outputted by the described program), and we could interpret a large amount of strings as descriptions of programs that outputs something. So why are the sizes different?

The reason is that these mappings are not bijective: the map from programs to strings outputted is clearly surjective, as we can output any string, but also clearly not injective, as there are multiple programs that output the same string. So, the set of programs must be larger than the set of strings outputted by them. That means if we sample over the set of programs, we need to sample over a much smaller set to get strings of a certain size, than if we were to sample over the strings directly.


Algorithm to Assign Values Based on Constraints I have variables x y and z, and I have the values that they can be assigned to, I.E. x can be assigned 1,2, or 3, y can be 1, and z can be 2.  The problem is a constraint that says once a value has been taken by a variable, no other variables can have that value.

The issue that I am running into is if I start with x, how can I efficiently tell that it's value should be 3?

The problem you are describing amounts to constraint programming and the specific constraint you are talking about is the alldifferent constraint. I'm not offering a purely algorithmic solution, but reading a bit on constraint programming could give you some ideas on how to construct a search tree where you make a decision (i.e., assign a value to a variable) at each node, and how to backtrack to a feasible node when you reach an infeasible node.


Regularity of “middles” of words from regular language I need some help with the following problem. Let $L \subseteq \Sigma^*$ be a regular language. I have to prove that the language $P = \{\alpha \mid \beta\alpha\gamma \in L, \beta,\gamma \in \Sigma^*\}$ is regular, where $\Sigma$ is the alphabet. In other words $P$ is the language of all substrings of words from $L$.  How do I prove that $P$ is regular?

Let $R$ be a regular language. Then there is a finite automaton $M$ for which the language, $L(M)$, of $M$ is $R$. Without loss of generality, we may assume that $M$ has no unreachable states. Construct a new FA, $M'$, as follows:

For each state $q$ of $M$ which has a sequence of transitions to a final state of $M$, make $q$ a final state. Call the set of such states $S$.
Add a new start state $q_0$ having $\epsilon$-transitions to each element of $S$.

It's not hard to see that $M'$ will accept any string which is a substring of some string in $R$.


Is cubical type theory still consistent with univalent excluded middle and univalent choice? I want to formalize some undergraduate maths in cubical agda, and learning cubical type theory in the proccess. The problem is that I will need univalent excluded middle and univalent choice (and maybe propositional resizing). I know these are consistent with homotopy type theory (although computation is lost when axiom are used), but cubical that type theory is stronger (in the sense that univalence is a theorem). Are this axiom still consistent in the cubical setting? Is there a better way of doing classical theorems in cubical type theory?

I decided to rewrite my answer, because I thought I could explain the details
better. I'd still defer to someone more knowledgeable should they happen to come
along.

I think it is relatively safe to say that cubical type theory as an approach on
the whole is compatible with the classical axioms you want. The reasons for
this are:

The differences people usually point out, like the $\mathsf{Glue}$ type,
are just a way of making univalence hold for all types, independent of
their belonging to a universe. This is (in my view) merely fixing a
limitation of the HoTT approach of minimally extending Martin-löf type
theory, where it's impossible to state the univalence axiom except by
reference to a universe. However, if you have enough universes with
univalence axioms, every type is in a universe, and so univalence holds for
all types. In fact, this is how Agda actually works directly; the universes
are primary, and all types are declared as part of a universe, similar to a
pure type system.
There is (I've heard) a cubical set model (discovered by Emily Riehl) that is
completely compatible with the standard simplicial set model, and I believe
it has been shown to be adequate for doing cubical type theory. I think what
this means is that if you add EM (and maybe choice), you get the same
homotopy theory as the classical simplicial set model. I've also heard that
there are constructive analogues of the simplicial set model, so it is not
inherently classical.

Now, what you have to worry about are other details. For instance, cubical Agda
uses the sort of cubes with inversions and connections. So, if i and j are
dimension variables, then ~ i is a dimension, and so is i ∨ j. There are
also Cartesian cubes that don't have ∨ but have other similar constructions.
These affect the details of how you are able to construct paths. Having more of
them is convenient for easily constructing compositions of paths and whatnot,
but my understanding is that the model that matches the classical simplicial
model lacks most of these things.

Now, more specifically, I've also heard that most of these other cubical set
models are anti-classical (I'd forgotten that earlier). I've not been able to
work out the details of how you demonstrate this inside implemented cubical
type theories, but my understanding is that, using ~ as an example, you try to
construct some contradictory scenario using a point i on the interval such
that i = ~i. There's no way given in the type theory to construct such a
point, and somehow it's inconsistent to presume that you can tell whether any
abstract point is or is not like that.

So, I guess the answer to your specific question is that there is probably a
way to refute excluded middle in cubical Agda (although I don't know how), and
every other computer implemented cubical type theory. But it's also likely that
a cubical type theory could be implemented that is consistent with classical
axioms (and homotopy theory) and supports all the reasoning desired (although
maybe it's more difficult to construct certain things). Unfortunately, you'll probably have to wait until the details are fleshed out more and some implementation decides to pick up the compatible version of the theory.

Another option, I suppose, is to not worry about the anti-classical part too much. If you use the cubical primitives to implement something similar to reasoning in the HoTT book, and avoid working directly with the cubical operations, you can probably be reasonably confident (I think) that you haven't relied on any paradoxes. I think there are efforts to provide a HoTT interface on top of cubical type theory in some of the libraries available. You could also dabble in learning the direct cubical parts, even though you don't use them directly, although I don't know exactly which parts are still part of the 'proper' model.

Edit: by the way, here is a presentation about cubical set models of homotopy type theory that mentions the anti-classical properties of many cubical set models. It describes, vaguely, what you have to do to refute excluded middle, but it's all in terms of looking at the models from the outside, hence some of the difficulty of translating that to a refutation within cubical type theory (for me).

Edit 2: here's a potential more positive answer. It's been pointed out to me that the constructions in the above video may not be possible to carry out inside cubical type theory. They are constructions that can be carried out in the 'intended' cubical set models, but just like Martin-löf type theory has other models than the intended one (which is how you get to HoTT), the cubical set models aren't necessarily the only model of the corresponding cubical type theory. So it's possible that cubical type theories are compatible with excluded middle and choice, even though their most obvious models are not.


Kolmogorov Complexity of String Concatenation For all bit strings $x$, $y$ and Kolmogorov complexity $K$, is $K(xy) > K(x)$?

Let $w = 0^{2^n}$, so that $K(w) = O(\log n)$. The string $w$ has $2^n+1$ prefixes, and so some prefix $x$ satisfies $K(x) \geq n$. This example strongly violates your inequality.

On the other hand, given $xy$ and $|x|$, we can easily extract $x$. This shows that $K(x) \leq K(xy) + O(K(|x|))$. In particular, if $|x| = n$ then $K(xy) \geq K(x) - O(\log n)$.


Can the reproduction function of an evolutionary algorithm consider gene strength? I am trying to solve the Zen Garden puzzle using an evolutionary algorithm. My question relates to evolutionary algorithms in general.

Bit about evolutionary algorithms:
An evolutionary algorithm is an algorithm which tries to solve a given problem in a semi-random way. Most often I have seen it is implemented thusly: for a given starting state of the problem a generation of random solution approaches for is generated. Each speciemen (approach) has a set of genes which define it. Each speciemen is then used to try and find a solution to the problem. If no solutions are found, then we try to determine the fitness of each speciemen by some set of rules. For example- if the problem was to collect all treasures on a map, then the fitness a speciemen could be determined by the ammount of treasures it managed to collect. Once we determine their fitness we try to crossbreed the speciemen semi-randomly, giving higher chance of reproduction to those with higher fitness. This way we create a new generation of speciemen, where each of them has some genes from both of its parents. Then we try to solve the problem using the new generation of speciemen and the cycle goes on until a solution is found or we reach some kind of pre-determined limit of max-generations.

Question: Can the reproduction function which determines how speciemen (solution attempts) reproduce take into account some kind of gene strength to also determine which genes are best to be passed down to the child of two speciemen? What I mean by that is that for example if I could measure how much a certain gene contributed to the solution attempt can I give the gene a higher chance to be passed on or should child genes be passed on randomly?

Can the reproduction function which determines how speciemen (solution attempts) reproduce take into account some kind of gene strength to also determine which genes are best to be passed down to the child of two speciemen?

Of course it can.

Anyway, consider that in GA this already happens implicitly. Using the established methods and genetic operators of genetic algorithms (not only reproduction but also crossover and mutation) the Holland's schema theorem states that low-order schemata with above-average fitness increase exponentially in successive generations.

(a schema is a template that identifies a subset of strings with similarities at certain string positions)

In Genetic Programming things are different:

GA representations are often fixed size whereas GP representations and usually variable sized;
GA normally have a semantic interpretation for a given location in a chromosome while GP solutions often do not exhibit location dependent meanings.

John Koza attempted to explain why genetic programming works by extending Holland's schema model and theorem to GP but with various differences / limitations (the class of problems and problem representations for which block processing is useful remains a challenging and open research topic in GP).

In GP your idea is the base of the modularization approach, e.g.

The encapsulation operation is a genetic operation that identifies a
potential useful subtree and gives it a name so that it can be referenced and used later (see Genetic Programming: On the Programming of Computers
by Means of Natural Selection)
Better yet, Adapting Representation through Learning (ARL). With ARL New subroutines are created using blocks of genetic material from the pool
given by the current population.

The detection of what are salient blocks of code is based on two notions: differential offspring-parent fitness and "active" blocks.

The process of discovering building blocks and creating new subroutines based on simple blocks of code is applied recursively so that subroutines of
any complexity can be discovered.

Subroutines beneficial to some individuals could be invoked also by other individuals. The end result is the collection of subroutines that acquires the necessary structure for solving the problem (take a look at Towards Automatic Discovery of Building Blocks in Genetic Programming by Justinian Rosca for a complete description).


Is maximum matching problem equivalent to maximum independent set problem in its dual graph? A hypergraph $H = (V,E)$ consists of a set $V = \{v_1, v_2, \cdots, v_n\}$ of vertices and a set $E = \{e_1, e_2, \cdots , e_m\}$ of edges, each being a subset of $V$.

A subset $M \subseteq E(H)$ is a matching if every pair of edges from $M$ has an empty intersection.

The dual $H^*$ of $H$ is a hypergraph whose vertices and edges are interchanged, so that the vertices are given by $\{e_1, e_2, \cdots , e_m\}$ and whose edges are given by $X = \{X_1, X_2, \cdots, X_n\}$ where $X_j = \{e_i | v_j \in e_i \}$, that is $X_j$ is the collection of all edges containing $v_j$.

My question: Is maximum matching problem equivalent to maximum independent set problem in its dual graph?
Are both NP-hard and cannot be approximated to a constant factor in polynomial time (unless P = NP)?

Thank you!

To start with possible NP-hardness (where for each problem, we want a matching/independent set of size at least $k$):

Independent set is NP-hard on "normal" graphs (and also on hypergraphs)
Maximum matching is polynomial-time solvable on "normal" graphs, see the wikipedia page on matching.
Maximum matching is NP-hard in hypergraphs (as shown in this wikipedia page, it is even hard for hypergraphs where each edge contains only 3 vertices).

I believe both problems are equivalent in the following sense:  set $S \subseteq E(H)$ is a matching in $H$, if and only if $S$ forms an independent set in $H^*$.

(If you need further explanation or if this is not your definition of equivalance, please clarify)


Are weakly polynomial time algorithms truly polynomial? I've been looking through a ton of sources to try and understand the definitions of strongly and weakly polynomial time algorithms. Wikipedia
states an algorithm runs in strongly polynomial time if

  the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and
  the space used by the algorithm is bounded by a polynomial in the size of the input.

A weakly polynomial time algorithm is then just an "algorithm that runs in polynomial time but that is not strongly polynomial."

What I'm confused about is how weakly polynomial time algorithms can actually be said to be polynomial. As stated in this post in reference to weakly polynomial time algorithms,

  The algorithm is already polynomial time in the arithmetic model, so as long as its space is bounded in the TM model then the rest of the algorithm is still polynomial time in the TM model.
  Think of it like this, when converting from the arithmetic model to the TM model, the only thing that can go wrong is the space. The numbers you produce need to be representable in a number of bits that is polynomial in the number of bits in the input. So long as that holds, the rest of the algorithm is still polynomial time in the TM model.

I understand the difference between the arithmetic model and the TM model. But this quote and the wikipedia definition itself seem to imply that a weakly polynomial time algorithm will not run in polynomial time on a TM. This being because (to my understanding) if the space being used isn't bound by a polynomial in the size of the input, just the time spent allocating the space necessary to run the algorithm on a TM eliminates any hope of polynomial time. The classic example is in the post I linked above and the Wikipedia article and involves calculating $2^{2^n}$ given $2^n$.

So how can we say weakly polynomial algorithms are still polynomial? There seems to be a consensus that weakly polynomial is better than pseudo-polynomial, but aren't they both not polynomial on a TM?

Edit: I would also like to add that confusingly this post states that

  Consider running either one on a Turing Machine. Both will run in a number of steps polynomial in the length of binary-encoded input.

This seems to contradict the previous post I linked which states

  Any strongly-polynomial time algorithm can be converted into a polynomial time algorithm on a TM by replacing the arithmetic operations with equivalent algorithms in the TM model.

suggesting that the difference is weakly polynomial time algorithms don't run in polynomial time on a TM. Either I'm missing something fundamental or multiple definitions seem to be floating around.

As Wikipedia says, there are two conditions for strongly polynomial time algorithms:

  the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and
  the space used by the algorithm is bounded by a polynomial in the size of the input.

I will simply call these two conditions as condition 1 and condition 2 in this answer.

  The algorithm is already polynomial time in the arithmetic model, so as long as its space is bounded in the TM model then the rest of the algorithm is still polynomial time in the TM model. Think of it like this, when converting from the arithmetic model to the TM model, the only thing that can go wrong is the space. The numbers you produce need to be representable in a number of bits that is polynomial in the number of bits in the input. So long as that holds, the rest of the algorithm is still polynomial time in the TM model.

This paragraphs is describing why condition 2 is necessary for strongly polynomial time algorithm, it is not stating the difference between strongly and weakly polynomial time algorithms. In fact, condition 2 is also necessary for weakly polynomial time algorithm, and the example algorithm that computes $2^{2^n}$ given $2^n$ is NOT weakly polynomial (and is even not a polynomial time algorithm).

In fact, it is condition 1 that describes the difference between strongly and weakly polynomial time algorithms. Note the definition of strongly polynomial time algorithms is equivalent to

  condition 1; and
  the algorithm is a polynomial time algorithm (in the TM model)

While the definition of weakly polynomial time algorithms is equivalent to

  condition 1 is not satisfied; and
  the algorithm is a polynomial time algorithm (in the TM model)

It is more clear to see the difference between strongly and weakly polynomial time algorithms with these two redefinitions.

This post is wrong to suggest the difference is weakly polynomial time algorithms don't run in polynomial time on a TM. I have added a comment on that post addressing this issue.


Dijsktra's algorithm applied to travelling salesman problem I am a novice(total newbie to computational complexity theory) and I have a question.

Lets say we have 'Traveling Salesman Problem' ,will the following application of Dijkstra's Algorithms solve it?

From a start point we compute the shortest distance between two points. We go to the point. We delete the source point. Then we compute the next shortest distance point from the current point and so on...

Every step we make the graph smaller while we move the next available shortest distance point. Until we visit all the points.

Will this solve the traveling salesman problem.

Dijkstra's algorithm returns a shortest path tree, containing the shortest path from a starting vertex to each other vertex, but not necessarily the shortest paths between the other vertices, or a shortest route that visits all the vertices.

Here's a counter example where the greedy algorithm you describe will not work:

Starting from $a$, the greedy algorithm will choose the route $[a,b,c,d,a]$, but the shortest route starting and ending at $a$ is $[a,b,d,c,a]$.
Since the TSP route is not allowed to repeat vertices, once the greedy algorithm chooses $a,b,c,d$, it is forced to take the longest edge $d,a$ to return to the starting city.


complement of a language-nfa hi i know that the question 5 is true because by definition  w ∈ L if and only if δ*(q0,w)∩F ≠ ∅. Consequently, if δ∗ (q0,w)∩F = ∅, then w ∈ L1. "L1 is the complement of L"

but iam really confused about the question 6 our teacher told us that it's false but i think it's true  because i don't see any difference between the 2 questions

i get this picture from peter linz book : An-Introduction-to-Formal-Languages-and-Automata

Your teacher is right. $\delta^*(q_0, w) \cap (Q - F) \neq \emptyset$ does not necessarily imply that $\delta^*(q_0, w) \cap F = \emptyset$. Question 5 says that you don't terminate in any of the accept states, question 6 says that you terminate in some non accepting states, but NFA can still terminate in some accepting state.


Union of a regular and a non-regular language Let's say we have $L_1$ which is a regular language and $L_2$ which is not.

I understand that if $L_1 \cup L_2 = \Sigma^*$ then $L_1 \cup L_2$ is a regular language.

Does that implicitly mean that if $L_1 \cup L_2 \neq \Sigma^*$ then $L_1 \cup L_2$ is non-regular?

I assume you can already prove that the union, intersection, and complement of regular languages is regular.

Let $L_1$ be regular and $L_2$ be non-regular. Then you should also be able to prove:

At most one of $L_1 \cup L_2$ and $L_1 \cap L_2$ is regular.
If $L_1 \subset L_2$ then their union is irregular. (You should also be able to construct an example).
If $L_2 \subset L_1$ then their union is regular. (You should also be able to construct an example).
If the complement of $L_1$ contains at least two words, there is a regular language $L_3$ such that $L_1 \cap L_3 = \emptyset$ and $L_1 \cup L_3 \subsetneq \Sigma^*$. Then either $L_3 \cup L_2$ is regular or $L_1$, $L_3 \cup L_2$ are an example of a regular and an irregular language whose union is regular but where neither is a subset of the other and their union is not $\Sigma^*$.


When is Viterbi's algorithm practical? Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 3 (The data link layer), Page 208:

  The internal state is kept in six memory registers. Each time another bit is input, the values in the registers are shifted to the right. For example, if 111 is input and the initial state is all zeros, then the  internal state, written left to right, will become 100000, 110000, and 111000, after the first, second, and third bits have been input, respectively. The output bits will be 11, followed by 10, and then 01. It takes seven shifts to flush an input completely so that it does not affect the output. The constraint length of this code is thus $k=7$.

  A convolutional code is decoded by finding the sequence of input bits that is most likely to have produced the observed sequence of output bits (which includes any errors). For small values of $k$, this is done with a widely used algorithm developed by Viterbi (Forney, 1973). The algorithm walks the observed sequence, keeping for each step and for each possible internal state the input sequence that would have produced the observed sequence with the fewest errors. The input sequence requiring the fewest errors at the end is the most likely message.

My question is about this part:

  For small values of $k$, this is done with a widely used algorithm developed by Viterbi (Forney, 1973).

My question is how do they determine whether the value of $k$ is considered small or big? What is the threshold value for $k$? For example, length of this code is 7 and they considered it a small value. How about $10$? How about $20$? Are they considered small values or large values? I'm curious about the threshold value of $k$.

There is no threshold of $k$. Viterbi's algorithm has a certain complexity. For small enough $k$, you will be able to run Viterbi's algorithm on the given hardware at the given speed. For larger values of $k$, Viterbi's algorithm would be too slow. The exact threshold depends on your hardware (its capabilities, and how much "space" is available to implement the algorithm), and on the required speed. Viterbi's algorithm is optimal, and so it should probably be preferred over other algorithms when the constraints allow using it.


Proving equivalent definitions for MSTs I am working on the following homework exercise:

Let $G = (V,E)$ be an undirected graph and $c: E \rightarrow \mathbb{R}$ it's cost function. Further let $T = (V,E')$ be a spanning tree in G.

I need to show the equivalence of the following statements:

$T$ is a MST.
For all $e = \{x,y\} \in E \setminus E'$ holds: No edge of the (unique) path from $x$ to $y$ has a higher cost than $e$.
For all $e \in E'$ holds: Let $C$ one of the two connected components of $T-e$, then $e$ is an edge with minimal weight in $\delta(V(C))$.

I have done $1) \implies 2)$ and $2) \implies 3)$, but I do not know how to prove $3) \implies 1)$. Could you give me a hint?

EDIT:
Please note that $\delta$ refers to the cut, i.e.:

$$\delta(X) = \{ \ \{u,v\} \in E(G) : u \in X \text{ and } v \notin X \}\}$$

In order to make sure $3)\implies1)\,$ is true, let us assume that all costs of edges are different. Otherwise, there is a counterexample at Is a set of acyclic |V| - 1 light edges always a Minimum Spanning Tree?.

Here is a hint to prove $3) \implies 1)\,$. Suppose you have some MST $T'$. Show that $T$ and $T'$ have the same number of edges.  Show that $T'$ must contain every minimal cut.


How to do last step of Krom's algorithm for solving 2SAT problems I was making a program for solving 2 SAT problems, using Krom's algorithm. I did not found a lot of information searching in Google, so I used Wikipedia's description of Krom's algorithm to implement it but I'm stuck in the last step.

If I understand it well, the algorithm could be resumed in this:

1) You have to reduce your original 2 CNF boolean formula using Krom's inference rule as much as you can:

(a or b) and (¬a or c) => (b or c)

2) While preserving consistency, for each variable in the original formula, you must add only one of these special clauses: (x or x) and (¬x or ¬x).

(For Krom, a formula is consistent if there aren't both of these special clauses at the same time in the formula)

3) You assign to each variable TRUE or FALSE depending on which of these special clauses has been added to the formula. If the variable x has the special clause (x or x) then we assign TRUE to x; and if the variable y has the special clause (¬y or ¬y) then we assign FALSE to y.

4) This is the step where I am stuck.

My problem is that I don't know what to do once I have made the assignments to the variables. And the last paragraph of the Wikipedia describing the algorithm doesn't explain it clearly. Do I have to check satisfiability on this formula or also in the original formula as well?

Furthermore, for example:

I have this formula:(a or b)

Then I add for each variable its special clause (as the algorithm doesn't specify which of them you should pick) like this (a or b) and (¬a or ¬a) and (¬b or ¬b)

So I assign to the variables a and b the value FALSE, but then the first clause (the clause on the original formula) becomes false. What do I do in that case? Could somebody explain me the last step of Krom's Algorithm for solving 2SAT problems?

The first step in implementing an algorithm is understanding why it works.

In your case, Krom's algorithm is based on repeated application of the resolution rule
$$
\begin{array}{c}
a \lor b \qquad \bar{a} \lor c \\\hline
b \lor c
\end{array}
$$
Here $a,b,c$ are literals. This rule is valid, and applied to two 2-clauses produces a 2-clause. Hence there is no harm in running it until reaching a point at which it can be applied no more. If in this way we reach a clause $a \lor a$, then the literal $a$ must be true. So if we reach both $a \lor a$ and $\bar{a} \lor \bar{a}$, there is no solution.

More interestingly, if all solutions have $a$ set to true, then the completeness of resolution implies that $a \lor a$ will be generated.

This suggests the following algorithm:

Generate all 2-clauses reachable by resolution.
If you have generated both $a \lor a$ and $\bar{a} \lor \bar{a}$ for some variable $a$, then there is no solution.
Otherwise, if for some variable $a$ we have generated neither $a \lor a$ nor $\bar{a} \lor \bar{a}$, add one of them as you please and go back to step 1.
Output the truth assignment satisfying all literals $a$ for which we have generated $a \lor a$.

This is just one implementation; others are possible. (For example, we could immediately substitute any known values before step 3.)

Back to your example: $a \lor b$. Step 1 produces no new clauses. The variable $a$ is "free", so in step 3 we add (say) $\bar{a} \lor \bar{a}$. Step 1 is now more interesting:
$$
\begin{array}{c}
a \lor b \qquad \bar{a} \lor \bar{a} \\\hline
b \lor \bar{a}
\end{array}
\\
\begin{array}{c}
a \lor b \qquad b \lor \bar{a} \\\hline
b \lor b
\end{array}
$$
We can now read off the truth assignment $a=F,b=T$.

Had we added $a \lor a$ instead, step 1 would still not do anything, and so we would add either $b \lor b$ or $\bar{b} \lor \bar{b}$ in step 3, and then read off one of the truth assignment $a=T,b=T$, $a=T,b=F$.


Finding the minimum cut of an undirected graph Here's a question from a past exam I'm trying to solve:

For an undirected graph  $G$ with positive weights $w(e) \geq 0$, I'm trying to find the minimum cut. I don't know other ways of doing that besides using the max-flow min-cut theorem. But the graph is undirected, so how should I direct it? I thought of directing edges on both ends, but then which vertex would be the source and which vertex would be the sink? Or is there another way to find the minimum cut?

There are plenty of algorithms for finding the min-cut of an undirected graph. Karger's algorithm is a simple yet effective randomized algorithm.

In short, the algorithm works by selecting edges uniformly at random and contracting them with self-loops removed. The process halts when there are two nodes remaining, and the two nodes represent a cut. To increase the probability of success,
the randomized algorithm is ran several times. While doing the runs, one keeps track of the smallest cut found so far.

See the Wikipedia entry for more details. For perhaps a better introduction, check out the first chapter of Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal.


How would it be possible that primality testing is in P, but not factorization? Suppose that P != NP. Then there exists 3SAT formulas such that their satisfiability is computationally "evil" (i.e, the satisfiability can be exponentially hard to determine in the size of the formula).
Primality testing can be reduced to the satisfiability of a multiplication circuit, which can be reduced to the satisfiability of a 3SAT formula. But "Primes is in P". The satisfiability of this formula cannot be "evil", since it can be reduced to AKS primality test for example.
Integer factorization can be achieved by finding a satisfying assignment to the same formula. This can be achieved by choosing a variable, and then testing the satisfiability again. Choosing a variable, simplifies the formula through unit propagation. The new formula is a subset of the previous one. Now suddenly "we don't know" whether this formula can be solved in polynomial time.
Isn't this a contradiction? Is it possible that the subset of a formula is harder to solve than the formula itself?

First of all, it doesn't make sense to talk about solving any particular formula in polynomial time--every specific formula can be solved in constant time (the answer is either yes or no, we just don't know which). So talking about whether any particular formula is "evil", probably does not make sense.
Also, just because we can solve problem A, by reducing to the problem B, doesn't mean we can solve everything near problem B. In fact, we may not even be able to solve problem B, in some cases!
Can you remove some clauses and make a family of SAT problems harder? Definitely. Take any family, and add the clause $A \& \bar{A} $. Now the answer is definitely "no". Remove that clause, and the problem is hard.
This makes sense--removing constraints often feels like intuitively makes things harder. Think about sudoku--less filled in boxes, doesn't always make the problem easier.


Calculate joint entropy of a Hamming Code over a Binary Symmetric Channel? I have a normal (7,4,3) Hamming Code over GF(2) and a parity check matrix for it (not posted, because I don't think it's involved).

I have a set X of 4 bit source vectors called x. They all have equal probability to be sent. So I would assume p(x) = 1/16. They are sent over a BSC with the bit error probability p=0.15.

Y is the decoded message set. It contains the same elements as X. However it can occur that a message x from X sent and decoded into y from Y would not be x = y (too many errors to correct/detect).

For each pair (x, y) from X x Y (Most likely Cartesian product?) we can derive a probability p(x,y) (the probability that a message x was sent, but received as y).

The task says "it is not hard to see we can calculate p(x,y) if we have the BSC bit error probability."

It is hard to see for me, though. I would have 16 vectors in X and 16 vectors in Y, that would give me a 256 row table. Then for each of that to calculate the probability of 1 scrambled bit, 2 scrambled bits, 3... and so forth?

I can write a program to do it, but this course is meant to be done by hand. Any help appreciated!

You can express $p(x,y)$ as a formula that depends on just the number of bits that differ between $x$ and $y$.  Try to see if you can do that.  That will provide a nice clean formula that doesn't require examining $16 \times 16$ cases by hand.


Are there any natural $\Pi_2^P$-complete problems? I know that the quantified Boolean formula problem for a formula
$$
\psi = \forall x_1 \ldots \forall x_n \exists y_1 \ldots \exists y_n \phi
$$
where $\phi$ contains no quantifiers and only the variables $x_1, \ldots, x_n, y_1, \ldots, y_n$ is an example of a $\Pi_2^P$-complete problem. However, I wonder whether there are any natural problems known to be $\Pi_2^P$-complete, just as Circuit Minimization is a natural $\Sigma_2^P$-complete problem (see Polynomial hierarchy for details)?

There are very many natural complete problems for $\Pi_2^p$, and there is a survey [1] on completeness for levels of the polynomial hierarchy, containing many such problems.  The paper On the complexity of min-max optimization problems and their approximation [2] contains a nice overview of "min-max problems" with several proofs of completeness.  The latter paper is opened   with the following sentence:

  The computational complexity of optimization problems of the min-max form
  is naturally characterized by $\Pi_2^p$, the second level of the
  polynomial-time hierarchy.

Some problems:
Here are some examples, all of which are $\Pi_2^p$-complete, listed in the aforementioned survey [1].

$\forall \exists \text{3SAT}$: Given 3-SAT formula $\phi(x,y)$, is it true that for all $x$ there exists a $y$ such that $\phi(x,y)$ is satisfiable?
NOT-ALL-EQUAL-$\forall\exists\text{3SAT}$
MINMAX SAT, MINMAX CIRCUIT, MINMAX CLIQUE
LIST CHROMATIC NUMBER
GRAPH SATISFIABILITY
DYNAMIC HAMILTONIAN CIRCUIT, LONGEST DIRECTED CIRCUIT
SUCCINCT TOURNAMENT REACHABILITY
CONSTRAINTS OVER PARTIALLY SPECIFIED FUNCTIONS
ARGUMENT COHERENCE
3-COLORING EXTENSION, 2-COLORING EXTENSION
(STRONG) ARROWING, GENERALIZED RAMSEY NUMBER
etc., etc.

References:

[1] Schaefer, Marcus, and Christopher Umans. "Completeness in the polynomial-time hierarchy: A compendium." SIGACT news 33.3 (2002): 32-49. (PDF)

[2] Ko, Ker-I., and Chih-Long Lin. "On the complexity of min-max optimization problems and their approximation." Minimax and Applications. Springer US, 1995. 219-239. (PDF)


A dense NP complete language implies P=NP We say that the language $J \subseteq \Sigma^{*}$ is dense if there exists a polynomial $p$ such that $$ |J^c \cap \Sigma^n| \leq p(n)$$ for all $n \in \mathbb{N}.$ In other words, for any given lenght $n$ there exist only polynomially many words of length $n$ that are not in $J.$

The problem I am currently studying asks to show the following

  If there exist a dense $NP$-complete language then $P = NP$

What the text suggest is to consider the polynomial reduction to $3$-$SAT$ and then construct an algorithm that tries to satisfy the given $CNF$ formula while also generating elements in $J^c.$

What I am wondering is

  Is there a more direct proof? Is this notion known in a more general setting?

This is a nice homework problem about Mahaney's theorem.

Note that the complement of a "dense" language is a sparse language. Moreover if a language is  $\mathsf{NP}$-complete its complement is $\mathsf{coNP}$-complete.

If there is a "dense" $\mathsf{NP}$-complete language, there is a sparse $\mathsf{coNP}$-complete language.

Mahaney's theorem tells us that there is no sparse $\mathsf{NP}$-complete language unless $\mathsf{P}=\mathsf{NP}$.

We can adopt the proof to show that there is no sparse $\mathsf{coNP}$-complete language unless $\mathsf{P}=\mathsf{coNP}$ which is equivalent to $\mathsf{P}=\mathsf{NP}$ (since $\mathsf{P}$ is closed under complements).

In summary, the answer is no unless $\mathsf{P}=\mathsf{NP}$. Note that if $\mathsf{P}=\mathsf{NP}$ then every nontrivial language is $\mathsf{NP}$-complete.

ps:
You may want to try the following and then use Mahaney's theorem: there is a sparse $\mathsf{NP}$-complete set iff there is a sparse $\mathsf{coNP}$-complete set.
However I doubt that a proof for this statement would be much easier than a proof for Mahaney's theorem.


Describe a Monte Carlo algorithm for the Triangle Packing problem Book: Parameterized Algorithms by Marek Cygan (free to download legally)
Chapter about Multivariate polynomials on Page 353 (In the book not the pdf) Question 10.19:
Describe a Monte Carlo $2^{3k}n^{O(1)}$ - time polynomial-space algorithm for the Triangle Packing problem: given a graph $ G $  and a number $ k \in N $, decide whether $ G $ contains
$ k $ disjoint triangles (subgraphs isomorphic to K3).
Hint 10.19 in Page 354: Use a similar approach as in the $2^{k}n^{O(1)}$ -time algorithm for $k$-path from this
chapter (Page 333).
I tried to solve the problem using the hint, but without success unfortunately, there are solutions to the book? I would be happy to get help if it can be solved even without official solutions of the book but it is important to solve it using the hint they brought in order to use the tools learned in the same chapter.
Thanks in advance.

Although I agree with Yuval, I'll try to get you started on the connection to their longest path approach. The goal is, given a graph $G$, to define a polynomial $P_G$ which is nonzero iff $G$ has $k$ disjoint triangles. If you could evaluate $P_G$ on an arbitrary point in the underlying field $\mathbb{F}$ in time $2^{3k}n^{O(1)}$ then Schwartz-Zippel gives you the desired result (assuming that the degree of $P_G$ is low enough compared to $|\mathbb{F}|)$.
Denote by $T$ the set of all length $3k$ vertex sequences $(v_1,...,v_{3k})$ such that for all $i$ satisfying $i=1\pmod 3$,  the triplet $(v_i,v_{i+1},v_{i+2})$ is a triangle in $G$. Now, it is not hard to see that if $\mathbb{F}$ has characteristic 2 then the following polynomial (over $|E|+3k|V|$ variables) is nonzero (i.e. has a nonzero coefficient) iff $G$ contains $k$ disjoint triangles:
$P_G(\pmb{x_e},\pmb{y_{(v,j)}})=\sum\limits_{(v_1,...,v_{3k})\in T}\sum\limits_{l\in S_{[3k]}}\prod\limits_{i\in[3k]}x_{(v_i,v_{i+1})}\prod\limits_{i\in[3k]} y_{i,l(i)}$
Where $S_n$ is the symmetric group. The hard part is evaluating $P_G$ without going over all possible sequences in $T$. The fact that we don't care about repetitions in sequences in $T$ will allow (after some considerable work in rewriting $P_G$) efficient dynamic programming to come into play. The rest pretty much follows the proof for the longest path case (after extending the sum to functions whose range is a subset of $[3k]$, the dynamic programming part would look a bit different, e.g. you would probably want to shorten the sequence by three elements at a time).


Has the notion of "non-cheating" quines been formalised? Informally, it is often said that some quines "cheat", such as those that read their own source code from memory, or the case where a program consisting of the empty string happens to output the empty string.

Quines that are considerd to be "non-cheating" always seem to have the same structure. There is some data structure (usually, but not always, a string) which contains some representation of the source code. This structure is read twice, once to reformat it into the code part of the final output, and a second time where it's copied verbatim to reproduce the data part. For example, the following Python example (which I just invented) has this structure:

x = """x = {0}{1}{0}
print x.format(chr(34)*3,x)"""
print x.format(chr(34)*3,x)

The string 'x' is referred to twice in the last line, once to reformat it, and a second time to paste it verbatim into the reformatted string.

My question is whether this notion of "cheating" or "non-cheating" quines has been, or can be, formalised. That is to say, if we are given a formal specification of a language and its semantics, and we are also given an example of a quine in that language, is there a well-defined way to say, in principle, whether that quine is "cheating" or not? Or is this notion of "cheating" inherently too vague to admit a formal definition?

If this notion can be formally defined, is it possible to have a language that only admits "non-cheating" quines, and is an example of such a language known?

Most formal semantics for programing languages tend to keep things simple, in particular, it's pretty rare to have the ability to express "grabbing your own source code" in a formal semantics.

This has the somewhat dubious advantage of disallowing some kinds of "cheating" by construction: the "cheat" is simply not part of the language semantics. In particular, a simple lambda calculus with simple string concatenation and printing primitives cannot implement many (any?) of the "cheats" you have in mind. In such a language, a quine might be a program which prints the exact string representation of it's own code. You can even avoid the print primitive if you allow returning the string rather than printing it. In that case, you only need string literals and concatenation.

It's a useful exercise to figure out various properties of quines in such a language. It's pretty easy to see that some variable will need to be repeated twice: there are no "linear" quines. However the statement

  This structure is read twice, once to reformat it into the code part of the final output, and a second time where it's copied verbatim to reproduce the data part.

is a bit vague, and I'm not sure it's true in general, depending on the precise meaning of "copied verbatim".


Can undecidability theorems be detected by a machine? this question was originally written in mathoverflow, but a comment recommended me to rewrite it as a CS question.

This is not a mathematically formalized question. I'm sorry for that but think it's more like mathematics than philosophy.

When we proved a theorem A which says "B is undecidable", we don't try to prove neither B nor (not B). Can a machine do the same thing? Can it detect "meaning" of a statement, like "something is undecidable"?

Here's a reason why I don't think so.

Suppose a sentence

universal_Turing_machine(program, input, output)

is true if and only if resulting output of "program" with given "input" is "output". Of course, if the program doesn't halt, it would be false for any "input" and "output".

Now, let x be a Godel number of a sentence. Consider the following sentence:

there is no y such that:
y is a Godel number of a string which ends with a sentence encoded as x,
and universal_Turing_machine(program, y, true)

If the program acts as a "decision program accepting valid proofs", this sentence obviously means "a sentence encoded as x is not provable". If not, this sentence doesn't mean any undecidability. Hence if a machine can detect undecidability theorems, it has to detect programs which act as "decision programs accepting valid proofs"

But according to Rice's theorem, detecting programs which has a specific property is not possible.

Do you think this "reason" makes sense? Since this is not a pure mathematical question, I hope to listen to your opinions. Thank you.

Humans have found undecidability theorems. There is no reason known why an artificial intelligence cannot be built that matches what humans can do intelligence wise (although what is currently fashionable seems to be just pattern matching on a massive scale, which is not going to get you very far), therefore there is no reason known why an artificial intelligence, that is a machine, cannot find undecidability theorems.


Confused about the correctness proof of Dijkstra's algorithm In the proof of the correctness of Dijkstra algorithm, there is a lemma stating as follow:

  Let u be v's predecessor on a shortest path P:s->...->u->v from s to
  v. Then, If d(u) = δ(s,u) and edge (u, v) is relaxed, we have  d(v) =
  δ(s,v), where the funciton δ(x, y) denotes the minimum path weight
  from x to y.

I wonder why we need the condition d(u) = δ(s,u) in this lemma. If Path P: s->...->u->v is a shortest path from s to v, then by the property of optimal substructure, the subpath s->...->u of P must also be a shortest path from s to u. Therefore, d(u) must equal to δ(s,u).

Does there exist the case that d(u) ≠ δ(s,u) but P: s->...->u->v is a shortest from s to v? If it does, can someone offer an example here.

Any help will be appreciated

  PS: if you are interested in the entire proof. Check here, the proof starts at 45:30

It looks like you misunderstood the nature of $d(v)$ for a vertex $v$.

$d(v)$ is designed to hold the current known shortest distance from $s$ to $v$ at each step/stage of the algorithm. That is, $d(v)$ is not a fixed value given $s$ and $v$ alone.

At the start of Dijkstra's algorithm, $d(s)$ is initialized to 0 and $d(v)$ is initialized to $\infty$ for each vertex $v\not=s$ in $G$. For example, let graph $G$ have three vertices $s, u, v$ and two edges $\{s,u\}, \{u,v\}$. The path $s,u,v$ is a shortest path from $s$ to $v$. Right right after Dijkstra's algorithm has initialized $d(u)$ to $\infty$, we have $d(u)=\infty\not=1=\delta(s,u)$. This is one of the examples you are looking for. In fact, for all graphs in which $u$ is reachable from $s$, as long as $d(u)$ has not been relaxed to $\delta(s,u)$, we will have, of course, $d(u)\not=\delta(s,u)$.

On the other hand, $d(u)=\delta(s,u)$ must hold at the time when the edge $(u, v)$ is being relaxed in Dijkstra's algorithm. That might be the reason that prompts you to raise this question. Note that as a property of the Dijkstra's algorithm, that fact is not proved yet at the point of time in that lesson.


Can you operate on and draw conclusions on functions described asymptotically? This question is homework based (not using actual problem though)!

Say you have a function described as:

$$f(n) \in  O(2n^2) \, .$$

Can you then go on the treat this as:

$$f(n) = 2n^2$$

and performs mathematics on it and keep its asymptotic meaning?

In the above case could I conjecture that $f(n) \in  O(2n^2)$ implies $f(n) / 2 \in O(n^2)$ (assuming coefficients matter in this example)?

For some operations, such as addition, multiplication, you can operate directly on the asymptotic notation. For example, if $\small g(n) = \mathcal{O}(n^2)$ and $\small f(n) = \mathcal{O}(n^2)$, then $\small g(n) + f(n) = \mathcal{O}(n^2)$ and $\small g(n) \cdot f(n) = \mathcal{O}(n^4)$. For some other operations, such as division, it depends then. For example, for $\small g(n) = \mathcal{O}(n^2)$ and $\small f(n) = \mathcal{O}(n^2)$, it is not correct to say $\small \frac{g(n)}{f(n)} = \mathcal{O}(1)$ (consider $\small g(n) = n^2$ and $\small f(n) = n$). However, if $c$ is a fixed constant, then $\small \frac{g(n)}{c} = \mathcal{O}(n^2)$.


Is NSPACE(2^O(n)) = NSPACE(n^2 * 2^(O(n)) As said in the title, i am quite curious wether
NSPACE(2^(O(n)) equals NSPACE(n^2 * 2^(O(n))
I am aware of the fact, that NSPACE(k * 2^O(n)) equals NSPACE(2^O(n))
due to linear space reduction (i.e. some sort of super character representing k characters)
But since neighter n nor n^2 is linear, we cant use this here.
Thanks for your advise!

Yes. Clearly NSPACE($2^{O(n)}$) $\subseteq $  NSPACE($n^2 \cdot 2^{O(n)}$).
To show that NSPACE($2^{O(n)}$) $\supseteq $  NSPACE($n^2 \cdot 2^{O(n)}$) it suffices to notice that $n^2  \cdot 2^{O(n)} = 2^{O(n) + 2\log n}$ and $O(n)+2\log n =O(n)$.


Proving the given language isn't context free using Pumping Lemma i want to prove that the following Language isn't CF

$L=\{a^kba^kba^k|k\in \mathbb{N}\}$

Let $z=a^nba^nba^n$ be a String from $L$

$n$ is the pumping length and
$|z|=3n+2 > n$

and $z=uvwxy$ with $|vx|\geqslant 1$, $|vwx|\leqslant n$

but i'm not sure how to determine the correct substrings, how should i consider  them ? I tried the ones below are thy correct ?

Case 1 :
$u=a^n,\ uwx=ba^n,\ y=ba^n$

Case 2 :
$u=a^{n-l},\ uwx=a^lb,\ y=a^nba^n$

Case 3 :
$u=a^nb,\ uwx=a^nb,\ y=a^n$

Case 4 :
$u=a^nba^{n-l},\ uwx=a^{l-k},\ y=a^kba^n$

Case 5 :
$u=a^nb,\ uwx=a^n,\ y=ba^n$

The pumping segments $v$ and $x$ can be anywhere in the string assuming they are at most $n$ apart, i.e., $|vwx|\le n$. Like you I get five possibilities, but I think you wrote some special cases rather than the general picture.

Inside one of the $a$-segments, for instance :

the first $u=a^i$, $vwx=a^j$, $y=a^{n-i-j}ba^nba^n$ where $i+j\le n$ and $j\ge 1$. Or
the second $u=a^nba^i$, $vwx=a^j$, $y=a^{n-i-j}ba^n$ where $i+j\le n$ and $j\ge 1$. Or
the third $\dots$ .

Or overlapping with one of the $b$'s. Of course because of the lengths we cannot overlap with both $b$'s.

First: $u=a^{n-i}$, $vwx=a^iba^j$, $y=a^{n-j}ba^n$ where $0\le i,j\le n$, $i+j< n$ .
Second $\dots$ .

However this does not solve the pumping problem. Note we repeat the strings $v,x$ when pumping. In these last cases we do not know how $v,x$ look. Do they contain the $b$? More cases.

A shortcut to the proof would be to make the following observation.

The pumping segments cannot contain $b$.

That leaves five cases for the position of $v$, $x$ in the three $a$-segments. Either deal with them or argue

Now that $v$, $x$ can only contain $a$'s we can pump either one or two of the three $a$-segments in $z$. That means after pumping they cannot all contain the same number of $a$'s


Minimum-cut with minimum number of edges I am sure many folks here know the famous min-cut max-flow theorem - the capacity of the minimum cut is equal to the maximum flow from a given source, s, to a given sink, t, in a graph.

Firstly, let's state (for completeness) that an s-t cut is the partitioning of the vertices in the graph, into two parts, such that the source s is in one partition and the sink t is in the other. The cut-set is the set of edges that are going from vertices in the partition that contains s to those in the other partition.

There may be multiple s-t cuts that have the same capacity as the min-cut (with different sized cut sets). The problem that I wish to solve is, how to find the minimum s-t cut that also has the minimum size cut set?

For example, in the following graph where s = 0 and t = 4:

We can clearly see that the capacity of the minimum cut is 2. One possible way to  get this is to take edges 0-2 and 1-3 (This cut set has size 2). Another possible way to do this is to take edge 3-4 instead (This cut set has size 1) which is the optimal answer.

I have researched about this question and some people are saying that we need to transform the edge capacity, C, of every edge to C * (|E| + 1)  - 1, where |E| is the number of edges in the graph.

One such discussion here: https://codeforces.com/blog/entry/51748
Another such discussion here: https://stackoverflow.com/questions/38408852/finding-the-lowest-amount-of-edges-in-all-minimum-cuts-in-flow-network

The problem is, I don't understand why this formula works. In particular, why do we need to multiply by (|E| + 1) and not some other number? I cannot see how multiplying by any other number would "change" the augmenting paths in the graph as stated in the cited links.

Could someone please advise me?

Edit: The offset in the formula should be +1 and not -1 in order to get the cut-set of the smallest size.

Those answers assume that all edge capacities are integers.  Assuming they are, this works.

Suppose the min-cut in the original graph has total capacity $x$; then it will have total capacity $x(|E|+1)+k$ in the transformed graph, where $k$ counts the number of edges crossing that cut.  Note that if you consider any cut in the original graph with larger capacity, its original capacity will be $x+1$ or more, so its total capacity in the transformed graph will be $(x+1)(|E|+1)+k'$ for some $k'$ in the range $0 \le k' \le |E|$.  Now

$$\begin{align*}
(x+1)(|E|+1)+k'
&= x(|E|+1)+|E|+1+k'\\
&> x(|E|+1)+|E|\\
&\ge x(|E|+1)+k,
\end{align*}$$

so any cut in the original graph that isn't a min-cut won't be a min-cut in the transformed graph, either.

In other words, any min-cut of the transformed graph will be a min-cut of the original graph.

Moreover, out of all of the min-cuts in the original graph, the one whose cut set is smallest is the one that will have lowest capacity in the transformed graph (since the transformation adds one for each edge in the cut set).  So, the min-cut in the tranformed graph will be a min-cut in the original graph, and it will break ties by choosing the one with smaller cut set.


how to reduce the time complexity of this code? I have a graph G=(V,E). A list of nodes NODE subset of V. I want to find out all the neighbor nodes of each node in NODE and add edge if those neighbors have distance greater than 2. Can anyone here please help me to reduce the time complexity of this code to quadratic time or less.

import networkx as nx
import random

G = nx.erdos_renyi_graph(30, 0.05)

node=[]
for j in range(5):
        node.append(random.randint(1,30))

for i in node:
    lst=list(G.neighbors(i))
    if(len(lst)>1):
         for j in range(len(lst)):
             for k in range(j+1,len(lst)):
                 if(len(nx.shortest_path(G,lst[j],lst[k]))>2):
                     G.add_edge(lst[j],lst[k])

To get quadratic time, do the following:

Let $M = N(\text{NODE})$ be the neighbours of NODE in $G$.

Compute $G' = (G - \text{NODE})^3$, the 2nd power graph of $G$ without the vertices from NODE.

Then you do the following:  For every two vertices $u$ and $v$ in $M$, if $uv \notin E(G')$, add $uv$ to $G$.

This way you don't have to compute shortest_path anymore.


Longest path in an undirected tree with only one traversal There is this standard algorithm for finding longest path in undirected trees using two depth-first searches:

Start DFS from a random vertex $v$ and find the farthest vertex from it; say it is $v'$.
Now start a DFS from $v'$ to find the vertex farthest from it. This path is the longest path in the graph.

The question is, can this be done more efficiently? Can we do it with a single DFS or BFS?

(This can be equivalently described as the problem of computing the diameter of an undirected tree.)

We perform a depth-first search in post order and aggregate results on the way,
that is we solve the problem recursively.

For every node $v$ with children $u_1,\dots,u_k$ (in the search tree) there are
two cases:

The longest path in $T_v$ lies in one of the subtrees $T_{u_1},\dots,T_{u_k}$.
The longest path in $T_v$ contains $v$.

In the second case, we have to combine the one or two longest paths from $v$ into
one of the subtrees; these are certainly those to the deepest leaves. The length
of the path is then $H_{(k)} + H_{(k-1)} + 2$ if $k>1$, or $H_{(k)}+1$ if $k=1$,
with $H = \{ h(T_{u_i}) \mid i=1,\dots,k\}$ the multi set of subtree heights¹.

In pseudo code, the algorithm looks like this:

procedure longestPathLength(T : Tree) = helper(T)[2]

/* Recursive helper function that returns (h,p)
 * where h is the height of T and p the length
 * of the longest path of T (its diameter) */
procedure helper(T : Tree) : (int, int) = {
  if ( T.children.isEmpty ) {
    return (0,0)
  }
  else {
    // Calculate heights and longest path lengths of children
    recursive = T.children.map { c => helper(c) }
    heights = recursive.map { p => p[1] }
    paths = recursive.map { p => p[2] }

    // Find the two largest subtree heights
    height1 = heights.max
    if (heights.length == 1) {
      height2 = -1
    } else {
      height2 = (heights.remove(height1)).max
    }

    // Determine length of longest path (see above)
    longest = max(paths.max, height1 + height2 + 2)

    return (height1 + 1, longest)
  }
}

$A_{(k)}$ is the $k$-smallest value in $A$ (order statistic).


Why mod operation can be used as hash function I'm new here, and I'm currently trying to understand why mod operation can be used as a hash function.
For example, consider the function $h(x)=x\mod 2^{256}$, where $x$ can be a string of any length. The book says that this function will return a fixed size of 256 bits. To my understanding, $h(x)$ will return an integer in the interval $[0,2^{256})$, which can be expressed in 256 bits. My question is that, suppose $x$ is $5$, then $h(x)=5$, which can also be expressed in 3 bits (101). How do we guarantee that the output will be the size of $256$ bits? (I am just new to computer science and apologize if the question is too elementary).

The output of the function can always be expressed as a 256-bit value.  The value 5 is expressed as 00000...000101 (some 0's omitted).


Can the W hierarchy by defined by circuits having a satisfying assignment of weight at most k? Traditionally, the $W$ hierarchy is defined around the problem of weighted circuit satisfiability. More precisely, the class $W[t]$ is defined as the closure under $\mathrm{fpt}$-reductions of the following problem.

Given a circuit of weft at most $t$, and depth bounded by a constant, decide whether there is a satisfying assignment of weight exactly $k$.

My question is whether it would be equivalent to define it using the same problem but with weight at most k instead.

This seems to be true for even levels, as there is a theorem (Theorem 7.1 in Parameterized Complexity, Flum and Grohe, 2006) stating that for such levels the problem of finding a satisfying assignment of weight exactly $k$, in a monotone circuit, is $W[t]$-complete. On monotone circuits there is a satisfying assignment of weight exactly $k$ iff there is one of weight at most $k$.

The same argument can't be used however on odd levels, but I would be very surprised if the result wasn't true, so I think there might be a simple proof.

Any help would be appreciated.

No, but something similar holds true.

There is sort of a duality between even and odd levels of the W hierarchy. In particular, maximization problems like p-IndependentSet tend to inhabit the odd levels while minimization problems like p-DominatingSet inhabit the even levels. Asking for something of weight $\leq k$ is a minimization problem.

In terms of p-WSAT, the result you cite extends as follows: For odd levels, antitone levels suffice (antitone means that all atoms are negated). Then, there is a satisfying assignment of weight $k$ iff there is one of weight $\geq k$ (provided there are $\geq k$ variables at all, but if there aren't, the problem can be solved in FPT time by brute force).

And if you choose the wrong monotonicity, you even drop by one level: If $t$ is odd, then p-WSAT for monotone weft $t$, depth $d$ circuits is complete for $W[t-1]$ (respectively is in FPT for $t=1$). If $t$ is even, the same holds for p-WSAT for antitone such circuits. I'll sktech a partial proof.

Let us stick with odd $t$. Using standard normalizations, we can also assume that the circuit is in fact a tree of depth $t+1$ with alternating layers of AND and OR gates, the tree root being an AND gate, and small gates only in the very last layer. As $t$ is odd, the lowest sub-trees all are in $f$-CNF, where the bound $f$ on clause size is the fan-in bound for small gates from the definition of weft.

For some intuition, let us first assume $f=2$. Then, we have monotone 2-CNFs. Consider the graph whose vertices are variables and whose edges are clauses of the 2-CNF at hand. A satisfying assignment of the 2-CNF is a vertex cover of the graph and vice versa. We know how to handle vertex cover in FPT time.

More precisely, using the bounded branching algorithm for p-VertexCover, we can also do the following in FPT time: List all minimal vertex covers of size $\leq k$ of a given graph. With the same technique we can also solve the respective problem for arbitrary $f$: Given a monotone $f$-CNF circuit, list its minimal satisfying assignments of weight $\leq k$. Then, generate a new circuit with an OR gate at top. It has one input for each minimal satisfying assignment from the list. This input is an AND gate, whose inputs in turn are the variables that are set to true in that assignment. It can be seen that the new $k$-DNF circuit is equivalent to the old $f$-CNF one for assignments of weight $\leq k$. Thus we can replace each $f$-CNF subtree by its respective $k$-DNF subtree. After merging the latter's top OR gate with the OR gate that was the former's parent, we have reduced depth to $t$.

As sketched here, the fan-in of small gates is not bounded by a constant any more but by the parameter. Further techniques can remedy this. For the present purpose however, it may be sufficient that we have seen the depth to collapse by $1$.


What is static complexity? Definition : Kolmogorov complexity is a static complexity measure that captures the difficulty of describing a string.
For example, the string consisting of three million zeroes can be described with fewer than three million symbols (as in this sentence)
From wikipedia

In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of the shortest computer program (in a predetermined programming language) that produces the object as output. It is a measure of the computational resources needed to specify the object, and is also known as descriptive complexity, Kolmogorov–Chaitin complexity, algorithmic entropy, or program-size complexity

I am not able to understand few things like " static complexity " and why we need it

Complexities in this context could be divided into dynamic and static:

Dynamic complexity is an attribute of the execution of a program with the string as an input. For example, the time or space complexity of a Turing machine to accept or reject a string.
Static complexity is an attribute of a program that receives the string as input but not its execution. As you stated, Kolmogorov complexity is a static complexity since it is the length of the shortest program that creates the given string, an attribute that implies nothing about the execution of the program.


How hard can identifying non-membership in a semi-decidable language be? A language is called semi-decidable if there is an algorithm for identifying members. There are well-known examples of semi-decidable languages where identifying non-members is equivalent to $\emptyset'$, such as the Halting Problem.

My question is: how hard can identifying non-membership be?

A language $L$ is semidecidable if there exists a computable predicate $f$ such that
$$
x \in L \Leftrightarrow \exists y \, f(x,y).
$$
We can construct a machine $M$ which halts on $x$ iff $\exists y \, f(x,y)$: the machine just goes over all possible $y$, for each one checks whether $f(x,y)$, and if so, halts. This shows that we can decide $L$ using an oracle to the halting problem, i.e., using an $\emptyset'$-machine.


Why is overfitting bad? I've studied this lots, and they say overfitting the actions in machine learning is bad, yet our neurons do become very strong and find the best actions/senses that we go by or avoid, plus can be de-incremented/incremented from bad/good by bad or good triggers, meaning the actions will level and it ends up with the best(right), super strong confident actions. How does this fail? It uses positive and negative sense triggers to de/re-increment the actions say from 44pos. to 22neg.

The best explanation I've heard is this:

When you're doing machine learning, you assume you're trying to learn from data that follows some probabilistic distribution.

This means that in any data set, because of randomness, there will be some noise: data will randomly vary.

When you overfit, you end up learning from your noise, and including it in your model.

Then, when the time comes to make predictions from other data, your accuracy goes down: the noise made its way into your model, but it was specific to your training data, so it hurts the accuracy of your model. Your model doesn't generalize: it is too specific to the data set you happened to choose to train.


Is there a problem solution which, if implementable in a given language, implies that that language is Turing complete? I have been researching a bit lately and found myself thinking about the title question for some time now, but have found nothing conclusive.

For example, some problems require loops practically - making 10^100^1000^10000 repeated calculations (even no-ops) is not possible practically as the space necessary to store the code would likely be greater than the number of atoms in the universe, but would be possible theoretically given infinite memory (similar to how current implementations of programming languages only approximate Turing-completeness).

Alternatively: is there a problem which requires Turing-completeness to solve theoretically?

The answer is no (although from a rather syntactic reason, which might not be what you were looking for).

Let $f : \Sigma^* \rightarrow \Sigma^*$ be some arbitrary function, then it is implementable in the following "stupid" language which is not Turing complete:

Any string $s\in \Sigma^*$ is a valid program, and all strings represent the program which, given $x$ as input, outputs $f(x)$. Note that I don't really care how it computes $f$ (as I'm defining a new model of computation). If this bothers you, imagine any string is translated to the same fixed Java program which computes $f$ (assuming $f$ is computable).


Is there a non-trivial type which is equal to its own derivative? An article called The Derivative of a Regular Type is its Type of One-Hole Contexts shows that the "zipper" of a type—its one hole contexts—follow the differentiation rules in type algebra.

We have:

\begin{align}
\partial_x x &\mapsto 1 \\
\partial_x 0 &\mapsto 0 \\
\partial_x 1 &\mapsto 0 \\
\partial_x (S + T) &\mapsto \partial_x S + \partial_x T \\
\partial_x (S\times T) &\mapsto \partial_xS \times T + S \times \partial_x T
\end{align}

We can use this model to derive that the derivative of unit is void, that the derivative of list is a product of two lists (prefix times suffix), and so on.

A natural question to ask is, "what type is its own derivative?" Of course we already have $\partial_x 0 \mapsto 0$, which tells us that void (the uninhabited type) is its own derivative, but that is not very interesting. It is the analog of the fact that the derivative of zero is zero in the ordinary infinitesimal calculus.

Are there other solutions to the equation $\partial_x T \mapsto T$? In particular, is there an analog of $\partial_x e^x = e^x$ in type algebra? Why or why not?

Consider the finite multisets $\mathbf{Bag}\:X$. Its elements are given by $\{x_1,\ldots,x_n\}$ quotiented by permutations, so that $\{x_1,\ldots,x_n\}=\{x_{\pi 1},\ldots,x_{\pi n}\}$ for any $\pi\in\mathbf{S}_n$. What is a one-hole context for an element in such a thing? Well, we must have had $n>0$ to select a position for the hole, so we are left with the remaining $n-1$ elements, but we are none the wiser about which is where. (That's unlike lists, where choosing a position for the hole cuts one list into two sections, and the second derivative cuts selects one of those sections and cuts it further, like "point" and "mark" in an editor, but I digress.) A one-hole context in a $\mathbf{Bag}\:X$ is thus a $\mathbf{Bag}\:X$, and every $\mathbf{Bag}\:X$ can arise as such. Thinking spatially, the derivative of $\mathbf{Bag}\:X$ ought to be itself.

Now,

$$\mathbf{Bag}\:X = \sum\limits_{n\in\mathbb{N}}X^n/\mathbf{S}_n$$

a choice of tuple size $n$, with a tuple of $n$ elements up to a permutation group of order $n!$, giving us exactly the power series expansion of $e^x$.

Naively, we can characterize container types by a set of shapes $S$ and a shape-dependent family of positions $P$:
$$\sum\limits_{s:S}X^{(P\,s)}$$
so that a container is given by a choice of shape and a map from positions to elements. With bags and the like, there's an extra twist.

The "shape" of a bag is some $n\in\mathbb{N}$; the "positions" are $\{1,\ldots,n\}$, the finite set of size $n$, but the map from positions to elements must be invariant under permutations from $\mathbf{S}_n$. There should be no way to access a bag that "detects" the arrangement of its elements.

The East Midlands Container Consortium wrote about such structures in Constructing Polymorphic Programs with Quotient Types, for Mathematics of Program Construction 2004. Quotient containers extend our usual analysis of structures by "shapes" and "positions" by allowing an automorphism group to act on the positions, allowing us to consider structures such as unordered pairs $X^2/2$, with derivative $X$. An unordered $n$-tuple is given by $X^n/n!$, and its derivative (when $n>0$ is an unordered $n-1$ tuple). Bags take the sum of these. We can play similar games with cyclic $n$-tuples, $X^n/n$, where choosing a position for the hole nails the rotation to one spot, leaving $X^{n-1}$, a tuple one smaller with no permutation.

"Type division" is hard to make sense of in general, but quotienting by permutation groups (as in combinatorial species) does make sense, and is fun to play with. (Exercise: formulate a structural induction principle for unordered pairs of numbers, $\mathbb{N}^2/2$, and use it to implement addition and multiplication so that they're commutative by construction.)

The "shapes-and-positions" characterization of containers imposes finiteness on neither. Combinatorial species tend to organised by size, rather than shape, which amounts to collecting terms in and computing the coefficient for each exponent. Quotient-containers-with-finite-position-sets and combinatorial species are basically different spins on the same substance.


Definition of Turing Machine as a language acceptor The following is an excerpt from the book "An Introduction to Formal Languages and Automata" by Peter Linz.

My question is, why is $\Sigma^+$ used and not $\Sigma^\ast$?

Immediately after the definition, the text (fifth edition) continues

  This definition indicates that the input $w$ is written on the tape with blanks on either side. The reason for excluding blanks from the input now becomes clear: It assures us that all the input is restricted to a well-defined region of the tape, bracketed by blanks on the right and left. Without this convention, the machine could not limit the region in which it must look for the input; no matter how many blanks it saw, it could never be sure that there was not some nonblank input somewhere else on the tape.

This differs from the approach some other authors take, using a tape that's bounded on the left and unbounded in the other direction, and stipulating that the input string begins at the leftmost cell and continues to the first blank. I don't find Linz's definition to be better, if for no other reason than it eliminates any language containing the empty string from being the language of a TM.


Converting generalized NFAs to NFAs I came across generalized nondeterministic finite automata (GNFAs) in Sipser's Introduction to the Theory of Computation. These are automata where transitions are labelled with regular expressions, rather than single symbols from the alphabet. I thought he would explain why GNFAs are allowed. I mean, an appropriate explanation would be that GNFAs are equivalent to NFAs, or GNFAs are equivalent to DFAs or some such argument. But I couldn't find any such explanation in the book.

Online, I read in this article that you can convert a GNFA to an NFA as follows:

  For each transition arrow in the GNFA, we insert the complete
  automaton accepting the language generated by the transition arrow’s
  label as a “subautomaton;” this way, we can replace each regular
  expression by a set of states and character transitions

How is the automaton inserted?

Let's say we have a GNFA with an arrow going from state A to state B labelled with a regular expression R. To convert this GNFA to an NFA, do we get rid of that arrow, instead, take NFA N that recognizes L(R), and create an arrow from A to the start state of N labelled with the epsilon symbol, then create arrows from the accept states of N to B, each also labelled with the epsilon symbol?

Of course the accept states of N would no longer be accept states in the new machine, would they?

I know that GNFAs are equivalent to NFAs but I need a convincing proof, not just a short paragraph mentioning their equivalence.

You are correct in your understanding of the construction: For every transition arrow, say from state $A$ to state $B$ in the GNFA labeled by a regular expression $R$, you replace that transition by the NFA, $N$, for $R$, with an $\epsilon$-transition from $A$ to the start state of $N$ and $\epsilon$-transitions from the final states of $N$ (which you then "un-finalize") to state $B$. Do this for every transition in the GNFA and you'll wind up with an ordinary NFA.

To show that the two accept the same language, it's enough to rely on the previous result (Lemma 1.55 in Sipser) that any regular expression denotes a language that is recognized by a NFA.


5-state DFA that recognizes only the string 00001111 I'm having trouble coming up with a 5-state DFA that, on all inputs of length 8, recognizes the string 00001111 and no other string (of length 8). The DFA must have an exiting transition for every symbol in the alphabet (namely {0, 1}). The behavior on input of other lengths does not matter. A 6-state solution is pretty simple, but reducing down to 5 states requires more sophistication.
Any help would be appreciated!

[If I understand the question correctly, this only relates to strings of length 8, i.e. for an automata $A$ we only look at $L(A) \cap \Sigma^8$]

There is a slight variance in interpretation of what a DFA is that plays a role here.

You can construct a DFA with 5 states that accepts $00001111$, but it is not complete, meaning not every state has an exiting transition for every symbol of the alphabet. This quesiton addresses this point in more details.

What this difference in notation allows you to do is skip the sink-node:

If the input string is of length 8, this automaton accepts only $00001111$.


Turing reducibility of 2 versions of the satisfiability problem I need help with this problem.

  There are 2 versions of the satisfiability problem:

  [1] decision version: determine whether an arbitrary formula f is
  satisfiable or not

  [2] search version: if an arbitrary formula f is satisfiable, return
  an assignment of truth values to variables in the formula that makes f
  satisfiable. if f is unsatisfiable, return NIL.

  Show that [2] is Turing reducible to [1].

I have to prove that the oracle algorithm of [1] entails that of [2] to say "[2] is Turing reducible to [1]".

I see that [2] is just the oracle algorithm of [1] since it discriminates the satisfiability of an arbitrary formula f.

Can this mean the oracle algorithm of [1] entails that of [2]? If can, what would be the reason?

Any algorithm that decides the satisfiability of a formula can also be used to find an assignment for a satisfiable formula:

While not all variables are assigned:

Pick a variable and choose value 0.
If formula is no longer satisfiable, replace value with 1.


Why do BNF specifications of C-like languages define expressions in terms of seemingly unrelated parent expressions? Backus-Naur Form specifications for the grammars of languages like like C or C++ build up expressions with counter-intuitive definitions. For instance, a multiplication expression like

5 * 3

is also a logical-or-expression and an equality-expression and a bunch of other things it doesn't actually look like, because the grammar makes it an:

expression

consisting of an assignment-expression

consisting of a conditional-expression

consisting of a logical-or-expression

consisting of a logical-and-expression

consisting of an inclusive-or-expression

consisting of an exclusive-or-expression

consisting of an and-expression

consisting of an equality-expression

consisting of a relational-expression

consisting of a shift-expression

consisting of an additive-expression

consisting a multiplicative-expression.

A snippet from the grammar looks like:

<exclusive-or-expression> ::= <and-expression>
                            | <exclusive-or-expression> ^ <and-expression>
<and-expression> ::= <equality-expression>
                   | <and-expression> & <equality-expression>
<equality-expression> ::= <relational-expression>
                        | <equality-expression> == <relational-expression>
                        | <equality-expression> != <relational-expression>

So if I were to write a parser that just followed these productions, I'd end up having to interpret the expression 5 * 3 12 different ways, e.g. by making it an instance of a MultiplicativeExpression class which derives from AdditiveExpression... all the way up to a base Expression class. And that seems very wasteful, since those classes would implement adding, AND-ing, OR-ing, etc. but would simply no-op for the single-term case.

By comparison, the Wikipedia example of BNF makes more sense:

<postal-address> ::= <name-part> <street-address> <zip-part>
<name-part> ::= <personal-part> <last-name> <opt-suffix-part> <EOL>
              | <personal-part> <name-part>
<personal-part> ::= <initial> "." | <first-name>
...

The Wikipedia example reads like "a postal address consists of a [...]", whereas C-like language grammars read more like "a [...] can be treated as an expression". Why are C-like language grammars so "polymorphic"?

Why are C-like language grammars so "polymorphic"?

Because that's the way algebra works :-).

The arguments to (for example) a relational expression could be shifts or sums or products (or, for that matter, variables or constants, to say nothing of a variety of unary operator expressions), and all combinations are possible. So you could write out all nine possibilities (and then sixteen possibilities for equality expressions, etc.) (not counting the unary/base possibilities) but the quadratic explosion gets annoying. It's easier to consider each precedence level to include all the more tightly-binding levels as well.

I wouldn't call this polymorphism, really, although you might implement the expression type from a base Expression and individual derived types for each operator. The semantic value of every *-expression production is then a derived type of Expression, and it is not semantically necessary to know which one; the production labels are no longer needed.


Do Approximation Algorithms Analyzed in the Worst Case? From wikipedia:

For some approximation algorithms it is possible to prove certain properties about the approximation of the optimum result. For example, a $ρ$-approximation algorithm $A$ is defined to be an algorithm for which it has been proven that the value/cost, $f(x)$, of the approximate solution $A(x)$ to an instance $x$ will not be more (or less, depending on the situation) than a factor $ρ$ times the value, OPT, of an optimum solution.
$$\begin{cases}\mathrm{OPT} \leq f(x) \leq \rho \mathrm{OPT},\qquad\mbox{if } \rho > 1; \\ \rho \mathrm{OPT} \leq f(x) \leq \mathrm{OPT},\qquad\mbox{if } \rho < 1.\end{cases}$$

For a maximization problem, a $\rho$-approximation algorithm means that, for an instance $x$, $\rho \mathrm{OPT} \leq f(x) \leq \mathrm{OPT}$, for any $\rho<1$. Is this mean that in the worst case the algorithm produces a solution that is at least $\rho \mathrm{OPT}$? Or is this in the average case? Because there are some instances where the algorithm find the optimal solution.
I mean, if the algorithm is executed, say $10000$ times (with randomly generated instances) and produces $\mathrm{OPT}$, say $9995$ times and $5$ times it produces a value that is greater than $\rho\mathrm{OPT}$. What can we say about the algorithm then?

It's a worst case guarantee. It can in some cases do better than $\rho OPT$, but it will never do worse.

In your example we can say very little about the algorithm since you've only tested it with relatively few random instances of a given size. On non-random (structured) inputs it might perform much worse.


regular expression to accept all strings other than one containing ads or adlib My intention is to select only those packages whose name do not contain  adlib or ads. But if i add *adlib* and *ads*  it  selects all packages containing the substring adlib and ads. So i need a regular expression to select all packages that do not contain substring adlib and ads.

Let $[$^$x]$, $[$^$xy]$ be short cuts for $\Sigma - \{x\}$, $\Sigma - \{x, y\}$ etc., i.e., $[$^$a]$ will be regular expression: $(b+c+d+\dots)$.

Then the regular expresseion for words not containing ads or adlib would be

$[$^$a]^*(a[$^$d][$^$a]^*+ad([$^$sl][$^$a]^* $ $+ adl[$^$i][$^$a]^* + adli[$^$b][$^$a]^*)^* (\epsilon + a +ad + adl + adli)$.

Basically we wait for an $a$ and then check it is not followed by the disallowed combinations.

Since regular expressions have built in operators for union, kleene and concatenation only, we will always have trouble with intersection, complement and minus operations. Basically the operation you want in your question is the complement.


Idea for a Graph Based Algorithm Assume there is a Shopping Mall x and all the roads in the city are one way such that, irrespective of the path you take starting from x, you will always end up at vertex x. Device an algorithm to test the same. This seems to be the opposite of a mother vertex, where x is reachable from all vertices instead of all vertices being reachable from x. One way I can think of solving it is to perform DFS on all the vertices and check whether x is visited. An alternate solution which I'm not very sure of, would be to perform the Kosaraju's strongly connected algorithm and prove that there is only 1 connected component. As the question dictates that irrespective of the path you take, you always end up at x, would mean that every vertex would eventually, connect to a vertex connecting to x followed by x itself. Is this intuition correct?

You don't mention that visiting a vertex multiple times is not allowed so I will assume that there isn't such a restriction. In your comment on your question you state that:

  The question is on the lines of If I were to start driving from X, no matter how I drive, I can always reach x

So the question is if $x$ is reachable from all nodes which are reachable by $x$. This is an easy to solve problem in linear time. First do a dfs from $x$ using the right direction of the edges to find which nodes are reachable by $x$. Let's name this set of nodes $A$. Then do a second dfs from $x$ to find from which nodes you can reach $x$. Let's name this set of nodes $B$. The answer of the problem is positive iff
$$A \subseteq B$$
You can check if this condition holds in linear time. The algorithm consists of the following steps:

Read input and initialize two adjacency lists (right and reverse edge directions): $O(N + M)$
Execute dfs from $x$ using right edge directions and mark visited nodes ($A$): $O(N + M)$
Execute dfs from $x$ using reverse edge directions and mark visited nodes ($B$): $O(N + M)$
Check whether $A \subseteq B$ or equivalently if $u \in A \Rightarrow u \in B$: $O(N)$

The total computational and space complexity of the above algorithm is $O(N + M)$ (linear), where $N = |V| \wedge M = |E|$. You may check the following C++ code if you want.

#include <iostream>
#include <vector>
using namespace std;

#define MAXN 100005  // Maximum number of nodes + 5 (change according to your requirements)

vector<int> E[MAXN];  // Adjacency lists with right edge directions
vector<int> RE[MAXN];  // Adjacency lists with reverse edge directions

bool A[MAXN];  // A[i] will become true iff i-th node is reachable from x
bool B[MAXN];  // B[i] will become true iff x is reachable from i-th node

void dfs(int u)
{
    A[u] = true;  // u was reached from x
    for (int i = 0; i < E[u].size(); i++)  //  for every out-neighbour of u...
    {
        int v = E[u][i];  // We name this node v
        if (!A[v]) dfs(v);  // If you haven't visited v yet, visit it now
    }
}

void dfsr(int u)
{
    B[u] = true;  // x can be reached from u
    for (int i = 0; i < RE[u].size(); i++)  //  for every in-neighbour of u...
    {
        int v = RE[u][i];  // We name this node v
        if (!B[v]) dfsr(v);  // If you haven't visited v yet, visit it now
    }
}

int main()
{
    // Read input and make initializations...
    // I assume that nodes are numbered from 0 to N-1
    int N, M, x;
    cin >> N >> M >> x;
    for (int i = 0; i < M; i++)
    {
        int u, v;
        cin >> u >> v;  // There is an edge from u to v
        E[u].push_back(v);  // Right direction from u to v
        RE[v].push_back(u);  // Reverse direction from v to u
    }

    dfs(x);  // DFS from x using the right direction of edges
    dfsr(x);  // DFS from x using the revers direction of edges

    // Check if A is a subset of B (A[x] => B[x])
    for (int i = 0; i < N; i++) if (A[i] && !B[i])
    {
        cout << "NO\n";
        return(0);
    }
    cout << "YES\n";
    return(0);
}

I would like to note two facts:

In your comment you say that the problem statement is equivalent with wether $x$ is reachable by every node. This is not true based on your previous statement. It asks if $x$ is reachable by every node reachable by $x$, which is different. If that was the case only one dfs from $x$ using the reverse edges would be required.
On your question you proposed an idea about finding the strongly connected components. It is true that you can answer the question using this technique, but you don't have to find if there is only one strongly connected component (that solves the wrong problem - see 1.). Instead you have to verify that there is no edge from $x$'s strongly connected component to any other strongly connected component (in which case there would be nodes where you could go starting from $x$ but then you could not return to $x$ from them). This is a correct solution for your problem which also has linear time complexity. Although its implementation is a little bit harder and there is no reason to make things more complex than they are.


Pros and Cons of Average Memory Access Time When Increasing Cache Block Size Assuming we have a single-level (L1) cache and main memory, what are some of the advantages and disadvantages of having a larger cache block size (considering average memory access time).

The only ones I can think of are that a larger block size could increase the hit rate when adjacent memory locations are accessed, i.e. good for spatial locality. I can't think of any other advantages; are there?

As for disadvantages, I assume that having a larger block size increases the cache size, thereby increasing cost (since L1 cache is expensive), but I can't see any disadvantages relating to average memory access time. Are there?

An increased block size is indeed good for spacial locality.

On the other hand, a large block size increases the possibility of fragmentation and false sharing (in multiprocessor system).

Another way of thinking about this problem is if your cache size is fixed (based on cost, etc.), and you are changing the block size. In this case, as you increase your cache block size, accessing adjacent memory locations will have more hits (spacial locality), but there is a disadvantage considering temporal locality. Consider the extreme case, in which the cache has one block. Of course, this would be good for spacial locality, but it is terrible for a program repeatedly accessing two memory locations that are at least one full block size away from each other. The cache will miss every time.

EDIT

Consider this: you have a process with data in consecutive memory locations "A" through "H" of size "1." You have a warm cache of size "4" (ignoring compulsory misses, the misses/repeat below are average case) and an LRU cache replacement policy.

Let the cache block size be 4 (the "largest" block size case).

For repeated, in-order memory accesses A-H, this cache has 2
misses/repeat.
For repeated, out-of-order memory accesses A, B, E, F,
C, D, G, H, this cache has 4 misses/repeat.
For repeated, out-of-order memory accesses A, B, E, F, this cache has 2 misses/repeat.
For repeated, random memory accesses A, E, B, F, this cache has 4 misses/repeat.

Let the cache block size be 1 (the "smallest" block size case).

For repeated, in-order memory accesses A-H, this cache has 8 misses/repeat.
For repeated, out-of-order memory accesses A, B, E, F, C, D, G, H, this cache has 8 misses/repeat.
For repeated, out-of-order memory accesses A, B, E, F, this cache has 0 misses/repeat.
For repeated, random memory accesses A, E, B, F, this cache has 0 misses/repeat.

Let the cache block size be 2 (the "optimal" block size case).

For repeated, in-order memory accesses A-H, this cache has 4
misses/repeat.
For repeated, out-of-order memory accesses A, B, E, F,
C, D, G, H, this cache has 4 misses/repeat.
For repeated, out-of-order memory accesses A, B, E, F, this cache has 0 misses/repeat.
For repeated, random memory accesses A, E, B, F, this cache has 2 misses/repeat.

The "largest" block size case is best for repeated, in-order memory accesses (best for spacial locality) and worst for repeated, random memory accesses (worst for temporal locality).

The "smallest" block size case is worst for repeated, in-order memory accesses (worst for spacial locality) and best for repeated, random memory accesses (best for temporal locality). It is good for out-of-order memory accesses, depending on the size of the working set.

The "optimal" block size case is good for repeated, in-order memory accesses and good for repeated, random memory accesses, but it is not the "best" for either case.


Prove regular languages are closed under f(n) = 2^n and f(n) = n^2 Suppose $ R $ is a regular language, let $ f(R) = \{ w \mid \exists x \text{ such that } |x| = f(|w|) \land wx \in R\}$, prove that $ f(R) $ is regular for $ f(n) = 2^n $ and for $ f(n) = n^2$. I've been on this question for a while now, and I'm not really sure how to approach it. I only really know elementary techniques like Myhill-Nerode and constructing DFA/regex, so I probably won't understand solutions using more complex logical models of regular languages.

For $f(n)=2^n$:

Let $M=(Q,\Sigma,\delta,q_0,F)$ be the DFA recognizing $R$. Denote by $\mathcal{G}$ the set of functions from $Q$ to $\mathcal{P}(Q)$ (where $\mathcal{P}(Q)$ means the power set of $Q$), and for any $g,h\in\mathcal{G}$, denote by $gh$ the function defined as $$gh(\cdot)=\bigcup_{q\in h(\cdot)}g(q).$$

Construct a new DFA $M'$ of whose states each is labeled a pair $(q,g)\in Q\times\mathcal{G}$. The transition function $\delta'$ of $M'$ is defined as

$$\delta'((q,g),a)=\left(\delta(q,a),gg\right),$$

for all $q\in Q, g\in\mathcal{G}, a\in\Sigma$. The start state of $M'$ is $(q_0,g_0)$ where $g_0$ is defined as $g_0(\cdot)=\{\delta(\cdot,a)\mid a\in \Sigma\}$. The set of accept states of $M'$ is $\{(q,g)\in Q\times\mathcal{G}\mid g(q)\cap F \neq \emptyset\}$.

Now we claim that

  After reading a word $w$, if $M$ reaches state $q$, then $M'$ reaches the state $(q,g)$, where $g(\cdot)$ represents the set of states $M$ can potentially reach when starting at state $\cdot$ then reading a word of length $f(|w|)$.

This cliam can be proven by mathematical induction on $|w|$. With this claim, we can see $M'$ indeed recognizes $f(R)$.

For $f(n)=n^2$, the proof is similar. In this case, each state of $M'$ is labeled a tuple $(q,g_1,g_2)\in Q\times \mathcal{G}^2$, the transition function becomes

$$\delta'((q,g_1,g_2),a)=\left(\delta(q,a),g_1g_0,((g_2g_1)g_1)g_0\right),$$

where $g_0(\cdot)=\{\delta(\cdot,a)\mid a\in \Sigma\}$ as above, the start stae becomes $(q_0,I,I)$ where $I(\cdot)=\{\cdot\}$, and the set of accept states becomes $\{(q,g_1,g_2)\in Q\times\mathcal{G}\mid g_2(q)\cap F \neq \emptyset\}$.

Also, our claim becomes

  After reading a word $w$, if $M$ reaches state $q$, then $M'$ reaches the state $(q,g_1,g_2)$, where $g_1(\cdot),g_2(\cdot)$ respectively represent the set of states $M$ can potentially reach when starting at state $\cdot$ then reading a word of length $|w|,|w|^2$.


LR(0) expressive power So I have grouped the following formalisms into a power hierarchy (and made classes for them):

Class 1

DFA
NFA
NFAϵ
reg.exp

Class 2 (DCFL expressivity?)

LR(1)
DPDA

Class 3

CFG
PDA

Class 4

TM
NTM

Class 4 is the most powerful class and Class 1 is the least powerful.
Now I want to compare them to LR(0) parsers. My current intuition is that LR(0) parsers can handle all of Class 1 (and probably belongs to class 1). Class 2 has more power than LR(0) due to the fact that LR(0) defines a subset of Class 2 (DCFL's with the prefix property).

So I guess the question is, should LR(0) parsers be put into its own class or should it go into Class 1 (which would be my guess).

You're correct that all regular languages have a LR(0) grammar. Moreover, there are LR(0) grammars which generate a non-regular language. (Exercise: Construct a LR(0) grammar for $\{ a^n b^n\,|\,n>0 \}$.)

LR-ness is a tricky concept to get a grasp on, because LR-ness is a property of the grammar, not necessarily the language. Having said that, it is known that all DCFLs can be recognised by a LR(k) parser in $O(n)$ time. It's also known that any LR(k) grammar can be mechanically transformed into an equivalent LR(1) grammar, and that there are examples for which there is no LR(0) grammar. So LR(1) is the same as DCFL/DPDA, and LR(0) is a proper subset.

So, yes, DCFL/DPDA/LR(1) sits somewhere between 3 and 4 on the Chomsky hierarchy, and LR(0) sits between that and 4. (By the way, don't forget Chomsky type 2 when you're examining hierarchies of languages and machines.)


Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row? For example, a valid number would be 6165156 and an invalid number would be 1566515.
I have tried many times to construct a finite state machine for this with no success, which leads me to believe the language is not regular. However, I am unsure how to formally prove this if that is indeed the case. I tried applying the pumping lemma but I am not completely sure how to apply it to this particular language.
Any help is appreciated!

I attempted to solve the question separately:
The "no more than two 5s" bit can be represented by the regex $a^*(\epsilon+5)a^*(\epsilon+5)a^*$.
The "no two 6s in a row" bit can be represented by the regex $(a+6a)^*(6+a+\epsilon+6a)$.
Where $a\in\{1,2,3,4,7,8,9,0\}$.
Notice that we could potentially replace all the a*s in the first regex with the second regex, but this is problematic since it would allow double 6s. So I drew a FSM that uses this idea without violating the constraints. Hopefully, you could work out the regex and minimize the FSM if it can be minimized.
The language is regular since an FSM that defines it exists, hence its regular expression can be obtained.