Does 2-edge-colourability imply 2-colourability? Why is it that if the edges of an undirected graph G can be grouped into two sets such that every vertex is incident to at most 1 edge from each set, then the graph is 2-colorable.

The reason that I am guessing this happens is because the graph is bipartite. But I was not sure about this... I was trying to show it was bipartite and then show thus that it was two colorable, but I didn't really know how to start showing it was bipartite. Somebody know of a rigorous way to show this? Or what the intuition for the proof is?

Hint: Consider a cycle in your graph. The edge colors must alternate, so the cycle must have even length. A graph is bipartite iff it has no odd cycles.


Exhaustive list of ways to distribute n objects to k sets I am working on a research paper and we are developing a brute force algorithm to examine another clustering technique.

In this brute force algorithm we test every possible clustering example and see what natural clusters occur.

The problem comes from the assignment of every possible clustering. If give each value a cluster sequentially the complexity is much higher than necessary and results in many overlaps.

Sequential Example: 5 objects into 3 clusters
 11111, 11112, 11113, 11114, 11115, 11121, etc. . .

But 11112 and 11113 are effectively the same. The complexity above is O(k^n) where k is the number of clusters and n is the number of objects. This makes for a terrible time afterwards because duplicates will not be fun to work with and parse. Looking at natural clusters becomes easier with more points as well, and in a simple example, assigning 20 to 5 results in 3,200,000 mostly duplicate clusterings.

If we look at this using combinatorics then we can assign n objects to k groups in (n + k - 1) C (k - 1) ways. This results in 20 objects to 5 clusters having only 10626 different combinations.

Is there any way already made to exhaustively produce these arrangements in this way to eliminate the duplicates?

The objects you are interested in enumerating are counted by Stirling numbers of the second kind. In particular, $\genfrac{\{}{\}}{0pt}{}{n}{k}$ is the number of ways to partition a set of size $n$ into $k$ non-empty parts. The Stirling numbers satisfy the recurrence
$$
\genfrac{\{}{\}}{0pt}{}{n+1}{k} = k\genfrac{\{}{\}}{0pt}{}{n}{k} + \genfrac{\{}{\}}{0pt}{}{n}{k-1}.
$$
Indeed, either element $n+1$ is in a partition of its own, or it joins one of the other $k$ parts. The initial conditions are $\genfrac{\{}{\}}{0pt}{}{0}{0} = 1$ and $\genfrac{\{}{\}}{0pt}{}{0}{n} = \genfrac{\{}{\}}{0pt}{}{n}{0} = 0$ for $n > 0$. In other words, if $n = k = 0$ then there is a unique solution (the trivial solution), and if $n = 0$ or $k = 0$ otherwise then there are no solutions.

You can use this recurrence to recursively generate all partitions you are after.


Page cache and its relationship to page table I was reading about the page cache Page cache - the cache in memory for files, but I couldn't find the answer to my question. Does the page table have anything to do with, or maintain any entries, for the page cache? My guess is no, despite the similar sounding name, as the page table only stores entries for text/code, stack, and heap segments for a process (i.e., virtual memory).

The only link is that they both operate with the same page size and, well, the same pages.

The reason is the mechanism of file access. You can request access to file via mapping its contents into memory space. In this case, the entire file isn't read into memory at once, instead, the page table is filled with inaccessible pages. Once application tries to access these pages, the actual file contents is read into memory.

So, the file cache stores individual pages of files, and this mechanism is described in the page cache article.


Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free? Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free ?

If we fix $n \in N$ then we know that the language $L = \{ a^ib^j \mid \ \forall \ 1 \le k \le n \ , \ \  j\neq ki \} $ is context free (as it can be presented as a finite union of context free languages in a similar way to the example here: Is $L= \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $ context free?)

I think that it's not context free but have failed to prove it.
By reading other questions on this site I noticed this interesting observation: CFL's in $a^*b^*$ are closed under complement as can be seen here: Are context-free languages in $a^*b^*$ closed under complement?

So our language $L$ is context free if and only if $ \bar L = \{ a^ib^j \mid \ \ i\ \mid\ j \ \} $ is context free. I tried using the pumping lemma but  to no avail.

Thanks in advance

If I'm not mistaken, you can pump $\bar L$ using $\sigma = a^{n}b^{n^{2}}$, because $n \mod n^{2} = 0$. The result is that $\bar L$ is not context free. The property that you mentioned has an "iff", then $L$ is not context free.


Loop-invariant code motion with unsafe operations There are well-known algorithms LICM, and they work well.
Unfortunately, there are certain cases when these optimizations can cause runtime failures with code that was initially correct.
Consider the following example:

read a
read_array bs
for (b in bs) {
    if (a != 0) {
        c = 5 / a
        print b * c
    }
}

applying loop-invariant code motion we find that c = 5 / a is loop-invariant and therefore can be moved out of loop.
These may cause runtime error when a == 0, though original code works fine.

What to do then?
I am not certain, but I have several ideas.

We can refuse from optimizing potentially unsafe instructions
We can apply loop unswitching before loop-invariant code motion.
But I would not rely on this optimization, since it must be applied
carefully to avoid code bloating.
When moving unsafe instructions out of loop body we add range checks.
However, it again causes code bloating
(but not as great as in the previous case).
Also this approach harder to implement, since we can't put these checks
into single basic block, unless we have a special division instruction
that does not cause runtime error.
Perform range analysis before applying LICM.
If divisor is never equal to zero, don't perform LICM.

Are there best practices to deal with such unsafe operations?
Notice, that I am looking primarily for algorithms appropriate for SSA form.

This kind of optimization is more difficult than typical data-flow based transformations, because you need to actually change the branching structure of the control flow graph.

You need something more than SSA (or something more than the dataflow graph you get from reaching definitions.)  That "something" is the control dependence graph (which relies on the same (post)dominator analysis that you use to construct the SSA graph.  (Google for "program dependence graph" (which is the combination of the control-dependence graph and the SSA data-flow graph).)  Loop invariants (including loop invariant conditionals) are "obvious" in the program dependence graph.  A loop invariant is any node all of whose data and control dependences come from outside the loop.

Unfortunately, in the general case, rebuilding a control-flow graph from the program-dependence graph is somewhat involved.  (Google for "percolation scheduling" and "gated SSA form" if you are interested.  Also (self promotion) my dissertation gives a (terse) overview of a method for converting from PDG back to CFG.)  You can, luckily, do something substantially simpler if you are willing to restrict your transformation to specific structured control flow (in your case, an if-else block inside a do-while block.)  This is the same simplification that loop unswitching makes.

So working through the steps.  First convert while and for loops to if-do-while

read a
read_array bs
b = bs.first
if (b is not bs.end):
  do:
    if (a != 0):
      c = 5 / a
      print b * c
    more stuff
    b = b.next
  while (b is not bs.end)

Then (as with loop unswitching) you see that a != 0 is loop invariant, so the if statement is loop invariant, so any statements inside the if block that are loop invariant (c = 5/a) can be moved out of the loop (along with the conditional that protects those statements.)  Essentially what you are doing is breaking each invariant conditional block into the parts that are and are not loop invariant:

read a
read_array bs
b = bs.first
if (b is not bs.end):
  do:
    if (a != 0):
      c = 5 / a
    if (a != 0):
      print b * c
    more stuff
    b = b.next
  while (b is not bs.end)

Then you can move the entirety of the blocks that are completely loop-invariant out of the loop:

read a
read_array bs
b = bs.first
if (b is not bs.end):
  if (a != 0):
    c = 5 / a
  do:
    if (a != 0):
      print b * c
    more stuff
    b = b.next
  while (b is not bs.end)


Shortest cycle for each vertex I have an unweighted undirected graph.How is it possible in this graph for each vertex to find the length of the shortest cycle containing it?

P.s
This graph have not non-tree edge, but it have a cycle. What can be considered subtrees of the vertical 10? How will the algorithm work when the BFS reaches 16 and 17?

An easy way is as follows: For each vertex $s$, perform a BFS visit to discover the shortest cycle containing $s$.

When a visit from $s$ is performed a BFS tree $T_s$ is built and each non-tree edge $(u,v) \not\in E(T)$ for which $u$ and $v$ belong to different subtrees rooted in the children of $s$ in $T$ tree induces a cycle containing $s$.
Since, the shortest cycle containing $s$ must use a non-tree edge $(u,v)$ with this property, it will be found by the visit. You can optionally stop the visit early: if you find a cycle while visiting $u$, you can stop the BFS as soon as all the vertices in the level of $T$ containing of $u$ are visited.

The overall required time is $O(n \cdot m)$.


How does the index of a disk work in finding the desired address? I've been trying to understand computer concepts and such recently and I've been curious to know how the process works of a processor asking for an address and sending the bits to the hard drive, as well as how the hard drive index works when it's just a bunch of magnetic specs that cooperate with a mechanical arm. What does the index say to the system? How do the processor and HDD cooperate? Hopefully I'm asking on the right website this time due to the fact that I accidentally posted this question on the Computational Science site. Thanks

-Ryan

The index specifies the cylinder, head, and sector where the data resides.  The hard drive then moves the arm/head so it is positioned over that block and reads the data stored in that block as the disk rotates under the arm.  The hard drive then sends that data back to the processor.   Read http://pages.cs.wisc.edu/~remzi/OSTEP/file-disks.pdf for more of an overview how hard drives work.


Search in a partial ordering defined by tuples of numbers This is a graph theory and partial ordering problem. Consider a set of triples {(di,ai,ci)}i=1...N, which specify edges between two nodes A and B, d denotes a departure time, a an arrival time and c a cost. Technically there can be multiple incomparable costs, for example in $ and % chance that your goods arrive safely.

An example of such a situation could be these 5 edges:

(I did not draw the time axis on scale)

There are five edges, I, II, III, IV and V. The costs are denoted at the edges, they are either 100, 10 or 1. Edge V is drawn red to easily discriminate it from the other edges, since it crosses through them. However, aside from that it is not different.

Given such edges, a few things are important:

An edge is only interesting if it departs after we arrive at A, for example in the image we can arrive at (a), then edge I is not an option anymore. The same goes for edges II and V if we arrive at (b), etc.
Given an arrival and its set of interesting edges, and edge ei is dominated if there exists an edge ej with ej< ei. This is the case iff aj ≤ ai ^ cj ≤ ci ^ (aj < ai v cj < ci). In layman terms, cost and arrival need to be at least as small, but one must be strictly smaller. This is a partial ordering, some edges are incomparable.
Given a arrival in A, I want to find all relevant, undominated (or Pareto) edges.

We can enumerate all the edges:

I:   (0  , 1, 100)
II:  (0.5, 2, 10)
III: (2  , 3, 100)
IV:  (2.5, 4, 10)
V:   (1.5, 5, 1)

Putting them in a partial ordering, using a directed acyclic graph (dag), we get this:

An arrow denotes the <-relation between edges. Note that an edge in this case is a node in the dag: confusing, I know. When I say edge, I mean a node in the dag above.

I added an edge (-∞, -∞), which is always irrelevant, but creates a nice 'root' of the dag. This way we sort of have a tree, where leaves sometimes merge without creating cycles. I also only denote the arrival at B and cost, needed to create the dag, but technically there is also a departure are A for each of the edges.

If we were to arrive at A at -1, we can simply return all the children of (-∞, -∞) as relevant and undominated, but for another arrival we may need to traverse the tree differently (in a more complicated fashion). I was thinking of this:

marker := map from edge to bool # marks whether edge has been traversed
for all edges: marker(edge) := false # none have been traversed

traverse(root, arrival):
    if(marker(root)) return []  #already been at this node
    marker(root) := true;
    if(departure(root) > arrival) return [root]; # return singleton list, all children will be dominated by this edge.

    # this node is irrelevant, but possible some children are relevant.
    l = [];
    for each child of root:
        append traverse(child, arrival) to l
    return l

Traverse returns a list of undominated, relevant edges. However, Is this an efficient way to tackle this problem? Is there a better solution to this problem? Is this problem known under a known name?

I solved my OP as my intuition was. First I created a graph as described by the second picture of the OP. Then I traverse it like this:

global: visited, front

function proceed(arrival)
    visited := array of bool for each node initialized to false
    for each x &isin; front
        proceed(arrival, x)
    return front

function proceed(arrival, node):
    if(visited[node]): return
    visited[node] := true
    if(node.departure > arrival):
       remove node from front
       for each node x:
           append x to the end of front

function calculate_outgoing:
    outgoing := array of lists for each arrival at A, each list contains feasible and relevant A->B connections for that arrival.
    front   := [(-&infin;, -&infin;)]
    for each arrival at A in increasing order:
        outgoing[arrival] := proceed(arrival)
    return outgoing

Initially only the root of the dag is in the is in the front. Then the front is moved towards the 'leaves' of the dag as the arrival times increase, that is, certain options 'fade away' and hence are replaced by other options.

Notice that I have a tree-view on the dag. The key difference is that a node can have more parents, hence I mark which nodes are already visited, preventing one from visiting them twice via different parents.

I find this solution more satisfying then @d-w's, since he did not address the problem of multiple costs, like stated in the OP: "Technically there can be multiple incomparable costs, for example in $ and % chance that your goods arrive safely.", nor did he comment on it. If you have only one cost, his solution is adequate.


Time complexity of a 3 nested for-loop for(i = 0; i<n; i++) {
    for(j = 1; j<i*i; j++) {
        if(j % i == 0) {
            for(k = 0; k<j; k++) {
                //statement;
            }
        }
    }
}

Here, it's been asked to find the time complexity. I think it's O(n^4), but prof. said it's wrong. Can someone explain how this works ?

First, to get some idea add code to your program that counts the operations and prints the total, then try with n=1, 10, 100 and 1000.  That’s not exactly scientific but is a hint about the correct answer. If n= 1000 takes too long, try 200, 300, 400.

Now: How many steps does the innermost loop perform at most, depending on I? And for a given I, how often is the whole loop performed? And how many values of i are there? That together gives you an upper bound, and guess what - it looks like O(n^4) to me.

I’ve just typed this on my phone, so you do it much more carefully and you may show be able to show your professor that you are indeed right. If the code is exactly what you wrote.

A bit more precise: The inner loop for k has j iterations. j % i == 0 is true when j is a multiple of i, that is j = i, j = 2i, j = 3i, ..., j = (i-1) i. So for a given i, the executions of the inner loop are i, multiplied by the sum over j for 1 ≤ j ≤ i-1. That sum is (i-1)(i-2) / 2, so the inner loop executes i (i-1) (i-2) / 2 times, which is quite exactly $(i-1)^3 / 2$ times.

We have 0 ≤ i ≤ n-1. Ignoring i = 0 and i = 1, 1 ≤ i-1 ≤ n-2. So the number of executions of the inner loop is about $((n-3)(n-2))^2 / 8$.


Machine Learning to predict the Halting Problem I seem to recall an academic paper from some years ago which used machine learning (possibly genetic or evolutionary programming) to predict whether a Turing Machine would halt.

By predict, I mean the standard notion in ML: minimize the error on some validation set. For simplicity, let's assume that the ML is a binary classifier,  (although AFAIK the actual paper may have framed it as a regression problem).

The notion is then not 'solving' the Halting Problem (which we know is impossible), but rather using ML to agree with an Oracle that knows the answer on the training (and validation) set.

However, I haven't been able to find anything so far.

Does anyone know of a reference?

After some digging around, I finally came across the original paper.

Regarding applications of a (necessarily fallible) predictor of halting - one possibility is to use it as a heuristic in some wider heuristic process, for example in the generation of Turing-complete programs for Genetic Programming.


Concatenation of languages in NP I have a hard time to understand why the concatenation of two languages over an alphabet (concatenation is in NP), doesn't imply that each of the languages for themselves are in NP. I talked with my Prof about the problem today, but I can't wrap my head around it. Can you help me out?

Take the concatenation of $\Sigma^*$ with any language that contains the empty word but is known not to be in NP (for example, an undecidable language).


Could someone explain Fagin's theorem on the equivalence between NP and existential quantifier This quote on descriptive complexity theory is given in Wikipedia:

"The first main result of descriptive complexity was Fagin's theorem, shown by Ronald Fagin in 1974. It established that NP is precisely the set of languages expressible by sentences of existential second-order logic; that is, second order logic excluding universal quantification over relations, functions, and subsets."

Is there a simple proof of the theorem?

You can check out these lecture notes, as well as countless more. The proof of Fagin's theorem is divided into two parts: showing that every language expressible in existential second-order language is in NP, and showing that every language in NP is expressible in existential second-order language. The first part is easy – we just have to guess the quantified relations. The second part is more complicated, but resembles the proof of Cook's theorem. The idea is that the quantified relations encode the computation of an NP machine.

For more details, you can consult Neil Immerman's book Descriptive Complexity.


Is paradox recognition paradoxical or not paradoxical? Russell's paradox: The set that contains all the sets that do not contain themselves. Does it contain itself? It contains itself if and only if it does not contain itself.

Russell's paradox for the lambda-calculus: The functions that may not be applied to themselves when combined with themselves, they negate themselves.

lambda calculus uses anonymous functions called lambda-expressions. So, the paradox re-stated in lambda-calculus terms becomes:

The lambda-expressions that may not be applied to themselves when combined with themselves, they negate themselves.

If such a lambda-expression is encoded into a string w, then input to a Turing machine, will the Turing machine (Paradox Recognizer machine) accept it? not accept it: reject it? or loop forever?

Thanks in advance for your comments.

Rafee Kamouna.

Russel's paradox does not apply to the lambda calculus. Intuitively speaking, Russel's paradox comes up when there is a level system (e.g. sets that are members of “bigger” sets one level up), and there is a form of negation. The lambda calculus has neither: all lambda terms are at the same level and there is no negation.

I don't know what you think you mean by “The lambda-expressions that may not be applied to themselves”. Any lambda term can be applied to any lambda term.

An analog of Russel's paradox (or rather the similar Burali-Forti paradox) arises in the higher-order typed lambda calculus, where terms have types that themselves have types. If $\mathsf{Type} : \mathsf{Type}$, it's possible to construct a well-typed term that of type $\mathsf{Type}$ that does not terminate. See Example of a false proposition when assuming Type : Type. As can be done in set theory, type theory can solve the problem by adding a universe stratification: base types have the sort $\mathsf{Type}_0$ and higher-order types obey $\mathsf{Type}_n : \mathsf{Type}_{n+1}$.


Compiler instructions to sync core caches: are they really needed? I have read reviews of this book, and quote the following from one of the reviews (emphasis mine):

  Other than straining your eyes with old-styled C++, you can read such
  misconceptions in the book like "Since Boolean values are generally
  atomic, setting and checking can be done simultaneously without risk
  or requiring a mutex." Which ignores the facts that, the compiler
  doesn't necessarily have to generate instructions to resync the value
  in register with the one in memory. And even if it does, the hardware
  doesn't have to resync the cache lines.

I have also followed all of the "High Performance Computer Architecture" course from Georgia Tech (also on YouTube) and learned about cache coherency protocols.

From what I have learned, modern processors will use the write-invalidate protocol; when one core writes to a block, any other cores that share this same block will learn of the change via an invalidation message sent on the bus so they will have to go and get the new value from memory instead of using their cached copy.

With this in mind, what is the author of this comment talking about?  It seems the coherency protocol is doing everything for me, hence there is no need to use synchronisation?  Are they wrong or am I missing something?

PS Yes I know I mention C++ but I feel this is more hardware related hence me asking it here.

PPS If I've missed something, please post a link to the information before just downvoting; a downvote without explanation is useless.

Update

If a boolean b was being used in two threads, each one on a different core, what would making the variable atomic/using a sync variable do regarding the cache coherency that doesn't happen with a none-atomic var/no use of a sync variable?  (I think this is the problem in my understanding - I am believing that the cache coherency protocol fires off "for free" (is this right?); or do I need to use some special instruction to "start it off" (that is, trigger the sending of the invalidation message on the bus) for want of a better phrase?)

Update 2

Write Invalidate Snooping Coherence - Georgia Tech - HPCA: Part 5 talks about how the caches of different cores operating on the same block are synchronized.

My confusion stems from the fact that the comment I quote seems to state that boolean values are not guaranteed to be synchronized between caches on different cores, and that some sort of atomic operation or synchronization primitive (eg mutex) is needed to do this.  The video I link to however mentions nothing of the sort; it suggests (to me at least) that the caches are updated automatically by virtue of the coherency protocol, not by any special instructions (such as those generated for atomic operations or synchronization primitives) in the code.  This is what I am asking for clarification on.

This is very simple actually, and has nothing to do with hardware whatsoever. If you have a variable

static bool b;

and some code

b = true;
dosomething();
b = false;
dosomethingelse();
b = true;

If the compiler can figure out that dosomething() and dosomethingelse() don't read or write b, then the compiler is not required to generate code for the assignments to b, except the last one.

With the book's subtitle "Write robust, concurrent, and parallel applications" this is quite worrying.


Extending ordered tree edit distance to DAGs Computing edit distance (shortest sequence of edit operations) on ordered trees is a well studied problem with many known algorithms (e.g. Zhang & Shasha, RTED). There is also considerable literature on edit distance for general graph (e.g., this review). I am however interested in a mixed case that has arisen in our inquiries into RNA structures in computational biology: how to compute edit distance between directed acyclic graphs (DAGs) with ordered children, i.e. a DAG where each node imposes a total ordering on its outgoing edges. There seem to be multiple ways to define edit operations on such "ordered DAG" but as a first approximation, I don't care about which edit operations are primitive. I was unable to find any literature on this problem.

Is there a known algorithm for edit distance on ordered DAGs (or more general graphs with ordered outgoing edges)? Or can some of the known tree edit distance algorithms be easily extended to cover DAGs?

Note that I cannot defer to algorithms for general graph edit distance as those (AFAIK) don't take order of outgoing edges into account.

So after some thinking and digging around, I know believe (no rigorous proof) that edit distance between ordered DAGs is NP hard (in fact even Max-SNP hard) and thus no efficient algorithm is likely. The informal reasoning follows:

Edit distance between RNA structures with pseudoknots is Max-SNP hard and the reduction to Max-Cut works even if we ignore the RNA sequence (Ma, Wang & Zhang, 2002: Computing similarity between RNA structures)
One can represent an RNA structure with pseudoknots as a DAG with ordered children and labelled edges by extending the tree representation from Zhang & Shasha 1989: Nodes still represent base pairs and unpaired nucleotides, "normal" edges represent the "is contained in" relationship and new type of  edges to represent a "contains only first nucleotide of a base-pair" relationship let us represent crossing base pairs.
An algorithm for edit distance on labelled DAGs would therefore likely give an algorithm for Max-Cut which is Max-SNP hard. This obviously depends on what edit operations are allowed, but it seems to work for any sensible set of edit operations I came up with.


Hardness of approximation of the 3 colorability problem If we have polynomial algorithm that $c$-approximation, $c<\frac{4}{3}$ for graphs that their chromatic number $\geq k$ then $NP=P$, how to prove such statements?

I also have some sort of explanation of this statement: It's NP-hard to separate between graphs that have chromatic number $k$ and chromatic number $c \cdot k$ when $c<\frac{4}{3} \quad \forall k\geq 3$


Resolution and incomplete Knowledge Base Assume I have an incomplete knowledge base, for example:

(rich(dave), poor(dave))  // dave is either poor or rich

(not rich(dave), not poor(dave))  // dave is not poor and rich at the same time.

My questions are:
1. If I do resolution on the above clauses, will I get the empty clause?  and 2. If Yes, Does that mean my knowledge base is inconsistent?

The theory is not inconsistent and trivially admits two different models :

a first one in which dave is rich but not poor;
a second one in which dave is poor but not rich.

You're maybe confusing the "empty clause" which contains no literal, thus being always false, with the "true clause" which contains both a literal and its negation, thus being always true. Applying resolution leads to the "true clause" resolvent, not the "empty clause".


Constrain certain variables in CNF to unique satisfying assignments [Reposted because the original question was deleted by the poster.]

I'm looking for a way to add additional clauses (and maybe additional variables) to an already existing SAT instance so that solutions with non-unique assignments for certain variables are invalidated.

Currently I enumerate all the original solutions, and filter out the bad solutions having duplicate partial assignments on specific variables. But this becomes impractical when there are many solutions to the original instance, compared to a very small number of good solutions.

If the SAT solver had information within the CNF that duplicate partial assignments on certain variables invalidate any solution that contains those partial assignments, it would speed up the search significantly.

Here's an example with 16 variables: 90 original solutions, 42 filtered solutions. https://gist.github.com/re-curse/7b1c970768400ef5d0fe

This example instance generates 90 solutions, but 48 solutions are bad because they duplicate assignments for variables 1-8 or variables 8-16. I need to add clauses to the CNF to filter out those bad 48 solutions while the solver searches instead of retroactively filtering after enumerating all original solutions.

An example of two bad solutions for this instance are (00110110 00110110) and (00110110 00111001) because variables 1-8 have an assignment [ie. 00110110] that shows up more than once in the 90 original solutions.

If you could add clauses to a CNF formula to cause it to be unsatisfiable iff certain sets of variables don't have non-unique assignments among the formula's satisfying assignments, you could use this same method to solve UNIQUE-SAT for any CNF formula.  Since UNIQUE-SAT is co-NP-complete, you'll have proven NP = co-NP.  So it is unlikely there is a solution to the problem that involves simply adding clauses.


Why is 2^32 in a 32-bit system = 4GiB and not 4Gib? I was watching this video 32-Bit vs 64-Bit - The Advantage and at 1:19 (timestamp) the narrator mentioned the 4GB memory allocation for the 32-bit system. I later found out it should've been 4GiB but am still confused about the bit vs byte part. After all, it's a 32-"bit" and not 32-"byte" system.

"32-bit" describes the size of many of the units of data that the processor can use. In this context, it refers to the size of memory addresses. A 32-bit address can address $2^{32}$ distinct objects; in a byte addressable system, that means it can address $2^{32}$ distinct bytes.

We don't give addresses to individual bits in memory, but rather groups of bits. In a byte addressable system those are bytes (ie, octets of 8 bits); you can also have a word-addressable system where you can only address groups of, say, 32 bits. In a system with 32-bit addresses addressing 32-bit words, you'd be able to use $32 * 2^{32}$ bits, or 17GB! But nowadays most consumer hardware in phones/computers are byte addressable.

Concretely, in byte-addressable memory, the first 8 bits are referred to as byte 0, the next 8 bits are referred to as byte 1, and the last 8 bits are referred to as byte 4294967295. There is no pointer to individual bit 26; you instead need to read/write the entire byte that contains it (byte with address 3 contains the 27th bit)


Pumping lemma for regular languages vs. Pumping lemma for context-free languages How can I prove the next claim:
If a language $L$ meets the pumping lemma for regular languages then $L$ meets the pumping lemma for context-free languages?
(Without any pre-condition about the regularity of $L$)

The pumping lemma of context-free languages means finding $x,y,z,v,u$ such $w=xvyuz, |vu|>0,|vxu|\le p$, and for all $n\in\mathbb N$, $xv^nyu^nz$
The regular pumping lemma means finding only $v,y,u$ where $w=abc,|b|>0,|ab|\le p$ and $ab^nc\in L$. ("a","b","c" here are representing sub-words of w)
So, simply take $x=a,v=b,y=c,u=\epsilon,z=\epsilon$


What is the combinatorial reasoning for the $n$ factor in $n \times n! / (b!(n - b)!)$? I am currently studying the textbook Artificial Intelligence: A Modern Approach, 4th Edition, by Russell and Norvig. Chapter 3 Solving Problems by Searching says the following:

Another type of grid world is the sokoban puzzle, in which the agent's goal is to push a number of boxes, scattered about the grid, to designated storage locations. There can be at most one box per cell. When an agent moves forward into a cell containing a box and there is an empty cell on the other side of the box, then both the box and the agent move forward. The agent can't push a box into another box or a wall. For a world with $n$ non-obstacle cells and $b$ boxes, there are $n \times n! / (b!(n - b)!)$ states; for example on an $8 \times 8$ grid with a dozen boxes, there are over 200 trillion states.

I understand the combinatorial reasoning for why we get $n! / (b!(n - b)!)$ (the binomial coefficient), since we are looking for the number of ways we can choose (with replacement) $b$ boxes from a world with $n$ non-obstacle cells. But I don't understand where the $n$ factor in $n \times n! / (b!(n - b)!)$ comes from. What is the combinatorial reasoning for this $n$ factor?

Part of the state of the world is the location of the agent. Since there are $n$ cells, this variable has $n$ possible values, producing the factor of $n$.
Actually, there may be a mistake in Russell and Norvig's formula. After we have chosen the location of the agent, there are only $n - 1$ possible locations for the $b$ boxes, giving us $(n - 1)! / (b! (n - b - 1)!)$ choices for where to put all of the boxes. So, the number of states is $n \times (n - 1)!/(b!(n - b - 1)!)$, which simplifies to $n! / (b! (n - b - 1)!)$. (This is the trinomial coefficient $n \choose 1, b$.)


Why is it necessary to use binary numbers in logspace? I have noticed that a lot of problems that are in L and NL use binary numbers. I don't understand why this is the case. Does a TM use less space by storing a binary number, than a "normal" one. In my head, it uses less space to store the number 0, than the binary ecquivalent number 0000. Hope someone can help me understand :)

The "usual" encoding of numbers is binary. Binary can mean two things:

Encoding a number in the range $0,\ldots,2^n - 1$ using $n$ bits.
Encoding an arbitrary natural number.

In the latter case, the "width" or "length" of the number is not known in advance, and so some special encoding has to be used. An especially simple one encodes a number $b_0 \ldots b_{n-1}$ as
$$ 1b_0 1b_1 \ldots 1b_{n-1} 0. $$
This is known as a self-delimiting encoding. If you allow the input alphabet to be larger, then you can use a non-binary character as a separator instead, which is a popular convention.

We are more used to decimal numbers rather than binary numbers. In terms of encoding length, the two differ by a multiplicative constant, so binary encoding and decimal encoding are equivalent for most purposes. Binary encoding is used since sometimes we imagine the input encoded as a string over $\{0,1\}$ (this is the case when we talk about circuits, for example).

The other option is unary encoding, in which the number $n$ is encoded by $1^n 0$ (that is, $n$ times the bit 1 followed by the bit 0).

Encoding $n$ takes $n+1$ bits in unary, but only $\Theta(\log n)$ bits in binary. This can make a huge difference in complexity theory, since the running time is measured in the size of the input. For many problems, however, the number parameters pale in length compared to other inputs (say an input graph), and so the exact encoding used is not important.

Here is an example in which encoding is important. Many cryptographic algorithms include a subroutine that accepts $n$ and outputs a key of length $n$. If the input is encoded in binary then its length is $\Theta(\log n)$, and so the subroutine must run in exponential time (since the output is of length $n$). If the input is encoded in unary then there is no such restriction. This is why in such algorithms, $n$ must be encoded in unary.

In other cases, encoding an input parameter in unary might make the problem too easy, and so it is important to encode it succinctly. Unfortunately, I can't think of any such problem right now, since as stated before, usually the number parameters are dwarfed in length by other inputs.


Find a subgraph whose edge weights sum to at least the number of nodes Given a graph G = (V,E)
  every edge is assigned a real number Xe $\in$ [0,1]

  The sum of x variables for all edges is equal to the number of edges -1 : $\sum x_V = |V|-1$

  For a subset S $\subset$ V let us denote by $E_{(S)}$ the set of all edges with both endpoints in the subset S.

  Give a polynomial time algorithm that takes as an input graph G and numbers $X_e$ for e $\in$ E, and either finds a subset S such that

  $\sum_{e \in E(s)} X_e  > |S|-1 $

  or says that no such set S exists.

Analysis of its correctness and its running time.

Any suggestion please ?

---------------------------- IDEAS

min-cut project selection
min-cut baseball elimination
dynamic programming

I was trying to build a list of dictionaries, storing for each node, the sum of the edges of every subgraph in which it is.

work in progress..

Your problem is very similar to the classical densest subgraph problem, in which you want to maximize the ratio $|E(S)|/|S|$. Goldberg gave a polynomial time algorithm for this problem based on network flow. Perhaps you can use his ideas to solve your specific problem as well.


Designing a DFA and the reverse of it There is a theorem that says if a language is regular, its reverse is regular as well. How can I draw a DFA that shows if a language is regular, it's regular as well?

$L^R$ is the reverse of the language $L$ and for designing $L^R$ you must:

Reverse all edges in the transition diagram.
The accepting state for the LR automaton is the start state for the main automaton.
Create a new start state for the new automaton with epsilon transitions to reach of the accept states for the main automaton.
Convert this NFA back into a DFA.


Finding Euclidean Minimum Spanning Tree Given a set of point $P$. Find the euclidean minimum spanning tree where each points is equally distributed on the plane using randomization.

We can solve this problem with Prim's algorithm in $O(n^2)$ which is too slow. I've found an algorithm called Delanuay Triangulation but is there any other ways to solve this problem in $O(n log n)$ or faster?

If you're asking this question because you want something easier to implement than a Delaunay triangulation algorithm you're most likely out of luck.

You should also specify in what space you're operating. If you're working with $\mathbb N^2$ coordinates, you can possibly do it in $\mathcal O(n \log\log n)$ (with a randomized algorithm to generate the triangulation).

If you have $P\in \mathbb R^2$ your choices (ordered by difficulty of implementation from easiest to not-easiest) are:

Delaunay triangulation
WSPD based approaches (first find clusters on Quadtree of $P$, then build MSTs for each cluster and then connect clusters to get complete MST)
Improved version of Boruvka's algorithm: paper

The last one is also an improvement over the other two in higher dimensions. This answer is more or less a condensed version of the literature review of the linked paper.


Find nth number which does not contain the digit c This problem was given to 9-graders. We write down numbers except for the ones which contain the digit c. Find the nth such number. I looked at the indications, but the algorithm used there stumped me. I will describe in here: if $c \ne 0$, then we transform the number n - 1 (since 0 is part of the series) in the 9th base. Then each digit in the representation of the 9th base which is bigger of equal than c and smaller than 9 will be incremented with 1. The number we obtain is the number we are looking for, BUT IN BASE 10. How? Could anyone explain it to me? Also, please, be patient since I have just started Competitive Programming and I am not really that good.

Let's do it in base 3.
Here are the first 8 numbers without 2 (left column) and the first 8 numbers without 1 (right column), with zero padding:
000    000
001    002
010    020
011    022
100    200
101    202
110    220
111    222

Hopefully you can take it from here.


If $B$ is worse than $A$ on some inputs, how do their worst-case time complexities compare? You are given two algorithms $A$ and $B$, with worst-case time complexity $f_A(n)$ and $f_B(n)$, respectively.

Assume:

(i) For each $n$ there exists an input $x$ of size $n$ such that the number of steps of algorithm $A$ on $x$ is half the number of steps of $B$ on $x$.

(ii) $f_A(n) = \Omega(h(n))$ for some positive function $h(n)$.

Is it possible that $f_B(n) = \Omega(h(n))$
Is it necessary that $f_B(n) = \Omega(h(n))$?

Explain your answers.

You are essentially asking the following question:

  Suppose that $f(n) \geq g(n)$ for some $n$. Is there a universal constant $C$ such that $\min_n f(n) \geq C \min_n g(n)$?

Hopefully this formulation makes it easier to answer.


What is the difference between control flow graph & interprocedural control flow graph? I am doing research on control flow analysis on aspect oriented programs and I found in some papers an interprocedural approach for doing control flow analysis on others call graph or control flow graph. Is there a real difference between control flow graphs and interprocedural control flow graphs?

CFG (Control Flow Graph): representing control flow for a single procedure
IPCFG (Inter-Procedural Control Flow Graph): representing control flow for a program

source: http://web.cs.iastate.edu/~weile/cs513x/4.ControlFlowAnalysis.pdf


Karp hardness of searching for a matching cut Follow-up question in the series:
Karp hardness of searching for a matching erosion
Karp hardness of searching for a matching split

Maximum Matching Cut problem
Input: An undirected graph $G(V, E)$ and an integer $k$
Output: YES if there exists $M \subseteq E$ such that $M$ is a matching of size $k$ (i.e. $k$ edges) and also a cut, NO otherwise

What is the complexity of this problem? (Turing completeness was established, what can we tell about its Karp hardness?)

An edge cut is a subset of $E$ the removal of which would increase the number of connected component of $G$, and for each edge in the set, its two endpoints are in (two) different components.

You can reduce the problem without cardinality constraint to the problem with cardinality constraint.

For an instance $G=(V,E)$ of the problem without cardinality constraint, simply add $m>|V|/2$ isolated edges as well as $2m$ new vertices. Now there is a matching cut in the old graph if and only if there is a matching cut of size $m+1$ in the new graph.

Edit: One can also add an edge $(u,v)$ for each newly added edge $(u,x)$ and a fixed vertex $v$ in the previous graph to make $G$ connected. The conclusion is the same.


Can a NP problem be reduced to another NP problem? I have three related questions which have been bothering me for a while now...

Suppose I have a problem $A$, which is in NP. Suppose there is another
problem $B$ in NP, can I reduce $A$ to $B$?
If it is possible, can this reduction be done in polynomial time?
Is it even meaningful (having any importance, in terms of complexity analysis) if we have a non-polynomial time reduction?

Help for these questions would be highly solicited!

Thanks in advance!

Suppose I have a problem $A$, which is in NP. Suppose there is another problem $B$ in NP, can I reduce $A$ to $B$?

Maybe, maybe not. It depends on what $A$ and $B$ are. I suggest you revise the concept of NP-completeness and bear in mind that every problem in P is also in NP. These will help you understand the situation better and I think you'll be able to answer your question yourself, then.

  If it is possible, can this reduction be done in polynomial time?

Not necessarily. I think when you've figured out part 1, you'll probably be able to figure this one out, too.

  Is it even meaningful (having any importance, in terms of complexity analysis) if we have a non-polynomial time reduction?

If we don't restrict the power of reductions, they're not interesting.  Let $A$ be any problem at all and let $B$ also be any problem, except for $\emptyset$ and $\Sigma^*$.  We can define a reduction from $A$ to $B$ as follows.  Choose any string $y\in B$ and any string $n\notin B$ (think: "yes" and "no").  Now define the function
$$f(x)=\begin{cases}y&\text{if }x\in A\\ n&\text{if }x\notin A\,.\end{cases}$$
This is a reduction from $A$ to $B$. It's as hard to compute as $A$ is, which could be in P, NP, quadruply exponential nondeterministic space, uncomputable, or anything else; it's independent of the complexity of $B$. Can you see why we need $B\neq\emptyset$ and $B\neq \Sigma^*$?

So unrestricted reductions aren't really of any interest. However, there are situations in which we consider reductions other than polynomial-time ones. For example, when we study computability (e.g., the undecidability of the halting problem), we usually allow any computable reduction.1 In other contexts, we use reductions that are weaker than polynomial time. There is a perfectly good concept of P-complete problems but, as a consequence of the things I wrote above (can you see why?), it's boring to consider polynomial-time reductions between problems in P. So, typically, we use logspace reductions, there.  In fact, we can consider NP-completeness with respect to logspace reductions and, as far as anybody knows, that gives exactly the same class of NP-complete problems. Sometimes, even weaker notions of reductions are used.  There are probably also contexts in which it makes sense to use resource-bounded reductions (i.e., not just any computable function) that are more generous than polynomial-time. Maybe if you were studying problems of such high complexity that, say, an exponential-time reduction would still be cheap compared to solving the actual problem.

1. Actually, thinking about it, most of the reductions you'll see in an undergraduate computability course probably can be done in polynomial time, but that's unnecessary detail if all you're trying to work out is "Computable? Yes or no."


Existence of a CFL $L$ such that $\sqrt{L}$ is not CFL Does there exist a CFL L such that the language defined as $L' = \sqrt{L} = \{w | ww \in L\}$ is not CFL? I feel that there is no such $L$ but obviously, I am unable to prove it.
I am sorry but I have not made any mentionable progress with my attempts on this problem.
I would appreciate any hint to the proof or a language $L$ that could satisfy this.

There is an example, and $L = \{a^nb^na^{2m}b^ka^k \mid n,m,k \in \mathbb{N}\}$ does the trick. We get that $\sqrt{L} = \{a^nb^na^n \mid n \in \mathbb{N}\}$, which is a standard example of a non-context-free language.
To elaborate a bit on how to get there: CFLs can express that two numbers are the same, but not that three numbers are the same. So I want the square-root operation to introduce another equality, as it seems predisposed to do so.


Shortcut for "in the worst-case, with high probability"? I am writing a paper in which the worst-case analysis of a certain randomized algorithm is correct with probability $1-1/n$ (where $n$ is the size of the problem). I find myself writing, time after time, the following sentence:

  "With high probability, in the worst case, the performance of phase A is at most X".

The worst-case is with relation to the inputs; the high probability is with relation to the randomization of the algorithm. I.e, there is an adversary that choose the worst possible inputs, but then I do a lottery on which the adversary has no effect.

Since there are many phases, this sentence appears many times throughout the paper and it looks cumbersome.  I tried to make it shorter by writing:

  "In the worst case (WHP), the performance of phase A is at most... "

This still looks cumbersome... Is there a more common way to express this meaning?

Your second example looks fine to me. "In the worst case, phase A takes time/space X whp" is even shorter.


Optimal way to pack items with multidimensional weight such that the number of items is minimized? I am given a set of items S = {a1,a2,a3,...,an}. Each item has a corresponding M dimensional bit vector indicating the properties of that item. For example, if item x has corresponding vector: {0, 1, 0}, then item x does not have property 1, does have property 2, and does not have property 3.
I am also given a M dimensional "goal" vector indicating the number of items I need that match each property. For example, if my goal vector is: {1, 3, 2}, then I need 1 item with property 1, 3 items with property 2, and 2 items with property 3.
My question is, how can I select a subset of items from the set S such that the constraints listed in the goal vector are met exactly and so that the number of items selected from S is minimized? What is the name of this problem, and what is an efficient algorithm for solving it? Also, what algorithm would I use for the opposite scenario where I would like to maximize (instead of minimize) the number of items used?
Could this be a variation on the knapsack problem or the bin packing problem?

This problem is NP-hard, so you can't expect a general algorithm that is efficient and always correct.  In particular, in the special case where the goal vector has only 1's and 0's in it, it becomes an instance of the exact cover problem.
Your problem can be viewed as an instance of the multidimensional subset sum problem.
If you have to solve it in practice, I would suggest formulating it as an instance of integer linear programming and using an off-the-shelf ILP solver.


Does there exist a problem for which no existing solution can be parallelized on a Turing machine? I'm asking for problems for which we know there exists a solution for which an equivalent parallel program cannot be written on a Turing machine.
Alternatively, have we proven the opposite to be true - that for every problem, there exists at least one parallelizable solution?

The question is not precisely defined, so it's not really amenable to a precise technical answer at this stage.  But a common view/hypothesis/expectation is that there exist problems that are inherently sequential, in the sense that they cannot be substantially sped up on a parallel computer, no matter how many parallel processors you have.  A weak version of this view is implied by the conjecture that $NC \ne P$ (see https://en.wikipedia.org/wiki/NC_%28complexity%29), which is conjectured but not known to hold.  In particular, P-complete problems are good candidates for problems that don't benefit much from parallelization.  There are stronger versions of this view; for instance, in cryptography, timelock puzzles utilize functions that are believed to be inherently sequential: a parallel processor cannot speed them up very much.


Can the following O(...) expression be simplified? I have an algorithm with three variables affecting the time complexity: $k$, $L$, and $n$. I have come up with the following that expresses the complexity:

$O(kn + k^2L + k^2nL + knL)$

I think I should be able to simplify this to:

$O(k^2nL)$

Am I correct? I'm a little fuzzy on how to simplify things when working with multiple variables, but it seems right that since every other term is a factor of $k^2nL$, it should dominate the other terms?

Suppose that there exists a strictly positive constant $c > 0$ such that $k,n,L \geq c$; this happens for example if $k,n,L$ are all positive integers. In this case, a function is in $O(kn + k^2L + k^2nL + knL)$ iff it is in $O(k^2nL)$, where for our purposes $f(k,n,L) = O(g(k,n,L))$ (read: $f(k,n,L)$ is in $O(g(k,n,L))$) if there exists a constant $C>0$ such that for all $k,n,L$ "in range" we have $f(k,n,L) \leq C g(k,n,L)$. Here "in range" is the common domain of the functions $f,g$, such as all positive integers or all positive reals which are at least $c$, for some positive $c>0$.


Approximating sign function by tanh in Multi Layer perceptrons This is an exercise problem from the book "Learning from Data".

Given $w_1$ and $\epsilon \gt 0$, find $w_2$ such that, $$\lvert \mbox{sign}(w_1^Tx_n)-\tanh(w_2^Tx_n)\rvert \le \epsilon$$  Where $w_1, w_2, x_n$ are all real vectors.

I know that for large $y$, $\mbox{sign}(y) \approx \tanh(y)$. But I am unable to proceed. Any help would be appreciated.

Thanks

Here's one solution. The central insight is that your error becomes exponentially smaller as $w^tx$ increases. In particular, $1-tanh(x)$ approximates $1$ exponentially fast. That is, for positive $x$:

$$\frac{1-tanh(x)}{1-tanh(x+1)} \geq \frac{tanh(0)}{tanh(1)} \approx 4.19\ldots = \alpha$$

In fact, its asymptote is at $e^2$. I didn't know that, but Wolfram Alpha did. You can use this fact to estimate your error. Let $\tau = sign(w_1^Tx)$ be the target, and let $E(w_2^Tx)=|\tau-tanh(w_2^Tx)|$ be the error. Figure out a weight vector $w$ that will give you $w^Tx=1$. Then $E(kw^Tx) \geq \alpha \cdot E((k+1)w^Tx)$ for any positive number $k$, because of the exponential improvement we just discovered. This is great; now we've reduced our problem to finding a good $k$. We know that for $k=0$, your estimate is $tanh(0)=0$ so $E(0)=1$, and every time you increment $k$ by $1$, your estimate becomes at least $\alpha \approx 4.19$ times as good. So, we solve the following simple equation:

$$\frac{1}{\alpha^k} \leq \varepsilon, \quad\text{so} \quad k \geq \ ^\alpha log\left(\frac{1}{\varepsilon}\right)$$

Hope this helps.


Recursive Algorithm Analysis $$T(n) = 2\cdot \sqrt{n} \cdot T(\sqrt{n}) + \Theta (\lg n)$$

I have been trying to solve this question but I could not find anything.

My approach:

$n = 2^k$

$S(k) = T(2^n)$ and $S(k/2) = T(2^{n/2})$

Finally:
$S(k) = 2^{1+k/2} \cdot S(k/2) + c \cdot \lg(k)  $

After that, I tried to build recursion tree but I can not find the sum. Do you have any ideas?

Thanks in advance.


OS: Are User-level threads and software threads (and also kernel-level threads and hardware threads) the same? I am referencing the Book Fundamentals of Computer Algorithms" by Ellis Horowitz et al.
At the part which they talk about multi-threading models, user-level and kernel-level thread are introduced.
And at the scheduling chapter, under multi-core processors, they talk about software threads and hardware threads.
Even though both sections are titled 'multithreading', one deals with how user-threads are mapped to kernel threads and the other deals with hyperthreading. (correct me if I am wrong)
I just want to know whether they are talking about the same terms. If not, will you clarify what is the difference between User-level threads  vs software threads?
Thank you.

Kernel threads and user threads are both software threads. This is only terminology, but I think that hardware threads in your book are the actual CPU cores including hyperthreading threads that the CPU can run at once. So a hardware thread is not instructions or an actual thread, it is simply the threads that the CPU supports. For example, if the CPU has 4 cores and each core uses hyperthreading to have 2 virtual threads each, then you would have 8 hardware threads available for software threads to run.
Kernel threads and user threads are separated by a permission bit in the page tables. Having a thread with a permission of 0 (kernel thread) doesn't make the thread a hardware thread. It is simply a software thread running in kernel mode.


What is the definition of computable partial function? Let $f:\mathbb{N} \to \mathbb{N}$ be a computable partial functions and $T$ a Turing Machine which computes it. By this I understand that $T$ writes $f(n)$ on its tape and halts when $n$ is an input on which $f$ is defined. But then what should $T$ do on inputs from $\mathbb{N}$ for which $f$ is undefined, and what should it do on inputs that do not represent a natural number? Should it halt or not?

A Turing machine $\Phi$ computes a partial function $f:$ $\subseteq\mathbb{N}\rightarrow\mathbb{N}$ iff:

For each $n\in dom(f)$, $\Phi(n)$ halts and equals $f(n)$.
For each $n\not\in dom(f)$, $\Phi(n)$ diverges (that is, never halts).

What about when we feed $\Phi$ a "nonsense" input - that is, some string not corresponding to a natural number? Well, we don't actually place any requirements on how $\Phi$ behaves in such a case, so there isn't anything to say there. (One reason this should feel fine is that it is computable to tell whether a given finite string represents a natural number - so we're not missing anything interesting by ignoring the behavior of $\Phi$ on nonsense inputs.)

Note that there is a related, weaker notion:

One partial function $f$ extends another partial function $g$ if $dom(f)\supseteq dom(g)$ and for all $n\in dom(g)$ we have $f(n)=g(n)$.
We can say that a partial function $g$ is extendible to a partial computable function if there is some computable partial function $f$ which extends $g$.

It turns out that "extendible to a partial computable function" is a strictly weaker condition than being a partial computable function; this is easy to prove by a simple cardinality argument (exercise).

More interestingly, we can cook up partial computable functions which are not extendible to any total computable function - sort of "fundamentally incomplete" functions which are nonetheless computable. A classic example comes from Godel's incompleteness theorem:

  Fixing some appropriately-computable bijection $b$ between sentences in the language of arithmetic and natural numbers, let $h(x)$ be the least $n$ such that there is a proof of $b^{-1}(x)$ of length $n$, and be undefined otherwise. Then $h$ is a partial computable function which cannot be extended to a total computable function.

Here "proof" means "proof from PA" (or your favorite axiom system). The reason that $h$ can't be extended to a total computable function is simple: if $f$ were a total computable function extending $h$, we could tell whether a given sentence $\varphi$ was provable from PA by searching for a proof of $\varphi$ of length at most $f(b(\varphi))$ - if we find one it is, and if we don't find one it isn't. But from this data we could built a complete consistent computable extension of PA (exercise), contradicting Godel's incompleteness theorem.

The (non-)extendibility of partial computable functions to total, or otherwise "frequently-defined," computable functions is an important topic in computability theory.


Video lectures on type systems For my job, I need to pick up a working understanding of the implementation of type systems (in particular, how to write typing rules based on a design document). I've been given a copy of Types and Programming Languages and that's great, but I'd really like to watch someone work through it.

In my school, the course that teaches this is called "Programming Languages," but searching for "video lectures programming languages" turns up lots of stuff about how to learn C++, which I'm not interested in. I couldn't find anything on MIT Open Courseware.

I'd really like video lectures that go through TAPL, but I'll settle for anything useful. Are there good resources out there?

If you poke around the Oregon Programming Languages Summer School web site you should find a lot of video lectures on the topic, given by the leaders in the area. For instance, see Robert Harper's "Type Theory Foundations" on the curriculum page.


Divide a number in k powers of 2 Example

N = 9 and K=3

4 + 4 + 1 = 9 .

What I have tried.

We can not go on dividing with 2.

We can use unbounded knapsack with array elements from 2^0 to 2^32.

If $k>N$, this cannot be done (as $\forall p_1,\dots, p_k\geq 0,\sum_{i=1}^k 2^{p_i}\geq k>N$)

If $k\leq N$: Write $N$ in binary, and denote by $n$ the number of $1$s. We have written $N$ as a sum of $n$ powers of two (which happen to all be distinct).

If $n\leq k$, then you can always split some of the powers of two (iteratively if needed) in order to obtain $N$ as a sum of $k$ powers of two (you cannot be stuck with only terms of the form $2^0$ -which cannot be split- before reaching $k$ terms as $k\leq N$ by assumption).
If $n>k$, then it cannot be done. Indeed, assume it could be done, and consider the decomposition into $k$ powers of two. (Iteratively) merge these powers of two until you reach a binary decomposition of $N$. This decomposition has at most $k$ $1$s, which is absurd by uniqueness of the binary decomposition.


Simplifying $b(abb + abbbb + aba^*bbb)^*$ I'm having issues simplifying regular expressions. I can't find a method to approach this problem.
How would I approach simplifying this regular expression:
$$b(abb + abbbb + aba^*bbb)^*$$

Note that $abbbb+aba^*bbb = aba^*bbb$. Also, note that you can "factorize" common expressions in the parentheses.
Your regular expression is equivalent to $b(a(\varepsilon + ba^*b)bb)^*$ (I don't know if it can be simplified again).


How do I interpret the wording of this passage about abstract binding trees from the book Practical Foundations of Programming Languages On page 7/8, section 1.2, of Practical Foundations of Programming Languages, 2nd edition, Robert Harper gives this initial definition of abstract binding trees:
The smallest family of sets closed under the conditions

If $x \in \mathcal{X}_s$, then $x \in \mathcal{B}[\mathcal{X}]_s$
For each operator $o$ of arity $(\vec{s_1}.s_1,\ldots,\vec{s_n}.s_n)s$, if $a_1 \in \mathcal{B}[\mathcal{X},\vec{x_1}]_{s_1},\,\ldots,\, a_n \in \mathcal{B}[\mathcal{X},\vec{x_n}]_{s_n}$, then $o(\vec{x_1}.a_1;\ldots;\vec{x_n}.a_n) \in \mathcal{B}[\mathcal{X}]$

(Here $\mathcal{X}$ denotes a set of variables, $\mathcal{X},x$ the union of $\mathcal{X}$ with $\{x\}$ where $x$ is fresh for $\mathcal{X}$, $\vec{x}$ a sequence of variables,$\mathcal{X}_s$ a set of variables of sort $s$, $\mathcal{B}[X]_s$ the set of abstract binding trees of sort $s$ over the variables in $\mathcal{X}$

This definition is almost correct, but fails to properly account for renaming of bound variables. An abt of the form $\text{let}(a_1;x.\text{let}(a_2;x.a_3))$ is ill-formed according to this defnition, because the first binding adds $x$ to $\mathcal{X}$, which implies that the second cannot also add $x$ to $\mathcal{X},x$, because it is not fresh for $\mathcal{X},x$.

I am confused about his meaning here.
How does this definition result in an ill-formed abt?
By first/second binding does he mean A) outer/inner (read from left to right) or B) inner/outer (read from the inside out)?
What I think he is saying:
Because of the outer("first") binding of $x$, assume that $x$ occurs free in $a_2$. For example $a_2=x,\, a_3=x$. Then because $x$ occurs free in $a_2$, it must be that $a_2 \in \mathcal{B}[\mathcal{X}]$ where $\mathcal{X} = \{x\}$. Since $a_3$ occurs inside an abstractor that binds $x$, $a_3 \in \mathcal{B}[\mathcal{X,x}]$, but then $a_3 \in \mathcal{B}[\{x\},x]$ which is ill-formed since $x$ is not fresh for $\{x\}$
But then I think of the concrete example $\text{let}(y,x.\text{let}(z,x.x))$ in which $a_2 \in \mathcal{B}[\{z\}]$ and $a_3 \in \mathcal{B}[\{z\},x]$, which poses no problems in this interpretation.

Edit to elaborate on the accepted answer...
What I now believe Harper meant is that the outer binding of $x$ indicates that $x$ is considered to be among the free, or "already used" variables in the inner let. This may or may not mean that $x$ must actually appear free in the inner let.
In either case, it means that validation of abts for well-formedness must proceed from the outside-in. In the specific examples Harper gives, the outer binding of $x$ means $x \in X$ in the validation of the inner let:
if $a_2 \in \mathcal{B}[\mathcal{X}]$ and $a_3 \in \mathcal{B}[\mathcal{X},x] \ldots$ (<-- ill formed; $x$ is not fresh for $\mathcal{X}$)
If in particular the wording means that $x$ must specifically appear free in the inner let, then in the given example, it would have to be in $a_2$ as suggested in my question and in the answer below. This amounts to saying that a particular instance of an abt in $\mathcal{X}$ is not automatically an abt in $\mathcal{X}\cup\mathcal{Y}$ for any set of variables $\mathcal{Y}$.

Just to clear something up that may not have been obvious, $\chi$ is a set and the notation $B[\chi, x]$ is meant to be ABTs under free variables that are either $x$ or are in $\chi$. In this notation I believe it is implied that $x \notin \chi$ when you write $B[\chi, x]$, which is important.

Using the definition of ABT above, you cannot prove for any $\chi$ that let(z, x.x) is in $B[\chi,x]$, but i claim that this is necessary to prove if you want to use it as the inner formula $a_1$ in let(y, x.$a_1$).

The reason you cannot prove let(z, x.x) is in $B[\chi,x]$ is because using the rule#1 stated above, the free variable $x$ is only an ABT in $B[\chi]$ when $x \in \chi$ (or alternatively: $x$ is only an ABT in $B[\chi',x]$ for some $\chi'$), but then using rule#2, we deduce $z \in B[\chi] \wedge x \in B[\chi, x] \rightarrow let[z,x.x] \in B[\chi]$. As I had mentioned in the first paragraph, this implies $x \notin \chi$, which means that the formula let(z, x.x) is ONLY in ABTs where $x$ is not a free variable.

The reason why $x$ needs to be free in this inner formula is because otherwise we cant apply rule#2 again on the outer formula let(y, x.$a_1$).


Understanding Interval Schedulling problem requirement Here is a modification of the weighted interval scheduling problem.

Given $n$ intervals by their end points $s_i$ and $t_i$ for $1 ≤ i ≤ n$, I want to minimize number of intervals so that every interval has a nonempty intersection with one of the selected intervals. In other words, select $S ⊆ {1,..., n}$ such that for each $1 ≤ j ≤ n$, interval $j$ intersects with some interval $i ∈ S$.
We say that the $j^{th}$ interval $[s_j, t_j]$ overlaps with $i^{th}$ interval $[s_i, t_i]$ if there exists a point $x$ such that $x$
belongs to the $i^{th}$ interval and the $j^{th}$ interval. A point $x$ belongs to an interval $[s, t]$ if $s ≤ x ≤ t$. Assume that $s_i
’s$ and $t_i's$ are distinct.

What I'm confused on is what this problem is even asking. It says minimize the number of intervals so that every interval has a non-empty intersection with a selected interval. So I get that means I want to find an interval that overlaps with another interval. But am I trying to find a sequence that avoids this as much as possible? In other words, am I just trying to set it up so that I maximize number of intervals while also minimizing overlapping intervals or am I trying to do something different?

Let us check some simple examples.

Suppose there are three intervals [1,3], [2,5], [4, 6]. Then the wanted number is 1. Here is how. Let $T$ be any two of the intervals. Then every interval will has a nonempty intersection with one of the intervals in $T$. For example, you can let $T$ be {[1,3], [2,5]}. You can also let $T$ be {[1,3], [4,6]}. On the other hand, Let $M$ be the set of [2,5], i.e., $M$={[2,5]}. Then every interval will has a nonempty intersection with the only one interval in $M$, [2,5]. Since the wanted number can not be smaller than 1, it is 1.

For a slightly more interesting example, suppose there are 5 intervals [1, 3], [2,5], [4, 7], [6,9], [8,10], where each interval intersects its two neighboring intervals.

The wanted number is 2. Why? Firstly, any interval will not intersect either [1,3] or [8,10]. So one interval is not enough. Secondly, consider intervals [2,5] and [8,10]. We can see that every interval will intersect one of [2,5] and [8,10]. So two intervals are enough.
If you name those five intervals A, B, C, D, E respectively and connect a pair of letters if the corresponding two intervals intersects, you get a graph with vertices {A,B,C,D,E} with edges AB, BC, CD, DE. (Graphs obtained this way are called interval graphs.) Now it is easy to translate our problem about intersecting intervals into a problem about graphs. The new problem is called the minimum dominating set of a graph.

Here is an equivalent version of the problem that is much simpler.

  Given $n$ fixed intervals all of whose endpoints are distinct. Select some intervals such that the intersection of every original interval and the union of selected intervals is nonempty. How to minimize the number of intervals selected?


Algorithm for antialiasing thin lines A very tricky problem in graphics rendering is drawing thin lines ($1px$ width) that do not look jaggy. The only implementation I have seen that is very good is that in Mathematica, but their algorithm is proprietary.

Is there a well known algorithm for anti-aliasing thin lines?

You can use Xiaolin Wu algorithm, but the concept is not restricted to straight lines, it handles circles, ellipses, any kind of functions. Moreover this is concept of fast antialiasing, if you need some polyline you have to apply it for every segment. If you meant curves, these are locally flat segments, so this concept is still applicable.

The thin line might described $1px$ lines, but if you need thinner width (less than $1px$) the common algorithm that comes to mind is Gupta-Sproull, which is not that common due to computation time. The same is applicable here like in the Wu case, it is not limited to straight lines.

The idea of drawing lines (probably with Bresenham) and then blurring is more computationally expensive and weights are not normalised, which gives feeling of thicker lines.

The concepts described can easily be extended to thicker lines (using Bresenham and applying antialiasing to the outter layer) or even varying width lines (with Bresenham extension - the Murphy algorithm).

Techniques like MSAA or FXAA are too expensive, unless implemented on GPU with a lots of lines and no concern about perceptible width. After reading about Mathematica, it uses MLAA (Morphological Anti-Aliasing), graphics is rendered on GPU, also Mathematica's reference supports this statement merely by looking at de Moiré patterns.


How does "language" relate to "problem" in complexity theory? I am looking up the meaning of reduction in complexity theory:

On Wikipedia it says: reduction is an algorithm for transforming one problem into another problem

On the Princeton's notes on NP-Completeness, it says: reduction is whereby given all x $\in $ language L1, for instance f(x) $\in$ L2, apply decision algorithm to f(x), then L1 $<=$ L2

Can someone make clear how a language (which is just a bunch of numbers) relates to a problem? If they are used interchangeably, can someone show how does I can conceptualize a language as a problem?

Thanks

A (decision) problem is a predicate on strings (that is, a property of strings) that can be either TRUE or FALSE; the problem is to decide whether a string satisfies the predicate (that is, has the property). We represent this predicate as the set of TRUE strings (that is, strings satisfying the property). A language is a set of strings. Thus the denotations of problem and language are the same – they are both sets of strings – and they can be used interchangeably. But semantically we use problem when our set of strings comes from a predicate, and language in other cases.

Here is an example. The NP-complete problem CLIQUE is the set of all pairs $(G,k)$ such that $G$ is a graph that has a $k$-clique. As stated, this is not really a set of strings, but rather a set of pairs $(G,k)$. But when we say the set of all pairs $(G,k)$ we really have some encoding in mind. For example, we can encode a graph $G$ as a list of edges, where the vertices are indexed by numbers, in the format $((i_1,j_1),\ldots,(i_\ell,j_\ell))$. For example, the following is an encoding of a triangle $((1,2),(1,3),(2,3))$. Under this encoding, the language CLIQUE contains the string $(((1,2),(1,3),(2,3)),3)$ but not the string $(((1,2),(1,3),(2,3)),4)$ nor the string $()()($, for example. Another issue that comes up when we talk about strings is: strings over what alphabet. In this case, our strings are over the alphabet $(),0123456789$; but since everything can be encoded in binary, we typically imagine such binary encoding of our strings.

CLIQUE is a predicate on pairs $(G,k)$ that holds if $G$ is a graph containing a $k$-clique. It is also a property of pairs $(G,k)$, that of $G$ having a $k$-clique. The corresponding language (which we identify with the CLIQUE problem) consists of all strings encoding (in a fixed way) pairs of graphs $(G,k)$ such that $G$ has a $k$-clique. The corresponding decision problem (which we identify with the language of all accepted instances) is to decide, given a pair $(G,k)$, whether $G$ contains a $k$-clique.


Applications of model counting I have been reading about model counting, a.k.a. the #SAT problem. What are the practical applications, if any, of this problem, and how exactly do they reduce to it? I have been unable to find any, though that's simply due to my own ignorance of the subject.

A recurring application for SAT model counting in the literature is extracting predictions from Bayesian networks. See "Algorithms and Complexity Results for #SAT and Bayesian Inference" and
"On probabilistic inference by weighted model counting".


Using decision oracle to solve optimization problem of maximum polyomino tiling So, this problem is a kind of variant of polyomino packing which has been discussed frequently elsewhere, but I haven't been able to find anything on my particular problem. Suppose we have a list of polyominos $p_1, p_2, ..., p_n$ (not necessarily distinct), and we want to find a tiling of a rectangle of dimension $a \times b$ with $a, b \leq n$ that maximizes the number of squares covered, where we can use each $p_i$ at most once, and polyominos must be fully contained within the rectangle. Now, we have the decision problem which tells us, for a given $t$, if there is some tiling covering at least $t$ squares, and the optimization problem which is finding a tiling that covers the maximum number of squares.

There are two parts: first, if you can solve the optimization problem in polynomial time, can you solve the decision problem in polynomial time? And secondly, if you can solve the decision problem in polynomial problem, can you solve the optimization problem in polynomial time?

The first part is easy, for if we have an oracle that solves the optimization in polynomial time, solving the decision problem in polynomial time is obvious.

However, given an oracle for the decision problem, I was unable to find a way to solve the optimization problem in polynomial time. The main issue I'm facing is that the decision oracle only works for rectangular boards, which means we can't just place pieces and then use the oracle to see if the placement works, since we won't have a rectangular board if we want to exclude the piece we just placed. It isn't hard to determine the actual maximum number of tiles you can cover, and you can even find the actual pieces you need to use, but I haven't been able to figure out a way to find an arrangement of the pieces in polynomial time using the oracle. I assume there is some trick here, but I don't see it.

Here are some more details. A similar problem can be found here, so to address the commenter's question a priori we sort of hope that this problem can be solved using the decision oracle. However, there is only one difficulty with adapting this approach which makes it seem fruitless:

The oracle in the linked question is in a sense stronger because it works on any graph. In particular we can encode the notion of coloring using a modified graph. In this sense the oracle of this problem is much, much weaker since it only works on rectangular boards.

Although the shape of the problem instance is constrained, we still have total control over the polyominos themselves in any problem instance we decide to create, and we can get there by carefully messing with them.

A gangly polyomino in a double-width problem instance

Given the initial $a \times b$ problem instance, create a new instance of size $(2a+1) \times (b+1)$ in which each polyomino's width has been doubled, and a new polyomino has been added that consists of a row of $2a+1$ blocks with a column of $b$ blocks hanging below its leftmost block (thus giving it a total height of $b+1$) and a double-width copy of polyomino $p_1$ (the template polyomino) below the top row and to the right of the left column but pushed up and left as far as it will go, so that at least one block of column 2 below row 1 is occupied, and at least one block of row 2 to the right of column 1 is occupied. Intuitively, because all other polyominos have even width, the only way to fill up the odd-width rectangle we have is to use this gangly new polyomino, in which case its horizontal and vertical "arms" must form the topmost row and leftmost column, respectively.

Let the size of an optimal solution to the original problem be $k$ (this can be found in $O(\log {ab})$ time with binary search using only decision problem oracle calls). Iff there is a solution to the newly constructed decision problem instance with size $2k+(2a+1)+(b+1) = 2(k+a)+b+2$, then there is a solution to the original instance that has $p_1$ in its top-left corner.

If the answer is "no", try the same instance again but with a different template polyomino: form the gangly polyomino by pressing $p_2$ into the top-left corner instead of $p_1$. Repeat this until you find you hit a "yes" instance. If none of the polyominos results in a "yes" instance when pressed into the top-left corner, start again with $p_1$ but one block down from where it was in the first constructed problem, and with the blocks at positions $(2, 2)$ and $(2, 3)$ also filled in. Why? These represents a (double-width) block that we know must remain empty in every optimal solution (since if there was some optimal solution where it was covered by a polyomino, we would have found it by now). Add 2 to the target value for the decision problem to compensate for the added filler blocks.

If performing this down-one-row move would cause the polyomino to extend past the bottom of the range, add the 2 filler blocks as usual but instead move the template polyomino back up to the top (so that its topmost block occupies row 2) and as far left as possible so as to not overlap any existing block.

In general, a constructed instance with $f$ filler blocks gets $f$ added to its decision problem target.

Once you hit a "yes" instance, you know that this placement of the template polyomino is part of some optimal solution, so you keep that placement of the template in the gangly polyomino from that point on. Form the next problem with the next available polyomino as template immediately below the last one, or flush with the top and to the right as usual.

Time complexity

Each time we try all $n$ polyominos at some position, we add at least 2 blocks (either 2 filler blocks, or the double-width blocks corresponding to some input polyomino) to the gangly polyomino. We can only add at most $ab$ such pairs of blocks before it is no longer possible to obtain a "yes" answer, so at most $abn$ calls to the decision oracle suffice.


Measuring the difficulty of SAT instances Given an instance of SAT, I would like to be able to estimate how difficult it will be to solve the instance.
One way is to run existing solvers, but that kind of defeats the purpose of estimating difficulty. A second way might be looking a the ratio of clauses to variables, as is done for phase transitions in random-SAT, but I am sure better methods exist.
Given an instance of SAT, are there some fast heuristics to measure the difficulty? The only condition is that these heuristics be faster than actually running existing SAT solvers on the instance.

Related question
Which SAT problems are easy? on cstheory.SE. This questions asks about tractable sets of instances. This is a similar question, but not exactly the same. I am really interested in a heuristic that given a single instance, makes some sort of semi-intelligent guess of if the instance will be a hard one to solve.

In general, this is a very relevant and interesting research question. "One way is to run existing solvers..." and what would this even tell us exactly? We could see empirically that an instance seems hard for a specific solver or a specific algorithm/heuristic, but what does it really tell about the hardness of the instance?

One way that has been pursued is the identification of various structural properties of instances that lead to efficient algorithms. These properties are indeed prefered to be "easily" identifiable. An example is the topology of the underlying constraint graph, measured using various graph width parameters. For example it is known that an instance is solvable in polynomial time if the treewidth of the underlying constraint graph is bounded by a constant.

Another approach has focused on the role of hidden structure of instances. One example is the backdoor set, meaning the set of variables such that when they are instantiated, the remaining problem simplifies to a tractable class. For example, Williams et al., 2003 [1] show that even when taking into account the cost of searching for backdoor variables, one can  still obtain an overall computational advantage by focusing on a backdoor set, provided the set is sufficiently small. Furthermore, Dilkina et al., 2007 [2] note that a solver called Satz-Rand is remarkably good at finding small strong backdoors on a range of experimental domains.

More recently, Ansotegui et al., 2008 [3] propose the use of the tree-like space complexity as a measure for DPLL-based solvers. They prove that also constant-bounded space implies the existence of a polynomial time decision algorithm with space being the degree of the polynomial (Theorem 6 in the paper). Moreover, they show the space is smaller than the size of cycle-cutsets. In fact, under certain assumptions, the space is also smaller than the size of backdoors.

They also formalize what I think you are after, that is:

  Find a measure $\psi$, and an algorithm that given a formula $\Gamma$ decides satisfiability in time $O(n^{\psi ( \Gamma )})$. The smaller the measure is, the better it characterizes the hardness of a formula.

[1] Williams, Ryan, Carla P. Gomes, and Bart Selman. "Backdoors to typical case complexity." International Joint Conference on Artificial Intelligence. Vol. 18, 2003.

[2] Dilkina, Bistra, Carla Gomes, and Ashish Sabharwal. "Tradeoffs in the Complexity of Backdoor Detection." Principles and Practice of Constraint Programming (CP 2007), pp. 256-270, 2007.

[3] Ansótegui, Carlos, Maria Luisa Bonet, Jordi Levy, and Felip Manya. "Measuring the Hardness of SAT Instances." In Proceedings of the 23rd National Conference on Artificial Intelligence (AAAI’08), pp. 222-228, 2008.


Distinguishability of distributions that are not close given just one sample Consider (over $n$-bit strings) the uniform distribution $U$, and another distribution $D$ such that
\begin{equation}
\text{Distance}(D, U) \geq \frac{1}{e},
\end{equation}
where $\text{Distance}$ stands for the total variation distance, given by
\begin{equation}
\text{Distance}(D, U) = \sum_{z \in \{0, 1\}^{n}} \left|\underset{\text{Z} \sim D}{\text{Pr}}[\text{Z}=z] - \underset{\text{Z} \sim U}{\text{Pr}}[\text{Z}=z]\right|,
\end{equation}
for a random variable $\text{Z}$.
In other words, $D$ and $U$ are quite far from each other. Even then, it seems intuitively true to me that we should not be able to distinguish between these two distributions with a polynomial-time algorithm if we are given one (and just one) sample as input, with the promise that the sample comes from one of these two distributions.
By this, I mean that it seems intuitive to me the quantity
\begin{equation}
\left|\underset{x \sim D}{\text{Pr}}[A(x) =1] - \underset{x \sim U}{\text{Pr}}[A(x) =1]\right|
\end{equation}
is small, for a polynomial time algorithm $A$.
Is my intuition correct? If not, it just doesn't seem obvious to me how we could distinguish these distributions with just one sample. Isn't it too little information? Can you show how we are to distinguish by any explicit description of such an algorithm for any such $D$?

Total variation distance, which is exactly half of your notion of distance, is equal to
$$
d_{TV}(D,U) = \frac{1}{2} \operatorname{Distance}(D,U) = \max_A \bigl|\Pr_{x \sim D}[A(x)] - \Pr_{x \sim U}[A(x)] \bigr|.
$$
You can take $A$ to be the indicator of $\Pr[D(x)] \geq \Pr[U(x)]$. The event $A$ might be hard to compute, but it could also be easy to compute. In the latter case, you will be able to efficiently distinguish between $D$ and $U$, even using only one sample. This may even be possible in the former case, though with an advantage less than the total variation distance.

Here is a proof of the equivalence between the two formulations.
Since
$$
\Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)] =
-\left(\Pr_{x \sim D} [\overline{A(x)}] - \Pr_{x \sim U}[\overline{A(x)}]\right),
$$
where the overline represents negation, we have
$$
\delta_{TV}(D,U) = \max_A \bigl( \Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)] \bigr).
$$
Let $S = \{ x : A(x) \}$. Then
$$
\Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)] =
\sum_{z \in S} \bigl(\Pr_{Z \sim D}[Z = z] - \Pr_{Z \sim U}[Z = z]\bigr).
$$
This formula makes it clear that an optimal choice for $S$ is
$$
S = \{ z : \Pr_{Z \sim D}[Z = z] \geq \Pr_{Z \sim U}[Z = z] \}.
$$
For this choice of $S$, we have
\begin{align}
d_{TV}(D,U) &=
\Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)] \\ &=
\Pr_{x \sim D}[x \in S] - \Pr_{x \sim U}[x \in S] \\ &=
\bigl(1-\Pr_{x \sim D}[x \notin S]\bigr) - \bigl(1-\Pr_{x \sim U}[x \notin S]\bigr) \\ &=
\Pr_{x \sim U}[x \notin S] - \Pr_{x \sim D}[x \notin S].
\end{align}
By definition of $S$, we have
\begin{align}
\Pr_{x \sim D}[x \in S] - \Pr_{x \sim U}[x \in S] &=
\sum_{z \in S} \Pr_{Z \sim D}[Z = z] - \sum_{z \in S} \Pr_{Z \sim U}[Z = z] \\ &=
\sum_{z \in S} \bigl| \Pr_{Z \sim D}[Z=z] - \Pr_{Z \sim U}[Z=z] \bigr|.
\end{align}
Similarly, we have
$$
\Pr_{x \sim U}[x \notin S] - \Pr_{x \sim D}[x \notin S] =
\sum_{z \notin S} \bigl| \Pr_{Z \sim D}[Z=z] - \Pr_{Z \sim U}[Z=z] \bigr|.
$$
It follows that
\begin{align}
\mathrm{Distance}(D,U) &=
\sum_{z \in S} \bigl| \Pr_{Z \sim D}[Z=z] - \Pr_{Z \sim U}[Z=z] \bigr| + \sum_{z \notin S} \bigl| \Pr_{Z \sim D}[Z=z] - \Pr_{Z \sim U}[Z=z] \bigr| \\ &=
\Pr_{x \sim D}[x \in S] - \Pr_{x \sim U}[x \in S] +
\Pr_{x \sim U}[x \notin S] - \Pr_{x \sim D}[x \notin S] \\ &=
2\bigl(\Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)]\bigr) \\ &= 2d_{TV}(D,U).
\end{align}


How to decide whether a real life problem can be dealt with by computers? I get that complexity theory will be helpful to decide whether the resources at hand can deal with a mathematical function, but when presented with a non-purely mathematical problem - like building a robot that can cook, drive or make beds - how can we know whether it's feasible?

The way we decide is we try to solve it and see if we are successful; or we look to see whether someone else has solved it (e.g., in the research literature).

Usually the question doesn't really make sense, as it is not well-defined what it means to "solve" or "deal with" a problem.  It's not like in mathematics, where it is a crisp black-and-white.  Instead, one may need to measure how well computer systems can address the problem, in what contexts they do or don't suffice, what their strengths and limitations may be, and so on.

Normally, the way we assess all of this is through experiments, not mathematics: we try techniques and evaluate how well they work empirically, and see what we can learn from that.


What does "bounded above" mean in Family of Bachmann–Landau notations? Per wiki

  |f| is bounded above by g (up to constant factor) asymptotically

with this concrete example,

$$f(n) = \log n$$

$$g(n) = n^c = n^{0.000001}$$

Does "bounded above (up to constant factor)" means $f(n)$ is above $g(n)$

A quantity $a$ is bounded above by a quantity $b$ if $a \leq b$.

A quantity $a$ is bounded above (up to constant factor) by a quantity $b$ if there exists a constant $C>0$ such that $a \leq Cb$. (This makes sense when $a,b$ depend on some other variable).

A quantity $a(n)$ is bounded above (up to constant factor) asymptotically by a quantity $b(n)$ if there exist constants $N,C>0$ such that $a(n) \leq Cb(n)$ for all $n \geq N$. This is usually expressed as $a(n) = O(b(n))$.


Is a regular grammar valid if it only contains production rules that have nonterminals in the right operand? For example:

S -> Sa

Let's say the alphabet is {a} and that is the ONLY production rule of the grammar. Is that grammar valid regular grammar ? Or valid grammar at all? Can it be a context free grammar, but not a regular one ?

As far as I can think... a grammar tree built on it will never end, it will never have only leaves so there is NO  string that is accepted or generated by this grammar so it should not be considered a valid grammar.

However I did not see in the definition of grammar this specific constraint of a grammar, that it necessarily should have a production rule with ONLY terminal symbols on the right hand side of a production rule.

Back to the definition. According to Wikipedia, a context-free grammar $G$ is a 4-tuple $(V, \Sigma, R, S)$. In this case, $G = (V, \Sigma, R, S)$ can be defined as

$V$, nonterminals, is $\{S\}$,
$\Sigma$, terminals, is $\{a\}$,
$R$, production rules, is $\{ S \mapsto Sa \}$, and
$S$ is the start symbol and an element of $V$.

So this is a context-free grammar although the language recognized by $G$ is empty as you noticed.

You can also verify whether this is a regular CFG by going back to the definition.


Why is $\binom{n}{f}^g=O(n^{fg})$ true? Why is it true? I understand why $n^g$ but how does the $f$ get there in the power??
I believe from the context that it's not just that $\binom{n}{f}^g$ is strictly smaller than $n^{f g}$, but rather that it really belongs to this class, which means it's also tightly bounded by it or very close. But why is it?

This reduces to showing $\binom{n}{f} = O(n^f)$.

In one variable the idea of an approximation being tight is pretty simple; you just see if the limit of the quotient goes to one.

In multiple variables there's no such thing as "the" limit.  There are limits along different curves.  Some may be tight and some may not be, but as long as the limit along one curve is tight there's no way of improving things across the board.

In situation at hand we have $$\binom{n}{f} = \frac{1}{f!}n(n-1)\ldots(n-f+1)$$.  For f small compared to n, the $(n-i) \approx n$.  If n grows a lot faster than k!, then it also blows out the k! term in the denominator as well.  So along a curve like this the bound is tight.

(It's also possible we're considering fixed k and just considering the growth as a function of n, in which case the $1/k!$ is just a constant factor.)


What is the earliest use of "trees" in computer science? I have a little history question, namely, as the title says, I am looking for early uses of trees  (as a data structure, search tree, whatever) in computer science.

Wikipedia says that the first use of tree in mathematics was by Cayley in 1857.

Since the use in computer science is taken directly from mathematics, it seems more fundamental to ask when they originated there. Unless computer scientists originally called trees something else, the first computer scientist to use "tree" doesn't seem any more significant than, say, the first Australian to use "tree".


Packing sets to maximize overlap We are given a set of $m$ elements $\{e_1,...,e_m\}$ that form our universe $\mathcal{U}$. Each element of our universe is further associated with a positive weight $w(e_j)$ with $j\in \{1,...m\}$. We are further given a collection $S=\{S_1,...S_n\}$ of subsets of  $\mathcal{U}$ whose union equals the universe. The intersection of any two sets in $S$ may be non-empty (i.e. subsets may overlap with each other).

Furthermore,

1) we are given an infinite number of configurations; each configuration can host up to $k$ subsets from $S$. There is no cost for using a configuration.

2) When assigning 2 or more subsets to one configuration and there is an overlap between the sets (i.e. an element is part of more than one set) we pay the weight of that element only once. Obviously, there can be no overlap between subsets when considering different configurations.

Objective:

we want to assign each subset of $S$ to exactly one configuration in such a way that the weighted sum of the elements over all configurations is minimized. Consider the following example:

$\mathcal{U}=\{a,b,c,d,e,f,g\}$,

$w(a)=2$

$w(b)=2$

$w(c)=3$

$w(d)=4$

$w(e)=1$

$w(f)=2$

$w(g)=2$

$S=\{S_1, S_2, S_3\},$

$S_1=\{a,b,c\}, S_2=\{c,d,e\}, S_2=\{e,f,g\}$

$k=2$

In this case, since $k<|S|$, it is obvious that more than one configurations are needed. Moreover,  $S_1$ and $S_2$ should be packed together in the same configuration because of their heavy overlap ($S_1 \cap S_2$ gives the biggest overlap in our example - we pay 3 less cost units). So, the total cost of such an assignment is 12+5=17 and 2 configurations are needed.

Any ideas on how to prove that the problem is indeed intractable? Any ideas on how to calculate a good bound on the number of configurations that are needed?

The unweighted version (when the weights of the elements are all 1) is also very interesting to me. However, I did not manage to find something so far in the literature also for this problem.

Thank you!

When $k=1$, the problem is trivial: the optimal solution is to put each set in its own configuration.

When $k=2$, the problem can be solved in polynomial time using graph matching.  Build a complete undirected graph with one vertex per set.  The cost of the edge $(S_i,S_j)$ is the cost of putting $S$ and $T$ together in the same configuration (i.e., the weight of $S_i \cup S_j$).  Now the optimal solution to your problem is given by the minimum-cost perfect matching in this graph.  That matching can be computed in polynomial time using standard algorithms.

When $k=3$, the problem is NP-hard.  In fact, it is NP-hard to determine whether a graph can be covered by a disjoint union of cycles of length $\le 3$ (i.e., whether you can find a set of cycles, where each cycle has length 2 or 3, where no two cycles have any vertex in common, and where every vertex appears in one of these cycles).  This implies that your problem is intractible when $k\ge 3$.

The proof of the hardness result I alluded to can be found in Section 3 of the following paper:

Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges.  David J Abraham, Avrim Blum, Tuomas Sandholm. EC 2007.

That said, not all hope is lost.  There are techniques available for finding a solution that will be close to optimal, using integer linear programming.  For instance, you can express your problem as an instance of integer linear programming and then apply an off-the-shelf ILP solver.  See the paper above for some more sophisticated techniques that might be applicable in your situation as well.


Recursive Universal Turing Machines Let $U$ be a universal Turing machine that on input $<M,w>$ simulates a Turing machine $M$ on input $w$. I have a question about what would happen if $U$ "operated" on itself.

That is, what happens when we consider the input $<U, <M,w>>$?

Or what about the input $<U, <U, <M,w>>>$?

If we give the input $<U, <M,w>>$ to the Turing machine U, it will simulate the Turing machine U on input $<M,w>$. The behavior of the simulated machine U on input $<M,w>$ is to simulate the Turing machine $M$ on input $w$. So it seems like the behavior would still be a Turing machine that simulates $M$ on input $w$. At least two questions need further clarification:

How is the input $w$ encoded? If we have a requirement that only input where "$<$" and "$>$" are "perfectly matched" is allowed, then we can just copy the input "w" unmodified between $<M,$ and $>$. This is the strategy used by Tcl, which can be surprising if you are not used to it. Otherwise, you have to encode the input "$w$" suitably, which can mean that you have to escape "$<$" and "$>$", as well as the escape character itself. In this case, the "$w$" in $<U,<U,<M,w>>>$ is quite different from "$w$" itself, because it has been encoded multiple times. For example the escape character "\" might have turned into "\\\\\\\\".
What exactly do we mean by "simulate"? The most important aspects of a simulation of a Turing machine is whether it halts or not. If the Turing machine M halts, it is (or can be) also important which output it leaves on its tape. If the machine M doesn't halt, we need to be careful how to define the output of the machine. For simplicity, let's assume that either the machine has a dedicated output tape, or that we don't care for the output in case the machine never halts. The output should never be encoded like the input, but directly match the original output.

What about the efficiency of the simulation? A good simulation would have only a constant offset in memory consumption and a logarithmic factor (logarithmic in the input to $U$) in runtime (->multi-tape Turing machine is assumed here). Both properties seem to be conserved by applying $U$ to itself, so you still have an efficient simulation of $M$ on input $w$ if you apply $U$ (repeatedly) to itself.