Standard information-theoretic lower bound? There should be a simple argument, but I'm struggling to see it.

Suppose Alice has a string $x \in \{0, 1\}^n$ and sends a message $s = s(x)$ to Bob. And suppose that given $s$, Bob can reconstruct each bit of $x$ with probability $2/3$ (say). (Note that this is weaker than the claim "with probability $2/3$, Bob can recover the entire string $x$." A clean proof of this case would be appreciated too.)

Then we should be able to conclude $|s| = \Omega(n)$, and this seems obvious, but can someone formalize this for me?

I understand your question this way:

  Assume Alice has some $X\in\{0,1\}^n$. Alice encodes (compresses) $X$ into $s = s(X)$, where $|s|\le n$. Bob decodes $s$ to obtain $X'=dec(s)$.
  Show that unless $|s|=\Omega(n)$ it cannot hold that Hamming$(X,X') < n/3$.

If this is what you meant, then this follows from the fact that most strings cannot be compressed. Assume that for any $X$, $|s(X)|=o(n)$. Note that there are at most $2^{|s|}\ll 2^n$ such strings. More accurately, $2^{|s|} / 2^n \to_{n\to\infty} 0$.

Then, for each possible $s$ construct $dec(s)$ and define $Y_s$ to be a Hamming ball of radius $n/3$ centered at $dec(s)$. Verify that $|Y_s| = \sum_{d=0}^{n/3}\binom{n}{d} < 2^{n\cdot h(1/3)}$, with $h(\cdot)$ the binary entropy function.
Thus $\left|\bigcup_s |Y_s|\right| \le 2^{o(n)}2^{0.92n} \ll 2^n$. This means that there exists a string $X$ not covered by the $Y_s$ for any $s$, i.e., not within a Hamming-distance of $n/3$ from any of the decoding of any $s$.

 If this is not what you meant, you will have to formulate your statement in a proper way. For instance, you say "with probability 2/3", but there is no probability space defined in your statement, etc.


Storage cost of a suffix array MY question is about storage complexity of a suffix array. According to textbooks it is O(n) with an exact cost that approximates 4n. However a suffix array of a string of length n is an n-size integer array, along an index that maps each substring to the appropriate position of the array. This index has size $1+2+..+n= O(n^2)$. So why the storage cost it is said to be $O(n)$ at the textbooks?

You don't store the actual suffixes in the array. You only store indices, $n$ of them. Each index takes $O(1)$ space in the RAM model (which is what the textbook is using to count space), so in total the space consumption is $O(n)$. The number of bits used is $\Theta(n\log n)$.


CLRS: Asked to prove a result and then told to give a counter example I am reading Introduction to Algorithms, and I am stuck at this execercise in the Appendix:

  Argue for any integers $n \ge 0$, $j \ge 0$, $k \ge 0$ and $j + k \le n$.

  $${n \choose j + k} \le {n \choose j} {n-j \choose k}$$

  Privde both an algebraic proof and an argument based on a method for
  choosing $j+ k$ items out of $n$. Give an example in which equality
  does not hold.

Here I am asked to prove it and then give a counter example. I can't seem to find any problem with the proof or the couter example, $n=4$, $j=k=1$. Puzzeled!

Here is a proof:

  First, let's establish that, $j!k!\le (j+k)!$. Both sides have the
  same number of terms, but the right side has $k$ terms more -
  $(j+1)(j+2)\ldots(j+k)$ - that are greeter than the corresponding
  terms on the left side $1\cdot2\cdot\ldots\cdot k$.

  Thus:

  $${n \choose j}{n-j \choose k}=\frac{n!}{j!(n-j)!}\frac{(n-j)!}{k!(n-j-k)!}=\frac{n!}{j!k!(n-j-k)!}\ge\frac{n!}{(j+k)!(n-j-k)!}={n \choose j+k}$$

You aren't asked to give a counterexample to the proof, as that would be impossible.

Instead, they're asking for an example where equality does not hold, that is, the left hand side is strictly smaller than the right hand side. That's not a counterexample since the theorem states less or equal.


Do reductions form a total binary relation? I was wondering if the following property holds true:

$$\forall A, B \subseteq \Sigma^* : A \leq_m B \lor B \leq_m A$$

And the same for Turing reductions

$$\forall A, B \subseteq \Sigma^* : A \leq_T B \lor B \leq_T A$$

If $A \not \preceq B$ and $B \not \preceq A$ then we say that $A,B$ are incomparable with respect to the order $\preceq$.

As mentioned in the comments, the halting problem and its complement are incomparable with respect to many-one reductions; indeed, one of the reasons behind considering many-one reductions is that they make such distinctions possible.

One can also construct sets $A,B$ which are incomparable with respect to Turing reductions. These are known as incomparable Turing degrees. One way to do it is using diagonalization, as we explain below.

It will be somewhat less confusing to construct Boolean functions $\alpha,\beta$ instead of sets $A,B$. The construction will proceed in infinitely many steps. At step $i$ we will have finite partial functions $\alpha_i,\beta_i$, which extend the functions $\alpha_{i-1},\beta_{i-1}$ from the previous step. Initially, $\alpha_0 = \beta_0$.

At step $2i$, we make sure that the $i$th program cannot compute $\alpha$ given $\beta$. We start by picking the minimal input $x$ not in the support of $\alpha_i$. For each complete function $\beta'$ extending $\beta_i$, we run program $i$ on input $x$ with $\beta'$ as oracle. If none of these runs ever terminates, we set $\alpha_{i+1}(x)$ arbitrarily, and continue to the next step. Otherwise, suppose that program $i$ terminates on input $x$ with $\beta'$ as oracle. Since the program terminates, it only accesses the oracle at a finite number of places. We extend $\beta_i$ to $\beta_{i+1}$ so that it agrees with $\beta'$ on this finite number of places. Finally, we set $\alpha_{i+1}(x)$ to disagree with the output of program $i$ on input $x$ and oracle $\beta'$.

At step $2i+1$ we make sure that the $i$th program cannot compute $\beta$ given $\alpha$, in the same way. Our construction ensures that $\alpha = \bigcup_i \alpha_i$ and $\beta = \bigcup_i \beta_i$ are total functions that correspond to incomparable Turing degrees.


Conversion from octal numerical system to binary numerical system I know that in order to convert a numeral in base-8 to a numeral in base-2 I can write each octal digit as a binary word of 3 bits.

I know that 2^3 = 8 that is exactly the dimension of the base of the octal system.

I just cannot understand the fundamental reason why it works. Is it just a coincidence?

Its not a coincidence. It is a general result for any number represented in a positive base $b$, its representation in base $b^k$ for some positive integer $k$, is simply grouping $k$ digits in its base $b$ representation starting from the least significant digit to the most significant digit.

Take base $10$ for example.

$427428$ in base $10$ is $(4,2,7,4,2,8)$.
$427428$ in base $10^2$ is $(42,74,28)$.
$427428$ in base $10^3$ is $(427,428)$.

You can now find an analogy to your problem.

Edit: Proof for the above claim

Let a number $n$ be represented in base $b$ positional system as

$n = (a_{m-1},a_{m-2},\space...\space,a_1,a_0)$ such that $0 \le a_i \lt b \space \forall i\in\{0,1,\space...\space,m-1\}$

where $m$ represents the number of digits $n$ has in the base $b$ representation. We wish to represent $n$ in base $B = b^k$ for some positive integer $k$.

For the sake of simplicity of the argument, let $m$ be a multiple of $k$, i.e. $m = c k$ for some integer $c$. (If $m$ is not a multiple of $k$, the representation of $n$ in base $b$ can be prefixed by $0$'s untill the number of digits are a multiple of $k$)

From the representation in base $b$, we can write $n$ as follows

$n = a_{m-1} b^{m-1} + a_{m-2} b^{m-2} + \space ... \space + a_2 b^2 + a_1 b + a_0$

$\space\space= a_{ck-1} b^{ck-1} + a_{ck-2} b^{ck-2} + \space ... \space + a_2 b^2 + a_1 b + a_0$

$\space\space = a_{ck-1}b^{ck-1} + a_{ck-2}b^{ck-2} + \space ... \space + a_{(c-1)k+1} b^{(c-1)k+1} + a_{(c-1)k} b^{(c-1)k}$

$\space\space\space + a_{(c-1)k-1}b^{(c-1)k-1} + a_{(c-1)k-2}b^{(c-1)k-2} + \space ... \space + a_{(c-2)k+1} b^{(c-2)k+1} + a_{(c-2)k} b^{(c-2)k}$

$\space\space\space\vdots$

$\space\space\space + a_{2k-1}b^{2k-1} + a_{2k-2}b^{2k-2} + \space ... \space + a_{k+1} b^{k+1} + a_k b^k$

$\space\space\space + a_{k-1}b^{k-1} + a_{k-2}b^{k-2} + \space ... \space + a_1 b + a_0$

We can rearrange the last expression by taking out powers of $b^k$ from each sequence of $k$ terms as follows

$\space\space\space + \{\space a_{ck-1}b^{k-1} + a_{ck-2}b^{k-2} + \space ... \space + a_{(c-1)k+1} b + a_{(c-1)k} \space\}.b^{(c-1)k}$

$\space\space\space + \{\space a_{(c-1)k-1}b^{k-1} + a_{(c-1)k-2}b^{k-2} + \space ... \space + a_{(c-2)k+1} b + a_{(c-2)k} \space\}.b^{(c-2)k}$

$\space\space\space\vdots$

$\space\space\space + \{\space a_{2k-1}b^{k-1} + a_{2k-2}b^{k-2} + \space ... \space + a_{k+1} b + a_k b \space\} . b^k$

$\space\space\space + \{\space a_{k-1}b^{k-1} + a_{k-2}b^{k-2} + \space ... \space + a_1 b + a_0 \space\}$

$\space\space = p_{c-1} B^{c-1} + p_{c-2} B^{c-2} + \space ... \space + p_1 B + p_0$

Where, $p_i = a_{(i+1)k-1} b^{k-1} + a_{(i+1)k-2} b^{k-2} \space ... \space + a_{ik+1} b + a_{ik} \space$
$\space\space\forall i \in \{0,1,\space ...\space ,c-1\}$

We can see that this is a representation of $n$ in base $B$ i.e. base $b^k$, with $c$ digits.

$n = (p_{c-1},p_{c-2},\space ... \space, p_1,p_0)$.

For the above to a valid representation in base $B$, $\forall i:\space0 \le p_i \lt B$

We can verify this by finding the maximum value of any of the group of terms in the above expressions.

Since, $\forall i:\space 0 \le a_i \lt b$, maximum value of $a_i$ is $b-1$.

Now we get for any $i$,

$a_{(i+1)k-1}b^{k-1} + a_{(i+1)k-2}b^{k-2} + \space ... \space + a_{i+1} b + a_i$

$= (b-1)b^{k-1} + (b-1)b^{k-2} + \space ... \space + (b-1)b + b$

$= (b-1)(b^{k-1}+b^{k-2}+\space...\space+b+1)$

$= (b-1)\frac{b^k-1}{b-1}$

$= b^k - 1 $

which is strictly less than $b^k$ or $B$.

Hence, we prove the claim.


Brackets in distributive law? The (second) distributive law in boolean algebra is defined as

  $A + (B C) = (A + B) (A + C)$

But wouldn't it be correct to define it that way:

  $(A + (B C)\, ) = (A + B) (A + C)$

Because if you transform

  $(\sim D + \sim C) (\sim D + B + A) (C + \sim B + \sim A)$

to

  $\sim D + (\sim C (B + A) \, ) (C + \sim B + \sim A)$

it would be incorrect since * has higher precedence than +, so

  $(\sim D + (\sim C (B + A)\, )\, ) (C + \sim B + \sim A)$

would be correct, or am I totally mistaken?

The real problem is you're making a mistake with the precedence rules being used. The sentence:
$$
(\lnot D + \lnot C)(\lnot D + B + A)(C + \lnot B + \lnot A)
$$
is ambiguous until we add rules of precedence, or explicitly parenthesise it. Because logical $\mathsf{AND}$ is associative (and commutative), we normally ignore the fact that we have to decide, one way or the other, which of the two $\mathsf{AND}$s applies first.

The normal rules we use (when nothing else gets in the way, go left to right) implicitly parenthesises the sentence as:
$$
[(\lnot D + \lnot C)(\lnot D + B + A)](C + \lnot B + \lnot A)
$$

If we parenthesise in this explicit way, and apply the distributive law, then you get what you expect:
$$
[\lnot D + \lnot C(B + A)](C + \lnot B + \lnot A)
$$

If we changed our rules of precedence to right-to-left and thought about it as
$$
(\lnot D + \lnot C)[(\lnot D + B + A)(C + \lnot B + \lnot A)]
$$
then we can't apply the distributive law at all, we have to apply the associative property first, then we again get what you expect.

In general you have to remember that we often simplify mathematical notation to ease reading, so when you are manipulation expressions, you have to remember that we're leaving things out, or put them back in for clarity.


Example of Minimum Test Collection Problem I'm studying the Minimum Test Collection problem and I can't find an example of some instance of the problem, given values to the sets. The Garey and Johnson book  only contains the proof of its NP-Completeness.

I hope someone can give me an example in order to understand in a better way the problem.

The problem is defined as follows:

Instance: A finite set A of "possible diagnoses," a collection C of subsets of A, representing binary "tests," and a positive integer J≤|C|.

Question: Is there a subcollection C′⊆ C with |C′|≤ J such that, for every pair $a_{i},a_{j}$ of possible diagnoses from A, there is some test c∈C′ for which |{$a_{i},a_{j}$}|∩ c|=1 (that is, a test c that "distinguishes" between $a_{i}$ and $a_{j}$)?

Thanks.

The formal definition of the problem from Garey and Johnson is

  Minimum Test Collection

  Instance: A finite set $A$ of "possible diagnoses," a collection $C$ of subsets of $A$, representing binary "tests," and a positive integer $J\leq |C|$.

  Question: Is there a subcollection $C'\subseteq C$ with $|C'|\leq J$ such that, for every pair $a_i,a_j$ of possible diagnoses from $A$, there is some test $c\in C'$ for which $|\{a_i,a_j\}|\cap c|=1$ (that is, a test $c$ that "distinguishes" between $a_i$ and $a_j$)?

Think of $A$ as a set of diseases, and each element of $C$ is a set of all the diseases in $A$ that have some particular symptom.  You can use these sets to figure out what disease a person has. For example (not necessarily medically accurate), suppose our diseases are
$$A = \{\mathrm{flu}, \mathrm{measles}, \mathrm{ebola}\}$$
and our tests are
$$C = \{\mathrm{cough}, \mathrm{rash}, \mathrm{bleeding}\}\,,$$
where
\begin{align*}
\mathrm{cough} &= \{\mathrm{flu}, \mathrm{ebola}\}\\
\mathrm{rash}  &= \{\mathrm{measles}, \mathrm{ebola}\}\\
\mathrm{bleeding} &= \{\mathrm{ebola}\}\,.
\end{align*}

A doctor might try to diagnose a patient by checking whether they have a cough and/or a rash and whether they're bleeding. Minimum Test Collection asks if we can do any better than that, since tests might be expensive to carry out.

In this case, we can.  It's enough to check whether the patient is coughing and whether they're bleeding. If they're bleeding, we know they have ebola. If they're not bleeding, but they are coughing, they have the flu; if they're neither bleeding nor coughing, they must have the measles.  (Note we're assuming as part of our test procedure that these are the only three diseases in the world, and that people only go to the doctor if they have at least one symptom.)


Prove that there exists an undecidable complementary language Some language A ⊆ Σ∗
is called complementary if A ≤m complement of A. How can I show that there exists an
undecidable complementary language?

Take $\Sigma=\{0,1\}$ for simplicity.

Define $A \oplus B = 0A + 1B$. We have that $(A \oplus B)^c \equiv_m A^c \oplus B^c$ since they differ only by the empty string.

We now take any non recursive $A$, and consider $B = A \oplus A^c$. We have $A \leq_m B$, so $B$ is not recursive as well. Further, $B = A \oplus A^c \equiv_m (A^c \oplus A)^c \equiv_m (A \oplus A^c)^c = B^c$.


Why are directed graphs important? We have been reading about algorithms for MST, strong-connectivity, routing, etc. in directed graphs.

Also recently people have been doing research for dynamic and fault tolerant algorithms for directed graphs.

But I was wondering if there are any practical applications where the underlining graph network is "Directed". Other than social-networks all problems that I could think of like rail/road network, Internet network, etc. deal with undirected graphs only.

Edit 1: I understand that these can be used to model some scenarios where links are directed but I was wondering how often these scenarios occur in real-world, and how important is study of fault tolerance for directed graphs.

Recalling that a directed graph is a graph where the edges have an associated direction with them.

Using a directed graph you can represent asymmetrical relationships between nodes, while in undirected graph we can represent only symmetrical relationships.

Practically, using a directed graph you can represent:

Road networks (using a directed graph you can represent streets'  direction);
hyperlinks connecting web pages;
dependencies in software modules;
prey-predator relationships;
deterministic finite automaton.

Besides these classical examples, you can depict many other real-world scenarios (financial trade, scheduling, infectious disease, citation, control flow, etc) that needs an ordered relationship [1].


Size of decision tree and depth of decision tree I'm doing some classification experiments with decision trees ( specifically rpart package in R). By setting the depth of a decision tree to 10 I expect to get a small tree but it is in fact quite large and its size is 7650. So what is exactly the definition of size (and depth) in decision trees?

PS: my dataset is quite large.

The depth of a decision tree is the length of the longest path from a root to a leaf.

The size of a decision tree is the number of nodes in the tree.

Note that if each node of the decision tree makes a binary decision, the size can be as large as $2^{d+1}-1$, where $d$ is the depth.  If some nodes have more than 2 children (e.g., they make a ternary decision instead of a binary decision), then the size can be even larger.  So, a size of 7650 is not unreasonable, if some nodes make binary decisions and some make ternary or multi-way decisions.


Examples of maximal paths in undirected graphs According to me, maximal paths in a graph are those paths which cannot be included in any other larger paths. Could anyone please explain me this with some examples? Also what would happen if the graph happens to contain cycles?

We can say a path is maximal if you cannot add any new vertices to it to make it longer. You can contrast this with a path of maximum length: it is the longest path in a graph (so it is also maximal, but note the difference). A bit informally, when something is "maximal", it means you cannot add anything to it to make it larger. When something is "maximum", it is globally the largest "object" there is.

For an example, consider the tree pictured in this Wikipedia article. The path on the vertices $\{1,2,4\}$ is maximal; you cannot add any vertex to it to make it longer. But a maximum path (i.e., longest path) in the tree is on the vertices $\{ 1,4,5,6 \}$. Clearly, it is no problem if the graph you consider contains a cycle. For example, then you can see that not every vertex of the graph can be in a longest path.


Where are file-information like "created" or "last edited" actually stored? I can access some information about the files ("created" or "last edited") on my PC. But where are those information actually stored?

Are they stored by the operation system? Could be possible as if I transfer a file with FTP to an other PC, it has new timestamps for those information.

Or are they stored in the beginning of the file itself?

How does it work?

Information like "creation time" is called metadata.  The filesystem stores both the contents of the file and its associated metadata on the hard drive.  It has to -- if you reboot the computer, we need that information to persist, so it has to be stored somewhere that will survive reboots.  That place is the hard drive.

See https://en.wikipedia.org/wiki/File_system, How do Hard Drives Send and Recieve Data?, Reconstructing files from binary, Typical file structure, and a good operating system textbook to learn more about how filesystems work.


Complexity of sending an $n$-bit string Consider a $2$-party communication model in which $A$ wish to send to $B$ an $n$-bit string. It is very easy to prove that any deterministic protocol for this problem requires $\Omega(n)$ bits to be transmitted. It is also well-known that any randomized protocol for this problem also requires $\Omega(n)$ bits to be transmitted. Although this considered to be a trivial fact, I failed to formally prove (or find a formal proof) for this. So my question is: how to show that any randomized protocol for this problem requires $\Omega(n)$ bits to be transmitted?

You haven't defined when a randomized protocol is declared to be successful, so I will assume that at the end of the protocol, Bob tells a judge what he thinks the message is, and we want that for each message $x$, the probability that Bob is correct is at least $1-\epsilon$.

Let $X$ be a random $n$-bit string, and let $\Pi$ be the corresponding transcript. Let $R$ be the randomness in the protocol (i.e., given $R$ the protocol is deterministic, and Bob's output is deterministic). Let $Y$ be Bob's output, and let $B$ be an indicator variable for the event $X=Y$.

The definition of correctness of the protocol shows that
$$
\begin{align*}
H(X|\Pi R) &\leq H(BX|\Pi R) \\ &= H(B|\Pi R) + H(X|\Pi RB) \\ &\leq 1 + \Pr[B=1] H(X|\Pi R,B=1) + \Pr[B=0] H(X|\Pi R,B=0) \\ &\leq 1 + 1 \cdot 0 + \epsilon \cdot n \\ &= \epsilon n + 1.
\end{align*}
$$
This implies that
$$
H(\Pi|R) = H(X\Pi|R) - H(X|\Pi R) = H(X) - H(X|\Pi R) \geq (1-\epsilon) n - 1,
$$
since $H(X\Pi | R) = H(X | R)$ (given $R$, Alice's input $X$ determines the transcript $\Pi$) and $H(X|R) = H(X)$ (since Alice's input and the randomness are independent).

We conclude that the communication complexity is at least
$$
(1-\epsilon) n - 1 = \Omega(n).
$$


Variation on Bellman-Ford Algorithms? We have a Directed Graph with 100 vertexes. v1 --> v2 --> ... v100 and all edges weights is equal to 1. we want to used bellman-ford for finding all shortest paths from v1 to other vertexes. this algorithm in each step check all edges in arbitrary order. if in each step the shortest distance v1 to all others vertexes is not changed, this algorithm halt. the number of steps is related to checking order of edges. what is the minimum and maximum of steps in this problem?

Solution: 2 and 100.

How this solution will be achieved?

Since we are checking edges in different order each time, the time taken will depend on the order of the edges being checked in Bellman-Ford algorithm.

We will get the final result in 2 steps if our order is $v_1v_2, v_2v_3, v_3v_4, ... v_{99}v_{100}$.

However we  will get the final result in 100 steps if our order is $v_{99}v_{100}, v_{98}v_{99}, ..., v_3v_2, v_2v_1$. We can prove that this is worst possible by noting that in Bellman-Ford algorithm with positive weights, in every iteration at least one shortest distance is calculated correctly. So in first iteration we will only determine the shortest distance to $v_2$, others will remain $\infty$, in second iteration we will determine the shortest distance to $v_2$ and $v_3$ while others still remain $\infty$, and so on so forth.


Reduce Clique to N-Degree-Clique I want to show that there is a polynomial-time reduction from the standard $\text{Clique}$ problem to the $\text{N-Degree-Clique}$ problem, where:
$$ \text{N-Degree-Clique} = \{ \langle G, k\rangle: \text{$G$ has a clique of size $\geq k$,} \\ \text{and every vertex of $G$ has degree at least N} \}$$
I am not sure how to map the last condition and could use help figuring out a reduction.

One almost correct reduction looks like: consider the graph $G'$ that is obtained by adding $N$ new vertices to the input graph $G$. Also, add edges that connect every new vertex to all the vertices in $G$. Its not hard to show that $G$ has a clique of size at least $k$ iff $G'$ has a clique of size at least $k+1$. Note that the degree of each new vertex equals the number of vertices of $G$, which not necessarily at least $N$. But this is a minor issue that I leave for you to fix (along with proving correctness).


Creating artificial NP-Complete problems Stephen Cook's proof of the NP-completeness of SAT is constructive. Given a Turing machine $M$, one can create a logical formula that is satisfiable if and only if $M$'s computation halts in an accepting state. This suggests that we could take a logical formula and create a Turing machine $M'$ whose computation is described by that formula, thereby creating an artificial problem solved by $M'$. Is it possible to use existing NP-complete problems to create other NP-complete problems? Can this be automated?

Dodging any questions about whether this is "interesting" or "artificial" (or whether Computer Science really needs any more NP-complete problems than it already has), the answer is "yes".  Pick a structure-preserving mapping between some set of strings and problem instances of 3SAT.  Show that the mapping can be computed in polynomial time (i.e., it is a polytime reduction).  Then, deciding if a string is in your set of strings is NP-complete.  Repeat as desired (the composition of polytime reductions is a polytime reduction.)

If you wanted to automate this process of creating new NP-complete problems, then it would likely be more efficient to construct the mappings from some base set of polytime mappings, using methods known to preserve polynomial time, rather than picking an arbitrary mapping and proving that it is a polytime reduction.

Note that this is not quite what you suggest in your question.  You can take a logical formula and build a Turing machine corresponding to it, but that in itself doesn't lead to an NP-complete problem.  For instance, 2SAT instances can be decided in polynomial time.  And a particular formula will only correspond to a particular machine, whereas you need a set of formulas (or machines) to define a complexity class; so to make new problems in NPC, you really need to show how one set can be converted into another (i.e. a polytime reduction), even if your sets are sets of logical formulas.


Are there NP problems, not in P and not NP Complete? Are there any known problems in $\mathsf{NP}$ (and not in $\mathsf{P}$) that aren't $\mathsf{NP}$ Complete?  My understanding is that there are no currently known problems where this is the case, but it hasn't been ruled out as a possibility.

If there is a problem that is $\mathsf{NP}$ (and not $\mathsf{P}$) but not $\mathsf{NP\text{-}complete}$, would this be a result of no existing  isomorphism between instances of that problem and the $\mathsf{NP\text{-}complete}$ set?  If this case, how would we know that the $\mathsf{NP}$ problem isn't 'harder' than what we currently identify as the $\mathsf{NP\text{-}complete}$ set?

Are there any known problems in NP (and not in P) that aren't NP Complete? My understanding is that there are no currently known problems where this is the case, but it hasn't been ruled out as a possibility.

No, this is unknown (with the exception of the trivial languages $\emptyset$ and $\Sigma^*$, these two are not complete because of the definition of many-one reductions, typically these two are ignored when considering many-one reductions). Existence of an $\mathsf{NP}$ problem which is not complete for $\mathsf{NP}$ w.r.t. many-one polynomial time reductions would imply that $\mathsf{P}\neq\mathsf{NP}$ which is not known (although widely believed). If the two classes are different then we know that there are problems in $\mathsf{NP}$ which are not complete for it, take any problem in $\mathsf{P}$.

  If there is a problem that is NP (and not P) but not NP Complete, would this be a result of no existing isomorphism between instances of that problem and the NP Complete set?

If the two complexity classes are different then by Ladner's theorem there are problems which are $\mathsf{NP}$-intermediate, i.e. they are between $\mathsf{P}$ and $\mathsf{NP\text{-}complete}$.

  If this case, how would we know that the NP problem isn't 'harder' than what we currently identify as the NP Complete set?

They are still polynomial time reducible to $\mathsf{NP\text{-}complete}$ problems so they cannot be harder than $\mathsf{NP\text{-}complete}$ problems.


How are semaphores and test-and-set instructions connected? Cheers, so my textbook explains these parts very poorly, so I would gladly take any advice! I am confused between the test-and-set instructions, which per my book is a very common CPU instruction set, and the use of semaphores for which my book says that: a flag implemented using this way, is a semaphore. Does that mean that semaphores are a part of these instructions or the opposite? Also, if a operating system does not support semaphores, can it support test-and-set instructions and if yes, can you reach mutual exclusion this way? Thanks!

Semaphores are an abstract mechanism to control access to a shared resource. Other such mechanisms exist, for example locks and monitors. These are the counterparts of abstract data structures – they specify an API for a mechanism and its semantics, but not its implementation.
Implementing such mechanisms correctly requires hardware support. One way to implement semaphores is using test-and-set. Another popular instruction is compare-and-swap. Both of these are examples of atomic instructions, which are instructions performing several operations that cannot be interrupted in the middle. Such atomic instructions are necessary to correctly implement mechanisms such as semaphores.
Typically these control mechanisms are implemented by the operating system. For example, POSIX-compliant systems implement POSIX semaphores. Semaphores are just one more service provided by the operating system. Under the hood, semaphores are implemented using atomic instructions provided by the CPU.


Different ways to generate a big number with some small numbers Imagine we have a set of numbers $\{x_1,x_2,\dots,x_m\}$. We want to compute the different ways to make a big number $P$ by those small numbers.

For example, if $P = 5$ and we have $\{1,2,3,4,5\}$ we can make $P$ by:

1+1+1+1+1 or
2+3 or
1+4 or ...

This is a well-known problem called the subset sum problem. Essentially we are looking for a subset of the elements that sums up to a target value, P. The problem is NP-hard, meaning it does not admit a polynomial time solution unless P = NP.  Here is a link that explains how to solve this problem. There are multiple algorithms for the problem. The recursive one runs at in an exponential time of $O(2^n)$. This problem is mostly associated with a Dynamic Programming solution since its run-time is $O(P\cdot n)$, such a running time is called pseudo polynomial, since it is polynomial in the value of the input instead of its size (which is the log of the value).


How can I prove or disprove that the following function is bijection? For a research project, I tried to prove or disprove that a function called xxhash128_low is a bijection from 64 bit unsigned integer to 64 bit unsigned integer. I have shown that it is sufficient to prove that the following critical code is a bijection:
Input: a 64-bit integer x
0. Let c=0x9e3779b185ebcaa7
1. Let x_low= the 8-low bytes of c*x.
2. Let x_high= the 8-high bytes of c*x.
3. w= x_high+2*x_low.
4  y= shift right 3 bits of w.
5. return x_low XOR y.

What I have proved till now: returning only the low 64 bits, x_low, can be shown to be a permutation. Also, y can be expressed as a function of x_low (i.e., y=f(x_low)).

Originally, the hash function was defined as follows:

Input: a 64-bit unsigned integer $x$.
Calculate $(9E3779B185EBCB87)_{16} \cdot x = 2^{64} x_h + x_l$, where $x_l,x_h$ are 64-bit unsigned integers.
Output $x_l \oplus \lfloor (x_h + 2x_l)/8 \rfloor$.

Under this definition, there is a collision: both $(2DCE4F983BBEB685)_{16}$ and $(72E04DBED1540FE1)_{16}$ map to $(A5C53FE6E277BD92)_{16}$.
You can find such collisions using a cycle detection algorithm.


Clarification on NP-hardness and hardness of approximation results for set cover? I'm not familiar with complexity theory at all so please correct me if I make any incorrect statements.

I am wondering what is the hard case of set cover? My understanding of NP-hardness is that it describes a worse case scenario. In other words, if I am only considering set cover for say the case that the number of subsets is less than the number of elements in the ground set (or vice versa), can I say that this case falls under a 'hard' or 'easy' case of set cover.

Moreover, in looking at the work by Dinur and Steurer 2013 , they say it is NP-hard to approximate set cover within a factor of $(1−\epsilon)ln (n)$, where $n$ is the size of the universe, but they don't mention the size of the collection of subsets (denote $m$), does this imply that this inapproximability result should hold for any $m$, regardless of it $m < n$ or $m > n$?

When you have a result like "It is NP-hard to approximate X within ..." or say "X is NP-complete", it means that there is an infinite family of instances of X that are hard. This is what worst case intractability means.

In your example, the hardness of approximation result holds for the set cover problem, meaning that there is an infinite family of instances of set cover that are hard to approximate.

At this point, you might put further constraints on a problem in the form of "suppose every set satisfies this property" or whatever, but this is then a different problem, i.e., you are narrowing down on the instances that you care about. If you have a statement that says "set cover with your favorite property is NP-hard to approximate", it means that there is (still!) an infinite family of instances of this problem that remain hard.


How do I reduce subset sum to another problem in NP? I'm trying to solve the following problem about arranging pens on rows. The problem goes as the following.

Given $n$ integers $l_1, \dots l_n$, the lengths of the pens, r rows and a goal G. Is it possible to arrange the pens where each row has a maximum length G, where G is the minimum possible.

I have shown that this problem is in NP, but now I'm trying to reduce a subset sum problem to this problem with karp reduction.

I know how the subset sum problem looks like, but I'm having a trouble where to start with the reduction, any tips would be greatly appreciated.

Let $S, k$ be a given instance of the subset sums problem. The goal is to build an equivalent instance of your problem (let us call it the pens arrangement problem). In the subsetsums problem, we are looking for a subset of the given set that sums up to $k$. So it is intuitive to set $G$ to $k$ and set the lengths of the pens to be the numbers in the given set.

However, In the subset sums problem, if you found a subset that sums to $k$ the rest will sum up to a number equal to $\sum_{a \in S} a -k$ which might be not equal to k and hence might generate a problem. An easy solution is to add one number to set, namely $\sum_{a \in S} a - 2k$. And change k onto$\sum_{a \in S} a - k$. By this changes we turned the subset some problem into the two partitioning problem, where we are looking for a subset of the given set that sums up to half the sum of the elements in the setand hence, the rest of the elements have the same sum. After this step we canset the number of rows to two and the columns to the new value of $k$. Try to prove why this reduction works.


Automatic seat assignment algorithm I am looking for articles relating to algorithms that deal with automatic selection of seating assignment.
I need an algorithm (preferably more than one) that can automatically select a seating place while enforcing certain constraints that are predefined.
Originally I was planning on having the seats selected on the fly, meaning whenever a new person comes, the system selects the optimal seat for him based on the seats which were already taken, but I guess it is not a must.
if there is a more general algorithm that can also present an approach fit for my problem that is also great.

Lets call the seated people "players" , and our seating domain lets picture as a 2d matrix. lets say we have several groups among our "players" and you can set your "players" anywhere within the matrix as long as they are not seated next to other "players" from their own group . I am not claiming there is a perfect solution, I am looking for articles that are dealing with some approach for giving a solution - if you can direct me to an article or even give me a name for that kind of problem it is also good for me.

Thanks,
Olaf

You could start your investigation from an online bipartite matching [PDF] point of view.

In specific, in this case, you know one side of the bipartition, namely the seats and their properties, and then you will get orders on-the-fly (online).  The performance you are looking to analyze is the number of matched buyers in the online algorithm versus the number of matched buyers if you'd know the buyers in advance (offline).


Insertion sort vs Merge sort - memory access I am a computer science sophomore doing a data structures and algorithms course. My professor said that insertion sort requires random access, while merge sort does not.

According to him, the insertion step in insertion sort requires random access. But can't it be implemented using sequential access in a linked list, going through each element, and as soon as you find that the element of the next node is more than the element you wish to insert, you squeeze that element after the current element (for ascending order list).

He is almost never wrong, but he also doesn't entertain doubts, due to which I'm forced to ask here. Please let me know. Thanks!

The implementation of merge sort that your instructor has in mind accesses memory sequentially, in the sense that merging steps from left to right over the two arrays being merged and the target array as well.  Insertion sort has a more complicated memory access pattern.

As you note, if you sort linked lists instead of arrays, insertion sort also conceptually moves from left to right.  However, the implementation of linked lists will still do pointer operations that lead to non-sequential memory access.


Schedule Optimization With Priority and Weighted Costs I need an algorithm to determine the best itinerary for a series of events.
Each event has a time, location, and reward. Arriving at an event in time yields the reward; too late means no reward. Each event is at a physical location thus it takes time to travel from event to event. It is not necessary to attend every event.
What itinerary will yield the largest total reward?
Does anyone know if there is an existing algorithm for this or one that would be easily adapted? Given the similarity to the traveling salesman problem I am tempted to start with a weighted TSP solution and work from there.

We can construct a directed graph with events as vertices, where an event $E_2$ has an incoming edge from another event $E_1$ if starting from $E_1$, we can arrive $E_2$ in time to get its reward. The edge value is the time difference between the events.
For each vertex (event), we do a depth first search rooted at this vertex where on each iteration we add the value of the previous tree edge to the current tree edge and check to see if it is greater than the time associated with the current vertex. If it is then our considered sequence of events from the root vertex has just timed out.
var MaxReward = 0
var bestItinerary = []

f(graph):
  for vertex v in graph:
    _f(v, v.time, 0, [])

_f(v, curr_time, rewardSoFar):
  if time > v.time:
    if rewardSoFar > MaxReward:
      MaxReward = rewardSoFar
      bestItinerary = itinerarySoFar
  else
    rewardSoFar = rewardSoFar + v.reward
    itinerarySoFar.append(v)
    for edge, neighbor in v.getNeighbors:
      _f(neighbor, curr_time + edge.value, rewardSoFar, itinerarySoFar)


Time complexity of expanding decimal to new base There is already a post on this topic on stackoverflow.

Nevertheless, I am asking the question here again, primarily because I do not understand the answer given there, and also because I have some takes on the problem I would like to supplement with.

To reiterate, we have a problem in CLRS which goes like this:

  Show how to sort $n$ integers in the range $0$ to $n^3-1$ in $O(n)$ time.

There seems to be a consensus that we first convert the numbers into base $n$, which ensures that each number is made up of at most 3 digits. Then we can use radix sort to sort the number in $\Theta(3(n+n)) = \Theta(n)$ (the parameter $k$ equals $n$ because we are in base $n$).

What I am concerned with is the cost of converting the $n$ numbers to and from base $n$. Converting back to decimals is $\Theta(1)$ obviously, so $n$ conversions equals $\Theta(n)$. But converting a decimal to another base takes $\Theta(\log n)$, so that the first $n$ conversions to base $n$ would take $\Theta(n\log n)$ time, and break the time complexity of $\Theta(n)$ of the algorithm overall.

I have read that you can view the expansion as a $O(1)$ operation under the RAM model though I do not understand why (probably because I do not understand the difference between the RAM and BIT models in connection to complexities). In the original post the answer given also tries to explain how if integer arithmetic is done in $O(1)$ time, then "... converting a number to base $n$ is basically most significant digit: x/n, least significant digit: x%n," which I really don't get any of.

Let me start with a short introduction on computation models. A (C-like) computation model specifies the inventory of operations, and the cost of each operation. Two popular computation models are the bit complexity model and the word RAM model, though the latter doesn't really have a canonical description.
In the bit complexity model, all basic operations operate on bits (except for instructions like JUMP, which we ignore here for simplicity), and they all have constant cost. The exact cost of each operation, and the exact repertoire of operations, isn't important (as long as we have a complete set of operations!), since it only affects the running time by a constant factor.
In the word RAM, we associate with each input a parameter $n$ which is a "yardstick" for the input. For example, a function that accepts an array of length $n$ will use the input length as a parameter (but this only works if the array entries are "small" – more on that later). In the word RAM, all basic operations operate on machine words. What is a machine word? It is a value which is $C\log n$ bits long, for some constant $C$ depending on the algorithm (we will see that $C$ doesn't really matter shortly). Each operation on machine words takes time $O(1)$. The operations allowed are arithmetic operations (addition, subtraction, multiplication, division with remainder), comparisons, bitwise operations (NOT, AND, OR, XOR), and shifts. Since we can simulate an operation on words of width $C\log n$ bits using $O(1)$ operations on words of width $\log n$ bits (where the constant depends on $C$), the value of $C$ doesn't really matter.
Let us now come back to the definition of $n$. We usually assume that the input consists of $Cn$ machine words of length $\log n$ bits (for some constant $C$ depending on the algorithm), for a total input length of $Cn\log n$ bits. We obtain an equivalent definition by setting $n$ to be the input length in bits, essentially since $\log(Cn\log n) = \Theta(\log n)$.
(We have not touched on the random access aspect of the RAM model, and on the uniformity aspect of both models, since these are not relevant here.)

Now back to your question. Since your array consists of numbers of length $3\log n$ bits (so we are using $n$ as our yardstick for the word RAM model), we can assume that each of them fits into a single machine word. Packing and unpacking these numbers to base $n$ is very easy:

UNPACK($m$):

$m_0 = m \bmod n$.
$m_1 = \lfloor m/n \rfloor \bmod n$.
$m_2 = \lfloor m/n^2 \rfloor$.
return $m_2,m_1,m_0$.

PACK($m_2,m_1,m_0$):

return $n^2 m_2 + n m_1 + m_0$.

You can see that both operations use $O(1)$ operations, so take $O(1)$ time in the word RAM model. With some care, the implementation can be improved to use $O(d)$ operations for numbers up to $n^d$:

UNPACK($m$):

$m_0 = m \bmod{n}$, $m = \lfloor m/n \rfloor$.
$m_1 = m \bmod{n}$, $m = \lfloor m/n \rfloor$.
$m_2 = m \bmod{n}$.
return $m_2,m_1,m_0$.

PACK($m_2,m_1,m_0$):

return $m_0 + n(m_1 + n (m_2))$.


Set of all Languages Sorry if the Question sounds a little trivial.
Let A* be the set of all languages over A={a,b}. Then A can be written as {aUb}*
which is a regular expression.So this is the set of all languages(actually set of all strings) regular.Am i thinking in the right direction.

You're almost there, but you need the right notation. Let's start with the alphabet $\Sigma = \{a,b\}$. Then the regular expression $(a+b)$ represents a set of two strings, namely $\{a,b\}$. The expression $(a+b)^2$ represents the set of the strings $\{aa, ab, ba, bb\}$. The expression $(a+b)^3 \ldots$ The expression $\{a,b\}^*$, also denoted $\Sigma^*$, represents the union of all these sets. Each of these sets is called a language, and so $\Sigma^*$ is also a language. So $\Sigma^*$ is one language, not the set of all languages, over the alphabet $\Sigma$, and it contains all the strings you can form out of that alphabet.

The set of all languages you can form using that alphabet is the power set of $\Sigma^*$, denoted by $\mathcal{P}(\Sigma^*) = \{L | L \subseteq \Sigma^*\}$. That is, if $L$ contains only strings from your alphabet, then $L$ is a language over $\Sigma$, so $L$ is an element of the set $\mathcal{P}(\Sigma^*)$. Now, some of these languages are regular, and some are not. Certainly the language $\Sigma^*$ is a regular language, and $\emptyset$ is a regular language (you can draw their finite automata and see that they are the two simplest automata). Other languages, such as $\{a^nb^m|n+m \text{ is prime}\}$ are not regular. I hope that clears some things up.


Shortest Path problem(Single Source&Destination) Given: A completely connected directed acyclic graph.

What would be the most efficient(Least Time complexity) way to find a shortest path among a very large number of nodes?

Constraint:
1)The result should be optimal.
2) The cost between any two connected nodes is computed in time complexity of O(layer-no). For, e.g., if we consider the graph to be layered(Since its a DAG) then the cost between Layer 'K-1' & 'K' can be computed in a time complexity of O(K)

Known Solutions:
1) A* - But heavily dependent on the heuristic function
2) Dynamic programming - requires to compute the cost of path for all possible path.

So, Is there any way to compute it more efficiently or with similar time complexity?

Your goals are not achievable.

You want the running time to be $O(K)$, where $K$ is the number of layers (or the distance from the source to the destination, I'm not sure which).  However, this running time is not achievable.  Suppose we have only a handful of layers, but millions of vertices in each layer: say, $K$ layers, but $N/K$ vertices per layer, where $K$ is small and $N$ is large).  Then there is no way to get a running time of $O(K)$, because any solution will have to look at every vertex in each of those layers.  Therefore, the best you can hope for is a worst-case running time of $O(N)$; $O(K)$ isn't achievable.

So, there is no algorithm that will meet your constraints.

That's the bad news.  The good news is that there is an algorithm that is efficient and has a running time that is asymptotically optimal.  This is the standard algorithm for computing shortest paths in a DAG: you topologically sort the DAG, then visit the vertices in topologically sorted order, calling "Relax" on each edge.  Any good algorithms textbook is likely to describe this algorithm.

The running time of this algorithm is linear, i.e., $O(V+E)$.  One can also prove that this is the best worst-case running time one can hope for: it's not possible to do any better, in terms of asymptotic worst-case running time.  So, from a theoretical perspective, the standard algorithm is excellent.

Now this doesn't rule out the possibility that clever implementation can improve the constant factors.  Indeed, it is likely that careful consideration of things like the structure of your graphs and the memory hierarchy might yield speedups that are measurable in practice.  But you shouldn't expect an improvement in the asymptotic running time.


Proving that a set of operations can't generate one integer from a given one Given two numbers, $n$ and $m$, are there some mathematical methods of deducing $m$ from $n$ using limited number of elemantary operations?

Example:  335 can be deduced from 2000 using division by 2, addition of 5 and division by 3: $((2000/2)+5)/3) = 335$.

I need to prove that 1889 can't be derived from 2019 using the following 3 operations:

$n+7$ ;
$n*2$;
$n/3$ (if divisible).

All I come up with is some sort of breadth-first search.

If you have implemented breadth first search correctly, you should have found that 1889 can be reached.
$\quad 2019+7\to 2026$
$\quad 2026+7\to 2033$
$\quad\quad\cdots\quad$ (add 7 repeatedly)
$\quad 4238+7\to 4245$
$\quad 4245 \div 3 \to 1415$
$\quad 1415 * 2 \to 2830$
$\quad 2830 * 2 \to 5660$
$\quad 5660 + 7 \to 5667$
$\quad 5667 \div 3 \to 1889$
It is possible that you had been asked to show that 1883 can't be derived from 2019.
A number can be derived from 2019 iff it is a positive integer not divisible by 7
Proof:
"$\Longrightarrow$": If $n$ is not divisible by 7, neither is any of $n+7$, $n*2$ and $n/3$ (when $n$ is divisible by 3). If we start with a number that is not divisible by 7, it will remain not divisible by 7 regardless of how many operations we have applied on it. Since 2019 is not divisible by 7, we cannot derive any number that is divisible by 7.
"$\Longleftarrow$":
In fact, we can derive all positive numbers not divisible by 7 without the operation $n\to n * 2$. For all $k\ge0$,

$\dfrac{2019 + 7 * (((7k+1)*3^{6k+7}-2019)/7)}{3^{6k+7}}=7k+1$
$\dfrac{2019 + 7 * (((7k+2)*3^{6k+11}-2019)/7)}{3^{6k+11}}=7k+2$
$\dfrac{2019 + 7 * (((7k+3)*3^{6k+6}-2019)/7)}{3^{6k+6}}=7k+3$
$\dfrac{2019 + 7 * (((7k+4)*3^{6k+9}-2019)/7)}{3^{6k+9}}=7k+4$
$\dfrac{2019 + 7 * (((7k+5)*3^{6k+8}-2019)/7)}{3^{6k+8}}=7k+5$
$\dfrac{2019 + 7 * (((7k+6)*3^{6k+10}-2019)/7)}{3^{6k+10}}=7k+6$

Exercises
Exercise 1. Assume the same three operations. Let $n$ be a positive number not divisible by 7. Then a number can be derived from $n$ iff it is a positive integer not divisible by 7.
Exercise 2. Assume the same three operations. Let $n$ be a positive number divisible by 7. Then a number can be derived from $n$ iff it is divisible by 7.
Exercise 3. If positive integer $m$ can be derived from positive integer $n$ using the three operations, then $m$ can be derived from $n$ using the first and last operations, namely, $n\to n+7$ and $n\to n/3$ (if divisible).


Is there an algorithm to find the minimal number of dimensions, given the distances between points? Given some finite set $S := \{x_1,x_2,\ldots,x_k\} \subset \mathbb R^n$ we can define a distance matrix $D = (d(i,j))_{ij}$ with $$d(i,j) = \Vert{x_i - x_j}\Vert$$

where $\Vert \cdot \Vert$ is the euclidean norm.

Is there an algorithm to determine the minimal $m$ just from $D$ such that there are $\{y_1,y_2,\ldots,y_k\} \in \mathbb R^m$ with $d(i,j) = \Vert{y_i -y_j}\Vert$?

Or equivalently: Given $D$ as well as some $m$, can we determine whether $D$ can stem from $k$ points in $\mathbb R^m$?

This problem of minimal dimensionality has been studied intensively.

Here is a slightly-edited excerpt from Learning metrics via discriminant kernels and multidimensional scaling: Toward expected euclidean representation by Zhihua Zhang, Proceedings of the Twentieth International Conference on Machine Learning (ICML-2003), Washington DC, 2003.

  Definition 1 (Gower & Legendre, 1986) An $m × m$ matrix $[a_{ij} ]$ is Euclidean if $m$ points $P_i$ $(i = 1, . . . , m)$ can be embedded in an Euclidean space such that the Euclidean distance between $P_i$ and $P_j$ is $a_{ij}$.

  The following theorem provides the conditions for a matrix to be Euclidean.

  Theorem 1 (Gower & Legendre, 1986) The matrix $[a_{ij}]$ is Euclidean if and only if $H^{\text{tr}}BH$ is positive semi-definite, where $B$ is the matrix with elements ${-\frac12}{a_{ij}}^2$ and $H = (I − \mathcal 1_ms)$ is a centering matrix where $I$ is the identity matrix, $\mathcal 1_m$ is the $m \times 1$ vector $(1, 1, \cdots , 1)$ and $s$ is a $1\times m$ vector satisfying $s\mathcal 1_m = 1$.

Note that in theorem 1, if the condition is true for one choice of $s$ (say $s=e_i$, the vector whose entry is 1 at $i$-th position and whose entries are 0 otherwise), it is true for every valid choice of $s$. That fact is included in Metric and Euclidean properties of dissimilarity coefficients by Gower & Legendre, 1986.

Thanks to theorem 1, we know the minimal $m$ such that there are $\{y_1,y_2,\ldots,y_k\} \in \mathbb R^m$ with $d(i,j) = \Vert{y_i -y_j}\Vert$ is one less than the minimum order of non-Eucidean sub-square-matrix of $[d(i,j)]$. A simple algorithm to compute that minimum order is to iterate through all submatrix (that allow non-consecutive rows or columns) of $[d(i,j)]$, checking whether each submatrix is Euclidean.

For more related information, we can read that article and dig further.


Decidability of the TM's computing a non-empty subset of total functions I have this HW problem:
Let $F$  be the set of computable total functions, and let $\emptyset\subsetneq S\subseteq F$. Denote
$$L_S=\{ \langle M \rangle | M \text{ is a TM that computes a function and } f_M\in S \}$$

where $f_M$ is the function $M$ computes.

Prove that for every such none-trivial $S$, $L_S \notin \mathcal{R}$.

I tried to  construct

$L_{f}=\left\{ x\#y\in{\Sigma^*}|y=f\left(x\right)\right\} $
$\tilde{S}=\left\{ L_{f}|f\in S\right\} $
$L_{\tilde{S}}=\left\{ \left\langle M\right\rangle |L\left\langle M\right\rangle \in\tilde{S}\right\} $

and then show with Rice that $L_{\tilde{S}} \notin \mathcal{R}$, when the idea behind it was to eventually show that $L_{\tilde{S}} \leq_m L_S $.
But the problem here is that I couldn't show a mapping reduction from $L_{\tilde{S}}$ to $L_S$ without assuming $L_{\tilde{S}} \in \mathcal{RE}$ (which I'm quite sure is not true).
So any other directions will be warmly welcomed!

For any function $f: \Sigma^* \rightarrow \Sigma^*$, let

$$L_f = \{ x \# y \mid y = f(x) \}$$

For any Turing machine $M$, we can construct the description of a Turing machine $M'$ such that $M'$ recognizes $L_f$ if and only if $M$ computes $f$. $M'$ will receive a string, check that it is of the form $x \# y$ and then simulate $M$ with input $x$. If the simulation returns $w$, $M'$ accepts if $w = y$. Therefore, the language

$$ A_f = \{ \langle M \rangle \mid M \text{ is a TM that computes the function $f$} \}$$

reduces to the language

$$B_f = \{\langle M \rangle \mid L(M) = L_f \}$$

The class

$$L_S = \{ L_f \mid f \in S \}$$

is a nontrivial class of Turing-recognizable languages and therefore the decision problem $B_f$ is undedicable by Rice's theorem.


Replacement of a substring with another substring in a string I apologize if this is not the right stackexchange for this question. I was playing around with the Python programming language, when I discovered something strange. It concerns replacing a substring of a string with another substring. For example, in "spammy", replacing "mm" with "xx" results in "spaxxy". However, in "spammmy", replacing "mm" with "xx" results in "spaxxmy", not "spaxxxxy" or even "spaxxxy". My question is, what is the proper, rigorous definition of replacing in a string $S$ a substring $T$ with a substring $T'$?

There is no proper, rigorous definition.  Or, rather, you can make multiple definitions.  All are valid.  You could provide a rigorous definition for replacing the first match, or a rigorous definition for replacing all matches.  Mathematics doesn't tell you which definition is "proper" or "best" or "most useful".
A meta-comment: You might to be expecting more from mathematics than it can bear.  Mathematics doesn't tell you what is "proper" or "right" or "best".  It gives us a model for a world: if the structure satisfies such-and-such conditions, then it has such-and-such properties.  You'll have to decide what conditions are appropriate, or what properties you want to have.


Constant problem for discrete functions Is there an algorithm to decide whether a closed-form expression over integer variables using, say, $\{+,-,\times,\div,\text{^},\lfloor\text{lg}\rfloor,!,()\}$, or some other useful set of operators, is everywhere zero?

For example, is $(jk)^2 +k!-2j$ always 0 when $j,k$ are integers (obviously not)? If some of the operators make it impossible, is it possible with just a subset, for example if one removes factorial?

To decide if a particular diophantine equation (i.e., an expression in integers using multiplication and addition/subtraction equated to zero) has any solutions is undecidable. This is essentially the answer to the negative to Hilbert's tenth problem, which asks for an algorithm to determine if a diophantine equation has a solution.


Understanding the flaw in a proof attempt of the Communication Complexity of Equality I'm new to communication theory and I've been wondering where the following simple argument fails:

Equality Problem
We have two players, player 1 Alice who gets an $n$-bit vector $X$ and player 2 Bob who gets an $n$-bit vector $Y$. We want one of them to output $1$ if and only if for all indices $i:$ $X[i] = Y[i]$.
Suppose that I choose the inputs $X$ and $Y$ uniformly at random from the set $\{0,1\}^n$. Initially, Alice knows nothing about Bob's input $Y$. Consider a protocol $P$ for equality. Alice and Bob run $P$ and assume that $P$ outputs $1$. By the correctness of $P$, Alice knows that for each index $i$, $Y[i] = X[i]$. Thus Alice has learned $|Y|=n$ bits . Doesn't this immediately imply the $\Omega(n)$ lower bound for $P$?

Note: Of course, I know that the above argument must be flawed since we can solve equality with $O(\log n)$ bits when allowing randomization. I'm just trying to understand why my proof attempt is flawed.

This vague argument can be made to work for deterministic communication complexity. In the randomized setting, protocols are allowed to err. Consider the standard protocol in which both players exchange a random hash of their inputs to some set of size $2^m$. They only learn $m$ bits of each other's input. When both hashes agree, they aren't completely sure that $X=Y$, and in particular no party has learned the other party's input.


Is there a basic proof that there exists some edit distance between two strings? Title says it all pretty much. I do realize that often edit distance is defined as the minimum number of operations needed to transform one string to another, but I want something to point to that's even more general than that.

I recently saw a brain teaser that claimed that some string was connected in a network to another as "friends" given an edit distance of one. It then went on to claim that friends of friends, friends of friends of friends, etc. (with no given upper bound on the degree of separation), were also in the network of that original string. I can't see how this definition of network doesn't include every possible string, and so I think the brain teaser is ill-formed. Given sufficient edits, a string can transform to any other string, right? -- but is there a name for that observation? I think this is so fundamental as to be near-impossible to Google, but there is always the distinct possibility of me being an idiot.

Given two strings $v,w \in \Sigma^*$ with $m = |v| \geq |w| = n$ (w.l.o.g.), align them like so:

$\qquad\displaystyle\begin{array}{ccccccc}
v_1 & v_2 & \dots & v_n & v_{n+1} & \dots & v_m \\
w_1 & w_2 & \dots & w_n & - & \dots & -
\end{array}$

This alignment implies an edit distance of

$\qquad\displaystyle 0 \leq d_{\text{edit}}(v,w) \leq d_{\text{Ham}}(v,w[1..n]) + (m-n)$.

In particular, there is an alignment for any two strings. Note furthermore that there are only finitely many alignments of $v$ and $w$ (we forbid columns $\genfrac{}{}{0pt}{}{-}{-}$), so one with minimal score (which is the edit distance) must exist.

Hence, any two strings have finite edit distance and the graph is connected.


Let $\Sigma = \{a, b\}$ and $L = \{aa, bb\}$. Use set notation to describe $\overline L$ Let $\Sigma = \{a, b\}$ and $L = \{aa, bb\}$. Use set notation to describe $\overline L$.

This is exercise 6 (page 28) from "An Introduction to Formal Languages and Automata" by Peter Linz. The author provides the following answer: $\overline L = \{\lambda, a, b, ab, ba\} \cup \{ w \in \{a, b\}^+ : |w|\geq 3\}$. Mine on the other hand is the following: $\overline L = \Sigma^* - L = \{w \in \Sigma^* : w \neq aa, w \neq bb\}$. Is my answer wrong? Thanks in advance.

You already got your answer in the comments: both the solutions provided solve the task. The only thing in which they differ is from which angle the attempt to solve the task. The author one goes from an empty set and adds only words that satisfy the given constraints (bottom-up approach). Yours goes from the set of all possible words and removes the ones that do not satisfy the constraint (top-down approach).
I would say his is more accurate IF you are not allowed to use $L$ or $\Sigma$, as it is often the case in exercise text books.


How does modulus affect the regularity of language? the question is as follows, further the notation used are standard as used in theory of computation
$$L = \big\{ w : w \in \{a,b\}^*,\ |n(a) - n(b)| = 2k\}\,.$$

Beware 'K' is not a fixed integer its a set of natural number , so 2k means all natural nunbers divisible by 2 and so on for 3k , 4k... .I think the above language is irregular or its finite automata can't be formed. Firstly the above question in basic language can be thought of as modulus of difference of number of $a$ and number of $b$ is divisible by $2$ or is even , similar to this reasoning we can extend this to more general like $3k$, $4k$, $5k$,... and so on. Secondly we know that any condition which have comprise the difference between the symbols would have infinite possible comparison between symbols, like an equation of
 $n(a) - n(b) =0/1/2/3...$ needs infinite states of finite automata which makes them irregular.

But here with the use of modulus it seems no different as here also we will need many comparison between symbols.

Thirdly its more of a general question like when define regularity of language $L$ over condition like,  $n(a) - n(b)\bmod 3 =0$, we say the all strings can be classified as having either remainder $0$,$1$,$2$ which by using Myhill-Nerode theorem proves the language regular. But why cant we use the same analogy over the relation like $n(a) -n(b)=2$ saying the all the strings would either have a difference $2$ or not. Further if you could answer the regularity of $n(a)- n(b) = 2k$, also how does taking modulus effect its regularity and how does it makes the states of finite automata finite which before applying modulus were infinite if you could a graphical representation would be appreciated.

You seem to be assuming that, to determine whether $n(a)-n(b)$ is a multiple of $m$ requires us to computer $n(a)$ and $n(b)$, subtract them, and then calculate the remainder. You're correct that a finite automaton can't do that, but it's not the only way.

The first thing to note is that you can computer $n(a)-n(b)$ directly. Initially, you've seen no $a$s or $b$s so the difference is zero. Each time you see an $a$, the difference increases by one; each time you see a $b$, the difference decreases by one. OK, that's a bit smarter but it still requires us to compute the value $n(a)-n(b)$, which could still be arbitrarily big, so still can't be done with a finite automaton.

The second thing to note is that, because of the way that modular arithmetic works,
$$(x-y)\bmod m = ((x\bmod m) - (y\bmod m)) \bmod m\,.$$
In other words, you can do everything modulo $m$. Each time you read an $a$, the difference increases by one modulo $m$. and each time you read a $b$, it decreases by one modulo $m$.

This means that you can recognize the language with an automaton with $m$ states: one for each value of $n(a)-n(b)\bmod m$.


How to define the Atomic Propositions in Model Checking The atomic propositions in Symbolic Model Checking form the state in the state-transition graph (the model $\mathcal{M}$ in Model Checking). The other part of Model Checking is the specification, which is usually some sort of temporal logic formula over the atomic propositions in the model.

My question is about the atomic propositions themselves. I have only seen a few rudimentary examples of them, such as $x = 20$ or $printer is busy$. These atomic propositions (I think) are stating a fact about the state of the program at that point in the system. You then use a temporal logic formula to see if the model holds under it. I am confused by how the atomic propositions are both defined and used.

First, how they are defined. I haven't seen anywhere a description on how you define these atomic propositions. That is my first question. I don't understand how stating $x > 100$ in a state in the model $\mathcal{M}$ means anything. I didn't have to prove it or anything. It was just stated as fact. Then the temporal logic formula comes along and is checked against it, but there's some disconnect there for me. The value was never proven correct in the first place. It's as if, in my program, I make an HTTP request and during the waiting period before a response, my atomic proposition is that $\mathtt{the\ sky\ is\ blue}$. Wondering why was it put there, how do I know that it is true. A better atomic proposition would be $\mathtt{the\ request\ was\ sent}$. But again, I don't see how the program/model/checker "knows" this. I don't see what is doing the verification that that statement is true.

So my question is basically, how you define atomic propositions in Symbolic Model Checking. What goes into them. How you are allowed to make such statements that seemingly aren't verified. I don't see how I can say anything about the state of the program without something else "checking" that yes $\mathtt{the\ request\ was\ actually\ sent}$. I understand that after we define this model, we have our specification formulas and check them against the model. But we never checked the model itself for accuracy, is what I'm trying to get at.

I feel like, after writing down, in a specific state, an atomic proposition, I would then need to write a unit test to verify that it was true for some input. Not sure what I'm missing.

Formal verification often involves at least three steps:

Make a formal model of the real-world system.  (The formal model might be a state-transition graph or automaton, for example.)
Write down a specification that hopefully captures the real-world requirements.
Verify that the formal model of the system meets the specification.

Formal methods provides guarantees about step 3; if step 3 succeeds, then we know that the formal model meets the spec.  It doesn't provide any guarantees about steps 1 or 2.  If there is a bug in the model, that causes it to fail to accurately capture the behavior of the real-world system, then the result of the verification process becomes meaningless and all guarantees are off.  So, you need some separate way to gain assurance in those steps.

The atomic propositions are part of that modelling process.  Usually, there are some parts of the real-world system that we model in the state-transition graph and others that we don't.  For instance, consider a traffic light.  It has some sensors to sense presence of cars and pedestrians; some logic to determine what color light to show in each direction; and some actuators (light bulbs) to actually display those chosen colors.  We might choose to model the logic in a formal model, and verify that the logic works properly.  This verification process might not verify anything about the sensors or the actuators; it might just assume they are correct.  That might be justified if, for instance, we think the logic is the part that is most likely to have subtle errors.  Then you might have an atomic proposition for "sensor #1 detected a pedestrian at such-and-such cross-walk" ($p_1$) and an atomic proposition for "turn on the green light facing in the N direction" ($q_N$).  Those atomic propositions represent the inputs or outputs to the logic, or facts about the state of the system.  The spec then has to be stated in terms of the atomic propositions, e.g., "it should be impossible to have the green light turned on in the N direction and in the E direction" ($G (\neg q_N \lor \neg q_E)$).


Deriving recursive definition from function specification Given this function specification, where name xs is bound to a list, # denotes its cardinality and . is the list index operator...

$$\left( \sum i: 0 \leq i < \#xs: xs.i * (i + 1) \right)$$

I need to derive a recursive function using induction.

Base case: []

\begin{align}
 \left( \sum i: 0 \leq i < \#[]: xs.i * (i + 1) \right) && \text{(Textual substitution - xs is free)} \\
 \left( \sum i: 0 \leq i < 0: xs.i * (i + 1) \right) && \text{(Def. of #)} \\
 \left( \sum i: False: xs.i * (i + 1) \right) && \text{(Algebra)} \\
 \left( \sum i: 0 \leq i < \#xs: xs.i * (i + 1) \right) && \text{(Empty range)}
\end{align}

Inductive case: (x:xs)

\begin{align}
  \left( \sum i: 0 \leq i < \#(x:xs): (x:xs).i * (i + 1) \right) && \text{(Textual substitution - xs is free)} \\
  \left( \sum i: 0 \leq i < 1 + \#xs: (x:xs).i * (i + 1) \right) && \text{(Def. of #)}
\end{align}

How can I proceed from here ?

Your notation and understanding are pretty good.

It is easier to consider (xs:x) as the inductive case instead of (x:xs)

\begin{align}
\sum_{i:\ 0 \leq i < \#(xs:x)} &(xs:x).i * (i + 1)\\
&=\sum _{i:\ 0 \leq i < \#xs+1} (x:xs).i * (i + 1) \\
&=\sum_{i:\ 0 \leq i < \#xs} (xs:x).i * (i + 1)+\sum_{i:\ i=\#xs}(xs:x).i * (i + 1)\\
&=\sum_{i:\ 0 \leq i < \#xs} xs.i * (i + 1)+x*(\#xs+1),\\
\end{align}
where we assume that list index starts with 0.

If we denote the function by $f$, the above equality becomes
$$ f(xs:x) = f(xs) + x*(\#xs+1), $$
which is the recursive step of a recursive definition.

The base case, as you have indicated, is
$$ f([]) =  \sum_{ i:\ 0 \leq i < 0} [].i * (i + 1)  =  \sum_{i: \text{ empty set}}[].i * (i + 1) =0.$$

Exercise. Derive the following recursive formula of the same function $f$.
$$ f(x:xs) = f(xs) + t(xs)+ x, $$
where $$t(xs)=\sum_{i:\ 0 \leq i < \#(xs)} xs.i,$$
the sum of items in $xs$.


Finding recurrence relation for running time of an algorithm I am pretty new to this, consider the following algorithm:

Calc_a(n):
    if n ==1: return 1
    else:
    sum = 0
    for i=1 to n-1:
        sum = sum + calc_a(i)
    return sum

So after running this algorithm a few times I see it basically finds the n'th element in a sequence defined by this recurrence relation:

$a_n = \sum_{i=1}^{n-1}a_i $

I need to find the recurrence relation for this algorithm running time per input. Walk me through it :)

Lets define running time as $T(n)$.
So the base case n=1 is $O(1)$ (theta?), as we just return 1.
Then we iterate (n-1) times , each time performing addition and calling the function on the current index, this is where I get confused.
I know how to deal with loops and recursion individually, not together.

My homework specifies that I should use constants rather than asymptotic notations. Does that means I should define the running time of Calc_a(i) as some constant?

How should I go about this?

*** EDIT ****
The answer I've come up with:

$
T(n) =
\begin{cases}
1,  & \text{if $n = 1$} \\
\sum_{i=1}^{n-1}( T(i) + B) & \text{else}
\end{cases}
$

For some constant B.

For starters, there are a few ways to prove recursive complexity. Some helpful notes can be found all over. For this problem, we can think about the recursion tree. The root of the tree is the Calc_a(n) call, and it's children are all $n-1$ nodes for each Calc_a(i) call initiated by the original Calc_a(n) call. For each of it's children, we can define the subtree rooted at them in the same manner. Our first step will be to determine how many nodes are in this tree.

Lets for some call Calc_a(n), lets see how many times Calc_a(i) is called for some $i<n$. This is the same as counting all Calc_a(i) nodes in the tree defined above. Let's first notice a pattern.

Calc_a(n-1) is only called once, that is clear.
Calc_a(n-2) will be called by the original Calc_a(n) call as well as the Calc_a(n-1). 2 calls
What about Calc_a(n-3)? Well we have 1 from the original call, and we can see that there will be two calls from Calc_a(n-1), and one more from Calc_a(n-2) 4 calls

Why are there two calls from Calc_a(i-1)? Well, in the previous bullet point we see that for any $i$, Calc_a(i-2) will be called twice for every Calc_a(n). We can use that logic here.

Calc_a(n-4)? We have one from the original call. As we can see in the previous bullet point, there will be 4 resulting calls to Calc_a(n-4) from Calc_a(n-1), 2 from Calc_a(n-2), and 1 more from Calc_a(n-3) 8 calls

Again we use the fact that the previous bullet point showed that there are 4 resulting calls to Calc_a(i-3) from any Calc_a(i) call.

We notice the pattern unfold that any Calc_a(i) is called twice as many times as Calc_a(i+1). Therefore Calc_a(i) is called $2^{n-i-1}$ times.

$$\sum_{i=1}^{n-1}2^{n-i-1}=\sum_{i=0}^{n-2}2^{i}=2^{n-1}$$
(I'm not sure if you're expected to include the original Calc_a(n) call, if you are, just add 1)

Proof Method 1

Now, as far as $T(n)$ goes, we can define it as $T(n)=f(n)+\sum_{i=1}^{n-1}T(i)$ where $f(n)$ is the work done in the function not including the recursive calls. As I'm sure you can tell, this is just a constant, so each node in the work tree does constant work. So we've determined the number of nodes in the tree. This means that the total work of the tree is simply $T(n)\approxeq 2^{n-1}$ or $T(n)=\theta(2^{n-1})$.

You may be wondering why the sum doesn't contribute to the complexity. Well, we could look at the loop and include the sum, then $T(n)=f(n)+\sum_{i=1}^{n-1}(g(i) + T(i))$ where $g(i)$ is the complexity of computing the sum from $T(i)$. However, we can just consider $g(i)$ as a constant as well, since most arithmetic operations can be theoretically considered constant time (this is definitely not always the case, but that is a whole nother topic). Because the constant complexity of the addition is dominated by the complexity of the accompanying $T(i)$ call, we arrive at the same complexity.

Proof Method 2

A more formal method of proving this, and one that may be required (from my experience) on an exam or homework, is to use induction. Generally, the Method 1 above is useful for getting a guess on the complexity. Once you have a good guess, you use induction to prove it, as suggested in the comments below.

Claim: $T(n)=\theta(2^{n-1})$

Base case: $T(1)=1$ (we can also see that $T(2)=2$ and $T(3)=4$) (Notice we are counting the number of calls to Calc_a()

Inductive step
\begin{align*}
T(n+1) & = f(n+1) + \sum_{i=1}^n ( g(i) + T(i)) \\
& =     f(n+1) + \sum_{i=1}^{n-1} (g(i) + T(i)) + (T(n) + g(n)) \\
& =   f(n+1) + T(n) - f(n)+ T(n) + g(n)\\
&  =     2T(n) + g(n) \\
& \leq 2^n+c  \quad \text{for some } c\geq g(n)
\end{align*}
Where the last line follows from the inductive hypothesis and the fact that $g(n)$ is a constant i.e. $g(n)=O(1)$.


Upper bounds for $NP$ based on $NEXP = EXP$ It's open whether $EXP = NEXP \to P = NP$ (the other direction can be shown by padding).  My question: has there been any progress along these lines at all?  For example, can we show that $EXP = NEXP \to NP \subset SUBEXP$ (where $SUBEXP = \cap_{\epsilon > 0} 2^{n^\epsilon}$)?

If someone has demonstrated that $EXP=NEXP\implies NP\subseteq SUBEXP$, then that guy has unconditionally proved a long-sought separation $P^{NP}\subsetneq NEXP$.

Proof: If $EXP\neq NEXP$, then obviously, $P^{NP}\neq NEXP$.

So assuming $EXP=NEXP$, the above statement gives us $NP\subseteq SUBEXP$. We have:

$$P^{SUBEXP}=SUBEXP$$

So, $P^{NP}\subseteq SUBEXP\subsetneq EXP$.$\blacksquare$


What does it mean for a problem to be both NP hard and coNP hard I have a faint notion of what NP hard is (that a problem is legit difficult 3 SAT for example).

I have forgotten what coNP hard, and Wikipedia tells me that the complement of coNP hard is NP hard...not really helping there

Can someone please clarify for me on an intuitive level what does it mean for a problem to be coNP hard? Further, what does it mean for a problem to be both NP hard and coNP hard? What is a problem that illustrate this concept?

Thank you!

A language $L$ is NP-hard if for every language $R$ in NP there exists a function $f$ computable in polynomial time such that for all $x$, $x \in R$ iff $f(x) \in L$.

A language $L$ is coNP-hard if for every language $R$ in coNP there exists a function $f$ computable in polynomial time such that for all $x$, $x \in R$ iff $f(x) \in L$.

If a language is both NP-hard and coNP-hard then its exact complexity lies above both NP and coNP. Indeed, it is conjectured that NP$\neq$coNP, and this implies that a problem which is both NP-hard and coNP-hard belongs to neither NP nor coNP.

Problems which are both NP-hard and coNP-hard do exist. For example, any PSPACE-complete problem is both NP-hard and coNP-hard.


Regular languages closed under prefix operation Suppose that $D$ is a regular language over an alphabet $A$. How can I prove that the following language is also regular?
$$ \mathrm{LANGUAGE}_2(D) := \{ d \mid d,t \in A^* \text{ and } dt \in D \} $$
(This problem is taken from Introduction to the Theory of Computation by Mike Sipser.)

(1) If the regular language is given by a finite state automaton $M$ the language of prefixes can be obtaines by extending the set of accepting states. Choose all states that lie on a path from initial state to one of the original accepting states.
The prefix operation is a special case of the operation quotient
$K/L = \{ x \mid xy\in L, \text{ for some } y\in K\}$
where we take $L$ to be the language $A^*$ of all strings. Surprisingly, the regular languages are closed under quotient by arbitrary languages.
See are regular languages closed under division, and Closure against right quotient with a fixed language.
(2) If the regular language is given by a regular expression instead, then we can construct a new regular expression for the prefix language, directly using the inductive definition of regular expressions. See Regularity of “middles” of words from regular language.
(3) Also, there is a characterization in terms of Myhill-Nerode equivalence classes: a language is regular iff its number of equivalence classes is finite. In can be observed that $x \equiv_L y$ implies $x\equiv_{\text{pref }L} y$, so if $\equiv$ is of finite index, then so is $\equiv_{\text{pref }L}$.
More on this see Myhill-Nerode and closure properties.
(As Yuval noted, the exercise is somewhat standard, but I would like to have some remarks here to close the issue. Feel free to add relevant links.)


Algorithm to minimize distance variance between 2D coordinates I've been looking around for an algorithm that would optimize the distance between 2 list of coordinates and choose which coordinate should go together.

Say I have List 1:

205|200
220|210
200|220
200|180

List 2:

210|200
207|190
230|200
234|190

Calculated Distance between Coords:

205|200 to 210|200 == 5.00
205|200 to 207|190 == 10.20
205|200 to 230|200 == 25.00
205|200 to 234|190 == 30.68

220|210 to 210|200 == 14.14
220|210 to 207|190 == 23.85
220|210 to 230|200 == 14.14
220|210 to 234|190 == 24.41

200|220 to 210|200 == 22.36
200|220 to 207|190 == 30.81
200|220 to 230|200 == 36.06
200|220 to 234|190 == 45.34

200|180 to 210|200 == 22.36
200|180 to 207|190 == 12.21
200|180 to 230|200 == 36.06
200|180 to 234|190 == 35.44

This Algorithm would pick:

205|200 to 230|200 == 25.00
220|210 to 207|190 == 23.85
200|220 to 210|200 == 22.36
200|180 to 234|190 == 35.44

The Algorithm would pick these numbers as they would be the group that would have the littlest variance between the distance.
Conditions:

A Coordinate may only be used ones from each list
If List 1 or List2 is larger than it still only uses each coordinate once, but it tries to get the smallest distance variance and does nothing with the unused coordinates.

If you need more clarification please ask.

P.S. I've looked at the Hungarian algorithm and it seems like it will sort of do the job, but not exactly how I was expecting. The Hungarian algorithm will only try and make the least distance from all the coordinates, which can mean the smallest variance, but not every time as variance is more important here then least distance optimization.

Additional Information

I will have an array of List1, List2, and then the distances:

Distance[List1_item_0][List2_item_0] = 5;
Distance[List1_item_0][List2_item_1] = 10.20;
Distance[List1_item_0][List2_item_2] = 25.00;
Distance[List1_item_0][List2_item_3] = 30.68;

Distance[List1_item_1][List2_item_0] = 14.14;
Distance[List1_item_1][List2_item_1] = 23.85;
Distance[List1_item_1][List2_item_2] = 14.14;
Distance[List1_item_1][List2_item_3] = 24.41;

Distance[List1_item_2][List2_item_0] = 22.36;
Distance[List1_item_2][List2_item_1] = 30.81;
Distance[List1_item_2][List2_item_2] = 36.06;
Distance[List1_item_2][List2_item_3] = 45.34;

Distance[List1_item_3][List2_item_0] = 22.36;
Distance[List1_item_3][List2_item_1] = 12.21;
Distance[List1_item_3][List2_item_2] = 36.06;
Distance[List1_item_3][List2_item_3] = 35.44;

From the Distance['List1_item_#] I would need to pick a distance. Once that distance is picked the [List2_item_#] CANNOT be picked by a different [List1_item_#]. The distances picked for each [List1_item_#] element would need to be picked in a way that the variance between them all is minimal. So distance for each [List1_item_#] should be as close as possible to each other without reusing a [List2_item_#] more than once.

So here is a rather simple approach to solve this problem. You know that there are $O(n^2)$ different distances that matter. You can characterize the solution of your problem by the smallest and the largest distance ($d_\min$,$d_\max$) between your matched points. This gives you a set of $O(n^4)$ candidates.

So suppose you want to test, if there exists a matching where all distances are between $d_\min$ and $d_\max$. In other words, you want to solve the decision problem. This can be modeled as a perfect matching in a bipartite graph. Let $(u_1,\ldots,u_n)$ be the points in the first list and $(v_1,\ldots,v_n)$ be the points in the second list. Consider the bipartite graph that has an edge $(u_i,v_j)$ if and only if the distance between $u_i$ and $v_j$ is contained inside $[d_\min,d_\max]$. If this graph has a perfect matching, then there is an point-to-point assignment for the given distance constraints. Such a test can be done by the Hopcroft-Kahn algorithm, which needs $O(n^{2.5})$. A slightly faster solution can be achieved with fast matrix multiplication.

So you are left with trying out the candidates. This gives a $O(n^{6.5})$ algorithm. You can save a bit of running time by trying out all $d_\min$ values but then do a binary search for each $d_\max$ value. Now you have to solve only $O(n^2 \log n)$ decision problems (you also have to sort all distances, which is dominated by the overall running time) and hence the running time is only $O(n^{4.5}\log n)$.


The language of machines that accepts all palindromes is not Turing recognizable I have this question:

  $L = \{\langle M \rangle | M$ is TM that accepts every palindrome over
  its alphabet $\}$

  Proof that $L$ is not Turing-recognizable by showing reduction from other non Turing-recognizable language.

What I have tried to do is to show reduction from $A_{TM}$ (Accept problem) to $\bar L$, and I didn't succeed to show one. I tried to create a new machine that will reject some palindrome(s) if $M$ accepted $w$ when $\langle M,w\rangle$ is the input of $A_{TM}$. But if $M$ will not halt on $w$, then the palindrome(s) will reject also by mistake.

So how can I show reduction from $A_{TM}$ to $\bar L$ (or $\bar {A_{TM}}$ to $L$)?

Let $M_p$ be a TM that decides palindromes with runtime on $x$ at least $|x|$. Given $\langle M \rangle$ construct $\langle M' \rangle$ where $M'$ on $x$ behaves as follows:

Run $M$ on $\langle M \rangle$ and $M_p$ on $x$ in "parallel" (i.e. step by step, on separate cells, e.g. $M$ only uses odd cells, and $M_p$ uses only even cells of the tape).
If $M$ on $\langle M \rangle$ terminates, $M'$ rejects unconditionally.
If $M_p$ on $x$ terminates and $M$ on $\langle M \rangle$ is still continuing the computation at this step, $M'$ terminates the simulation of $M$ and outputs according to $M_p$ on $x$.

Note that $M$ on $\langle M \rangle$ does not halt if and only if $M'$ decides the language of palindromes. (Why?)


How to prove that concatenating a language A and A* is commutative? Suppose we have a language $A$. I want to prove that $AA^*$ is commutative. I know that this expression equals $A^+$, but I'm not sure how to go about a proof yet. This is my attempt so far.
If $A$ is a language, then
\begin{align*}
AA^* & = A(A^0\cup A^1\cup\cdots) \tag{Definition of $A^*$}\\
     & = A^1\cup A^2\cdots        \tag{Distributive law}   \\
     & = (A^0\cup A^1\cup\cdots)A \tag{Distributive law}  \\
     & = A^*A.
\end{align*}
Is this enough? I'm thinking that in order for it to be a proper proof, I have to show that $AA^*$ and $A^*A$ are subsets of each other. That is, take an element $s = xy$ where $x\in A$ and $y\in A^*$ and show that $x\in A^*$ and $y\in A$ (and vice versa). However, I get stuck very early when doing that method.

$AA^*$ is the set of all strings consisting of a string in A, followed by zero or more strings in A, which means all strings consisting of one or more strings in A. $A^*A$ is the set of all strings consisting of zero or more strings in A, followed by one string in A, which also means all strings consisting of one or more strings in A. So both are the same.


Definition and example of search problem I searched the pages a lot about the search problem but didn't understand much, so please make it clearer for me.
WIKIPEDIA:

In computational complexity theory and computability theory, a search problem is a type of computational problem represented by a binary relation. If R is a binary relation such that field(R) ⊆ Γ+ and T is a Turing machine, then T calculates R if:
If x is such that there is some y such that R(x, y) then T accepts x with output z such that R(x, z) (there may be multiple y, and T need only find one of them)
If x is such that there is no y such that R(x, y) then T rejects x

If anyone can explain it to me easily and give a few examples, it will help me a lot.

Here is an example of a search problem:

  Given a CNF $\varphi$, find a satisfying assignment $x$.

Every satisfying assignment would do. A machine solves this problem if on input $\varphi$:

If $\varphi$ is satisfiable, then the machine outputs a satisfying assignment.
If $\varphi$ is unsatisfiable, then the machine outputs "unsatisfiable".

An important class of search problems are those that always have solutions. Here is a canonical example:

  Given an unsatisfiable CNF $\varphi$ and an assignment $x$, find a clause not satisfied by $x$.

Note that since $\varphi$ is unsatisfiable, for every assignment there is a clause which $x$ doesn't satisfy. A machine solves this problem if given $\varphi$ and $x$, it outputs a clause of $\varphi$ unsatisfied by $x$.


Create binary numbers with a described pattern I am looking for an algorithm that can create binary numbers following certain patterns. Let $n$ be the size; and assume that is a power of 2. Let $E$ be the exponent; $n = 2^E; k = \log n$. The $0, 1$ on the "top level" are symbols, and let $0^n, 1^n$ represent $n$ consecutive zeroes and ones respectively.

For size 2, $E = 1$, and the one number is given by $0^1 1^1 = 01$.

For size 4, $E = 2$, and the two numbers are $0^2 1^2 = (0^2 1^2)^1 = 0011$ and $(0^1 1^1)^2 = 0101$.

For size 8, $E = 3$, and the three numbers are $(0^4 1^4)^1 = 00001111$, $(0^2 1^2)^2 = 00110011$, $(0^1 1^1)^4 = 01010101$.

For size $n = 2^E$, the $E$ numbers include $(0^1 1^1)^{n/2} = (0^{2^0} 1^{2^0})^{2^{E-1}}$ to $(0^{n/2} 1^{n/2})^1 = (0^{2^{E-1}} 1^{2^{E-1}})^{2^{0}}$. Thus, the $E$ numbers can be parameterized by a natural number $k$ from 0 to $E-1$ such that the member is expressible as $(0^{2^k} 1^{2^k})^{2^{(E-1)-k}}$.

Is there an algorithm using bit manipulation that can generate each of these numbers in the set with algorithm in the range of $O(1)$ to $O(n)$?
Important Note: I am looking for an algorithm that generates binary numbers not strings unless transformation from strings to binary numbers can be in the range of $O(1)$ to $O(n)$.

Let $n$ be the size; and assume that is a power of 2. Let $E$ be the exponent; $n = 2^E; k = \log n$. The $0, 1$ on the "top level" are symbols, and let $0^n, 1^n$ represent $n$ consecutive zeroes and ones respectively.

For size 2, $E = 1$, and the one string is given by $0^1 1^1 = 01$.

For size 4, $E = 2$, and the two strings are $0^2 1^2 = (0^2 1^2)^1 = 0011$ and $(0^1 1^1)^2 = 0101$.

For size 8, $E = 3$, and the three strings are $(0^4 1^4)^1 = 00001111$, $(0^2 1^2)^2 = 00110011$, $(0^1 1^1)^4 = 01010101$.

For size $n = 2^E$, the $E$ strings include $(0^1 1^1)^{n/2} = (0^{2^0} 1^{2^0})^{2^{E-1}}$ to $(0^{n/2} 1^{n/2})^1 = (0^{2^{E-1}} 1^{2^{E-1}})^{2^{0}}$. Thus, the $E$ strings can be parameterized by a natural number $k$ from 0 to $E-1$ such that the member is expressible as $(0^{2^k} 1^{2^k})^{2^{(E-1)-k}}$.

Thus, the examples are:

Size 2: $E = 1$. The one string is $(0^1 1^1)^1 = (0^{2^0}1^{2^0})^{2^0}$

Size 4: $E = 2$. The two strings are $0101 = (0^1 1^1)^2 = (0^{2^0} 1^{2^0})^{2^1}$ and $0011 = (0^2 1^2)^1 = (0^{2^1} = 1^{2^1})^{2^0}$.

Size 8: $E = 3$. The three strings are $01010101 = (0^{2^0} 1^{2^0})^{2^2}$ with $k = 0$, $00110011 = (0^{2^1} 1^{2^1})^{2^1}$ with $k = 1$, $00001111 = (0^{2^2} 1^{2^2})^{2^0}$ with $k = 2$.

This is an iterative algorithm. You list each string, of length $n$ a total of $\log n$ times. It is $O(n \log n)$ to list all the strings explicity. It is $O(\log n)$ to express them regex style like $(0^x 1^x)^y$ [note $x, y$ are powers of 2, and the exponents in the power form of $x, y$ add up to $E-1$].


If A is polynomial time reducible to B and B is in NP, then A is in NP If $A\leq_p B$ and $B$ is in $NP$, is it true that $A$ is in $NP$?

What about : "if $A\leq_p B$ and $B$ is in $coNP$, then $A$ is in $coNP$"?

Thanks in advance.

I think both hold. If $B$ is in $NP$, then the yes-instances of $B$ can be verified in polynomial time. If $A \leq_p B$, I can "translate" an instance of $A$ to a instance of $B$. Then I can use the verification algorithm for $B$ to check the yes-instances of $A$. The same should be valid for the second affirmation. I'm not sure though.

I think both hold too.

Co-NP version:some Problem A reduce to B,

if B is co-NP,$\overline{B}$ is in NP,and no-instance of B has some verify way and certificate bit. and A's no-instance can use it too.

So this A is complement of NP problem $\overline{A}$. this means complexity class of A is co-NP.


Greedy algorithms: Minimum sum number pairing Given $n$ real numbers (where $n$ is even) find a pairing which minimizes the maximum sum of a pair.

I think the optimal pairing is obtained by sorting the original set, pairing the first element with the last one, and so on. But I get stuck trying to prove it.

I tried use the "difference reduction method", examining differences between an optimal answer and the "greedy" answer, and trying to get the greedy from the optimal without losing optimality, but I didn't reach anything. Any idea?

Suppose that numbers are $x_1, \ldots x_{2n}$, and let us rename them as $a_1, \ldots a_n, b_1, \ldots, b_n$, where $a_i \geq b_j$ for any $i, j$, $a_1 \geq a_2 \geq \ldots \geq a_n$, and $b_1 \leq b_2 \leq \ldots \leq b_n$. In this notation, the suggested optimum solution is $(a_1, b_1), \ldots (a_n, b_n)$.

Given some arbitrary pairing, let us show we can reduce it to the right pairing without increasing the maximum sum of a pair. This shows that the expected correct solution is at least as good as any other. Equality might hold, eg. if all the values are the same, then any pairing is the joint best.

First suppose that there is some pair $(a_u, a_v)$. Then since there are an equal number of $a$'s and $b$'s, there must also be some pair $(b_s, b_t)$. Clearly $a_u + a_v \geq b_s + b_t$, furthermore $a_u + a_v \geq a_u + b_s$ and similarly $a_u + a_v \geq a_v + b_t$. So if we replace the pairs $(a_u, a_v), (b_s, b_t)$ by $(a_u, b_s), (a_v, b_t)$, we have reduced the maximum sum of a pair, or at worst kept it the same.

So now assume that our pairing is of the form $(a_{i_1}, b_{i_1}), \ldots (a_{i_n}, b_{i_n})$, but that it's not $(a_1, b_1), \ldots (a_n, b_n)$. There must be at least one pair of pairs, $(a_j, b_k)$ and $(a_l, b_m)$, where $j < l$ but $k > m$. (Otherwise, the $b$'s are in the same order as the $a$'s, which means it's the suggested solution.)

This means that $a_j \leq a_l$ and $b_k \leq b_m$. So $a_l + b_m \geq a_j + b_k$, also $a_l + b_m \geq a_j + b_m$, and similarly $a_l + b_m \geq a_l + b_k$. So $(a_l, b_m)$ must be the bigger of $(a_j, b_k), (a_l, b_m)$, and replacing those two pairs with $(a_l, b_k), (a_j, b_m)$ can only reduce the maximum (or keep it the same).

This shows that whatever pairing we start out with, we can swap pairs until we reach the suggested solution, without making the maximum sum any bigger. So the suggested solution must be the best.

I believe you could collapse the two steps into a single argument since both are very similar and rely on showing that two pairs can be 'flipped' without making the maximum sum any bigger. However I find it easier to imagine in two stages.


Secondary Storage in Von Neumann Achitecture For an assignment, I need to draw a diagram of Von Neumann architecture, and explain each part of it.

All the diagrams and explanations I've seen have a distinct "Memory" block that holds both the code and the program data of running processes. What I can't find information on however is if this memory refers to only primary memory (like RAM), or if it also includes secondary memory (like a SSD or HDD).

Does Von Neumann Architecture specifically refer to only primary memory, or does it also include secondary storage?

I'd also like to know if I'm using any terminology incorrectly above.

The von Neumann architecture concerns only memory and CPU, not peripherals or devices.  Storage, such as a hard disk or SSD, is typically a device, and thus is outside the scope of what's normally shown in the von Neumann architecture.  Thus, in a picture of the von Neumann architecture, the block labelled "memory" should be understood to refer to RAM -- not hard disk or SSD.

In particular, in the von Neumann architecture, the CPU can access memory through a bus (the memory bus).  In real computers, typically the memory bus cannot be used to read or write the hard drive; there's a separate path for accessing devices like the hard drive.  (That's from the perspective of the architecture/hardware level.  However, the lines can admittedly start to get blurred a bit from the user application's perspective, given memory-mapped devices, virtual memory, and demand paging.)