Relation of Space and Time in Complexity? I'm looking for some clarification on some concepts/facts I came across while studying for a class.

I was reading the following wikipedia article. The below specific section and statement intrigued me when looking it over.

http://en.wikipedia.org/wiki/Computational_complexity_theory#Important_complexity_classes
"It turns out that PSPACE = NPSPACE and EXPSPACE = NEXPSPACE by Savitch's theorem"

I also read that NTMs can be simulated by DTMs but that the shortest accepting computation of the DTM is exponential with respect to the shortest accepting computation of the target NTM.

My questions are:

1.) Are PSPACE and NPSPACE the set of all problems that require at least polynomial space to be solved on Deterministic and Non-deterministic Turing machines respectively?

2.) If so, is the actual size of the polynomial space required dependent on the size of the input?

3.) For P and NP, they are each the sets of problems that require at least polynomial time to be solved on DTMs and NTMs respectively correct?

4.) Is the reason that the shortest accepting computation of a DTM simulating a target NTM is exponential with respect to the shortest accepting computation of an NTM due to the exponential explosion of the number of configurations that an NTM supports as input grows for a given problem?

5.) My last and overarching question is: Are the differences in the set of problems that can be solved in polynomial time on DTMs versus NTMs related to time/space tradeoffs where DTMs can't run some polynomial NTM algorithms in polynomial time because they don't have the same "space" that an NTM has available to it?

I'd also appreciate any reading you can suggest to me on time/space tradeoffs and NTMs versus DTMs.

That's rather a lot of questions for one Stack Exchange post.  One or two closely related questions per post is best. But here goes...

  1.) Are PSPACE and NPSPACE the set of all problems that require at least polynomial space to be solved on Deterministic and Non-deterministic Turing machines respectively?

No. They're the set of all problems that require at most polynomial space to be solved on deterministic and nondeterministic Turing machines, respectively.

  2.) If so, is the actual size of the polynomial space required dependent on the size of the input?

No. For any given machine, the polynomial is fixed. The input to the polynomial is the length of the input.  (E.g., if the machine runs in space $3n^2+4$ and the input has length 3, the Turing machine will need at most 31 cells of storage on its work tape.)

  3.) For P and NP, they are each the sets of problems that require at least polynomial time to be solved on DTMs and NTMs respectively correct?

Again, at most.

  4.) Is the reason that the shortest accepting computation of a DTM simulating a target NTM is exponential with respect to the shortest accepting computation of an NTM due to the exponential explosion of the number of configurations that an NTM supports as input grows for a given problem?

We don't know for sure that there's any loss of efficiency at all when simulating a nondeterministic machine on a deterministic one. But the reason we don't know how to do it with better than exponential slowdown is, as you suggest, that we don't know any better technique than trying all the possible nondeterministic choices, one by one.

  5.) My last and overarching question is: Are the differences in the set of problems that can be solved in polynomial time on DTMs versus NTMs related to time/space tradeoffs where DTMs can't run some polynomial NTM algorithms in polynomial time because they don't have the same "space" that an NTM has available to it?

Not really. It's because the nondeterministic machine in a sense computes lots of options in parallel and it accepts if any of those parallel options accepts. As I said above, the only way we know how to simulate all of these parallel computations is to do them sequentially, one after another. But there isn't any particular time/space trade-off: if a nondeterministic machine makes some computation in time $t(n)$ and space $s(n)$, a deterministic machine can do the same computation in time $2^O(t(n))$ and space $s(n)+O(t(n))$. The exponential blow-up in time is because a $q$-state nondeterministic machine might make up to $q$ nondeterministic choices (i.e., spawn up to $q$ "parallel threads") at each step of its execution; the smaller increase in space is because of the book-keeping required to keep track of which choices we tried at each step.


insertion sort basic computation steps Here is insertion sort:

for i = 1 to length(A)
    x = A[i]
    j = i - 1
    while j >= 0 and A[j] > x
        A[j+1] = A[j]
        j = j-1
    end while
    A[j+1] = x
end for

My lecture notes say that the total number of basic computation steps is about

$$T = 1 + ( 5 + t_1 \times 3 ) + \dots + ( 5 + t_{n-1} \times 3 )\,,$$

where $t_i$ represents how many times the inner loop needs to run (anything between $0$ and $i$). $5$ for the basic operations in the outer loop, and $1$ for testing whether to enter the outer loop.

I understand the "1" and the "5" but not the "3". Because I think $t_i$ is not always anything between $0$ and $i$? Like say a number needs to move from position $5$ to position $1$, it repeats the inner loop meaning there will be more steps? The steps in the inner loop can possibly repeat for $n-1$ times?

So what is the basic computation steps?

You asked why the "3" is there in that equation.  Here's the explanation.

$t_i$ counts the number of iterations of the inner loop, for a particular value of $i$.  Each iteration executes 3 instructions (3 steps).  Therefore, the total number steps of computations consumed by the inner loop, for a particular value of $i$, is $3 \times t_i$.


run time analysis of a for loop I am trying to prepare for a test comping up on run-time analysis.  I have been hit with a for loop that is throwing me a bit.  I am hoping someone can help me.

the loop is

for(j=1; j< n; j=j*2)

J is increasing at an increasing rate so it will be less than n/2  however I am having trouble concluding what exactly it will be.

In your loop, $j$ will take the values $1, 2, 4, 8, \dotsc, 2^k$ where $2^k<n$. You need to know how many times this will iterate. In other words, what will be the largest $k$ for which we have $2^k < n$? Take the log to the base 2 of each side of the inequality and you're asking what the largest $k$ will be for which $k<\log_2n$. What this means is that you're right in your comment: the loop will iterate no more than $\log_2n$ times.


swapping between sorting algorithms for small input size left over Is it suggested to swap between sorting algorithms? Merge sort certainly performs better on large input size however Insertion sort performs better on small input size

  Analysis based on there graph comparison of running time of Insertion sort and merge sort

How often people swap the algorithms they are using? For example sorting problem of size 100K with merge sort and then switching to insertion sort when problem size reached to 500 input size?

Is is advisable to follow such techniques? For small input size the constants(c) does matter and insertion sort having small constant size than merge sort will certainly perform better. I guess

People don't usually program their own sorting routines, and I would advise against it, unless you're implementing a non-comparison-based sort such as counting sort. Library sorting routines are optimized beyond what the casual programmer can achieve.

If you're interested in the best practices of the field, you'll have to look at library sorting routines. For example, python uses Timsort, which switches to insertion sort for small arrays. The GNU implementation of Quicksort also switches to insertion sort for small arrays. So it seems switching to insertion sort for small arrays is indeed advisable.


Clarification on interplay between cache line size and read/write sizes Say that you have cache lines with the size of 64 bytes and a set-associative or directly mapped cache. Let's also say that the word size is 8 bytes.

According to my understanding, we use a number of the most significant bits of a memory address in order to determine where in the cache to place the data. Am I correct in believing that, if I want load data starting from, for example, address 30, then all data starting from address 0 to 63 will be loaded into a cache line? Or will all data from address 30 to 93 be loaded?

If the former is the case, I assume that, if an instruction to load 16 bytes from address, say, 60, then this forces us to load two 64 byte cache lines (one line 0-63 and another 64-127). Is that correct or have I misunderstood something? Also, is this something that often occurs or are there reasons for why that isn't the case?

Cache lines always start at a byte address that is a multiple of the cache size, like 0, 64, 128 etc. If you need 8 bytes starting at byte 30, then the cache line containing bytes 0 to 63 will be loaded.

If you need 8 bytes starting at byte 60, then you need bytes from two cache lines, so the cache line from byte 0 to 63 is loaded, then the line from byte 64 to 127. (Since this is more complicated, it very much depends on the CPU how long this will take, usually anything from "a little bit longer" to "a lot longer". Compilers will usually try to align data to minimise the cost of data straddling cache lines).

Sometimes the cache line size is bigger than the amount of bytes that can be read from RAM in one operation (say 64 byte vs 32 bytes). Some CPUs can then read the "right" 32 bytes first and deliver the data to the CPU, while the rest of the cache is being loaded. So if you want bytes 40..47 the CPU may be able to load bytes 32..63 first, then give the 8 bytes to the CPU while loading the second half.


Complexity of $Ax\geq 0$ May be it's a stupid question (sorry if it's the case).

What is the complexity the decision problem:

Input: $A\in\mathcal{M}_{n,m}(\mathbb{Z})$

does there exists $x\in\mathbb{N}^n,x>0$ such that $Ax\geq 0$?

Where $x\geq 0$ means for all $x_i\geq 0$ and $x>0$ means there exists $x_j>0$.

I know that integer linear programming is NP-complete but it's expressed has $Ax\leq b$ and I failed to reduce $Ax\leq b$ to $Ax\geq0$ ...

Your problem is in polynomial time, as the following claim implies.

Claim Let $A$ be an $m\times n$ matrix with rational entries. There exists an integer $x > 0$ such that $Ax \geq 0$ if and only if there exists a real $x > 0$ such that $Ax \geq 0$.

Proof The forward implication is trivial. For the backward implication, suppose that there exists a real $x > 0$ such that $Ax \geq 0$. In particular, the polytope $P = \{ x \geq 0 : Ax \geq 0 \text{ and } \sum x = 1 \}$ is non-empty. Pick some vertex $x$ of $P$. Since all entries of $A$ are rational, all coordinates of $x$ are also rational. Therefore for some integer $N>0$, all entries of $Nx$ are integral. Furthermore $Nx > 0$ and $A(Nx) = N(Ax) \geq 0$. $\square$

Given a matrix $A$, in order to determine whether there exists a real $x > 0$ such that $Ax \geq 0$, check whether the polytope $P = \{ x \geq 0 : Ax \geq 0 \text{ and } \sum x = 1 \}$ is non-empty using linear programming. This can be done in polynomial time.


A number of points on a line, with initial positions and speeds - find a minimum time that any two points meet How can I compute the minimum time for two points to meet in $O(N)$ time?

All I can think is to compute the time for all the point pairs and get the minimum.

Can anyone give me some hints?

I'm assuming we're given an ordered list $(y_0,y_1,...,y_{n-1})$ of initial point positions together with a list $(s_0,s_1,...,s_{n-1})$ of their speeds.

You can visualize moving points on a Cartesian plane with "position" and "time" coordinate axes - so the point $P_i$ trace will be a ray $R_i$, beginning at the point $(0,y_i)$ and consisting of points $(t, y_i+s_it)$ for $t\ge0$. If points $P_i$ and $P_j$ meet at some time $t$ then their corresponding rays $R_i$ and $R_j$ will intersect, and their intersection point will be $(t,y)$ - we'll call this time $t$ a meeting time.

Observation. If an intersection point $(t,y)$ for two rays $R_i$ and $R_j$ has a minimal meeting time $t$ among all the pairs $(i,j)$ where $i\lt j$, then $i=j-1$ (in other words - points $P_i$ and $P_j$ were initially neighbor ones - try to prove that).

So, it means that you can look for minimal meeting time among pairs of neighbor points only - their total number is $O(n)$, and the algorithm time is also linear. If the original list of points is not ordered by their coordinates, then the algorithm time will include sorting, which is $O(n\log(n))$.


Is time complexity of the greedy set cover algorithm cubic? I claim that the greedy algorithm for solving the set cover problem given below has time complexity proportional to $M^2N$, where $M$ denotes the number of sets, and $N$ the overall number of elements.

Question: true or false?

Approximation Algorithms, Vazirani, 2001, 1e, p.16, Algorithm 2.2:

  $C \leftarrow \varnothing$
  While $C \neq U$ do
   Find the set whose cost-effectiveness is smallest, say $S$.

  Let $\alpha = \frac{c(S)}{|S - C|}$, i.e., the cost-effectiveness of
  $S$.

  Pick $S$, and for each $e \in S - C$, set $\text{price}(e) = \alpha$.

  $C \leftarrow C \cup S.$

  Output the picked sets.

In the first iteration, the cost-effectiveness of $M$ sets have to be computed.

In the second iteration, the cost-effectiveness of $M-1$ sets have to be computed.

Since everything between $1$ and $M$ iterations may be needed to find the sets that cover all elements, in the mean it may be $M/2$ iterations.

I.e. in the worst case we need to compute $M + (M-1) + (M-2) + ... + 1 = M(M+1)/2$ times the cost effectiveness.

Determining cost-effectiveness requires the computation of a difference which has time complexity proportional to the number of elements.

Hence, the time complexity is dominated by the term $M^2N$.

EDIT

If the greedy algorithm outlined above does not have time complexity of $M^2N$, where's the flaw in estimating the computation time?

The following diagram shows the computation time per atomic operation versus the test index of 65 tests I ran my code on. The tests range from 6 sets to 1215 sets, and the values on the y-axis are computed as

$$
\text{computation time per atomic operation} = \text{cpu time used} / (M^2N).
$$

From what I can tell, the assumed time complexity $M^2N$ seems to model the behavior well. Otherwise, the computation time per atomic operation wouldn't be that stable. Small values for the y-axis are either due to the computation time being too short to be measured, or if the number of elements is substantially smaller than the number of sets ($N \ll M$).

EDIT (Sun APR 19 2020)

This post cites exercise 35.3-3 taken from Introduction to Algorithms (3e) claiming that the (unweighted) set cover problem can be solved in time

$$
\mathcal{O}\left(\sum_{S \in \mathcal{F}}|S|\right),
$$

where $S$ is a set of the problem description, and $\mathcal{F}$ are all the sets in the problem description.

Compared to the naming convention I'm using, this would mean that the problem can be solved in quadratic time $\mathcal{O}(MN)$. But how?

The algorithm still requires to find the set with the maximum number of elements involved, which requires to evaluate every set modulo the recently added one. Hence,

$$
M + (M - 1) + ... + 1 = (M + 1)M / 2,
$$

which is quadratic in $M$ again.

Or is there a more efficient way to do so?

EDIT (Mon APR 20 2020)

My initial estimate of $\mathcal{O}(M^2N)$ does not seem to be that bad. Refering to Introduction to Algorithms (3e), page 1119, last paragraph of section A greedy approximation algorithm, it is said

  a simple implementation runs in time
  $\mathcal{O}(|X||\mathcal{F}|\min(|X|, |\mathcal{F}|))$

where $|X|$ is the overall number of elements, and $|\mathcal{F}|$ reflects the overall number of sets.

Dividing the cpu time by this new upper bound, the variance of the time per atomic operation is clearly smaller compared to the upper bound used initially:

Acc. to Introductions to Algorithms (3e), given a "simple implementation" of the above given greedy set cover algorithm, and assuming the overall number of elements equals the overall number of sets ($|X| = |\mathcal{F}|$), the code runs in time $\mathcal{O}(|X|^3)$. So there are cases when the algorithm behaves cubic.


Is there an efficient solution to the travelling salesman problem with binary edge weights? Is there a way to solve TSP in polynomial time if there are only two kinds of weights, 0 and 1?

No, since if every edge has weight 1, there is still the question of whether any such tour exists, which is the Hamiltonian Cycle problem, and this is still NP-hard.  (The link is to a Wikipedia page for Hamiltonian Path -- both the path and cycle versions of the problem are hard.)


Algorithm for factoring elements of permutation groups? You can solve a Rubik's cube by factoring its permutation into a sequence of "elementary" permutations (a subset of permutations that is sufficient to construct every other permutation in the group). There are several algorithms for solving Rubik's cubes. Are there any algorithms for the general problem of factoring permutations?

It seems that your problem could be stated in terms of finding paths in Cayley Graphs, which might interest you:

Cayley Graph - Wikipedia


Counting binary trees (I'm a student with some mathematical background and I'd like to know how to count the number of a specific kind of binary trees.)

Looking at Wikipedia page for Binary Trees, I've noticed this assertion that the number of rooted binary trees of size $n$ would be this Catalan Number:
$$C_n = \dfrac{1}{n+1}{2n \choose n}$$

But I don't understand how I could come up with such a result by myself? Is there a method to find this result?

Now, what if the order of sub-trees (which is left, which is right) is not considered? For example, from my point of view, I consider that these two trees are the same:

   /\   /\
  /\     /\

Would it be possible to apply a similar method to count how many of these objects have exactly $n$ nodes?

For counting many types of combinatorial objects, like trees in this case, there are powerful mathematical tools (the symbolic method) that allow you to mechnically derive such counts from a description how the combinatorial objects are constructed. This involves generating functions.

An excellent reference is Analytic Combinatorics by the late Philipe Flajolet and Robert Sedgewick. It is available from the link above.

The late Herbert Wilf’s book generatingfunctionology is another free source.

And of course Concrete Mathematics by GKP is a treasure trove.

For binary trees it goes like this: First you need a clear definition of the tree.

A binary tree is a rooted tree in which every non-leaf node has degree 2 exactly.

Next we have to agree what we want to call the size of a tree.

On the left all nodes are equal. In the middle we distinguish the leaves and non-leaves. On the right we have a pruned binary tree where the leaves have been removed. Notice that it has unary branches of two types (left and right)!

Now we have to derive a description of how these combinatorial objects are built. In the case of binary trees a recursive decomposition is possible.

Let $\mathcal{A}$ be the set of all binary trees of the first type then symbolically we have:

It reads as: “An object of the class of binary trees is either a node or a node followed by two binary trees.” This can be written as equation of sets:

$$\mathcal{A}=\{\bullet\}\cup\bigl(\{\bullet\}\times\mathcal{A}\times\mathcal{A}\bigr)$$

By introducing the generating function $A(z)$ that enumerates this class of combinatorial objects we can translate the set equation into an equation involving the generating function.

$$A(z)=z+zA^2(z)$$

Our choice of treating all nodes equally and taking the number of nodes in the tree as notion of its size is expressed by “marking” the nodes with the variable $z$.

We can now solve the quadratic equation $zA^2(z)-A(z)+z=0$ for $A(z)$ and get, as usual, two solutions, the explicit closed form of the generating function:

$$A(z)=\frac{1\pm\sqrt{1-4z^2}}{2z}$$

Now we simply need Newton’s (generalized) Binomial Theorem:

$$(1+x)^a=\sum_{k=0}^\infty\binom{a}{k}x^k$$

with $a=1/2$ and $x=-4z^2$ to expand the closed form of the generating function back into a power series. We do this because, the coefficient at $z^n$ is just the number of combinatorial objects of size $n$, typically written as $[z^n]A(z)$. But here our notion of “the size” of the tree forces us to look for the coefficient at $z^{2n+1}$. After a little bit of juggling with binomials and factorials we get:

$$[z^{2n+1}]A(z)=\frac{1}{n+1}\binom{2n}{n}.$$

If we start with the second notion of the size the recursive decomposition is:

We get a different class of combinatorial objects $\mathcal{B}$. It reads: “An object of the class of binary trees is either a leaf or a interal node followed by two binary trees.”

We can use the same approach and turn $\mathcal{B}=\{\square\}\cup\bigl(\{\bullet\}\times\mathcal{B}\times\mathcal{B}\bigr)$ into $\mathcal{B}=1+zB^2(z)$. Only this time the variable $z$ only marks the internal nodes, not the leaves, because the definition “the size“ is different here. We get a different generating function as well:

$$B(z)=\frac{1-\sqrt{1-4z}}{2z}$$

Extracting the coefficient yields

$$[z^n]B(z)=\frac{1}{n+1}\binom{2n}{n}.$$

Class $\mathcal{A}$ and $\mathcal{B}$ agree on the counts, because a binary tree with $n$ internal nodes has $n+1$ leaves, thus $2n+1$ nodes in total.

In the last case we have to work a little harder:

which is a description of non-empty pruned binary tries. We extend this to
$$\begin{align}\mathcal{C}&=\{\bullet\}\cup\bigl(\{\bullet\}\times\mathcal{C}\bigr)\cup\bigl(\{\bullet\}\times\mathcal{C}\bigr)\cup\bigl(\{\bullet\}\times\mathcal{C}\times\mathcal{C}\bigr)\\\mathcal{D}&=\{\epsilon\}\cup\bigl(\{\bullet\}\times\mathcal{C}\times\mathcal{C}\bigr)\end{align}$$

and rewrite it with generating functions

$$\begin{align}C(z)&=z+2zC(z)+zC^2(z)\\D(z)&=1+zC^2(z)\end{align}$$

solve the quadratic equations

$$\begin{align}C(z)&=\frac{1-2z-\sqrt{1-4z}}{2z}\\D(z)&=\frac{1-\sqrt{1-4z}}{2z}\end{align}$$

and get yet again

$$[z^n]C(z)=\frac{1}{n+1}\binom{2n}{n}\quad n\ge1 \qquad [z^n]D(z)=\frac{1}{n+1}\binom{2n}{n} \quad n\ge0$$

Note that the Catalan generating function is

$$E(z)=\frac{1-\sqrt{1-4z}}{2}$$

it enumerates the class of general trees. That is the trees with no restriction on the node degree.

$$\mathcal{E}=\{\bullet\}\times\mathrm{SEQ}(\mathcal{E})$$

It reads as: “An object of the class of general trees is a node followed by a possible empty sequence of general trees.”

$$E(z)=\frac{z}{1-E(z)}$$

With the Lagrange-Bürmann Inversion Formula we get

$$[z^n]E(z)=\frac{1}{n+1}\binom{2n}{n}$$

So we proved that there are as many general trees as there are binary trees. No wonder there is a bijection between the general and binary trees. The bijection is known as the rotation correspondence (explained at the end of the linked article), that allows us two store every general tree as a binary tree.

Note that if we do not distinguish the left and right sibling in class $\mathcal{C}$ we get yet another class of trees $\mathcal{T}$:

the unary binary trees.
$$\mathcal{T}=\{\bullet\}\times\mathrm{SEQ}_{\le2}(\mathcal{T})$$
They have a generating function too
$$T(z)=\frac{1-z-\sqrt{1-2z-3z^2}}{2z}$$
however their coefficient is different. You get the Motzkin numbers
$$[z^n]T(z)=\frac{1}{n}\sum_k\binom{n}{k}\binom{n-k}{k-1}.$$

Oh and if you don’t like generating functions there are plenty of other proofs too. See here, there is one where you could use the encoding of binary trees as Dyck words and and derive a recurrence from their recursive definition. Then solving that recurrence gives the answer too. However the symbolic method saves you from coming up with the recurrence in the first place, as it works directly with the blueprints of the combinatorial objects.


Definitions of: virtual address space, page size (I can't seem to find actual definitions of these terms anywhere, only hints and guesses).

Is it fair to say, that:

Virtual address space is the amount of bytes that can fit into RAM cells of all virtual addresses belonging to this virtual address space (virtual address space HAS MANY pages HAS MANY virtual addresses).
Page is a set of virtual addresses (and it maps to the frame - a set of actual physical RAM addresses). Size of a page = amount of bits that can fit into this page. So, if the system is byte-addressable (meaning one RAM cell can hold 8 bits), page size is 8 * number of RAM addresses in a page.

Wikipedia defines a virtual address space as follows:

  In computing, a virtual address space (VAS) or address space is the
  set of ranges of virtual addresses that an operating system makes
  available to a process.

This definition is OK. However, I'll define the term "virtual address space" one word at a time.

  space

space is a mathematical term that generally means a set of things, where these things are potentially related in one or more ways.

  address

An address is generally an identifier for a thing, which is distinct from the thing itself. In this context, an address is a value that potentially identifies a physical device in the computer system. Typically, addresses are non-negative integers that identify memory locations that can hold data, and each address is represented as a constant number of binary digits.

  virtual

Virtualization means to create an interface for something that is different from its actual interface that is built with the thing. This is useful for many reasons such as managing a resource for multiple users or providing protection for a resource from being misused or corrupted.

Now let's put it all together. A virtual address space is a set of addresses created by the virtualization system (the OS) to allow an application to access system resources indirectly so that the system can control access to its resources.

  Virtual address space is the amount of bytes that can fit into RAM
  cells of all virtual addresses belonging to this virtual address space
  (virtual address space HAS MANY pages HAS MANY virtual addresses).

A VAS is not a single number (although it can be a set that contains a single address). Also a VAS is not memory itself; it does not store anything because it can't. Moreover, given only a VAS, you can only determine how many virtual addresses you have, but not how much memory you can use. you can have a 4 GB VAS, but zero physical memory locations. That's because of virtualization. That's what makes it virtual. It's up to the OS that creates it. Also the term "page" is independent from the term "virtual address space" in general. Although the OS can choose to partition the VAS into virtual pages, where each virtual page is a sub-set of the VAS.

  Page is a set of virtual addresses (and it maps to the frame - a set
  of actual physical RAM addresses).

Yes. Although a virtual page may not map to anything (invalid).

  Size of a page = amount of bits that can fit into this page. So, if
  the system is byte-addressable (meaning one RAM cell can hold 8 bits),
  page size is 8 * number of RAM addresses in a page.

Yes. When a virtual address space is said to be byte-addressable it means that each virtual address (an identifier) can identify an 8-bit resource (typically, physical memory cells). When a physical address space is said to be byte-addressable it means that each (valid) physical address (an identifier) does identify an 8-bit physical resource (typically memory cells).


Do all greedy algorithm produce just the first solution, no matter how bad it is? In all the exampls of the greedy algorithms I've seen so far, such as activity selection problem and unit-sized set coverage problem, the algorithm is usually very simple and intuitive and returns the first set that satisfies the constrain under greedy strategy.

For example, in the activity selection problem, all we need to do is to go down the list and keep finding solution of the type $d_i$ > $f_j$, and the first list that returns (even if it is near empty) is considered the greedy solution.

My question is that this strategy doesn't even take into consideration of any other case which may be better, is this the signature of greedy algorithm?

Thanks

Yes, this is the idea of greedy algorithms, also known as myopic algorithms. There is still a lot of freedom in deciding what the myopic choice is based on. Allan Borodin has developed a theory of priority algorithms formalizing the notion of greedy algorithm. Such a theory can be used to analyze what greedy algorithms cannot do.

Sometimes greedy algorithms give good results, sometimes they don't. When they do, the corresponding algorithm is very simple and fast. When they don't, we have to use more complicated algorithms. Here good results doesn't necessarily mean optimal results. The greedy algorithm for maximum coverage doesn't produce optimal results, only a $1-1/e$ approxmation – but this is also the best one can do in polynomial time (in the worst case), so the greedy algorithm is optimal with respect to the worst case approximation ratio.


Is the language $a^i b^j c^k$ with $i+j > k$ context-free? I am learning about Context Free Grammars and currently stuck on the following question.

  Is the following language context-free? If not, then how can we prove it using Pumping Lemma?

  $\qquad L = \{a^i b^j c^k \mid i,j,k \geq 0 \land i+j > k\}$.

After spending some time I have been able to generate the production rules for the following language, but unable to understand and conclude the above.

Important Condition ($i+j = k$)

  $\qquad M = \{a^i b^j c^k \mid i,j,k \geq 0 \land i+j = k\}$.

$\qquad\begin{align*}
  S &\to aSc \mid X \\
  X &\to bXc \mid ε
\end{align*}$

Any assistance in solving the condition ($i+j > k$) would be a great help.

There is a simple way to obtain a grammar for the language $L_{\geq} = \{a^ib^jc^k : i+j \geq k\}$ given a grammar for the language $L_= = \{a^ib^jc^k : i+j = k\}$. Starting with a grammar for $L_=$, change all rules mentioning $c$ to rules mentioning a new non-terminal $C$, and add the two productions $C\to c \mid \epsilon$.

Concretely, if we start with the following grammar for $L_=$:
$$
\begin{align*}
&S\to aSc \mid T \\
&T\to bTc \mid \epsilon
\end{align*}
$$
then the corresponding grammar for $L_{\geq}$ is
$$
\begin{align*}
&S\to aSC \mid T \\
&T\to bTC \mid \epsilon \\
&C\to c \mid \epsilon
\end{align*}
$$

Of course, this is not quite the restriction we were after. It is possible to modify the grammar for $L_{\geq}$ to a grammar for $L_{>} = \{a^ib^jc^k : i+j > k\}$ by "signalling" within the grammar that at least one $c$ was actually dropped. This requires duplicating some of the non-terminals and rules. Details left to you.

Another modification which will produce $L_{\geq}$ from $L_=$ replaces each $a$ by a non-terminal that generates $a^+$, and each $b$ by a non-terminal that generates $b^+$:
$$
\begin{align*}
&S\to ASc \mid T \\
&T\to BTc \mid \epsilon \\
&A \to Aa \mid a \\
&B \to Bb \mid b
\end{align*}
$$
Again we can use signalling to get $L_>$ rather than $L_{\geq}$. Details left to you.


Reduction from set cover problem to vertex cover problem Although the reduction from vertex cover problem to set cover problem is quite simple, I did not find anywhere the reduction in the opposite direction. From the similarity in the type of problems, I guess this reduction should be simple too. However, despite trying for some time, I could not develop this. So, any ideas how this reduction can be done?

Edit: Wherever it says "vertex cover", read "dominating set".

Suppose that the sets are $S_1,\ldots,S_n$ and the elements are $x_1,\ldots,x_m$. For each set $S_i$ there will correspond a vertex $S_i$. For each element $x_j$ there will correspond $n$ vertices $x_j^{(1)},\ldots,x_j^{(n)}$. There is also an additional vertex $t$. Finally, assume wlog that the optimal solution for set cover is not $S_1,\ldots,S_n$ (this can be checked in polynomial time).

The instance of vertex cover is as follows. The vertex $t$ is connected to all of $S_1,\ldots,S_n$. Whenever $x_j \in S_i$, the vertex $S_i$ is connected to all of $x_j^{(1)},\ldots,x_j^{(n)}$. If there's a set cover of size $M$, then there is a vertex cover of size $M+1$ (we need to take the extra vertex $t$ so that all set vertices are covered). I believe that the converse should hold as well.

Try to work it out yourself, and if it doesn't work out, try to fix it and let us all know how.


Given $g(n) = \omega(f(n))$, then $g(n) + f(n) = \Omega(g(n))$? I have a proof but I don't know if the assumptions I did are correct.

I know that $g(n)$ dominates $f(n)$, since $g(n) = \omega(f(n))$ and I did the assumption that $g(n) + f(n) = g(n)$. So, by reflexivity, $g(n) = \Omega (g(n))$.

Is this correct?

There is a simpler proof. Assuming (as is usually the case) that $f$ is non-negative, we get $g(n) + f(n) \geq g(n)$, which implies that $g(n) + f(n) = \Omega(g(n))$. There is no need to assume anything.

If we know that $g(n) = \Omega(f(n))$, we can conclude further than $g(n) + f(n) = \Theta(g(n))$. And if $g(n) = \omega(f(n))$ then $g(n) + f(n) \sim g(n)$.


Separability of languages in RE Say that a language $C$ is a separator for disjoint languages $A$ and $B$ if $A \subseteq C$ and $B \subseteq \bar{C}$.

I need to find two languages $A,B\in \mathrm{RE}$ that have no recursive separator $C$.

Hint: Such sets $A,B$ (sans the requirement of recursive enumerability) are called recursively inseparable. According to Wikipedia "it is possible for $A$ and $B$ to be recursively inseparable, disjoint, and recursively enumerable", and Wikipedia might have relevant examples.  (Even if not, now you know what term to look for in the vast sea of internet.)

Extra hint: Wikipedia does indeed provide two such examples:

$A$ is the set of encodings of TMs whose output is $0$, $B$ is the set of encodings of TMs whose output is $1$.
$A$ is the set of provable tautologies, $B$ is the set of refutable contradictions.


Pumping Lemma on Language with subtracted length My study group and I have had some back and forth on one exercise and I haven't found any matching solution online. The task looks as follows: Prove that $L$ is not regular given

$$ L = \{ a^k b a^{m-1} \mid k,m \in \mathbb{N} \} $$

Questions:

How does $m-1$ affect my choice of the word to be pumped? There must be a way to rule out $m=0$ because otherwise my length would be negative.
Would it be wrong to choose $w = a^{n-1}ba^n$ with the intent of pumping down $y = b$?

Every answer is highly appreciated.

You could argue with a reasonably straight face that L is not well-defined, since it supposedly contains the word $a^0ba^{-1}$, so L wouldn't be a language at all, therefore not a regular language and not an irregular language either.

If you change it slightly to $$ L = \{ w: w = a^k b a^{m-1} \mid k,m \in \mathbb{N} \} $$ then it is definitely regular; there's a very simple FSM with just two states for it.


What's a real life usage for detecting communities in complex systems? I am reading through the Girvan-Newman description, having come from the topic of "detecting communities in a complex system".

What exactly is a community in this context and why is it useful for a network to know about it? In simpler terms, what's a real-life usage of this algorithm?

Suppose you have a bunch of friends, regularly meeting together. Occasionally, you also visit your sibling, and they have their own friends. Can we extract these groups of friends just from knowing who's friends with whom on a social network? This is community detection, which is a form of intelligence gathering.


What is the whole picture of the NP-hardness proof of Super Mario Bros? I am reading the NP-hardness proof of Super Mario Bros. in the paper "Classic Nintendo Games are (Computationally) Hard" by Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta.

I can get the basic idea of the proof framework presented in Section 2.1. I think I also understand the Start gadget, Finish gadget, Variable gadget, Clause gadget, and Crossover gadget individually used in this proof. See the figure below.

However, I failed to plug these gadgets into the proof framework to construct a complete instance/scenario of Super Mario Bros. Specifically,

In the Variable gadget, Mario chooses the path to fall down. Then Mario goes to some Clause gadget where it hits the item block from below to release a Star. I don't understand how the Variable gadgets are connected to the Clause gadgets so that the orientations (fall down vs. "from below") fit together?
In the Clause gadget, the Firebar is on the right side. However, in the proof framework, the Check path goes from right to left. How can Mario pick the Star as desired in this case?
Where should the Crossover gadgets be plugged in the proof framework? Are the circles between the paths from the Variables to Clauses crossover?

Graph Connection and Gadget Orientation

Short answer to your first question is to use graph algorithms to compute gadget assembly. Erik mentions this briefly. Keep in mind the gadgets don't necessarily have to be oriented as shown above. You could rearrange the gadgets however you wish as long as you retain the edge connections and entrance/exits of the graph.

The idea of "falling down" from a variable is so that there is no way to get back up to it. After you fall down there could be a tunneling system or corridor that allows Mario to get to the bottom side of a clause and hit the question box from below.

Right-to-Left Check Path

You could use the mirror (about the y-axis) of the clause gadget to achieve the capability of going right to left. This would be true for any of these gadgets as long as you kept the entrances and exits hooked up properly using tunnels. You do not gain or lose anything from going right to left versus left to right in SMB. They would be equal movements and since the whole level is on the screen at one time, we are not restricted from going right to left.

The Crossover Gadget

The crossover gadget is placed where edges intersect (edges between literal and clause). This is because SMB is a 2-dimensional game and thus the graph
using all these gadgets must be planar. The crossover gadget will then act as a vertex where the two intersecting edges can safely connect and not interfere with each other. They will not interfere because if you enter top left, you can only leave top right and if you enter bottom left you can only leave top center. More on the planarity and edge interference here.

Importantly, the crossover gadget is directional. You can only go left to right through the gadget once. This means the edges must also be directional. Whenever you see an edge from literal to clause there are really two directional edges; (literal -> clause) and (clause -> literal). Which results in there being four crossover gadgets whenever the two directional edges cross with two other directional edges. Erik explains more in the video at 1h1m20s (It won't allow me to link to it because this is my first post).


Select certain number of column elements of a stochastic matrix, maximum one element per row Consider a $m \times n$ Matrix.
Every column represents a class and every row an observation. Every row/observation is a probability distribution, hence every row sums up to 1.
We now want to choose elements $a_{i,j}$ of the Matrix.
For every column $k_j$ elements have to be chosen, but we can choose just one element per row. The sum of the chosen elements have to be maximized.

I guess this problem is NP-hard. I didn't found an efficient solution.
To prove that, I want to find a reduction from a NP-hard problem to my problem.

Hopefully someone has an idea for a reduction (or an efficient algorithm).

Duplicate the $j$th column $k_j$ times to reduce to the case in which $k_j = 1$. You are now looking at the assignment problem, which can be solved efficiently.


How best to statistically verify random numbers? Lets say I have 1000 bytes that are supposedly random. I want to verify to a certain certainty that they are indeed random and evenly distributed across all byte values. Aside from calculating the standard deviation and mean value, what are my options for a robust verification process?

You can't.  Randomness is a property of the source, not a property of the values you get from that source.  In other words, randomness is a statement about the probability distribution, not about some specific values sampled from that distribution; from a finite sample, you can't give a definite answer to your question.

Or, to quote Dilbert:

What you can do is perform some kind of statistical test, with the properties that (a) if it is truly random, it'll probably be accepted, (b) if it is not truly random, it might be accepted or might be rejected (no guarantees).  In other words, if the statistical test rejects it, then odds are it wasn't random.  However, if the statistical test doesn't reject it, you can't conclude anything -- it might be random, or it just be a good enough mimic to fool that one statistical test.  Such statistical tests are often sufficient that they can reject many obviously-bad generators.

If that sounds like the kind of thing you're looking for, look up the DIEHARD test suite and related tools.

See also How can it be detected that a number generator is not really random?.


Communication complexity of comparing sets, for Bitcoin In Bitcoin, when one node wants to tell another node about a block, it sends the block header, then all the transactions it contains. This is inefficient, because the receiving node might already have some or all of those transactions.

The sending node needs to tell the receiving node

the transactions that the receiving node does not have
which transactions are in the block
what order those transactions are in

What would be more efficient than sending all of the transactions? (Each transaction is about 160 bytes)

You could send a list of hashes of the transactions. That would reduce the overhead for each transaction to 20 bytes (if you used SHA1). The receiving node could ask for the transactions that it was missing. This is the most efficient method that I can think of - but I think there’s probably something better.

One possibly better approach would be to use a Merkle tree, or some other hierarchical data structure like that.  If there's a large set of transactions that the sender can identify as probably already known to the recipient, then this might save a significant amount of data transfer.

Build a binary tree, where each leaf corresponds to a single transaction, and where each internal node has two children.  Now each leaf node will be labelled with 20 bytes, namely, the hash of the transaction.  Each internal node will be labelled with 20 bytes, namely, the hash of the concatenation of the labels on its two children.  For example, for each $i$, we might have an internal node at height $i$ that covers the first $2^i$ leaves, with a complete binary tree hanging underneath it (along with a bunch of other internal nodes).

The two parties can then compare their Merkle trees via some interactive protocol.  Note that if Alice and Bob established that they both have the same label for some node of their tree, they don't need to examine anything under that node; they know the subtree rooted at that node is the same for both of them.  If they have a different label for some node of their trees, then they can recurse and compare their children.

You can probably choose the structure of Merkle tree to take advantage of the probability distribution on where differences are most likely to appear.  You can also vary the branching factor.  This gives you a space of possible trees, with a range of tradeoffs between the typical number of rounds of interaction vs the typical amount of data that must be communicated.  You might be able to choose a parameter setting that is optimal in your setting.

Also, as another optimization, Alice can start by sending Bob the value of some fixed set of her nodes.  Notice that your example of sending a list of hashes corresponds to Alice proactively sending the value of all of the leaves.  However we might be able to do better by taking advantage of interaction: e.g., if Alice expects that one of her subtrees is probably shared by Bob, she can send just the label on the root of that subtree, and not send anything under that node (e.g., not the hashes of any of the transactions).  If she is right and Bob does have that transaction, neither has to do any other work.  If she is wrong, then some further interaction and additional data must be exchanged.

Many variations on this basic idea are probably possible.


Finding the smallest positive missing number in array of integers contains negative and duplicates number I found this solution but I don't understand it. Can anyone explain the idea behind it ?

the solution:

  A O(n) time and O(1) extra space solution:
  The idea is similar to this post. We use array elements as index. To mark presence of an element x, we change the value at the index x to negative. But this approach doesn’t work if there are non-positive (-ve and 0) numbers. So we segregate positive from negative numbers as first step and then apply the approach.

  Following is the two step algorithm.

  Segregate positive numbers from others i.e., move all non-positive numbers to left side. In the following code, segregate() function does this part.
  Now we can ignore non-positive elements and consider only the part of array which contains all positive elements. We traverse the array containing all positive numbers and to mark presence of an element x, we change the sign of value at index x to negative. We traverse the array again and print the first index which has positive value.

The solution has two parts. The first part filters out all non-positive numbers - this can be done in-place using the partition subroutine of quicksort.

After the first part, we have an array $A[1],\ldots,A[n]$ of positive numbers, and we want to find the smallest positive integer which is not present. We create a new Boolean array $B[1],\ldots,B[n]$ initialized to false. We go over all elements in $A$, and whenever we find an element $i \leq n$, we set $B[i]$ to true. We then find the smallest index $i$ such that $B[i]$ is false - this is the smallest positive integer which is not present. If all elements of $B$ are true, then $n+1$ is the smallest positive integer not present (why?).

As an optimization, we store the array $B$ by modulating the sign of elements in $A$: to represent $B[i]$ being false we use a positive sign for $A[i]$, and to represent $B[i]$ being true we use a negative sign for $A[i]$.


video shape recognition in real time I believe from common sense that video shape recognition problems (identifying shape of a moving object) is of natural interest in many real world situations. The process of identifying is understood as recognizing/finding one selected changing shape/signal among all the present shapes/signals. Ideally, it should be possible to track the shape.

I believe that this process (of recognising) might be computationally expensive (depends on the resolution). I would very much appreciate a survey level paper that summarises achievements so far.
It would be even better if the paper would point out to existing limits due to engineerical/hardware/technological restrictions. I am sorry that the question is a bit fuzzy.

One standard approach is to use object detection / objection recognition / object localization on each individual frame of the video.  This means we can apply algorithms for doing that on a single image.  For speed, once you have detected an object in one frame, we can use object tracking to keep track of where it moves to in the next frames, and we don't need to use an expensive object detection algorithm on the next frame.  For instance, we might apply object detection on every 10th frame, and then use object tracking to track its motion for the next 9 frames.

That should give you enough keywords that you can search and find lots of information on each of those techniques.


Polynomial-time algorithm for Graph Isomorphism in case of Maximum Constrained Maximum Degree From Wolfram:

  A polynomial time algorithm is however known for planar graphs (Hopcroft and Tarjan 1973, Hopcroft and Wong 1974) and when the maximum vertex degree is bounded by a constant (Luks 1982; Skiena 1990, p. 181).

What are the running times of such algorithms, in terms of size of the graphs? What algorithms are used in practice for graph isomorphism?

Algorithms used in practice differ a lot from theoretical algorithms. One popular software package is nauty. The link should also explain the algorithms used, which probably rely on combinatorial methods.

As for the running times for specific algorithms, they are likely stated in the papers. I suggest checking the references.


Why do we need so many sorting algorithms? We have some best sorting methods like quick sort, merge sort etc., then why we need other sorting methods which perform poor?

Some kind of sorting algorithms may end up being visually more pleasing, giving nicer intermediate steps allowing for visual inspection of data where a human can recognize where in the process one is and analyze what goes wrong and sanitze the data accordingly.

I know I have used sometimes some costly sorting algorithm because it came in handy during game programming, giving just the right effect(revealing something on monitor, sorting inventory, etc...) on screen without it looking computer generated.

Like T.S. Elliot said:

  The journey, Not the destination matters...

To see what I mean(source of images https://imgur.com/gallery/voutF):

  !

  !

  !

  !

  !

  !

  !


clarification about Algorithm of page replacement LRU with reference bits Studying LRU approximation Algorithms I think to have not understand how it works, for example:

consider a process with 3 logical pages and 2 frames allocated , an approximation of the
Algorithm Last Recently Used based of reference bits where every four references there is
a shift and where are considered just the first 2 bits, and the follow reference string:

  1 2 1 1 1 1 0 1 0 0

I'd solve it in this way:

  1 2 1 1 (m1) 1 1 (m2) 0 1 0 0

(m1)

4 references so I'd pass from

 frame                     frame
 -----+---+---     to       -----+---+---
    1 | 1 | 0                  1 | 0 | 1
    2 | 1 | 0                  2 | 0 | 1

(m2)

page fault so I'd pass from

 frame                     frame
 -----+---+---     to       -----+---+---
    1 | 1 | 1                  1 | 0 | 0
    2 | 0 | 1                  0 | 0 | 0

So the questions are:

Is my doing correct?
At m2 there is a page fault, is there a "reset" and all bits puts at 0?
the shift frequency (4 in the example) restart counting every page fault?

Is my doing correct?

If I don't misunderstand your notation, when you manipulate the frame for first time (filling it with page 1, then page 2) and then page 1 is called again, you shouldn't send to disk page 2, there is no need because page 1 it is already in frame.


The C3 linearization algorithm for method resolution in multiple inheritance OO languages: Looking for a justification for some implementation detail According to this description of Python's method resolution order (mro), a.k.a. C3 linearization, the algorithm can be described recursively as follows:

L(O) = <O>
L(C) = <C> + merge(L(B1),..., L(Bn), <B1,...,Bn>)

where

O is the class from which every class inherits.
C is a class that inherits directly from B1, ..., Bn, in this order.
< and > are list delimiters.
+ is the list-concatenation operator.
merge merges its list arguments into a single list, in a manner to be described below.

The above can be rephrased in words (quoted from the above Python document):

  the linearization of C is the sum of C plus the merge of the linearizations of the parents and the list of the parents.

The merge algorithm is described as follows (essentially quoted from the Python document, but slightly reworded):

  Consider the head of the first list, i.e L(B1)[0]: if it is a good head, i.e. if it is not in the proper tail of any of the other lists, add it to the linearization of C, and remove it from all the lists in the merge. Otherwise, consider the head of the next list, etc. Repeat until no more classes, or no good heads. In the latter case, it is impossible to construct the merge.

The following example is given as an illustration. Suppose A inherits directly from B and C, in this order, and suppose that the linearizations of B and C are

L(B) = <B, D, E, O>
L(C) = <C, D, F, O>

Then A's linearization is

L(A) = <A> + merge(<B,D,E,O>, <C,D,F,O>, <B,C>)
     = <A, B> + merge(<D,E,O>, <C,D,F,O>, <C>)
     = <A, B, C> + merge(<D,E,O>, <D,F,O>)
     = <A, B, C, D> + merge(<E,O>, <F,O>)
     = <A, B, C, D, E> + merge(<O>, <F,O>)
     = <A, B, C, D, E, F> + merge(<O>, <O>)
     = <A, B, C, D, E, F, O>

My question is: in terms of the original description of the algorithm, what purpose does it serve to give the list <B1,...,Bn> of direct parents as an argument to merge? Will the algorithm produce different results if this argument is omitted?

Without the last list:

merge(<B,D,O>, <C,F,O>, <D,O>) =
  <B,D,C,F,O>

With the last list:

merge(<B,D,O>, <C,F,O>, <D,O>, <B,C,D>) =
  <B> + merge(<D,O>, <C,F,O>, <D,O>, <C,D>) =
  <B,C> + merge(<D,O>, <F,O>, <D,O>, <D>) =
  <B,C,D,F,O>

Without the last list:

merge(<B,D,C,O>, <C,F,O>, <D,O>) =
  <B,D,C,F,O>

With the last list:

merge(<B,D,C,O>, <C,F,O>, <D,O>, <B,C,D>) =
  <B> + merge(<D,C,O>, <C,F,O>, <D,O>, <C,D>) =
  no-merge

Intuitively, the last list forces the final result to be compatible with the ordering <B1,...,Bn>. That might change the order, or make the merge fail.


Infinite calculations in finite time This is probably a silly thought, but suppose we have a computer that's programmed to perform an infinite sequence of calculations and suppose the $i^\text{th}$ calculation takes $1/2^i$ seconds to complete.  Then this computer can do an infinite number of calculations in a finite amount of time.

Why is this impossible?  Is there a lower bound on how long it takes to carry out a non-trivial calculation?

This "kind" of computer is known as a Zeno Machine. Its computational model falls into a category called Hypercomputation. Hypercomputational models are mathematical abstractions, and because of the ways in which they are defined to work, they aren't physically possible.

Take your Zeno Machine for example. If we imagine the Zeno Machine to be a calculating machine of any kind, whether it uses an abacus or integrated circuit doesn't matter. Say the program data used by the machine is fed to it by an infinitely long tape of symbols (just like a Turing Machine).

Of course, we know from mathematics that:

$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}... = \sum_{n=1}^{\infty}(\frac{1}{2})^n $

which we say is equal to $1$. Thus the computation should complete in 1 second because the sum absolutely converges.

But this convergence is, of course,  dependent on $n$ going to (and reaching) infinity. In the physical sense, this means that as the time required for each calculation gets smaller, the "read head" of the calculating machine will have to zip along the symbols in the tape faster and faster. At some point, this speed will exceed the speed of light.

So answering your second question, the absolute lowest-possible bound on a calculation would probably be on the order of the Planck time, given the speed of light as the primary limiting factor in theoretical, but physically-plausible models of computation.


Proving or disproving a set of total functions is countable Let S be the set of total functions from $N \rightarrow M$, such that for each $f \in S$, there is $i > 1$ such that for
  all $j < i$, $f(i)$ and $f(j)$ are not equivalent Turing machines. Prove or disprove that S is countable

I don't think this is actually countable, but I'm having a hard tie proving this using diagonilzation. Can anyone give me pointers / hint? Preferably explained at a lower level.

Hint: Let $M_1,M_2$ be an arbitrary pair of inequivalent Turing machines. Your set $S$ contains all functions satisfying $f(1) = M_1$ and $f(2) = M_2$.


Can oracle arguments separate P and NP? I know that the general consensus among CS researchers is that non-relativizing techniques will be needed to separate P and NP.  However, if there is an oracle language $A \in \textbf{P}$ such that ${\textbf{P}}^A \neq {\textbf{NP}}^A$ would that necessarily imply ${\textbf{P}} \neq {\textbf{NP}}$?  I read somewhere that it would be enough, but I'm not sure.

On the one hand, since any NDTM can be supplemented with a polynomial-time deterministic subroutine for $A$, having oracle access to it should not give an NDTM any more "power".

On the other hand though, aren't oracle TM's able to make queries about strings of any length in the oracle language?  In that case, we could not jump to the conclusion that P does not equal NP, because according to my understanding, polynomial-time Turing machines (whether deterministic or non-deterministic) cannot be "influenced" by strings of length exponential in the length of the input string.

For an oracle $A\in {\sf P}$ you have ${\sf P}^A={\sf P}$ (since you can encode all requests to the oracle as a submodule of the TM). By the same argument you als have that ${\sf NP}^A={\sf NP}$.

Thus in this case ${\sf NP}^A\neq{\sf P}^A$ would imply ${\sf NP}\neq{\sf P}$.

You basically said this already in your question. Note that we cannot query "exponentially long" strings to the oracle, since we need to write the string on the oracle tape first, and this would clearly take too long. Maybe this caused your confusion?


Turing complete and computational power In a lecture a professor mentioned that modern computers don't have as much computational power as a Turing machine because they don't have infinite memory, and since no computer can have infinite memory the Turing machine is therefore unattainable and simply represents the upper limit of computing. Is there a measure, or definition of what problems (or class of problems) lie beyond the reach of our computing power because of this?

If we think of the universe as finite, then anything that needs more memory than that finite amount is beyond our computational ability.

However this is not a good model for studying computability, the Turing machine model works much better in reality and that is the reason we use it for studying computation on real computers. A Turing machine doesn't really need an infinite amount of memory, it only needs an unbounded amount of memory. For example, we can provide additional memory to a computer over time (as the computer needs more and more memory) and then we have something similar to a Turing machine. If we assume that we have unbounded amount of time and memory for finishing our computation then the Turing machine captures this concept of computability in principle quite nicely.

Check the Wikipedia article about Turing machines, there is a section that discusses the relevance of the model.

If you are interested in feasible computability, then complexity theory (where we consider various amount of resources like time and space for performing a computational task) is closer to the what we can really do in practice than computability theory. Many experts state that the feasible computations fall in the complexity class $\mathsf{P}$ (and more recently in probabilistic and quantum versions of $\mathsf{P}$, i.e. $\mathsf{BPP}$ and $\mathsf{BQP}$).


Why are ambiguous grammars bad? I understand that if there exist 2 or more left or right derivation trees, then the grammar is ambiguous, but I am unable to understand why it is so bad that everyone wants to get rid of it.

Consider the following grammar for arithmetic expressions:
$$
X \to X + X \mid X - X \mid X * X \mid X / X \mid \texttt{var} \mid \texttt{const}
$$
Consider the following expression:
$$
a - b - c
$$
What is its value? Here are two possible parse trees:

According to the one on the left, we should interpret $a-b-c$ as $(a-b)-c$, which is the usual interpretation. According to the one on the right, we should interpret it as $a-(b-c) = a-b+c$, which is probably not what was intended.

When compiling a program, we want the interpretation of the syntax to be unambiguous. The easiest way to enforce this is using an unambiguous grammar. If the grammar is ambiguous, we can provide tie-breaking rules, like operator precedence and associativity. These rules can equivalently be expressed by making the grammar unambiguous in a particular way.

Parse trees generated using syntax tree generator.


Understanding Monte Carlo Probabilities I am trying to get a good grasp on Monte Carlo (MC) algorithms, but I feel I am missing something fundamental.

What I don't understand is how MC improves its confidence of giving the correct solution by running more executions.

So please correct me if I am wrong and assume that $Pr[false] \leq 0.5$. Assume we need to find the number of executions so that $Pr[false] \leq 0.125$, thus improving confidence.

Is it true that the number of needed executions is $3$, since $0.5^3=0.125$?

Thanks in advance...

This is the idea of probability amplification, in which one improves the probability of correctness of the algorithm by running it multiple times. You are talking about Monte-Carlo algorithms which have one-sided error. Lets take an example (from Wikipedia) having such a similar feature :

The Solovay–Strassen primality test is used to determine whether a
given number is a prime number. It always answers true for prime
number inputs; for composite inputs, it answers false with probability
at least 1/2 and true with probability at most 1/2. Thus, false
answers from the algorithm are certain to be correct, whereas the true
answers remain uncertain; this is said to be a (1/2)-correct
false-biased algorithm.

The probability that the above algorithm returns an incorrect answer is thus at most 1/2. Now, the key idea is to understand that successive runs of the algorithm produce answers that are independent of each other - hence, on running it twice, the probability that the algorithm returns an incorrect answer both times is at most $(\frac{1}{2})^2$. Thus, after $k$ iterations, the probability of an incorrect answer reduces to at most $(\frac{1}{2})^k$. Thus, if we adopt the scheme that the algorithm returns false if the any of the first $k$ runs give an output of false, else return true, then the probability that our scheme returns an incorrect answer is at most $1 - (\frac{1}{2})^k$, which can be driven down to $0$ for large values of $k$.


Prime number CFG and Pumping Lemma So I have a problem that I'm looking over for an exam that is coming up in my Theory of Computation class.  I've had a lot of problems with the pumping lemma, so I was wondering if I might be able to get a comment on what I believe is a valid proof to this problem.  From what I have seen online and in our review I don't think this is the customary answer to this problem so I want to know if I am applying the concepts behind the pumping lemma successfully.  The problem is not a homework problem and can be found on my professor's previous exams here under the fourth problem of his exam given in Fall of 2011, which is...

Let $L = \{0^p \mid \text{\(p\) is a prime number}\}$. Prove that $L$ is not context-free using the pumping lemma for context-free languages.

So here is my proof:

Assume that the pumping length is $m$, where $m+1$ is a prime number.  I shall also assume that there is a string $uvxyz = 0^{(m/2)}00^{m/2} \in L$.  There are two possible positions that do not violate conditions 2 and  3 of the pumping lemma for context languages, being $|vy| > 0$ and $|vxy| \leq m$.  These are:

$u = 0^{(m/2)}, v = 0, x = 0^{m/2}$, pumping by one results in $0^{m/2}000^{m/2}$.  Since m/2 + m/2 is m, which is one less than the prime number m+1, it is an even number.  m+2 is also an even number and since $|0^{m/2}000^{m/2}| = m + 2$, this number of zeroes is also even and thus cannot be prime, resulting in a contradiction.

The other placement is to place the string on the symmetric opposite or $x = 0^{m/2}, y = 0, z = 0^{m/2}$.  This results in the same contraction as in case 1.

The string cannot be placed in the center such that $v = 0^{m/2}, x = 0, y = 0^{m/2}$ as this would violate condition three or $|vxy| \leq m$, since $|vxy| = m + 1 > m$.
So my question is essentially, is this a valid proof and if not what is wrong with it?

Your proof is incomplete, there are many cases you don't cover. You are not ruling out, for example, $u = 0^{m/2-3}$, $v=0$, $x=00$, $y=00$, $z=0^{m/2-2}$.

A good hint that your proof is wrong is that all you're using about prime numbers is that they're odd¹. Odd numbers do form a context-free language.

The pumping lemma gives you $uvxyz=0^p \in L$ and for all $n\in\mathbb{N}$, $uv^nxy^nz = 0^{p+(n-1)k} \in L$, with $k = |vy| \ge 1$. Now you need to prove that the numbers $\{p + (n-1)k \mid n\in\mathbb{N}\}$ cannot all be prime.

   Look at the values of $p + (n-1)k$ modulo $k+1$ when $n$ varies from $1$ to $k+1$. Since $k$ and $k+1$ are co-prime, one of them has to be $0$ modulo $k+1$, meaning that it is a multiple of $k+1$ (and not $k+1$ itself because it's larger), so it is not prime. Depending on your mathematics background, you may formulate this argument using the Chinese remainder theorem or any other equivalent theorem.

¹  And you didn't account for $2$ being prime, but that's ok, it's enough to consider sufficiently long words, because the status of a finite number of words doesn't affect the context-freedom of the language.


Is the identity function a many-one reduction from a language to super-set? I need help with a question.

Prove or disprove the following claim:

  Let $f\colon \Sigma^* \to \Sigma^*$ be the identity function, i.e., $f(w) = w$ for all $w \in \Sigma^*$. Let $L_1$ and $L_2$ be two languages such that $L_1 \subseteq L_2$. Then $f$ is a many-to-one reduction from $L_1$ to $L_2$. In particular, if $L_2$ is decidable, $L_1$ is decidable as well.

I'm almost certain it's false, but I'm having a hard time with the justification. Can anyone help me out?

In order to disprove this, it is enough to disprove the conclusion that if $L_2$ is decidable then so is $L_1$. Can you think of a counterexample for the latter claim?

Another option is to directly disprove the fact. For $f$ to be a many-one reduction from $L_1$ to $L_2$ would mean that $x \in L_1$ iff $x \in L_2$, that is, $L_1 = L_2$. So to disprove this you only need to find two languages $L_1,L_2$ such that $L_1 \subsetneq L_2$.


Decide whether an $n$-bit positive integer is composite Question:

Given an $n$-bit positive integer. A decision problem is to decide whether it is composite. Is this problem in NP?

I know that for every composite number, a factor of the number is a certificate.
Verification proceeds by dividing the number by the factor and checking if the reminder is zero. My question is whether the verification can be done in  polynomial time of $n$? it seems that we need to use at most $2^n/2 = 2^{n-1}$ factors to test, does that mean we should use exponential time to verify?

NP doesn’t look at how hard it is to find a certificate (in this case a factor), just at how hard it is to test a certificate that claims to prove the answer is “yes”.

So it doesn’t matter how hard it is to find a factor, just that given a factor of an n-bit number, you can easily verify that it is a factor in $O(n^2)$. Or a bit faster with more effort. So “is x composite” is quite obviously in NP.

The opposite, “is x a prime”, has been shown to be in NP, but that is absolutely not easy to show. Basically you have to show that for any n-bit prime p, there is a certificate that allows us to verify in polynomial time time that p is prime.


EQ_{TM} is not Turing recognizable, but we can reduce A_{TM} to it? So as I understand $EQ_{TM}$ (problem of deceiding whether two turing machines are equivalent) is not Turing Recognizable (by showing that $A_{TM}$ is reducible to its complement ${NEQ_{TM}}$). But we can also reduce $A_{TM}$ to $EQ_{TM}$ itself, that means: $EQ_{TM}$ and ${NEQ_{TM}}$ are not disjoint since we can reduce $A_{TM}$ to the two of them? And also, $EQ_{TM}$ is not Turing recognizable but it contains some instance that is turing recognizable since we can reduce $A_{TM}$ to it?
I have an intuition that these two questions have 'YES' as an answer and they are not problematic: it is OK to answer them with YES. But I have an unclear image about the fact of being a complement but having some shared elements with its complement, maybe the elements that are shared are just the strings but not the problems themselves?
Any clarifications would be welcome

Note that $EQ_{TM}$ is the language of machines that recognize the same language (they are not necessarily equivalent).
You said

But we can also reduce $A_{TM}$ to $EQ_{TM}$ itself, that means: $EQ_{TM}$ and $NEQ_{TM}$ are not disjoint since we can reduce $A_{TM}$ to the two of them?

This is far from being true, if there are reductions from a language $A$ to two languages $B$ and $C$, this does not say anything about $B\cap C$ as the reductions need not be related. To be concrete, it is shown here that every non-trivial language is $\text{R}$-hard, so clearly, you cannot claim that every two non-trivial languages intersect.
You also said

And also, $EQ_{TM}$ is not Turing recognizable but it contains some instance that is turing recognizable since we can reduce $A_{TM}$ to it?

Clearly, $EQ_{TM}$ contains some instances $\langle M_1, M_2 \rangle$, where it is easy to check whether $L(M_1) = L(M_2)$ (for example, all instances where $M_2$ is identical to $M_1$ with some new unreachable states). Also, you're right, this indeed can be thought of a consequence of the existence of a reduction from $A_{TM}$ to $EQ_{TM}$. Formally, we have the following claim (I leave it to you as a good non-trivial exercise), and thus the image of the reduction (which is a subset of $EQ_{TM}$) is in $\text{RE}$.
Claim: Let $f: \Sigma^* \to \Sigma^*$ be a computable function and let $L\subseteq \Sigma^*$ be a language in $\text{RE}$. It holds that $f(L) = \{ f(x): x\in L \}\in \text{RE}$.
BTW, complement languages, by definition, have empty intersection.
So, regarding the question in the title, you can reduce $A_{TM}$ to $EQ_{TM}$ (here is a hint: there they asked about a reduction from the halting problem, but the hint is also good for your case), and being able to define such a reduction does not contradict anything.


Constructive proof of decidability of finite Halting-problem-style set that does not use table lookup I tried to prove that the following language is recursive: for $\Sigma=\{0,1\}$, $k$ a positive integer:
$$
L_k= H_{\mathrm{TM},\varepsilon}\cap \Sigma^k
$$
where $H_{\mathrm{TM},\varepsilon}=\{\langle M\rangle\mid M \text{ is a TM that halts on an empty input}\}$

It is easy to prove because $L_k$ is finite, but I didn't notice this and tried to prove it by finding a decider TM for it.
I thought that since the encoding of the TM is of length $k$ then it can't have more than $2^k$ states, and by running it on epsilon for $2^k$ steps, if it halts by then than accept otherwise reject.
I was told that it's incorrect - is it a wrong solution. How can I prove this using this method (and not the way I mentioned about $L_k$ being finite)?

There is no general way to find a decider TM for $L_k$

You are correct that $L_k$ is recursive because, being a subset of the
finite set $\Sigma^k$, it is also finite.

You would like to rather find a decider TM for $L_k$, and you suggest
some techniques. Without even going into the details of these
techniques and why they do not work, you do not stand any chance of
ever succeeding.

The first thing you should notice is that the finiteness argument
tells you that there exists a decider TM $M_k$ for the language $L_k$,
but it does not tell you what this TM is. It is an example of a
non-constructive proof: you prove that a decider exists, but you
cannot tell which it is.

Now, suppose that, given $k$, you have a procedure $\mathcal P(k)$ to
find such a decider $M_k$ for the language $L_k$ (rather than just
prove it exist). Then, given any Turing machine $M$, then there is an
integer $k'$ such that $|\langle M\rangle|=k'$, so that $\langle
M\rangle\in \Sigma^{k'}$. Then you can use the procedure $\mathcal P$
to find a decider TM $M_{k'}$ that can determine whether $\langle
M\rangle\in L_{k'}$. So you have a way to decide whether the TM $M$
halts on empty input. And this works for any TM $M$. However, this is
not possible, because it is undecidable whether a given TM $M$ halts
on empty input.

So the procedure $\mathcal P$ cannot exist.

Since you are looking for a general way to find the decider TM
$M_{k'}$, you cannot succeed because that method would be precisely a
procedure such as $\mathcal P$.

Note that this proof could still leave the (very remote) possibility
of finding a decider for some specific values of $k$, but you would
have to identify precisely the concerned values, and the method would
not work for all values of $k$. I am not advising you to try.


Can someone explain this formula for calculating Manhattan distance? This is from a Kickstart problem:

  Note: The Manhattan distance between two squares (r1,c1) and (r2,c2)
  is defined as |r1 - r2| + |c1 - c2|, where |*| operator denotes the
  absolute value.

Then in the analysis:

  Note that the manhattan distance has an equivalent formula:

dist((x1, y1), (x2, y2)) = max(abs(x1 + y1 - (x2 + y2)), abs(x1 - y1 - (x2 - y2)))

  This formula is based on the fact that for any point, the set of
  points within a manhattan distance of K form a square rotated by 45
  degrees. The benefit of this formula is that if we fix (x2, y2), the
  distance will be maximized when x1 + y1 and x1 - y1 are either
  maximized or minimized.

Could someone explain in more details how this formula can be derived?

Lemma. $|a|+|b|=\max(|a+b|, |a-b|)$ for any real number $a$ and $b$.
Proof 1.
$|x|=\max(x, -x)$ for all real number $x$. So
$$\begin{aligned}
|a|+|b|
&=\max(a, -a) + \max(b, -b)\\
&=\max(a+b, a-b, -a+b, -a-b)\\
&=\max(\max(a+b, -a-b), \max(a-b, -(a-b))\\
&=\max(|a+b|, |a-b|)
\end{aligned}$$
Proof 2.
There are $2 \times 2 = 4$ cases.

$a\ge 0$

$b\gt 0$. LHS is $a+b$, RHS is $a+b$.
$b\le 0$. LHS is $a-b$, RHS is $a-b$.

$a\lt 0$

$b\gt 0$. LHS is $-a+b$, RHS is $-(a-b)$.
$b\le 0$. LHS is $-a-b$, RHS is $-(a+b)$.

One dimensionality of Manhattan-distance.
The Manhattan-distance of two points $(x_1, y_1)$ and $(x_2, y_2)$ is either $|(x_1+y_1)-(x_2+y_2)|$ or $|(x_1-y_1)-(x_2-y_2)|$, whichever is larger. That is, $ d((x_1, y_1),(x_2, y_2))= \max(|(x_1+y_1)-(x_2+y_2)|, |(x_1-y_1)-(x_2-y_2)|)$$
Proof: By definition,
$$d((x_1, y_1),(x_2, y_2))=|x_1-x_2| + |y_1-y_2|.$$
Now apply the lemma above. QED.
This answer also serves as a complement to another answer of mine.


Regular expression for a palindrome of finite length? I have a language $$ L = \{ww^R, w \in \{ab\}^5\}$$

I know this is a regular language because it is finite (since w can only be of length 5). I want to prove it's a regular language, so I'd create a regular expression for it.

Theoretically, my regular expression could be the union of all strings in the language, but is there a concise way to express this rather than writing all possible strings out?

Sticking $w$ with its reverse together usually is not a regular language and therefore there is no natural concise way to represent that using regular expressions (at least to my knowledge)

Im not really sure why you would like to find a regular expression for this language, since - as you have stated - this language is finite, and therefore regular (if you want a proof for this claim, it is here)


Memory ballooning in the OS Some hypervisors optimize memory usage using a method that is called ballooning (at least that's what KVM calls it), this method deduplicates memory between VMs and sets common pages to read-only with copy on write.
This is sort of the opposite of a fork call.

Is it feasible to implement on an OS level for processes (I was mainly thinking of for the duplication of memory when browsing with Chromium with multiple tabs on the same site), has it been implemented already?

Actually, what you've described confuses ballooning and 'same-page-merging'. I'll try to elaborate on the two to make the distinction apparent.

Memory ballooning

This is a trick to make sure that some of the memory allocated to the guest virtual machine remains usable by another guest or the host itself (caches, etc). It's done in the following way:

The guest kernel is injected with a driver, that monitors guest memory usage, and 'steals' some of the unused memory (allocating it for itself in the guest memory space, thus making sure nothing on this guest can touch that range).

Then it informs the host kernel, that it can in fact remove these memory pages from the core, that they are not going to be used in the guest (until the guest experiences some memory pressure, at which point the balloon will deflate, and use these ranges again).

Ultimately, the kernel can allocate the exact same memory to another guest, and make the entire memory usage a lot more efficient if the guests are running with a lot of free memory.

Same Page Merging

This technique identifies identical memory pages, that for some reason are not already marked 'quasi-read-only' with copy-on-write, and marks them as such.

Now, on the OS level, there is limited need for these kinds of tricks. Simply enough, most time when you have identical memory pages, they are already read-only (sometimes even without CoW), since these are mostly applications code, libraries etc. They are natively opened through a Memory Map, and thus the kernel can keep only one copy of them in core (if any at all, it can also completely page it out, and allow it to be paged in from primary store as needed).

On the virtualized OS level, the same principle is properly applied within each guest subsystem. However, the host kernel, has no idea if two of the guests are running mostly the same code, and thus are sharing the same memory - the guests don't communicate to coordinate that.

Which is why it can occasionally scan the entire system for identical memory pages - most of the time, they will be identical across the guest OS's, not within each one - the guest kernel makes a decent job keeping the memory neat within it's range. Thus, in the typical VM environment, where one host kernel handles 50+ guests, the memory savings can be pretty substantial.

Both at once

Ballooning and Same-Page-Merging can co-exist very well, achieving pretty substantial memory overcommit for identical systems.

To answer your question - the Same-Page-Merging can and sometimes is enabled at an OS level. It has to do with page sharing that are interpreted, and thus could end up being identical without having the same backing file.

In your Chromium example - the process binaries themselves are already deduplicated through read-only startup map - they share the exact same memory space. The page caches (contents of the tabs) are usually also shared between processes (read-only copy-on-write) due to the way disk cache is managed - the same on-disk file can be opened simulatenously between different processes in the VM-optimal sense.

The advantage would be most evident with the shared state of different Javascript engines - but I'm not sure if they are allocated in the exact same memory layout, ensuring that the entire memory page is identical.

This is different on mobile systems. Android, for instance, extensively employs KSM to deduplicate identical code between different applications.

In either case, you can enable it yourself on Linux (Kernel SamePage Merging). The driver exports various statistics that, after reading this answer, you should be able to interpret, and make your own decision whether it's a good match for your purpose.

https://www.kernel.org/doc/Documentation/vm/ksm.txt


Sum of all distances in connected DAG in $O(n\log n)$ I have a DAG with $n$ nodes and $n-1$ edges. The edges in DAG (fixed) are defined as follows:  For every  node $i$, $1 \le i \le n-1$ is connected to node $i+1$. The lengths of the $n-1$ edges are given as input.

I need to compute the sum of all of the distances between all pairs of different vertices, i.e., to compute $\sum_{u<v} d(u,v)$, which is the sum of the distances for each pair $u,v$ such that $u<v$.

For example, suppose $n=4$, and the edge lengths are $1,1,1,1$.
Then the pairs along with their distance would be $(1,2):1,(1,3):2,(1,4):3,(2,3):1,(2,4):2,(3,4):1$, so the total sum of distances would be  $1+2+3+1+2+1=10$.

I tried Dijkstra's Algorithm (time complexity $O(n\log n)$) on every node  but the time complexity is $O(n^2 \log n)$ which is inefficient. Is there a way to reduce it to $O(n \log n)$ or less?

I think the question is not clear enough, but what I understood is that we want to find the sum of all the shortest path from $u$ to $v$ such that $u < v$. The trick is that the graph is actually a directed chain, so we can represent the edges in an array $A$ of length $n - 1$.

The brute force formula is $\sum_{i=1}^{n -1} \sum_{j=i + 1}^{n} \delta(i,j)$. Where $\delta(i,j)$ is the shortest path from $i$ to $j$, because our graph is a chain, we can simply express this as $\delta(i,j) = \sum_{k=i}^{j - 1} A_{k}$. In the example you provided with 4 nodes $A =[1,1,1]$. The above formulas have a complexity of $\Theta(n^3)$, which can be improved to $\Theta(n^2)$ by doing a prefix sum on $A$. But a pattern can easily detected by looking carefully where the items of $A$ repeat.

For example, if $A = [1,2,3]$ the above formulas would provide the following operations:

$(1 + (1+2) + (1+2+3)) + (2 + (2+3)) + (3)$, here each "big parenthesis" is the computation from each node. The last node is obviously ignored.

We can rewrite this as:

$3 *(3 * 1) + 2 *(2 * 2) + 1 * (1 * 3)$

For example $3 *(3 * 1)$ means that $3$ was repeated once ($1$) on $3$ parenthesis. Likewise, $ 2 *(2 * 2)$ means that $2$ is repeated two times on $2$ parenthesis and so on.

The repetitions have a pattern: the number of times it appears on a "big parenthesis" is actually the index of the element, but the number of times is repeated inside the parenthesis decreases as the index increases because less paths starts from nodes that are closer to the end of the chain. Work through the example and you will find the pattern, make sure you understand this paragraph.

As you mentioned that you have not found the pattern, the above discussion can be summarized in this formula: $\sum_{i=1}^{n - 1} A_{i} * i * (n - i)$. Remember that $n$ is equal to the number of nodes and $A$ contains the edges, which are $n - 1$.

The proof of the above intuition is left as an exercise for the reader :-).

EDIT: Just in case, the complexity is $\Theta(n)$ because we only do a loop to compute the summation and the inner operations are $\Theta(1)$. Depending on how you represent the graph in the input, the memory complexity can be either $\Theta(1)$ or $\Theta(n)$.


Implementing addition for a binary counter A binary counter is represented by an infinite array of 0 and 1.

I need to implement the action $\text{add}(k)$ which adds $k$ to the value represented in the array.

The obvious way is to add 1, k times. Is there a more efficient way?

Well, surely there is.

As a first thing I would convert $k$ to its binary representation $\text{bin}(k)$. If $c$ is the current value of your counter then in order to perform $\text{add}(k)$ just update the counter by setting it to $\text{bin}(c)+\text{bin}(k)$.

If you don't know how to add binary numbers efficiently, think how you would have done it using pen and paper.

For small $k\in O(\log c)$ the repeated increment might be efficient though.


For each given set choosing either it or its complement such that their union exactly has a given size Given an integer $k$ and $n$ sets $A_1,\ldots,A_n$, denote $U=A_1\cup A_2\cup\cdots\cup A_n$, $A_i^0=A_i$ and $A_i^1=U\backslash A_i$. The problem asks whether there exists $(b_1,\ldots, b_n)\in\{0,1\}^n$ such that

$$\left|\bigcup_{i=1}^nA_i^{b_i}\right|=k.$$

Is this problem NP-complete?

This problem can be solved in polynomial time.

If $k=|U|$, this problem is exactly another wording for SAT where each clause contains all variables. More precisely, for each element $j\in U$, let $l_{ij}=b_i$ if $j\notin A_i$ while $l_{ij}=\neg b_i$ otherwise. The problem is exactly to satisfy the clauses $l_{1j}\vee l_{2j}\vee\cdots \vee l_{nj}$ for all $j$. If all possible clauses are involved in, the answer is certainly NO. Otherwise, without loss of generality, say one missing clause is $b_1\vee\cdots\vee b_n$, we can set $b_1=\cdots=b_n=0$ to satisfy all other clauses, thus the answer is YES.

If $k<|U|$, then at least one element should not be included in the union. We can test for each element: if this element is not included in the union, we can determine for each set whether it or its complement should be chosen, then we can see whether their union exactly has size $k$.


Showing the predicate $n \leq \sqrt2 < n+1$ is primitive recursive Let h(x) be the integer n such that $n \leq \sqrt2 < n+1$ Show that h(x) is primitive recursive.

I know how primitive recursive functions are defined, but showing an integer is primitive recursive is throwing me off. I need some help starting the proof.

This relation can be written as
$$n \leq \sqrt{2} \text{ and } n+1  > \sqrt{2}$$
or equivalently
$$ ((n^2 < 2) \text{ or } (n^2 = 2)) \text{ and } ((n+1)^2  > 2)$$
In terms of functions
$$h(n) = and[or[ls(sqr(n),2), eq(sqr(n),2)], gr(sqr(n+1),2)]$$
So, we have exponentiation (squaring), increment by $1$ (i.e. $n+1$), less than, equal to, greater than, conjunction, and disjunction. They are all primitive recursive whose composition result in the primitive recursive predicate $h(n)$ equal to $1$ if $n \leq \sqrt{2} \text{ and } n+1  > \sqrt{2}$, and $0$ otherwise.

On @chi's hint:

In fact this predicate is true for only $n=1$. So this predicate is drastically simplified and takes the following form $$h(n)=eq(1,n)$$


How to decide the scope of the following lambda expression? I am having a difficulty in deciding the scope of the left-most lambda in the following expression.

λx.x(λuv.v)(λab.a)(λcd.c)

I have learnt that we should put brackets in such a way that the scope of lambda will be maximum. So arrived at candidate- answer 1, below.

On the other hand, since the expression (λuv.v)(λab.a)(λcd.c) does not contain any x, if we put brackets as in answer 2, still we are not changing the scope, right?

But I know that these two answers are not equivalent. So which one is the correct one?

The two candidate answers are:

λx.(x(λuv.v)(λab.a)(λcd.c))
(λx.x)(λuv.v)(λab.a)(λcd.c)

I came up with this confusion through the tutorial: A Tutorial Introduction to the Lambda Calculus by Raul Rojas. There, in page 6, ~T is given as λx.x(λuv.v)(λab.a)(λcd.c). If we apply brackets as in my answer-1, we will not be able to evaluate ~T to F.

The correct answer is:

  (λx.x (λuv.v) (λab.a) (λcd.c))

If I add in parethenese to disambiguate application, it becomes.

  (λx.((x (λuv.v)) (λab.a)) (λcd.c))


Admissibility of heuristic in the $A^*$ algorithm The CS188 course from Berkeley goes to great length in explaining why the optimality of $A^*$ algorithm is conditioned by the admissibility of heuristic.

Note: admissibility of heuristic means that:

$$\forall n, 0 \leq h(n) \leq h^*(n) $$

With $h^*(n)$ being the true optimal distance of $n$ to the goal.

The course's proof reasoning is sound and makes perfect sense.

However, this example uses a heuristic that is not admissible. For instance, the distance between the start state and the goal state is only $h^* = 2$ while the heuristic of the start state is $h = 17$ (see the example with the 8-puzzle, using Nilsson heuristic). Obviously, $17 \gt 2$ and therefore the heuristic is not admissible.

However, after having implemented the algorithm and tested it, it seems that it is able to find the optimal solution each time. Trying to alter the heuristic function only makes it worse than optimal.

So, if the admissibility of the heuristic a necessary condition for the guaranteed optimality of $A^*$, how comes that this example seems to refute this?

Did I miss something? Or perhaps, does the condition on the admissibility means that sometimes, the algorithm will be optimal even with an unadmissible heuristic, but only an admissible one guarantees the optimality?

I'd be curious to hear any thought about that.

It's exactly as you suspected:

Sometimes, the algorithm will find an optimal solution even with an unadmissible heuristic... only an admissible heuristic guarantees the optimality of the solution returned.

If you use an unadmissible heuristic, there's no guarantee what will happen.  The solution you get back might be the best one; or it might not be.  And, you probably won't have any way of telling whether the solution you got back was optimal or not, so you won't even know for sure when this is a problem and when it isn't.

If you use an unadmissible heuristic, you'll often (but not always) get sub-optimal solutions.


Trying to Explain Objects After a year hiatus from Computer Science courses in college, im back to hitting them hard for the next two years straight. In the next few weeks before classes start again I have been trying to refresh my memory on key concepts by writing and trying to explain them to people that have never gotten deeper into a computer than Word, or Excel, maybe even just Photoshop.

Right now i'm trying to explain Objects and Classes, using the cookie cutter is a class and a cookie is an object.

In trying to explain Objects I thought that starting with trying to describe a Cookie would be easy and I described it like so.

Dinosaur_Cookie_Name = "T-Rex"
Dinosaur_Cookie_Frosting_Colour = "Green"
Dinosaur_Cookie_Eaten = False

And then I was going to explain how these have no linking between them and that if you wanted to say that

my_cookie = Dinosaur_Cookie_Name

it doesn't necessarily mean that it's also green and uneaten.

So I was then going to explain that by making my_cookie a list, you could then iterate through the list to access properties and tada, a sort of rudimentary object. Afterwards would then be, tada here is what an object is.

That's where I froze. In the year since learning about Objects in my beginning C++ class I couldn't remember how I made the jump TO Objects.
I remember a little talk about name spaces and pointers but thats about it.

So do objects store properties in an array?
Would it be appropriate in teaching about Objects to have a middle step of a list, between non-associated variables and an object?

Car

My favourite explanation of objects/classes is centered at cars.

Class

Class is defined as a schematic of information you can "measure from" or "store in" a car instance.
For example, every car has a color, production date, total distance passed, etc.

Object

Objects are "real" or "existant" things made upon a class (schematic). All the cars consist of properties such as color and distance traveled, but the actual values of these properties may vary.

Implementation

Object implementation may differ between languages and compilers, but I guess this might be a good way to do it:

Calculate space needed for all subobjects/properties (pointers/ints/strings/other objects) which reside in the object itself. On object creation, take up precalculated memory.
Functions inside classes (methods) are no different than "normal" functions, it is just that compiler enforces them to be called on object or inside of fashion due to object-oriented programming philosophy.

When you try to get/set certain property of an objects, compiler actually translates it into memory offset from start of objects memory, so yes, you couldsay it acts like array with different data types in it.


Knapsack with non-overlapping rectangles Given a large rectangle and a set $S$ of small rectangles each with a value $v_i$. My problem is to find a collection of rectangles $T\subseteq S$ to put in the large rectangle so as to maximize the overall value $\sum_{i\in T}v_i$, subject to the constraint that the selected small rectangles cannot overlap with each other.

I suppose the problem is NP-hard.  Can we design an approximation algorithm (PTAS or constant-factor approximation ratio) approaching the optimum?

This problem is known as maximum disjoint set.  In your case, assuming the rectangles are parallel to the axes, the problem is maximum disjoint set for axis-parallel rectangles.  The problem is indeed NP-hard, but Wikipedia has an approximation algorithm with an approximation ratio of $O(\log \log n)$ if all values $v_i$ are the same, or approximation ratio $O(\log n/\log \log n)$ for the general case where the values may differ for each rectangle.  You can check out the citations there to find an entry point to the research literature.

I have not been able to find any lower bounds on what approximation ratio is achievable, so as far as I can tell, it is an open problem whether you can achieve a constant-factor approximation ratio for this problem.

If you're willing to relax the running time requirement, there is a recent result achieving an approximation ratio $1+\epsilon$, at the cost that the running time becomes larger than polynomial, namely, $2^{\text{poly}(\log \log n/\epsilon)}$.  See arXiv:1307.1774 and arXiv:1608.0027.

In the case where none of the small rectangles are too small (i.e., each small rectangle has an edge whose length is at least a constant fraction of the length of corresponding edge of the large rectangle), this problem has a PTAS, i.e., $1+\epsilon$ approximation ratio is achievable.  See arXiv:1703.04758.


Why is first-order logic (without arithmetic) VALIDITY only recursively enumerable, and not recursive? Papadimitriou's "Computational Complexity" states that VALIDITY, the problem of deciding whether a first-order logic (without arithmetic) formula is valid, is recursively enumerable. This follows from the completeness and soundness theorems, which equate VALIDITY and THEOREMHOOD, the latter being the problem of finding a proof for a formula, which had previously been shown to be recursively enumerable.

However, I am not seeing why VALIDITY is not recursive as well, because given a formula $\phi$, one could run two Turing Machines for THEOREMHOOD, one on $\phi$ and the other on $\neg \phi$, concurrently. Since at least one of them is valid, it is always possible to decide whether $\phi$ is valid, or not valid. What am I missing?

Note: this question refers to first-order logic without arithmetic, so Gödel's Incompleteness Theorem does not have a bearing here.

However, I am not seeing why VALIDITY is not recursive as well, because given a formula $\phi$, one could run two Turing Machines for THEOREMHOOD, one on $\phi$ and the other on $\neg \phi$, concurrently. Since at least one of them is valid, it is always possible to decide whether $\phi$ is valid, or not valid. What am I missing?

This is wrong. A formula $\phi$ is valid iff it holds in all models.

It is not true that at least one of $\phi$ and $\lnot\phi$ must be valid: both might hold in some models, but not all of them.

Trivial example: take FOL with two constant symbols ${\sf a}, {\sf b}$, and the formula $\phi \equiv {\sf a}={\sf b}$. Then $\phi$ holds in some models (those which interpret $\sf a$ and $\sf b$ with the same point), but not all of them (a model can map them to distinct points). And indeed, FOL can not prove ${\sf a} = {\sf b}$ nor ${\sf a} \neq {\sf b}$.


Advances in recent time in Von-neumann self replication idea I have read about Von-neumann self replication from  Theory of Self-reproducing automata, which are lecture notes reconstructed from lectures in book of the same name. Theory of Self-reproducing automata

  Its looks really interesting that neumann has formalize this even far before the discovery of DNA. I'm looking the work now from biological perspective and the work by Jeremy England his paper on Statistical Physics of Self-Replication and other similar work in irreversible biological process.

The work that Von-neumann did was around 50's. Is there any recent relevant work in this field based on the neumann's work. One that i could see is Enhancing the Robustness of
Self-Replication Processes

Thank You.

For those who don't know, I am the world's only producer of a von Neumann 29-state self-replicating cellular automaton.
Indeed, respecting vNCA, I am the world's expert.  Ask Sayama (U Binghamton), Reggia(U of Maryland), or Adamatzky (U of South of England).
While DW may be a moderator, he does not know anything about von Neumann's cellular automata, I dare say he has not designed such self-replicators, and he certainly had not designed a machine zygote.  For my design of a machine zygote, see here:
https://www.researchgate.net/publication/235432119_Computational_Ontogeny
One more thing, it is 29 states, not 28.


Pushdown Automata - can you have multiple transition functions options between 2 states? I was wondering if you have 2 states, lets say q0 and q1. Are you allowed to have multiple options to transition between these 2 states?

For example,

 - if you have a 1 and the stack is empty, push it on the stack, and transition to q1
 - if you have a 0 and the stack is empty, push it on the stack, and transition to q1
 - if you have a 1 and there is a 1 on the stack, push it on the stack, and transition to q1
 - if you have a 1 and there is a 0 on the stack, pop the 0 off, and transition to q1
 - if you have a 0 and there is a 0 or 1 on the stack, push it on the stack and stay in q0

I was wondering if this is allowed, and it knows what to do given the scenario?

Sorry if this is obvious, I have been looking at some PDAs and haven't seen any that have multiple options to transition between states and was wondering if it was allowed.

Simple answer: yes, that is allowed. In the example you give, it's simple--depending on the input symbol and the stack contents, there's one and only one choice for the action of the machine in state $q_0$. It's even possible to have several actions as consequence to a single (input, stack top) pair, like this,

-- input 0 and stack top 1, push 0 and go to state $q_2$

-- input 0 and stack top 1, push 1 and go to state $q_3$

Seems wierd, I know but such machines are called nondeterministic pushdown automata and are quite useful; look them up.