positivity condition in Coq/CIC I am recently learning the theory behind Coq and learnt that positivity condition guarantees termination of the program. But my question is, what would you think of the following definition?

Inductive t : Set := b : t | c : ((t -> unit) -> unit) -> t.

Sure it won't compile in Coq, but would it jeopardize termination guarantee? More precisely, in this definition, t is in a positive position as well, isn't it? So can I say theoretically speaking this should have also been a valid definition? Otherwise do you have any counter example?

My thought is, (t -> unit) -> unit should be isomorphic to t according to Yoneda lemma so it should be pretty safe, isn't it?

The positivity condition is not there just so that "programs terminate", as you put it (what programs?), but to make sure the type is well defined in the first place. The inductive definitions define the smallest type satisfying an equation. That is, we put into the type only those things which are prescribed by the clauses of the definition, and no arbitrary garbage. (Non-normalizing terms count as garbage, and I think that's what you meant when you spoke of terminating programs.)

Let us take a step back and think where the inductive definitions come from. They are solutions to type equations. Here is a type equation:
$$N = \mathtt{unit} + N.$$
What could $N$ be? We might be thinking that it must be the natural numbers, since every element of $N$ is either $\mathtt{inl}(\mathtt{tt})$, which is a fancy way to say "zero", or it is of the form $\mathtt{inr}(n)$ for some $n : N$. But this need not be the case! For example, $N$ could also contain a special element $\infty$ satisfying $\infty = \mathtt{inr}(\infty)$. It could also contain an extra "fake zero" $\mathtt{Z}$, together with its successors $\mathtt{inr}(\mathtt{Z})$, $\mathtt{inr}(\mathtt{inr}(\mathtt{Z}))$, ... There are many solutions to the above equation.

The smallest solution is called the inductive type, and the largest one the coinductive type. I am skipping technicalities about what "smallest" and "largest" mean precisely (they are the "initial algebra" and "final coalgebra", respectively), but I hope you get the point.

In order for us to say that we have a well-defined inductive type, we need to know that the smallest solution to the type equation actually exists. In fact, it does not always exist, sometimes there can be several incomparable solutions, or none at all. The positivity condition in Coq and CIC ensures that a smallest solution exists. It's not the only possible condition one could come up with, and there are variants, but for the purposes of a proof assistant we need something that makes sense computationally, and can actually be verified by a type checker (for instance, it wouldn't do to say that an inductive definition is valid if it defines a $\kappa$-accessible functor for some cardinal $\kappa$, and have the proof checker look for $\kappa$ – hmm, that's an interesting thought).

If we now look at your proposed definition

Inductive t : Type := b : t | c : ((t -> unit) -> unit) -> t.

the question to be asked is: how do you know that the smallest solution exists? Somebody proved that the strict positivity requirement ensures the existence, but your definition falls outside that criterion. You need to provide evidence that there is such a type. The evidence must be a well argued explanation of what the terms of t are that they do not break strong normalization of CIC. You might as well succeed, and there is such a type. The next question then is how do you propose to incorporate your argument into a type checker as a useful algorithm. It's probably not worth the trouble.

Just to show you how problematic these things are, how about the type

Inductive t : Type := c : ((t -> bool) -> bool) -> t.

Is it still totally obvious that there is a smallest solution? We're trying to solve the type equation
$$T = (T \to 2) \to 2.$$
It has no solution in set theory.


Help me understand this Turing-machine Problem concerning $A_{TM}$ I'm a Physics/C.S. student and have been struggling with this particular problem for a few days now.
So the task is as following:

Consider the following languages:
$\hspace{20pt} L_1 = \{\langle M \rangle \, | \, L(M) = A_{TM}\} \\
\hspace{20pt} L_2 = \{\langle M \rangle \, | \, L(M) = \overline{A_{TM}}\}$
Are these decidable? Prove your decision.
$A_{TM}$ is defined as $\{\langle M , w\rangle \, | \,\text{M is a TM and M accepts w}\}$

So first off I'm trying to understand the first language $L_1$.
What exactly would it mean for $L_1$ to be decidable? I understand why $A_{TM}$ isn't decidable, but what would a TM that decides $L_1$ actually do?
I feel like I already know the solution to the second problem but would like to know whether my gut instinct is right. So since $\overline{A_{TM}}$ isn't Turing-recognizable it means that $M$ with $L(M) = \overline{A_{TM}}$ doesn't exist/is empty. Thus $L_2 = \emptyset$ and that's easily decidable.

Solving the language $L_1$ means knowing for every TM if it's semi-deciding the $A_{TM}$ problem.
Your instinct is right - it is empty and therefore decidable. If it wasn't empty by any chance, then by Rice's theorem it would have not been decidable


Is TSP a more detailed form of the "Set Inclusion" question? Background

Set Inclusion

GIVEN: set of cards, some with blue backs, and each with a positive, integer face value.

QUESTION: Are there any [blue-backed cards] with a [face value <= L]?

2 independent variables: [blue/white cards], [integer face values]

Function A: Select a blue-backed card

face value depends on which card you select
each blue card potentially has face value <= L

thus, worst-case = [check all blue cards]

Function B: Select a face value <= L

blue back depends on which card you select
each card w/ face value <= L potentially has blue back

thus, worst-case = [check all cards w/ face value <= L]

Function B cannot exist. There is no way to verify that a selected card has a blue back, since don't know key info:

How are cards marked with a blue back?

WORST-CASE: turn over all blue-backed cards (Function A)

Travelling Salesman

GIVEN: complete graph, G(V,E), where all edges are positive, integer values.

DEFINITION: "config"

{A, B, u, v} where u & v are 2 vertices, and A & B are the remaining vertices split up as evenly as possible

DEFINITION: "optimal tour of a config"

shortest path from u to v, only going thru each vertex in A once, and
shortest path from v to u, only going thru each vertex in B once

Assume we have a function, f, that returns the optimal tour for a given config, in sub-exponential time. (EDIT: if you can prove this function must take exponential time, you've shown $P\neq NP$.)

A smallest tour must be the optimal tour of one of the configs in G.
Any config could produce the smallest tour.

NOTE: Each tour is an edge-set that can form |V|/2 or |V| configs, for even or odd |V|, respectively.

A COMPLETE GRAPH is equivalent to: set of cards, some with blue backs, and each with a positive, integer face value.

each card represents a set of edges with size = |V|
blue backs mark any edge-sets that are an optimal tour for a config
face value is the sum of the edge-set represented by the card

QUESTION: Are there any [blue-backed cards] with a [face value <= L]?

2 independent variables: [blue/white cards], [integer face values]

Consider case where L = length of smallest tour.

Only need look at blue cards (edge-sets that are an optimal tour for a config)
Only need look at cards w/ face value = L (edge-sets with sum = L)

Function A: Select blue-backed card

face value depends on which card you select
each blue card potentially has face value = L

thus, worst-case = [check all blue cards]

Function B: Select a card with face value = L

blue back depends on which card you select
each card w/ face value = L potentially has blue back

thus, worst-case = [check all cards w/ face value = L]

Unlike "Set Inclusion", now you can verify that a selected card for Function B has a blue back, by running f on the selected card's configs.

However, controlling either variable, [choosing blue card] or [choosing card w/ face value = L], causes the other to be uncontrollable.

WORST-CASE:

FACE-DOWN Approach: turn over all cards with blue back (Function A)
FACE-UP Approach:   turn over all cards with face value = L (Function B)

Question

So the final question: Is TSP-Decision a version of "Set Inclusion" that has enough information to define a Function B?

If so, does this mean that the worst-case running time of TSP-Decision is lower-bounded by the smaller of the 2 domains of Functions A and B?  i.e. min{number of blue cards, number of cards with face value = L} -- still only for the case where L = length of smallest tour.

EDIT: Both those lower-bounds are exponential, so if we can show that TSP-Decision is lower-bounded by them, we've shown that P != NP.

As far as I can see, your model is that the edges of the graph are represented by cards and the edges on the optimal TSP tour are cards with blue backs. You're asking if TSP corresponds to the problem of identifying the cards with the blue backs.  If that is the case, the answer is "yes".

However, there is a huge caveat. In the set inclusion problem, we can tell in constant time if the back of a card is blue: you just turn over that one card and look at it. You assume that we can do the same in TSP: in constant time, we can tell whether any single edge is in the optimal tour. This is a completely unrealistic assumption because it's impossible to tell if an edge is on the optimal tour without examining at least one edge from every vertex.

I think that what you've observed is basically that, if somebody has somehow solved a TSP instance, you can find the solution by asking them whether each individual edge is in the optimal tour. This is obviously true, but it's not very interesting.


Higher Residuocity Problem w.r.t. a composite Modulus An integer $q$ is called a quadratic residue modulo $N$ if it is congruent to a perfect square modulo $N$; i.e., if there exists an integer $x$ such that:
$x^2≡q\ (mod\ n)$.

Otherwise, $q$ is called a quadratic non-residue modulo $N$.

Given that $N$ is a composite number (whose prime factorization is known beforehand) can someone help with the generic higher residuocity problem of the form:

$(x^2-c^2)^k≡q\ (mod\ n)$.

Find $x$ (where $c$ is some random integer value)? $k$ is an even number (say 2).

I think we can solve it using an approach similar to the original QRP, but I am struggling with the exact approach. Can someone please help with an explicit example?

Testing whether $q$ is a quadratic residue modulo $n$ is hard when $N$ is composite: it is as hard as factoring $N$, which is believed to be hard when $N$ is large.

The same is true for your problem.

If the factorization of $n$ is known and $k=2$, you can test whether $q$ is a quadratic residue; find all square roots, call it $y$, such that $y^2 \equiv q \pmod n$, then for each such square root $y$, test whether $y + c^2 \bmod n$ is a quadratic residue and find a square root of it, i.e., an $x$ such that $x^2 = y + c^2 \pmod n$, and then you will have a solution to your original problem.  This will be efficient if there aren't too many square roots, i.e., if $N$ doesn't have too many different prime factors.

Alternatively, assuming $n$ is squarefree and has known factorization $n=p_1 \cdots p_m$ and assuming $k$ is not too large, you can factor the polynomial $(x^2-c^2)^k-q$ over $\mathbb{Z}/p_i\mathbb{Z}$ (separately for each prime factor $p_i$ of $n$), then if this polynomial has a root modulo every $p_i$, combine solutions via the Chinese remainder theorem.


Algorithm to recognize Strongly Regular Graph (SRG) I am looking for an algorithm to determine whether a graph is  Strongly Regular Graph (SRG) or not.

There is a trivial $O(kn^2)$ algorithm:

Choose a vertex $v$ and calculate its degree $k$. Then verify that all other vertices have degree $k$.
Choose some neighbor $w$ of $v$ and calculate the number of common neighbors $\lambda$. Then verify that all other pairs of adjacent vertices have $\lambda$ common neighbors.
Choose some non-neighbor $x$ of $v$ and calculate the number of common neigbors $\mu$. Then verify that all other pairs of non-adjacent vertices have $\mu$ common neighbors.

If you like linear algebra, you can also compute the square $A^2$ of the adjacency matrix $A$. Then check that:

All diagonal entries of $A^2$ are equal to some constant $k$.
All off-diagonal entries $A^2_{ij}$ such that $A_{ij} = 1$ are equal to some constant $\lambda.
All off-diagonal entries $A^2_{ij}$ such that $A_{ij} = 0$ are equal to some constant $\mu$.

This algorithm takes time $O(n^\omega)$.


Hiring one person out of n -- rank and probablity I am studying algorithms from CLRS book. I try to understand the difference between

probability of hiring the $i$th person out of $n$ and
probability of hiring the $i$th person out of $n$ persons based on ranks.

Using the normal probability, we know the answer for the first one is $\frac{1}{n-i}$ and the answer for the second is given as $\frac{1}{i}$ in the CLRS book. I am unable to understand the concept here. How is it $\frac{1}{i}$? Can it also be $\frac{1}{n-i}$ taking in ranks, too?

We have n candidates lined up for an intertiew.Once a candidate is interviewed he is given a rank.If the rank of the next candidate is greater the current greatest rank he is hired and his rank is now the current greatest rank

HireAssistant(n)
   best=0
   for i=1 to n
       interview candidate i
       if candidate i better than candidate best
          best=i
          hire candidate i

When people are interviewed following a random arrival order, the probability of candidate $i$ being hired is $\frac{1}{i}$. This follows from the fact that, assuming a random order of arrivals, for each $i$ the group of initial $i$ candidates is random, so that the $i$-th candidate has probability $\frac{1}{i}$ of being chosen which happens if he/she is better qualified than the previous $i-1$ candidates.

Now instead of considering a random order on the arrivals, impose your own order, based on ranks: the first candidate is the less qualified, and the last one is the one which is the best overall. In this case, if the group is made of $n$ candidates, numbering them from $0$ to $n-1$ you get for the $i$th candidate a probability of being hired which is $\frac{1}{n-i}$, since candidates are now arriving on the basis of their ranks, and the $i$-th candidate is always better qualified than the previous $i-1$.

This is why you want to permute the group of candidates: so that no particular input elicits the worst case behavior associated to the permutation in which candidates are sorted by rank.

CLRS explains how this minor modifications allows you to hire, on average, $O(\lg n)$ candidates instead of $n$ in the worst case. Note that this is only a probabilistic guarantee: nothing prevents the pseudorandom generator, if you are really unlucky, from generating the permutation corresponding to the candidates sorted by rank. But we do not expect this to happen frequently: the probability of generating the bad permutation is only $\frac{1}{n!}$ which, for large $n$, is very low.


Which Turing machine problems are Decidable? Let $M_0$, $M_1$, $M_2$,..., be an effective enumeration of all Turing machines. Which of the following problems is (are) decidable ?

Given a natural number $N$, does $M_N$ starting with an empty tape halts in fewer than $N$ steps ?
Given a natural number $N$, does $M_N$ starting with an empty tape halts after at least $N$ steps?
Given a natural number $N$, does $M_N$ starting with an empty tape halts in exactly $N$ steps?

I've looked some of these similar problems like :-

Prove that this language is decidable or undecidable

Is the set of Turing machines which stop in at most 50 steps on all inputs, decideable?

I've got some idea that $TM$ problems related to $N$ steps, only the cells upto $N$ are significant.

Such problems are decidable, however long input we take.

Hence, I come to the conclusion that $1$st part of my problem will be decidable similar to the reasoning as given above.

Similarly, for $3$rd part, if we check $N$th cell we can say $Y/N$ hence Decidable.

But, I am stuck in $2$nd part.

(What I think is that upto $N$th cell we can check if it halted, making it semidecidable otherwise it will definitely halt after the $N$th cell. Hence, I think it is also Decidable).

Please let me know how much correct progress I made. I don't have solutions for these questions. Need some confirmation ?

You can simulate a given Turing machine to a given number of steps. This allows you to decide Problem 1 and Problem 3, by running $M_N$ on the empty type for $N$ steps (or fewer, if it halts earlier).

Regarding Problem 2, assuming that $N$ is in the language if

$M_N$ halts on the empty tape, and
$M_N$ doesn't halt within the first $N$ steps,

then you can use this language to solve the halting problem (using the same effective enumeration). Given $N$, in order to determine whether $M_N$ halts on the empty tape:

Run $M_N$ for $N$ steps. If it halts, answer Yes.
Otherwise, use Problem 2 to determine whether $M_N$ halts on the empty tape, but not within the first $N$ steps.

Hence Problem 2 is undecidable.


Infinite Union of Recursive language Question

Is Infinite Union of Recursive language is Recursive?

I know it is already posted here, but the i am not getting answer also i want to know if my approach is correct.
My Approach/Doubt
$\text{let}\,\,L_1=abcd \,\,\,L_2=a^2b^2c^2d^2=aabbccdd,L_3=a^3b^3c^3d^3=aaabbbcccddd$
here $L_{1},L_{2},L_{3}\,....\text{are finite hence regular hence recursive}$
let $L_{Iu}=L_1 \,\cup\,L_2\,\cup\,L_3\,\cup........$
but $L_{Iu}=a^{n}b^{n}c^{n} \text{which is recursive }$ .
so can i say that Infinite Union of Recursive language is Recursive
Please help me out

Every finite language is recursive.

Every language can be written as an infinite union of finite languages.

Some language isn't recursive.


Construct a DAG using Tarjan This is a question related to a homework assignment so I guess I'm asking for hints, if that's ok? Basically, I'm wondering if there is some way to use Tarjan to compress the nodes in every SCC found into one single node, essentially producing a DAG. The problem I'm faced with is that every SCC is obtained as a set but I can't seem to find a way to preserve the edges leading out of the SCC.

Construct a new graph whose vertex set is the strongly connected components. Now go over all edge in the original graph, and if they connect two different strongly connected components, add the corresponding edge to the new graph if it's not already there.


Direct reduction from $st\text{-}non\text{-}connectivity$ to $st\text{-}connectivity$ We know that $st\text{-}non\text{-}connectivity$ is in $\mathsf{NL}$ by Immerman–Szelepcsényi theorem theorem and since $st\text{-}connectivity$ is $\mathsf{NL\text{-}hard}$ therefore $st\text{-}non\text{-}connectivity$ is many-one log-space reducible to $st\text{-}connectivity$. But is there a direct/combinatorial reduction that doesn't go through the configuration graph of the Turing machines in $\mathsf{NL}$?

$\mathsf{stConnectivity}$ (a.k.a. $stPATH$):
Given directed graph $G$ and vertices $s$ and $t$,
Is there a directed path from vertex $s$ to vertex $t$?

Clarifications:
You can assume a graph is given by its adjacency matrix (however this is not essential since standard representations of graphs are log-space convertible to each other.)
It is possible to unpack the proof of $\mathsf{NL\text{-}hard}$ness of $st\text{-}connectivity$ and move it into the proof so the proof does not use it that theorem as a lemma. However this is still the same construction essentially. What I am looking for is not this, I want a conceptually direct reduction. Let me give an analogy with the $\mathsf{NP}$ case. We can reduce various $\mathsf{NP\text{-}complete}$ problems to each other by using the fact that they are in $\mathsf{NP}$ therefore reduce to $SAT$ and $SAT$ reduces to the other problem. And we can unpack and combine these two reductions to get a direct reduction. However it is often possible to give a conceptually much simpler reduction that doesn't go through this intermediate step (you can remove mentioning it, but it is still there conceptually). For example, to reduce $HamPath$ or $VertexCover$ or $3\text{-}Coloring$ to $SAT$ we don't say $HamPath$ is in $\mathsf{NP}$ and therefore reduces to $SA$ since $SAT$ is $\mathsf{NP\text{-}hard}$. We can give a simple intuitive formula that is satisfiable iff the graph has a Hamiltonian path.
Another example, we have reductions from other problems in $\mathsf{NL}$ to $st\text{-}Connectivity$ which do not rely on $\mathsf{NL\text{-}complete}$ness of $st\text{-}Connectivity$, e.g. $Cycle$, $StronglyConnected$, etc, they involve modification on the input graph (and do not refer to any Turing machines that is solving them).
I still don't see any reason why this cannot be done for this one.
I am looking for a reduction of this kind.
It might be the case that this is not possible and any reduction would conceptually go through the $\mathsf{NL\text{-}hard}$ness result. However I don't see why that should be the case, why the situation would be different from the $\mathsf{NP}$ case.
Obviously to give a negative answer to my question we would need to be more formal about when does a proof conceptually include another proof (which is proof theory question that AFAIK not settle in a satisfactory way). However note that for a positive answer one does not need such a formal definition and I am hoping that is the case. (I will think about how to formalize what I am asking in a faithful way when I find more free time. Essentially I want a reduction that would work even if we didn't know that the problem is complete for $\mathsf{NL}$.)
Using the proof of Immerman–Szelepcsényi theorem is fine, using $\mathsf{NL\text{-}complete}$ness of $stPATH$ and configuration graph of an $\mathsf{NL}$ machine is what I want to avoid.

It is possible, if messy, to convert the proof of the Immerman-Szelepcsényi theorem to the reduction you want. There is absolutely no need to use the NL-completeness of st-connectivity.

Given an instance $G=(V,E),s,t$, we construct a new graph $G'=(V',E'),s',t'$. The "major vertices" of $V'$ record the following information: the current distance $d$ from $s$, the number of vertices of distance at most $d-1$, the number of vertices of distance $d-1$ counted so far, the current vertex we're guessing if it has distance at most $d-1$, the number of vertices of distance at most $d$ counted so far, the current vertex we're determining whether it has distance at most $d$. The minor vertices handle the part where we guess a path of length at most $d-1$ to a vertex which we guess to be of distance at most $d-1$. Edges that involve showing the vertex $t$ is reachable from $s$ are dropped. For each vertex which we're testing at the current distance, we only move forward to the next vertex if we have accounted for all vertices of smaller distance. When moving from distance $d$ to distance $d+1$, we copy the requisite information. The starting vertex $s'$ accounts for the fact that $s$ is the only vertex of distance zero. The ending vertex $t'$ is pointed at by all vertices representing the fact that the process has finished up to (and including) distance $n-1$, where $n=|V|$.

As you can see, it will be quite messy to write everything in full and correctly, but definitely possible. No overt use of NL-completeness was made, in that we never use the configuration graph of any NL machine. That's not needed, since we have something better than the configuration graph - the input instance itself.


What should I read to understand semantics of programming languages? I would like to have a good conceptual understanding of the semantics of programming languages: operational-, denotational-, axiomatic-, categorical-.

Is there a good (standard?) textbook for this?

There are many depending on where you want to start and what exactly you want.
Usually textbook start with giving semantics to the While or IMP language and then give references to semantics of lambda calculus (typed untyped) unless you are reading Gunter. I am listing down a few below that I have referenced a number of times:

Operational Denotational and Axiomatic:

a. Formal Semantics of Programming languages by
Wynskell

b. Programming Language Foundations by Stump

c. Theories of programming languages by Reynolds
Denotational semantics:
Denotational Semantics by Stoy
Denotational and Categorical semantics: Semantics of Programming languages by Gunter
Categorical semantics: Category theory for computing science by Barr and Wells
Mostly operational semantics (may be with types involved):

a. Types and Programming languages

b. Semantics Enginnering with PLT redux

See also this question and this question on stackexchange.
and this further reading section of wikipedia article


O(n) Palindromic Substring: Why is O(n^2) needed here? I have been doing dynamic programming problems, and I came across a palindromic substring question.  I answered it quickly, and found an $O(n)$ dynamic programming solution, but when I check the actual solution, I find that I should be getting an $O(n^2)$ result.

Can someone explain where I am going wrong/how this is not correct?

The problem reads: given string $x_1,x_2,\ldots,x_n$, find the longest palindromic substring.

I write:

$$
T(i) = \text{max length palindromic substring ending at position }i\text{ in string }X
$$

Then I write down the following subproblem (where $j$ is intended to be the letter right before the beginning of the palindrome ending at position $i$):

$$
\begin{align}
\text{IF  }x_i = x_j, \text{ where } &j = i - T(i-1)-1:\\
T(i) &= T(i - 1) + 2;\\
\text{ELSE IF} x_i = x_{i-1} \\
T(i) &= 2;\\
\text{ELSE } T(i) &=1;
\end{align}
$$

As far as I can tell, this is correct.  In order to recover the palindrome, I record it in linked lists or whatever, and calculate the argmax of $T$.

Where am I going wrong?

Consider the following string
$$ dabacabac $$
When you go to compute $T(9)$ (using one indexing), you have $T(8) = 7$. But since
$$ T(1) = d \neq c = T(9) $$
You will put $T(9) = 1$, when it should be $T(9) = 5$.


Show that the equivalence problem for deterministic Turing machines and its complement is not semi-decidable I would like to show that
$$EQ_{DTM} = \{ (\langle M_1\rangle,\langle M_2\rangle) \mid M_1\text{ and } M_2 \text{ are  DTMs  and } L(M_1)=L(M_2)\}$$
 and
$$\overline{EQ_{DTM}}$$
 are not semi-decidable. I think there must be a reduction from the complement of the halting problem.

I think an easier way to approach this is by reducing from
$$ALL_{TM}=\{\langle M \rangle: M \text{ is a DTM and } L(M)=\Sigma^*\}$$

Showing that $ALL_{TM}$ is not in in RE nor coRE a standard exercise, and you can find the solution e.g. here

Then, we can reduce from $ALL_{TM}$ to $EQ_{TM}$ as follows: given input $\langle{M\rangle}$ for $ALL_{TM}$, we output $\langle{M,T\rangle}$ where $T$ is a fixed TM that accepts every input immediately. Thus, $L(T)=\Sigma^*$, and we have that $L(M)=L(T)$ iff $L(M)=\Sigma^*$, so the reduction is correct.


Minimum Height Trees. Why does deleting leaves layer-by-layer give us the answer? Here is the problem I tried to solve. Finally, I gave up and found a solution which was correct. Here is it.

Here is the problem description:

  For a undirected graph with tree characteristics, we can choose any
  node as the root. The result graph is then a rooted tree. Among all
  possible rooted trees, those with minimum height are called minimum
  height trees (MHTs). Given such a graph, write a function to find all
  the MHTs and return a list of their root labels.

  The graph contains n nodes which are labeled from 0 to n - 1. You will
  be given the number n and a list of undirected edges (each edge is a
  pair of labels).

  You can assume that no duplicate edges will appear in edges. Since all
  edges are undirected, [0, 1] is the same as [1, 0] and thus will not
  appear together in edges.

Example 1 :

Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

    0
    |
    1
   / \
  2   3

Output: 1

Example 2 :

Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

 0  1  2
  \ | /
    3
    |
    4
    |
    5

Output: 3, 4

Here is the solution I tried to understand:

  The basic idea is "keep deleting leaves layer-by-layer, until reach
  the root."

  Specifically, first find all the leaves, then remove them. After
  removing, some nodes will become new leaves. So we can continue remove
  them. Eventually, there is only 1 or 2 nodes left. If there is only
  one node left, it is the root. If there are 2 nodes, either of them
  could be a possible root.

I'm not sure I understand it so I could explain it to somebody. Why does deleting leaves layer-by-layer give us the answer?

Let $T$ be a tree, and let $T'$ be the tree formed from $T$ by removing all leaves (vertices of degree 1). Assume that $T$ contains at least three vertices, so that $T'$ is not empty. This implies that every leaf $f \in T$ has a (unique) neighbor $p(f) \in T$ which is not a leaf.

For $v \in T$, denote by $h_v(T)$ the height of $T$ when rooted at $v$.
I claim that the following hold:

  For every vertex $v \in T'$, $$ h_v(T) = h_v(T') + 1. $$
  For every leaf $f \in T \setminus T'$, $$ h_f(T) = h_{p(f)}(T) + 1. $$

For the first claim, consider $T$ rooted at a non-leaf $v$. The height of $T$ is the length of the maximal root-to-leaf path. Every such path gets shortened by one in $T'$, implying that $h_v(T) = h_v(T') + 1$.

For the second claim, let $x$ be a leaf farthest away from $p(f)$. We can assuming that $x \neq f$ since $p(f)$ has at least two neighbors, and $f$ is at minimal distance from $p(f)$. Clearly $d(f,x) = d(p(f),x) + 1$, and so $h_f(T) \geq h_{p(f)}(T) + 1$. The other direction follows from the triangle inequality, which implies that $d(f,y) \leq d(p(f),y) + 1$ for all nodes $y$.

The algorithm. If $T$ contains one or two vertices, then clearly all vertices are centers (roots of minimum height trees). Otherwise, by the second claim, no leaf can be a center, and so by the first claim, the centers of $T$ are the same as the centers of $T'$. This suggests the following algorithm for computing the centers of $T$:

  While $T$ contains at least three vertices, remove all leaves of $T$.
  Once $T$ contains one or two vertices, return all vertices of $T$.

The correctness of the algorithm follows the reasoning stated above.


On complexity of the sieve, start crossing at the square of p - Part II Ok, this is a follow up question to this, about the Erathostenes Sieve.

If we look at this paper (page 3, footnotes), the author says:

  If we start crossing off at $p^2$ rather than $p$, the number of
  composites we cross off is $\frac{n}{p}−p+1$, but it makes no significant
  difference to our sum, because it only subtracts an irrelevant
  $O(n/ \log n)$ factor

The total cost counting crossings is:

$$\sum_{p\leq n}\bigl(\frac{n}{p}-p+1\bigr)=n\sum_{p\leq n}\frac{1}{p}-\sum_{p\leq n}p+\sum_{p\leq n}1$$

The first sum would give us the known $O(n\log\log n)$. But I don't see the second sum to be an "irrelevant $O(n/\log n)$", so how is that?

According to this post in math overflow an upper bound for the sum of the primes up to $n$ is:
$$\frac{n^2}{2\log n} + O\left(\frac{n^2}{\log^2 n}\right).$$

The sum only goes up to $\sqrt{n}$. You can see that in the big display at the bottom of page 3, where only the first $\pi(\sqrt{n})$ primes are considered. Substituting $\sqrt{n}$ for $n$ in your formula, we get $n/\log n + O(n/\log^2 n)$.


Refuting $H(L_1 \cap L_2) = H(L_1) \cap H(L_2)$ for homomorphisms I want to prove that $H(L_1 \cap L_2) = H(L_1) \cap H(L_2)$ is not always true.

If $L_1 = (ab)^*$ and $L_2 = (ba)^*$ with mapping $H(a) = 1$ and $H(b) = 1$, $H(\epsilon) = 2$, then $H(L_1 \cap L_2) = 2$ while $H(L_1) \cap H(L_2) = (11)^*$.

Is the above example correct to prove the above statement? Is it allowed to map two symbols to one same symbol?

Given two finite non-empty alphabets $\Sigma,\Delta$, a homomorphism is a mapping $h\colon \Sigma^* \to \Delta^*$ that satisfies the following two properties:

$h(\epsilon) = \epsilon$.
$h(xy) = h(x) h(y)$.

(Actually the first property follows from the second, since it implies that $h(\epsilon) = h(\epsilon \epsilon) = h(\epsilon) h(\epsilon)$, and so $h(\epsilon) = \epsilon$.)

It is not hard to show that $h$ is determined by its value on letters of $\Sigma$. Indeed, if $w = \sigma_1\ldots \sigma_n$, where $\sigma_1,\ldots,\sigma_n \in \Sigma$, then
$h(w) = h(\sigma_1) \ldots h(\sigma_n)$.
Conversely, if $h_0\colon \Sigma \to \Delta^*$, then the mapping $h(\sigma_1 \ldots \sigma_n) = h_0(\sigma_1) \ldots h_0(\sigma_n)$ defines a homomorphism. In formal language theory, one often identifies $h$ and $h_0$.


Equivalence of Horn formulas tractable? Assume I have two Horn formulas $\phi_1, \phi_2$.   Horn formulas are CNF formulas so that each clause has at most one unnegated literal.  For example:
$x_1 \wedge (\neg x_1 \vee \neg x_2 \vee x_3 )\wedge (x_3 \vee \neg x_4)$
I want to decide whether $\phi_1,\phi_2$ are logically equivalent, i.e., $\phi_1 \leftrightarrow \phi_2$.  Equivalently, I want to test whether  $F=(\phi_1 \vee \neg\phi_2)\wedge (\neg \phi_1 \vee \phi_2)$ is true for all assignments of $x_1,\dots,x_n$.
Is this problem tractable?

Yes, you can check equivalence in polynomial time (in fact, in quadratic time).
By similar logic to my answer to your previous question, it suffices to test satisfiability of $\phi_1 \land \neg c$ where $c$ ranges over the clauses of $\phi_2$.  If any of these are satisfiable, then $\phi_1,\phi_2$ are inequivalent.  Otherwise, if they're all unsatisfiable, and the same for $\phi_2 \land \neg c'$ where $c'$ ranges over all clauses of $\phi_1$, then $\phi_1,\phi_2$ are equivalent.
So, let's investigate how to test satisfiability of $\phi_1 \land \neg c$ where $c$ is a clause of $\phi_2$.  By assumption, $c$ is a Horn clause, so it has the form $\neg x_1 \lor \dots \lor \neg x_k \lor x_{k+1}$.  So, $\phi_1 \land \neg c$ has the form
$$\phi_1 \land x_1 \land \dots \land x_k \land \neg x_{k+1}.$$
This turns out to be a Horn formula, so you can its test satisfiability with the standard algorithm for testing satisfiability of Horn formula.  This takes linear time per clause, and there are linearly many clauses, so the total running time is quadratic.


What approaches are most useful when proving uncomputability of a given function? I'd like to understand what approaches should one adopt when deciding/proving that a given function F is uncomputable, by any Turing Machine (TM). The ones I've tried so far are as follows:

Reduction, from a known uncomputable function (such as $UC(\alpha)$, the uncomputable function as proved by Cantor's diagonalization argument in Chapter 1 of the book "Computational Complexity" by Sanjeev Arora and Boaz Barak, or $HALT(\alpha, x)$, which is nothing but the function in the Halting problem), to F. If such a reduction is possible, it can be argued that F is uncomputable as otherwise, the problems that are proved to be uncomputable would become be computable as well.
Proof by contradiction, in which one shows that if there is a TM M that computes F, it would lead to some sort of inconsistency in either the M's output, or the functions evaluated value.

I've applied (or rather, tried to apply) both the above techniques to some reductions, two of which I now state here (for illustrating the limitations of my approach):

If whenever a TM M accepts a string w $\in$ ${\{0,1\}}^*$, it also accepts $w^R$, the TM M is said to possess property R. ($w^R$ is the string obtained by reversing $w$ i.e. $(110)^R$ is $011$). Let $R: {\{0,1\}}^* \rightarrow \{0,1\}$ be defined as follows: $R(\alpha) = 1$ if $M_\alpha$ possesses property $R$, and $R(\alpha) = 0$ otherwise. Prove that $R$ is uncomputable.

Let $B: {\{0,1\}}^*$ x $ {\{0,1\}}^* \rightarrow \{0,1\}$ be defined as follows:
$B(\alpha,x) = 1$ if $M_\alpha$ writes a non-blank symbol on its output tape while computing input $x$, $B(\alpha,x) = 0$ otherwise. Prove that function $B$ is uncomputable.

For problem 1, I tried reducing the uncomputable function $UC$ to $R$, but the reason I couldn't quite complete the reduction is because $R$ is a property of the Turing Machine, not dependent on any input instance, where $UC$ depends on the output of a specific instance $M_\alpha(\alpha)$. Also, for both $R(\alpha)$ = 0 and $R(\alpha)$ = 1, it is possible that $M_\alpha$ can go on indefinitely for some inputs!
For problem 2, I tried reducing the function $HALT$ to $B$ (thus attempting to make a TM that computes $HALT(\alpha,x)$ by using the output of a TM $M_\beta$ that computes $B$). But here as in problem 1, it is possible that for both outputs of $M_\beta(\alpha,x)$, the TM $M_\alpha$ may not halt at all on input $x$!
So, I'm stumped here - I understand intuitively why these functions should be uncomputable (No TM should be able to predict whether another TM would halt/output anything on any possible input), I'm not quite able to derive a concrete proof! So, I really want to understand what approaches am I missing here, or are there holes in the current approaches that I've tried so far!
Note: For self-containment, I'm stating what are the functions UC and HALT here as well:
$UC: {\{0,1\}}^* \rightarrow \{0,1\}$:
$UC(\alpha) = 0$, when the Turing Machine represented by $\alpha$, $M_\alpha(\alpha)$ = 1
$UC(\alpha) = 1$, otherwise.
$HALT: {\{0,1\}}^*$ x $ {\{0,1\}}^* \rightarrow \{0,1\}$:
$HALT(\alpha, x) = 1$, when the Turing Machine represented by $\alpha$, $M_\alpha(\alpha)$ halts on input $x$.
$HALT(\alpha, x) = 0$, otherwise.

There are unfortunately as many techniques to prove functions uncomputable as there are to prove things in general, so there's no comprehensive doctrine for how you should approach this.

Note that the proof by reduction is just a special case of a proof by contradiction; assuming that the function is computable leads to a proof that some other problem is computable, which is a contradiction if there's already a proof that the other problem is not computable.

Your first problem can immediately be shown to be uncomputable due to Rice's Theorem. Briefly, Rice's Theorem states that for any non-trivial semantic property of TMs, detecting whether a given TM has the property is undecidable. Semantic means the property depends only on the language accepted by the TM (all TM's accepting the same language have the property, or all do not have the property, regardless of the specific implementation). Non-trivial simply means that there do exist languages that have the property, and languages that don't. So one way to solve this problem is to simply recognise that "for all strings w accepted by M, the reverse of w is also accepted by M" is a non-trivial semantic property and invoke Rice's Theorem. That may not be the most satisfying way to solve your problem if you're doing this to learn though (although the proof of Rice's Theorem is quite accessible; it's essentially a very generalised reduction from the Halting Problem).

For your reduction proofs, remember that you can "cheat". You are assuming the existence of a solver (call it P) for the problem you're trying to prove undecidable, and show that if you had that you could solve the Halting Problem. This means your reduction can presume that P "just works" by black-box magic, regardless of whether it seems possible. In particular, you do not need to care that the machines you construct to feed to P halt or do anything at all useful; only that they cause P to accept/reject in a way that can be used to solve the Halting Problem (or some other undecidable problem, but I found the Halting Problem to be very productive when I was doing these sorts of exercises at uni).

For example, one of my most enjoyable exercises in my undergraduate Theory of Computation course was proving that it as undecidable to detect whether a TM ever attempted to move the tape head left from the left-most cell of the tape (in the model we were using this would cause the tape head to simply remain in the left-most cell). I did this by showing that for an arbitrary TM M you could construct a machine that was in fact guaranteed not to halt on any input, but would attempt to move left from the left-most cell if-and-only-if M halted on the same input.

So what you need to do to prove $R$ uncomputable by reduction is find some undecidable problem P, such that you can transform an arbitrary instance of P's input into a TM that has the property R if-and-only-if the original input to P should be accepted (or rejected; the negative works too).

Similarly for problem 2, the obvious (to me) thing to do is to take an arbitrary TM M, and transform it into a machine M' that halts exactly when M writes something on the output tape, and is guaranteed not to halt if M never writes something on the output tape. Don't get hung up on whether M or M' halts; you're not planning to run either of them, only to run your hypothesized solver for problem 2 with M' as input.


Triangulation algorithm for an arbitary amount of points? I have multiple cameras that records the 2D pixel coordinates of the features each camera sees. After some searching, I came across this paper with a method to calculate the 3D coordinates of the features.

My problem is that the input of that algorithm requires a "feature tracks" for each feature. Meaning for each feature, there is a list of 2D coordinates corresponding to the camera that recorded them. In my case, I can have any number of features, how do I know which of the pixel coordinates belong to which feature? Is there a widely accepted algorithm for this? What would be the key word to search for the algorithm for this problem, would it be just a clustering algorithm I should look for?

Edit: In other words, I want to determine the 3D positions of a set of points by a set of 2D images taken by surrounding cameras. I do not know how many points I have.

In general, without additional information, you can't, due to scale ambiguity; for example, you can't tell the difference between a 1" bird that's 10' away, vs a 2" bird that's 20' away.  See, e.g., Using Headpose Vector and 2D Points to Compute Distances, calculting distance between a person and the object in the image, Is it possible to transfer a point from one camera to another, given n corresponding points?, find the actual size of an object from pixel coordinates.

If you don't have additional information but want to do the best you can, there are some heuristics; see Algorithms to convert 2D videos to 3D ones.

If you know the camera's instrinsic parameters, or the positions of the cameras, or other extra information, this is solvable  Relevant technology:

object detection lets you find the 2D coordinates of an object feature in a 2D image (you can apply this to each 2D image)
algorithms for the correspondence problem let you match these points between multiple 2D images, even without first doing object detection
camera calibration lets you figure out the camera parameters

See also Fundamental and essential matrices, value of intrinsic parameters, How to obtain the camera extrinsic matrix without using chessboard.


Linear time multiplication on RAM machine? This page says following:

  Integer Multiplication has an O-optimal linear-time algorithm on a RAM or SMM

Is this page fooling me or how can we multiply 2 numbers in linear time (bitwise complexity) using RAM?

The page is not fooling you. I'll refer you to the original paper, but accordingly they show the following:

  Theorem 6.1 There exists an SMM which performs integer-multiplication in linear time, i.e. there is a constant $c$ such that any $2N$-bit input is read as the concatenation of two $N$-bit integers $x$, $y$, and after at most $cN$ many steps their product $z=xy$ is output in binary representation.

It is a rather detailed paper which would be silly to write up all here. See below.

Schönhage, A. (1980). Storage Modification Machines. SIAM Journal on Computing, 9(3), 490-508. https://doi.org/10.1137/0209036


how to prove correctness of this BFS algorithm? Given an undirected connected graph, I wrote the following algorithm based on BFS. The algorithm detects wether this graph contains a cycle. If it contains a cycle then prints it. I'm pretty sure that it works just fine, but I don't really know how to prove its correctness properly.
Here is the pseudo-code:

Let s be the root
set parent[s]=s and parent[v]=null for all other v
create queue q ;
enqueue(s,q);
cycle=false;
while (!isEmpty(q) && !cycle) {
 u=front(q);
 for every edge (u,v) incident to u {
 if (parent[v]==null){
  parent[v]=u;
  enqueue(v);
 }
 else if (parent[u]!=v){
   cycle=true;
   keep the edge (u,v)
 }
dequeue(q);
if (cycle){
 print edge (u,v)
 while (parent[u]!=parent[v])&& (parent[v]!=u)&&(parent[u]!=v){
        print edge (u,parent[u]) and  edge (v,parent[v])
        u=parent[u];
        v=parent[v];
    }
    if (parent[u]==parent[v])
        print edge (u,parent[u]) and edge (v,parent[v])
    else
        print edge (u,v)
}
/**************************************************/
/**************************************************/

I've been working on the proof but i can't get through it.
 First i want to prove that if G contains a cycle then the algorithm does detect it.
My idea is the following:
Let s be the root of the bfs. We know that G contains a cycle, so there is a node such that there are two different paths from s to such a node. Let u be the first node that satisfies this.
Since that BFS visits all the nodes, and  explores each edge once, and also marks as visited all nodes that were visited, it will reach a step in which it is about to visit  the node u for the second time and then it finds the cycle.

Then I want to prove that in the afirmative case, the edges that it prints does forms a cycle, but i'm really stuck with this.

Assuming the graph has no cycles in it, the graph is hence a tree. Since in a tree, there is a unique path between two vertices, we will never encounter a visited vertex and hence our algorithm will not detect a cycle.

Now assuming there is at least one cycle in the graph. Consider the set $S$ of vertices, that belong to a cycle and have the least possible distance to $s$. Any two vertices in $S$ can not belong to the same cycle, since then they will form a cycle with a vertex with a smaller depth in the BFS-tree, which contradicts the assumption that they are closest possible to $s$. All these vertices belong to the same level of the BFS-tree since they have the same distance to $s$. The BFS-tree branches at each of them to at least two branches. Sice they all belong to cycles in the graph, there must exist an edge between two branches from the subtree rooted at one of them. This edge has its endpoints between two nodes on the same level in the tree, since else, one of them could have been visited by the other and get a smaller depth. When visiting this edge, our algorithm detects a cycle. The Cycle is hence this edge along with both paths in the BFS-tree from a vertex $v \in S$, to the endpoints of this edge. We output exactly these edges, where we start by printing this edge and backtrack on both branches until we reach back the vertex $v$ .


Do compilers of high programming languages always compile them directly to machine code? As an amateur Bash/JavaScript scripter who never wrote one sentence in Assembly, I ask:

Do compilers of high programming languages always compile them directly to machine code, or are there cases when a compiler of some high programming language compiles it to assembly (and then assembler will assemble input to machine code output)?

I've seen compilers that compile directly to object code.

I've seen compilers that compile to assembler code.

I've seen compilers that compile to byte code for a virtual machine.

I've seen compilers that compile to bit code which is intended to be further compiled to code for slightly different processors.

I've seen compilers that compile to a different language.

I've seen compilers for Javascript specifically that start interpreting code, then compile it very quickly to not very good code, then compile it carefully to reasonably good code, then compile it with a highly optimising compiler to very fast code, all depending how often some code is executed.


Putting as many items as possible with weight and size limit I am trying to design a greedy algorithm that has to take in multiple factors when making a greedy choice.

Any item has an item weight of Iw and item size of Is, these are both numerical values. Item sizes are originally translated from the values very small, small, medium, large, extra large to .1, .5, 1, 2, 2.5, respectively.

Imagine you are trying to optimize a box to have as many items in it as possible while being under a weight limit Tw and a size limit Ts. Also, the distribution of the size types (small, medium, etc) has to be a sort of bell curve where most of the items are medium, a smaller portion are small/large, and the least are extra large/very small.

I am familiar with creating a GA with only one variable, but am not sure how to do it with all of these factors.

Consider the following variant of subset sum problem:

  Given a set of $2n$ positive integers and a positive integer target $W$, is there a subset with size $n$, the sum of whose elements is $W$?

This problem is NP-hard by a reduction from one-in-three 3-SAT (almost the same reduction from 3SAT to the normal subset sum problem, except that we do not need the $s$ and $t$ values, and the target is always $111\ldots1$).

Now given an instance of this variant $x_1,\ldots,x_{2n}$ and $W$, denote $S=\sum_{i=1}^{2n}x_i$. We construct $2n$ items $1,\ldots,2n$, where Item $i$ has weight $x_i$ and size $S-x_i$, and construct a box with weight limit $W$ and size limit $nS-W$. We can see there is a subset with size $n$ the sum of whose elements is $W$ if and only if we can put $n$ items into the box.

As a result, your problem is NP-hard in general.

However, there are only five kinds of sizes in your specific problem, so you can try some brute force method. Suppose you choose $c_1$ items with very small size, $c_2$ items with small size, $c_3$ items with medium size, and $c_4$ items with large size. You can enumerate all possible values of $c_1,c_2,c_3,c_4$. For each possible values of $c_1,c_2,c_3,c_4$, you can then greedily pick items. This algorithm runs in $O(nn_1n_2n_3n_4)$ time where $n_1,n_2,n_3,n_4$ are the number of items with very small, small, medium, and large sizes respectively.


Is the given language finite or infinite? I have an idea regarding whether this language is finite or not, but for some reason I am still having some issues regarding exactly grasping what makes a language finite or infinite. I know that basically a language such as $0^*$ is obviously infinite since there can be any nonnegative number of $0$'s. However, is a language such as $(0 \cup 1)((0 \cup 1)^p)((0 \cup 1)^p)(0 \cup 1))$ also infinite? Technically, there can be any number of $0 \cup 1$ as it matters on the $p$ value, but I am also under the impression that there can only be so many values for $p$ and therefore the language is indeed finite. Can anyone explain as to why the language is either finite or infinite? I have read other examples but get a little confused when the language is in the gray area. Thanks!

(0 U 1)((0 U 1)^p)((0 U 1)^p)(0U1))  is not a language, but a regular expression. Moreover, to be well-defined, you must specify what $p$ is.

Is $p$ a specific value?  Then, this expression generates a finite number of words -> it generates a finite language.

But maybe you look at the language generated by the above expression for any p? then, there will be infinitely many generated words.

you need to tell us what is $p$ and what is the language under consideration.


Definition of "overhead" I am writing a paper on the invariance thesis introduced by Cees F. Slot and Peter van Emde Boas as;

  'Reasonable' machines can simulate each other within a polynomially bounded overhead in time and a constant-factor overhead in space.

The paper I am writing is in Croatian where I cannot find a properly convenient word like "overhead". Also, I am unable to find a strict Computer Science definition for the term.

Specifically, I have $Time(M)$ as the cost of reducing the $\lambda$-term $M$ to its normal form and a Turing machine able to simulate this reduction in $O((Time(M))^4)$. Therefore, I would like to say  "this TM can simulate $\lambda$-calculus with polynomial-time [overhead]" concisely as it is in English.

I would appreciate any suggestion in the form of literature references for the definition, advice on how to best define it myself or even synonyms of the word.

I doubt that “overhead” is a term. Here’s what we use in Russian papers:

оверхед — direct transliteration (for informal texts)
издержки — costs (of production)
Translations of “slowdown” (for time) and “blow-up” (for space).


Generate random weighted graphs representing a road network in order to solve a DARP problem I created a Python class, that can generate random graphs. I attribute a random number to every edge which represents the cost to travel over that edge.
My current solution for connecting vertices (and so create an edge) looks like this:

def connectVertices(self, vertexA, vertexB):
    vertexA.addNeighbour(vertexB)
    vertexB.addNeighbour(vertexA)
    weight = randint(1, self.maxDistance)
    self.adjacencyMatrix[vertexA.index][vertexB.index] = weight
    self.adjacencyMatrix[vertexB.index][vertexA.index] = weight

I insert a random integer in the adjacency matrix.
How ever this can creates graph which can not represent realistic road networks. Example:

Node A has a cost of 1 to B.

Node B has a cost of 1 to C.

Node C has a cost of 60 to A.

Since the cost when travelling over B between A and C is only 2, it does not make much sens to have a cost of 60 for the direct connection between A and C.

(I can not solve this problem by reducing the maximal cost, because I will need to generate large graphs.)

Are there algorithms that solve this problem ?

(Or :Is there maybe a python library which generates random weighted graphs which takes my problem in count ?)

One approach is to generate an arbitrary graph $G$ with arbitrary (positive) lengths on each edge.  Then, compute all-pairs shortest paths, and build a new fully-connected graph $G'$ where the length of the edge $u \to v$ in $G'$ is equal to the length of the shortest path from $u$ to $v$ in $G$.

The nice thing about this is that you're guaranteed by construction that $G'$ will satisfy the triangle inequality.

If you are happy with generating fully connected graphs, you can then output $G'$ as your random graph.  If you don't want the graphs to be fully connected, you could keep only some subset of the edges of $G'$ and delete the rest, then output the result.


Linear Temporal Logic with non-Boolean propositions (e.g. Integers)? LTL works with Boolean propositions.
People probably studied extensions to non-Boolean propositions...
Do you know a good starting reference?

(I am aware of STL, but it also seems to talk about clocks, is there a variant without clocks?)

Update: the question is not about "true, false, maybe" but rather about LTL where we can refer to integers, for example. Example: one might want to write G(i+1 == X(i)), meaning that value i should increment.

There has been some relatively recent work on constructive/intuitionistic variants or interpretations of LTL.

Kojima's and Igarashi's Constructive Linear-Time Temporal Logic: Proof Systems and Kripke Semantics is a decent place to start and references a bit of earlier work. In particular, Maier's Intuitionistic LTL and a New Characterization of Safety and Liveness. More recently, there was Jeffrey's LTL types FRP which showed that proofs of (constructive) LTL formulas corresponded to some FRP (Functional Reactive Programming) programs. Logics with tighter connections were formulated in later work, but this prompted some other work. One recent paper working in a linear logic setting shows a Curry-Howard correspondence between a LTL and event-driven programming: Paykin's, Krishnaswami's, and Zdancewic's The Essence of Event-Driven Programming.

At the level of logic, intuitionistic logic corresponds to having a Heyting algebra of truth values as opposed to a Boolean algebra. In a slightly different vein, Robust Linear Temporal Logic by Tabuada and Neider illustrates a many-valued (5-valued particularly) semantics for a LTL. They don't explore a proof theory except demonstrating that their rLTL can be translated to LTL.

While I didn't mention any, there is undoubtedly work in category theory that relates and would provide another perspective and categorical semantics. E.g. and related to the work above Jeltsch's Towards a Common Categorical Semantics for Linear-Time Temporal Logic and Functional Reactive Programming.


How to understand a equation related to speaker recognition? This question refers to the following paper:

Support Vector Machines for Speaker and Language Recognition, W. M. Campbell, J. P. Campbell, D. A. Reynolds, E. Singer, P. A. Torres-Carrasquillo, Computer speech and Language 20 (2006) 210-229.

I am trying to implement the algorithm in table 1 and table 2 in page 18. In step 6 of of table 1 they are calculating $b_z^i$ as a mean (or sum) of $b(z_i)$ and number of entries is $N_z$ which they claim to be the number of features.

The question is what is $N_z$ here. As I understand each feature set, which is of dimension $N_z$, has been used to create $b(z_i)$, so what this summation means? One can only sum over time dimension, which has nothing to do $N_z$. $N_z$ is kind of spatial dimension as one time frame of data is converted to features.

$N_z$ is number of frames in the utterance, it is exactly time dimension. Instead "number of features" they should say "number of feature vectors".


Big O proving for increasing functions Please help me to prove:

If $f, g ∶ \mathbb{N} \rightarrow \mathbb{N}$ and $f$ and $g$ are increasing $(f(n+1)>f(n),g(n+1)>g(n)$).

Need to prove $g=O(f)$ or $f=O(g)$.

Thanks

The claim is false. Let $f(n) = n^{1.75}$ and $g(n) = 2^{\lfloor \log_2 n \rfloor} n$, and note that both are increasing. When $n = 2^t$, we have $g(n) = n^2$, while when $n = 2^t-1$, we have $g(n) \approx n^{1.5}$. This shows that
$$
\liminf_{n\to\infty} \frac{f(n)}{g(n)} = 0, \quad
\limsup_{n\to\infty} \frac{f(n)}{g(n)} = \infty.
$$
In particular, it is not the case that $f = O(g)$, nor is it the case that $g = O(f)$.


Trying to understand interpretation and denotation in FOL I am going through the book "Knowledge Representation and Reasoning" by Brachman and Levesque.

So an interpretation $ F $ is defined as a pair $ \langle D,I \rangle $ mapping from a set of objects $ D$ called domain of the interpretation and $ I $ is a mapping called interpretation mapping from the non-logical symbols to functions and relations over $D$.

Then it has been written that   $ I $ will assign meaning to the predicate symbols as follows:

To every predicate symbol  P of arity $n$,  $I[P]$ is an n-ary relation, that is,
 $I[P]$  is contained in $ D \times D \times D \times \dots \times D$.

Now for denotation  it is written that  for an interpretation $ F = \langle D,I \rangle $ we can specify which elements of $ D $ are denoted by variable free term FOL.

And hence the notion of variable assignment  $ \mu $ has been introduced and the following two rules have been introduced:

Given an interpretation  $ F $ and a variable assignment  $ \mu $, the denotation of the term $ t $ is written as $ \|t\|_{F \mu} $ and defined as follows:

If $ x $ is a variable then $ \|x\|_{F \mu} =  \mu [x] $.
If $ t_1 ,\dots,t_n$ are terms and $ f $  is a function symbol of arity $ n $  then  $ \| f(t_1,\dots,t_n)\|_{F \mu} = G( d_1,\dots,d_n) $,
where $ G = I[f] $, and $ d_i =  \| t_i\| _{f \mu} $.

I am a bit confused about how to interpret the last two rules.

So the act of choosing elements from $ D $ to represent the arguments of the function symbol is represented by $ \mu $? Will it be right to say so?

How exactly are $ f $ and $ G $ related?

The output is evaluated by computing $ G $ for values which get substituted  in the argument which is represented in  $ d_i =  \| t_i\| _{f \mu} $ of the second rule.

But I could not understand how are the above two rules recursive?
What exactly should I conclude about the way $ I $, $ G $ , $f$ and $ \mu $ are related to each other and what exactly do they mean?
Is my understanding correct?

Attaching the screenshots from the book:

Consider the expression $+(x,\times(y,y))$, which is the FOL way to write $x+(y\cdot y)$. If I substitute $x=3$ and $y=5$ and do the arithmetic over the integers, what do I get? I need to evaluate the expression recursively.

In order to evaluate $+(x,\times(y,y))$, I need to evaluate $x$, to evaluate $\times(y,y)$, and then to combine them using the function $+$.

Evaluating $x$ is easy, since $x$ is just a variable. My assignment says that $x=3$, so the value of the expression $x$ is $3$.

Evaluating $\times(y,y)$ is more difficult. First I need to evaluate $y$ (twice) - as before, this is easy, and gives the result $5$. Now I need to combine the two values $5,5$ using the function $\times$. I have a large table which, for every pair of integers $a,b$, tells me what $\times(a,b)$ is. Looking at the table, I find out that $\times(5,5) = 25$.

Now that I have evaluated $x$ To $3$ and $\times(y,y)$ to $25$, I can finally look at the table for $+$ and deduce that $+(3,25) = 28$. So $28$ is the value of the entire expression.

The formal definitions you quote in your question attempt to capture the preceeding process in an abstract form. It's best if you work out the correspondence on your own.


Proof that languages are Turing-recognizable iff computably-enumerable A very small question on this proof, which I found as Theorem 3.21 in Sipser's, and in my lecture notes.
In the "only if" direction, we assume that a Turing machine $M$ recognizes some language $L$. We list all the strings in the input alphabet (in lexicographic order, say) as $s_1,s_2,s_3,\dots$
We then construct an enumerator $E$ that for each $i=1,2,3,\dots$ simply runs $M$ for $i$ steps on each input $s_1,s_2,s_3,\dots, s_i$; then it prints any $s_j$ which is accepted by $M$. $E$ is what we need.
Now, since I know that strings are finite, why should I run $M$ for $i$ steps on the first $i$ strings, when I could just run it on the $i$-th string? It feels like an unnecessary complication.
P.S. Another question was asked about this, but it addressed a different doubt:
Question for "Only if" part for the theorem "A language is Turing-recognizable iff some enumerator enumerates it."

If you run $M$ on the $i$-th string then it might never halt, so your algorithm will be stuck. The idea is that if $M$ does halt on the $i$-th string, say after $j$ steps, then we will see it once we get to the $\max(i,j)$-th string.


The Chomsky–Schützenberger representation theorem I've been trying to proof The Chomsky–Schützenberger, but I stuck on creating regular language from that theorem. I mean reagular language, which is intersected with Duck language. Could anyone give me hints how to construct proper language?

If you start with a pushdown automaton, then its instruction diagram can be interpreted as a finite state automaton. The instruction $(p,a,A,q,\alpha)$ — in state $p$ reading $a$ we pop $A$ go to state $q$ and push $\alpha$ — has an edge from $p$ to $q$ with label $(a,A,\alpha)$. This defines a regular language of possible instruction sequences (ignoring popping and pushing).

Now recode $(a,A,\alpha)$ by bracket symbols. $A$ is popped and is coded with the closing bracket $\bar A$, the symbols $\alpha$ are pushed and coded as opening brackets. If we code the instruction by the string $\bar A\alpha$ the (regular) language of instructions is a perfect matched bracket sequence (Dyck) if it is a legal sequence of popping and pushing. (Add $Z$ the initial stack symbol as first letter)

Now we forgot about the input letter $a$. This has to be inserted to the instruction, without losing the bracket structure. This is done by adding a virtual closing bracket $\bar a$ for each $a$. Thus, the finite state edge is now as follows: $(p,a\bar a \bar A\alpha,q)$.

Chomsky-Schutzerberger intersects with Dyck for the popping and pushing as I said, and retrieves the symbol $a$ using an homomorphism that deletes all other symbols.

It is also possible to start with a CF grammar in Greibach NF. Then the states totally disappear, the coding is similar, and the regular language is very simple: $S \{\; a\bar a \bar A \alpha^R \mid A\to \alpha \;\}^*$


Subset Sum: reduce special to general case Wikipedia states the subset sum problem as finding a subset of a given multiset of integers, whose sum is zero. Further it states that  it is equivalent to finding a subset with sum $s$ for any given $s$.

So I believe as they are equivalent, there must be a reduction in either side. The one from $s$ to zero is trivial by setting $s = 0$. But I had no luck finding a reduction from zero to $s$, i.e. given a set of integers $A$, construct a set of integers $B$ containing a subset with sum $s$ (for any $s$), if and only if there is as subset of $A$ with sum zero.

Can you give me some pointers?

You actually already have a reduction from special to general. By setting $s=0$, you are basically using the general algorithm to solve the special problem.

For the other way round (i.e. a reduction from general to special):

Suppose you are given a set $S = \{x_1, \dots, x_n\}$ and a number $K$ and you have to determine if there is some subset of $S$ which sums to $K$.

Now you want to solve this problem, given an algorithm for the case where you can determine if some subset sums to $0$.

Now if $x_i \gt 0$, we have an easy reduction: $S' = \{x_1, x_2, \dots, x_n, -K\}$.

$S'$ has a subset of sum $0$ iff $S$ has a subset of sum $K$.

The problem occurs when we can have $x_i \le 0$ for some of the $i$.

We can assume that $K \gt 0$ (why?).

Suppose the sum of the positive $x_i$ is $P$ and the negative $x_i$ is $N$.

Now construct a new set $S' = \{y_1, y_2 \dots, y_n\}$ such that

$y_i = x_i + M$ where $M = P + |N| + K$.

Each $y_i \gt 0$.

Now run the zero-subset-sum algorithm on the sets

$ S' \cup \{-(K+M)\}$

$ S' \cup \{-(K+2M)\}$

$ S' \cup \{-(K+3M)\}$

$\dots$

$ S' \cup \{-(K+nM)\}$

It is easy to show that if $S$ has a subset of sum $K$, then at least one of the above sets has subset of sum zero.

I will leave the proof of the other direction to you.


Is there any data structure that can't be represented or described inside a computer? We all know that, at least theoretically, there are several possible models of computation, varying in structure.

Strictly speaking, there are several (not just one) models of computation that exist or have been implemented in real life. Some machines (for example, amplifier circuits), though inexact, can be considered analog computers, but that's not what we commonly think of as 'computers', is it?

The machines that we usually think of as 'computers' are implementations of a computation model with discrete parts (discrete memory slots, discrete instructions and clock cycles, etc.) I've always wondered if there's some form of data that can't be represented/stored inside these discrete structures.

I've brought up this question in many websites, but I usually only find people who approach this issue with an incomplete picture of the problem, and without the required logical rigor.

I've been told that nothing with a continuous structure can be stored inside a computer, but from what I've gathered, this is not always true. Take the example of a circle (a geometrical shape). It's true that it has an infinite number of points in its circumference, but I can't say that they represent an infinite amount of information, since they can be derived from a very small number of parameters (center and radius) and a bunch of simple laws (algebra and symbolic math). My intuition tells me that this is the case for any geometrical shape, unless it has an infinite number of parameters, in which case I don't really know what to think.

Is my intuition accurate? Is this the case for any structure with a finite number of parameters? Are Von-Neumann/Harvard/... computers unfit to store certain data structure(s)? Has this been mathematically proven? Is the proof constructive? Are there any data structures that can't be stored in any known model of computation (or, for that matter, any model of computation)?

Note: I'm asking all of this from intuition. Even though I write code for a living, and harbor a great interest in Computer Science (and have a little knowledge of it through self-study), I am not a CS or Math graduate. From my limited, newbie perspective, I would think that this question belongs to the Theoretical Computer Science Stack Exchange, but I genuinely don't know if it's too basic, so I'll just play it safe for now.

There is a systematic way of computing datatype representations of mathematical objects: anything that can be described in higher-order intuitionistic logic has a representation as a datatype. Because we are talking about descriptions, and not about proofs of theorems, it does not even matter much that the logic is intuitionistic and not classical. Pretty much any mathematical object you encounter in practice can be represented. Some examples that can be done easily: real numbers, the space of square-integrable measurable functions $L^2[0,1]$ and other infinite-dimensional Hilbert spaces, Banach spaces, the space of compact subspaces of $\mathbb{R}^n$, etc.

Roughly, the process goes as follows. Take you favorite model of computation and build a realizability topos from it. Then take your description of the mathematical object and interpret it in the topos. It will tell you how to represent data, because the topos is built in such a way that every object is equipped with a data representation, and every statement is witnessed by a program. In most cases we do not actually need the entire topos, the much smaller and easier subcategory of modest sets suffices.

There is an important caveat: in intuitionistic logic an object may have several inequivalent descriptions which are classically equivalent. These will lead to different data representations (and this is good, as it means we can express more computational distinctions).

The process of interpretation is automatic. To make that point, Chris Stone and I wrote a tool rz which does this. You can feed it the definition of real numbers, or an infinitely dimensional Banach space, or anything like that, and it spits out a specification. (The software experienced bitrot, I should update it, but the paper has many examples.)

Let me also address the common misconception that "non-computable objects cannot be represented in a computer". There is a difference between non-computable and non-representable. For example, the digits of a real number may be written down on the tape of a Turing machine. It doesn't matter whether the real number in question is computable, it can be stored on the tape. The question of "who stored it onto the tape" is a separate concern. You may object that the tape is not infinite. Actually, it is infinite in most textbooks. But people like to press this point, to which I have two responses.

First, we may replace the infinite tape with a potentially infinite tape, i.e., think of the real number as a process which emits digits on demand. This can be some sort of a physical process, say a quantum-mechanics experiment that produces bits by making measurements. Would anyone like to presuppose that the real number so obtained is computable? In this case they have to produce some evidence for such a claim. Good luck with that. The moral here is that it is largely irrelevant whether "all reals in this universe are computable". What is important is that we can represent whatever reals there are, and that would by definition be all of them.

Second, we can study models of computation that have no infinite components, for example the $\lambda$-calculus. In such models infinite data, say a real number, is represented by a program that produces the data, say the digits of the real number. So obviously only computable reals may be represented. But this doesn't matter! The corresponding realizability topos still thinks there are uncountably many reals, and is a self-consistent world of mathematics.

For further explanation on how to represent uncountable data, I refer to my blog post Representations of uncomputable and uncountable sets. It's a bit of a rant, actually.

The takeaway is the motto from my PhD thesis:

  Data are continuous, programs are computable.


Algorithm for wait-for graph During the process of deadlock detection, the wait-for graph can be obtained from the resource-allocation graph. To detect whether there is a deadlock using the wait-for graph, can topological sort be used?

By making a slight modification, i.e., instead of removing the source as done in usual topological sort, we can remove the node (here, node represents a process) which does not point to another node first and proceed in this manner. As soon as the algorithm detects that it cannot proceed further and there are still nodes existing in the wait-for graph, it can be concluded as deadlock.

Other tags are topological-sort and deadlock-detection.

Hint: There is deadlock in the wait-for graph if the graph has directed cycles (why?). Perhaps topological sort is useful for detecting these.


Why sequential access is faster than random access? I am currently getting really confused of two documents I read:

one is from Wikipedia that states:

  The opposite is sequential access, where a remote element takes longer time to access.

and this Microsoft's document says:

  Accessing data sequentially is much faster than accessing it randomly because of the way in which the disk hardware works.

I found the two documents contradicting with each other. Maybe they refer to different things. But I would like to know why sequential access is much faster than random access (I don't understand the Microsoft document as I don't understand the concept of seek operation)

They are talking about two different things.

One is about a medium that supports sequential access versus random access. The other is about reading data that is arranged sequentially or spread out requiring random access for each chunk.

Imagine a deck of cards. If you had it in a stack, and I said to get the 39th card in the stack, you could take cards off the stack one at a time until you got to the 39th card. You need to skip past 38 cards to get to the 39th. Therefore, getting the 39th card is harder than getting the 3rd. This is like a sequential access medium.

Alternatively, let's say you spread out the cards around you in a circle in order. Now it takes just as much time for you to get any card as any other since you just reach in the appropriate direction. This is like a random access medium.

Sticking with the circle, let's say I asked for cards 1, 17, and 42. You can do this pretty quickly, but if I had asked for cards 1, 2, and 3, you could probably do it much more quickly since once you got the first card, you could just scoop up the next two cards all at once. This is the difference between reading sequentially organized data versus randomly organized data. Sequentially reading sequentially organized data is very easy with the stack organization of the deck too once you find the first card.

A seek operation is moving the reading head of the hard drive to a particular location. Once there the hard drive can (very) quickly read a sequential run of data. If all your data is all in a sequential run, then it can be read very quickly once the hard drive seeks to the beginning. If the data is spread all over the hard drive, then it has to seek after each portion, and while it's seeking it's not reading so you are wasting time.

In practice, hard drives (including solid state drives which don't have to "seek") assume that you probably want a bunch of data when you tell it to seek somewhere, so they just read in a bunch of data even if you haven't (yet) asked for it in the hope that you will ask for it in the near future. Other than needing space to store this pre-fetched data, there's no reason not to do this as it's essentially free. The read head is already there. This makes sequentially organized data perform even better and randomly organized data even more wasteful. Similar to this is the fact that there is usually a minimum "block" size of data that you can read and write at a time, and so you are going to get at least a block's worth of data no matter what. Sequentially organized data will fully utilize these blocks (until the last one perhaps). Randomly organized data may or may not depending on whether the "chunks" match some multiple of the block size.


$O(n \log n)$ algorithm to find next interval that is also disjoint Say there are some intervals $\{1, \ldots ,n\}$ with starting times and ending times, and they're sorted in order of starting time from first to last in an array intervals$[]$. Now I want create an array next$[]$ such that next$[i]$ is the interval after interval $i$ whose starting time is as close to $i$'s ending time as possible. The notes I'm reading says it is possible to do this in $n \log n$, but I don't see how. The fastest algorithm I have come up with would iterate over intervals$[]$, and in each step "look ahead" until it finds a starting time after $i$'s ending time. The worst possible scenario would be when all the intervals are bunched together (none are disjoint), in which case you would have to iterate over all of $i + 1, i + 2, \ldots ,n$ at each step $i$. This would be $O(n^2)$ because the total number of checks would be $0 + 1 + \cdots + n-1$ since we make $n-1$ for first the first number, $n-2$ for the second, etc. Am I missing a way to cut it down to $O(n \log n)$?

For interval i, you can binary search end[i] among the sorted array begin[]. Each binary search takes log n time.


Does deterministic imply algorithmic? I'm not exactly sure whether this question belongs to this SE or not, but it doesn't seem to fit elsewhere.

Say a process behaves in a deterministic fashion (that is, it gives the same output when an input is entered over and over again), then can we build it as an algorithm?; if not, can you think of a counter-example?, that is, a deterministic process which can't be modeled as an algorithm.

An algorithm must have a finite description, whereas a deterministic process according to your definition can use an infinite lookup table. For example there is a deterministic process that solves the halting problem for Turing machines, but there is no such algorithm.


How to guess the value of $j$ at the end of the loop? for ( i = n , j = 0 ; i > 0 ; i = i / 2 , j = j + i ) ;

All variables are integers.(i.e. if decimal values occur, consider their floor value)

Let $\text{val}(j)$ denote the value of $j$, after the termination of the loop. Which of the following is true?

(A)$\quad \text{val(j)} = \Theta(\log(n)) $
(B)$\quad \text{val(j)} = \Theta(\sqrt n) $
(C)$\quad \text{val(j)} = \Theta(n) $
(D)$\quad \text{val(j)} = \Theta(\log\log n) $

Please explain, is there any easy way to guess the value of $j$?

If you unfold the loop you get:

$$\text{val}( j)=n+n/2+n/4+ n/8 \ldots$$

In total you have $\log n$ terms.
See this post, how to evaluate the sum.


How does the halting theorem interact with the recursion theorem? Recursion theorem (paraphrasing Sipser, Introduction to the Theory of Computation):

Let T be a program that computes a function t: N x N --> N. There is a program R that computes a function r: N --> N, where for every w,

        t(<R>, w) = r(w)

The proof is by construction. The program R thus constructed computes the same thing as program T with one input fixed at <R>. But what if the right side does not compute anything? In that event we can reason as follows:

T(<R>, w) halts  <-->  R(w) halts

and by modus tollens

T(<R>, w)  does not halt  <-->  R(w) does not halt

In particular we have

R(w) halts  --> T(<R>, w) halts
T(<R>, w)  does not halt  --> R(w) does not halt

The transposition is based on the table below

T(<R>, w) halts__________________R(w) halts

   T                         T
   F                         F

But what if the value in the right column is unknown and unknowable?

T(<R>, w) halts__________________R(w) halts

   T                         T
   ?                     unknowable
   F                         F

We know that there is no universal halting decider, so the value in the right column may be unknowable to a given decider. So what if the decider concludes that T(<R>,w) does not halt? Is there anything wrong with the table below?

T(<R>, w) halts__________________R(w) halts

   T                         T
   F                     unknowable
   F                         F

In particular is there any compelling reason that if the value in the left column is F that the value in right column must also be F, i.e. that it cannot remain unknowable? It seems to me that if T(<R>, w) does not halt then it does not imply anything.

Is it possible for a decider to say [for some T] that T(<R>, w) does NOT halt yet remain agnostic about R(w) halting??

The recursion theorem states that for every two-place partially computable function $t$ there is a program $R$ which computes a partial function $r$ satisfying
$$ r(w) = t(\langle R \rangle, w) $$
for all $w$. The function $t$ is given by a program that doesn't necessarily halt, and so we can think of it as a function from $\mathbb{N}^2$ to $\mathbb{N} \cup \{ \bot \}$, where $\bot$ means that the program doesn't halt. We call such a function a partial function, since a different way of specifying such a function is as a function from some subset $S \subseteq \mathbb{N}^2$ to $\mathbb{N}$; the function doesn't halt on inputs outside $S$.

The equality $r(w) = t(\langle R \rangle, w)$ is an equality of partial functions: the functions have the same domain (or the same set of inputs on which the output is a natural number rather than $\bot$), and they agree on their domain.


What's wrong here, or, is CNF to DNF conversion in o(exp(n))? I've been thinking about conversion from CNF to DNF. Assume a "worst case" CNF formula with $k$ disjunctions, each containing exactly $l$ elements and no variable is used twice. Example with $k=3$ and $l=2$:

$(a \lor b) \land (c \lor d) \land (e \lor f)$

Obviously, this will result in a DNF of length $k^l$, as all possible conjunction combinations need to be listed and due to all variables being unique, nothing will vanish.
Given that, computation time complexity will at least be exponential and lay in $o(k^l)$.

Now, two questions:

Can we say that time complexity will also be within $o(exp(n))$, where n denotes formula length?
If 1. is true, wouldn't that prove that this problem isn't part of $P$, and, given CNF -> DNF is NP-hard NP-complete, that $P \neq NP$?
Edit: I'm aware CNF -> DNF is NP-hard, but is it NP-complete too?

Can we say that time complexity will also be within $o(exp(n))$, where $n$ denotes formula length?

No, because no one has proven that distribution of terms is the only way to convert CNF to DNF.  Obviously simple distribution of terms produces an exponential blowup in the formula size, but there may be other ways to compress the formula so that the same truth table is produced.  We already known that given a truth table clever algorithms can produce smaller formulas than full disjunction over the distributed terms.

  If 1. is true, wouldn't that prove that this problem isn't part of $P$, and, given CNF -> DNF is NP-hard NP-complete, that $P \neq NP$?

No.  If CNF to DNF conversion could be accomplished in polynomial time, its output would necessarily fit into polynomial space.  Therefore you could scan this output in polynomial time and decide satisfiability.  Thus P would be equivalent to NP.  But if CNF to DNF conversion takes exponential time it says nothing about whether some other algorithm could efficiently solve SAT and bring P and NP together.


Proving there is no polynomial algorithm for independent set I need some guidance in an assignment I'm doing.

I'm at complete loss, he says the the MAXIMUM INDEPENDENT SET problem is NP-hard and then asks me to prove that there is no polynomial time for the same algorithm and it also guarantees that some inequality holds, which I also don't understand, since $A(G)$ returns the size of a maximal independent set in $G$ and $OBT(G)$ returns the size of an independent set of maximal size for $G$ but isn't the case that a graph could have multiple maximal independent sets? Let's assume that it returns the largest one which reduces the epression to $0 \le K$ which should always holds since $K$ is a natural number?

As for the hint given, I don't see how we can use $H$ if I understand it correctly, it says split $G$ into disjoint sets. Also it says for every instance $G$ which is confusing me.

When I asked the professor she was very reluctant to help me, so please any guidance is appreciated.

The full question:   .

Suppose that there exists an integer $K$ and a polynomial time algorithm $A$ which, when run on a graph $G$, outputs a value $A(G)$ which satisfies
$$
 |A(G) - \alpha(G)| \leq K,
$$
where $\alpha(G)$ is the maximum size of an independent set in $G$.

We will show that $A$ can be used to determine $\alpha(G)$ in polynomial time, which contradicts the assumption $\mathsf{P} \neq \mathsf{NP}$.

Given a graph $G$, let $H$ consist of $2K+1$ disjoint copies of $G$; note that $\alpha(H) = (2K+1) \alpha(G)$. Run $A$ on $H$ to get a value $A(H)$ which satisfies
$$
 |A(H) - \alpha(H)| \leq K \Longrightarrow |A(H) - (2K+1) \alpha(G)| \leq K \Longrightarrow \\
 (2K+1)\alpha(G) \in \{A(H)-K,\ldots,A(H)+K\}.
$$
The set on the right contains $2K+1$ values, exactly one of which is a multiple of $2K+1$, hence we can determine $\alpha(G)$ given $A(H)$.


Why is the consensus number for test-and-set, 2? According to Wikipedia,

  The test-and-set operation can solve the wait-free consensus problem for no more than two concurrent processes.

Why can't it solve the problem for more than two processes?

Just to make sure we are on the same page, first let us consider these three definitions:

Definition. Test-and-set is a read-modify-write instruction on some binary register (let's just say that 0 and 1 are possible values) where a thread obtains the old value and writes 1.

Definition. Consensus is reached between $n$ threads iff all $n$ threads decide on the same value (the consistency requirement) and all threads decide on a value that was actually proposed by one of the threads (the validity requirement).

Defintion. A consensus protocol is wait-free iff every method call finishes in a finite number of steps.

Now follow two proof sketches.

Claim 1. The consensus number of test-and-set is at least 2. Proof. Suppose that we have two threads 0 and 1 that need to reach consensus. We could do this by letting each thread follow the consensus protocol below:

Write your proposed value to $A[t]$, where $t$ is the thread id and $A$ is an array of size 2.
Perform the test-and-set instruction on some register $R$, with $R$ initialised to 0.
If the return value is 0, you were first: return $A[t]$. Otherwise, you were second: return $A[|t-1|]$.

You can verify yourself that consensus and wait-freeness are satisfied. $\square$

(For the next proof, I will nest some proofs and definitions because I think it will make it easier to follow.)

Claim 2. The consensus number of test-and-set is at most 2. Proof. By contradiction. Suppose we have three threads $A$, $B$ and $C$ that wish to decide on values $a$, $b$ and $c$, respectively, and that we have some valid wait-free consensus protocol that is implemented using test-and-set (and atomic reads and writes).

We can visualise the consensus process as a directed tree, where:

The root is the state where none of the threads have 'made a move';
The left child of a node represents the state that results after a move by $A$, the middle child represents the state that results after a move by $B$, and the right child represents the state that results after a move by $C$;
A leaf node represents a state in which all threads have finished. Associated with a leaf node is a value $a$, $b$, or $c$, where the value depends on which value was decided on for that particular execution.

Definition. Let a state be multivalent if the outcome of the consensus process is not yet determined. In other words, not all possible interleavings of the remaining moves lead to the same result. Let a state be univalent when the outcome of the consensus process is determined.

The root is multivalent. Proof. If only one thread $X$ is active and the other threads lie dormant forever, then $X$ will finish in a finite number of steps (guaranteed by the wait-freeness assumption) and it will decide $x$ (for it has only access to this value and its decision will satisfy the consensus validity requirement). So for our situation, $a$, $b$ and $c$ are all possible outcomes. $\square$

Definition. Let a critical state be a state which is multivalent, with the additional property that a move by $A$ will determine $a$, and a move by $B$ will determine $b$.

There exists a critical state. Proof. From above we know that we start in a multivalent state. Let $C$ make no move at all. As long as either $A$ or $B$ does not force the tree into a univalent state, let it make a move. Wait-freeness guarantees that the tree is finite, so at some point a critical state must be encountered. $\square$

Now consider a scenario where we are in a critical state. There are at least two possibilities:

1) $A$ makes its move (thereby determining $a$) and halts. $B$ then makes its move and halts. Next $C$ runs until it finishes, eventually deciding $a$.

2) $B$ makes its move (thereby determining $b$) and halts. Next $C$ runs until it finishes, eventually deciding $b$. $A$ does not make a move.

Since atomic reads and writes have consensus number 1, $A$ and $B$'s moves had to be test-and-set instructions on the same register (if the registers are different, then $C$ would not be able to tell the order in which $A$ and $B$'s moves happened). From $C$'s perspective, then, scenarios 1 and 2 are indistinguishable, so we must have that $C$ decides both $a$ and $b$. This is impossible. $\square$

That the test-and-set instruction has consensus number 2 follows from both Claims 1 and 2.


Maximum flow in a graph, and conservation of flow The requirement for the conservation of flow in a flow network is, as I see it in the MIT lectures on Algorithms, that $\sum_{v\in V}f(u,v)=0$ for every $u\not\in \{s,t\}$ where $s,t$ are the source and sink respectively.  I think I get the intuitive idea expressed here, that there should be no accumulation or net loss in any vertex.  However, it seems to me this expression actually says "The follow out of u is always 0".  Am I confused or is the correct expression, $\forall u\not\in \{s,t\}$

$$\sum_{v\in V}f(u,v)=\sum_{w\in V}f(w,u) $$

Or is it there something about the requirement that $f(u,v)=-f(v,u)$ that takes care of this automatically?  And maybe somehow in the summation we don't pay too much attention to the placement of the $u$ in the formula?

The definition given in the lectures you've seen is the usual, which can be seen as the conservation of flow through a node, as it follows that flow exiting the node is equal to the flow entering the node. The expression doesn't only consider outgoing flow, as the equation $f(u,v) = -f(v,u)$ means that incoming flow can be described as 'negative' outgoing flow.

Your expression currently just says 'the flow through $u$ is the flow through $u$', which doesn't restrict the flow at all.

A better version of the expression you try to pose is the following:

$\begin{equation}
\sum_{v\in V_{in}(u)} f(v,u) = \sum_{v\in V_{out}(u)} f(u,v),
\end{equation}$

where $V_{in}(u)$ is the set of nodes $v$ that such that $v\rightarrow u$ is an edge and $V_{out}(u)$ the set of nodes $v$ such that $u\rightarrow v$ is an edge.

It can be easily shown that this equation is equivalent to $\sum_{v\in V} f(u,v) = 0$ when $f(u,v)= -f(v,u)$ for all $u,v\in V$.


Number of parenthesizations and Catalan numbers I read in CLRS that the number of possible parenthesizations for a product of $n$ matrices is given by the recursive formula:

$$
    P(n)=
\begin{cases}
    1 & \text{if } n = 1,\\
    \sum^{n-1}_{k=1} P(k)P(n-k)              & \text{if } n \ge2.
\end{cases}
$$

This comes from the following two facts:

For $n=1$ there is only only item, so only one way to fully parenthesize a matrix product.
For $n\geq2$ a fully parenthesized matrix product is the product of two fully parenthesized subproducts, and the split between the two subproducts may occur between the $k$th and $(k+1)$st matrices for any $k=1,2,\ldots, n-1$.

So far so good.

Now, I know that $\sum^{n-1}_{k=1} P(k)P(n-k)$ has a strong relationship with Catalan numbers, and I'm hoping to establish that relationship with precision.

For background, Catalan numbers are defined as a sequence of the following form:

$${\displaystyle C_{0}=1\quad {\text{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\text{for }}n\geq 0,}$$

where a term in the sequence is also known to follow the alternative expression: $C_n={\tfrac {1}{n+1}}{\tbinom {2n}{n}}.$

Expressing the original recurrence in terms of Catalan numbers shouldn't be hard, but the differences in summation and sequence indices are making it difficult for me. What's a good way to rearrange these types of Eqs. to re-express e.g. the first Eq. as a function of the second one?

Define function $Q:\mathbb N\to\mathbb N$  such that $Q(n)=P(n+1)$ for all $n\ge 0$. Or, what is equivalent, $P(n)=Q(n-1)$ for all $n\ge 1$.

We have $$Q(0)= P(0+1)=P(1)=1.\quad\quad\quad\quad\quad\quad\quad\quad$$

Also, for $n\ge0$,
$$\begin{aligned}
  Q(n+1)&=P(n+2)\\
   &=\sum^{(n+2)-1}_{k=1} P(k)P((n+2)-k)\\
   &=\sum^{n+1}_{k=1} Q(k-1)Q(n+1-k)\\
   &\stackrel{k=i+1}{=\!=\!=\!=}\sum^{n}_{i=0} Q((i+1)-1)Q(n+1-(i+1))\\
   &=\sum^{n}_{i=0} Q(i)Q(n-i).\\
\end{aligned}$$

We see that $Q(\cdot)$ and the Catalan numbers $C(\cdot)$ share the same initial condition and the same recurrence relation. So, we have, for all $n\ge0$,
$$ Q(n) = C(n).$$
So, for all $n\ge 1,$
$$P(n)=Q(n-1)=C(n-1)={\tfrac {1}{n}}{\tbinom {2(n-1)}{n-1}}$$

Exercise. Define function $D$ such that $D(n)=C(n-1)$ for $n\ge1$. Show that $D(n)=P(n)$ for $n\ge1$, assuming that you have not seen the deduction above.


Big O notation for Average case in Linear search Average case complexity for linear search is (n+1)/2 i.e, half the size of input n.
The average case efficiency of an algorithm can be obtained by finding the average number of comparisons as given below:
Minimum number of comparisons = 1
Maximum number of comparisons = n
If the element not found then maximum number of comparison = n
Therefore, average number of comparisons = (n + 1)/2
Hence the average case efficiency will be expressed as O (n).(I've seen this in many websites...)
Here, how can we say it as O(n) in big O notation or terminology. It should be O(n/2), I suppose. Kindly clarify me

Let us recall the definition of big-O notation.
If a function g(n) = O(f(n)), this implies that there exists two positive constants n0 and c, such that for all n > n0, 0 ≤ g(n) ≤ c f(n)
Hence, it follows that O(n) is equivalent to O(n/2), as n is just n/2 multiplied by a constant factor, which in this case is 2.


greedy algorithms - minimizing total payment The question:

I want to buy $n$ books. In the book store there's a big sale according to which, if you buy three books, then the cheapest book in any triplet costs only 20% of its full price.  Let $c_1, c_2, …, c_n$ be the full price of the books you want to buy.

Suggest an algorithm for minimizing your total payment. Prove its optimality and analyze its time complexity.

My algorithm:

sort the prices of the books from big to small, such that $c_1 \ge c_2 \ge ... \ge c_n $ (change the locations of the books).
each book $c_i$ if $i \% 3 = 0 $ then change its price to $c_i=0.2\cdot c_i$
return the sum of all books $\sum_{i=1}^nc_i$

Now, I'm having trouble proving that this is the optimal solution.
I want to prove that if $i\%3=0$ for $c_i$, then I have a discount on this book.

I'm having a hard time formalizing the Greedy choice property. Given an optimal solution, what happens if $c_i$ such that $i\%3=0$ is not in the optimal solution? (doesn't have a discount)?

This answer is a hint.

Assume an optimal solution exists.  Order its choices so that they agree with your algorithm's choices for as long as possible; the order after this is unimportant.  If all of them agree, then your algo picked an optimal solution, so you're done!  If not, then at look at the first group of 3 where they disagreed.  Even though you don't know exactly what an optimal solution is, you know that one exists, and you can make changes to it -- e.g. swapping some books in its ordering -- to produce a new solution.

Can you think of a way to change it in such a way that (a) it now agrees with your algo for 1 more group of 3 and (b) its score didn't get worse?  If so, then clearly you could repeat this step until...  What happens?