Confused about substitution in grammar in certain cases To illustrate my confusion let's say I'm given this unambiguous grammar in BNF:

         S ::= T O x
         T ::= empty
         T ::= "if" E "then" T x "else" T
         O ::= empty
         O ::= "if" E "then" T O

Here is the corresponding derivation tree:

                                         S
                     ____________________|______________________
                    /                    |                      \
                   T                     O                       x
                   |         ____________|_________________
                 <empty>    / |  |             |           \
                           if E then           T            O
                                       ________|_______     |
                                      / |  |   | |  |  \ <empty>
                                     if E then T x else T
                                               |        |
                                            <empty>  <empty>

Why couldn't we have this:

                                         S
                     ____________________|______________________
                    /                    |                      \
                   T                     O                       x
                   |         ____________|_________________
                 <empty>    / |  |             |           \
                           if E then           T            O
                                       ________|_______     |
                                      / |  |   | |  |  \ <empty>
                                     if E then T x else T
                                               |        |
                                       ________|_______ \
                                      / |  |   | |  |  \ <empty>
                                     if E then T x else T

Why is the first T <empty>? What are the rules that govern how you substitute the definitions in the graph.

There's no particular reason why the first $T$ should be replaced by $empty$. The other replacement would have been equally acceptable. A grammar rule says "you can replace this string by this other" and no more. In other words, a grammar may generate several strings, depending on which of the grammar's replacement rules are called into play at any stage.

In answer to your last question, there are no rules to specify which substituition you use: the choice is up to you.


Why does removing all copies of a letter preserve regularity? Let $P(a,L)$ remove every $a$ in $L$, for example
$$ P(a,\{ab,aab,aaab,bba\}) = \{b,bb\}. $$

How to show that if $L$ is a regular language then $P(a, L)$ is also a regular language?

My attempt:

If $L$ is regular then $P(a, L)$ is regular. Namely, let $D = (Q,Σ,δ,q_0,F)$ be a DFA for $L$.

Assume every state in $L$ is reachable from $q_0$. Then we can turn $D$ into an NFA $N$ for $P(a, L)$ by adding a new state $q_{−1}$ which becomes the NFA’s start state. For each state $q ∈ L$, we add an epsilon transition from $q_{−1}$ to $q$.

Therefore, define $N$ to be
$( L ∪ \{q_{−1}\}, Σ , δ′, q_{−1},F)$

Is this the correct way to prove it?

Given an NFA or a DFA (like in your proof, if you want), we replace each arc with letter $a$ by $\varepsilon$. We obtain an NFA for $P(a,L)$. So, $P(a,L)$ must be regular.

In details, each trace in the newly constructed NFA can be transformed back to $a$-full instance of $L$ .


Proof of universality in the circuit model I'm starting to study Turing machines, the Church-Turing conjecture and the circuit model. In particular, I'm interested in the proofs of universality that one can find in this context. So far, I have only found the universality proof of the circuit model for boolean functions (i.e., the gates AND, OR and NOT can be used to compute any boolean function). However, our experience with digital computers indicates that they can approximate really well more things than only boolean functions.
My question is: are there more proofs of universality in the context of the circuit model? For example, to approximate continuous funcitons. I have tried to find something about this particular case but I didn't find any proof nor any reference where approximation of continuous functions with boolean functions is discussed. And it is something that puzzles me because, in the context of machine learning, feed-forward neural networks are universal approximators of continuous functions, but we compute the feed-forward neural networks models in digital computers. All the possible references are wellcome!

I'm sure you are aware of the following problem: Turing-Machines can't compute any Boolean function. E.g. there is no such TM that prints $0$ if the input TM does not halt and $1$ if it halts (halting problem). This directly implies that TMs can't approximate any classical continuous function arbitrarily well. E.g. you could create the number
$$\xi = \sum_{i = 0}^\infty 2^{-i} h_i$$
where $h_i$ is $1$ if the $i$-th TM halts and $0$ if it doesn't for some mapping of $\mathbb{N}$ to the TMs. It's clear that $\xi \in \mathbb{R}$ and that you could work with the function $f(x) = \xi x^2 +\xi^2$ in analysis and differentiate it without a problem, but it's not computable, you can't approximate it's value arbitrarily well. One interesting field of study it computable analysis which deals with deals with a special kind of analysis where only functions and numbers are considered that are computable (arbitrarily closely approximatable  by a TM).
Now let us take a look at circuits. It's true that you can for a given table of inputs and outputs of a Boolean function construct a circuit that computes that table. The problem is that the table is sometimes not computable in the first place. E.g.
you could say that the circuit $C_n$ taken a binary representation of a TM up to length $n$ as input an outputs $0$ if it doesn't halt on the emtpy tape and $1$ if it halts. Now all circuits in the sequence $C_1, C_2, ...$ do exist in the sense that they are in the set of all possible circuits, but you can not build them, because of the halting problem. (It is very similar to $\xi$ it exists but you can not compute it). This also applies to your continuous functions. E.g. lets look at the function $f(n) = \xi$ (which is a normal real continues function). You could now define that $C_{n,k}$ is a circuit that takes $k$ as a binary number ($k < 2^i$) as input and computes $f(n)$ up to a precision of $2^{-k}$ that is $k$ places after the comma in binary. Now there are circuits $C_{1,1} C_{2,1}, ...$ that exist, because the mappings are all binary and if you had the Boolean tables for any particular $n,k$ you could build a circuit, but you can't compute the Boolean tables..., I hope you get a feel for the problem with computability and that there exists things, which you can define and use, but not construct. To answer your question, yes you can approximate continues functions with circuit sequences arbitrarily well, but that does not mean that there is an algorithm to find such circuits...
Anyhow I would recommend you to look into computable analysis. It seems to be what you are searching for.


Time complexity of checking whether a string exists in a HashSet From what I know hash sets generally have complexity of $O(1)$ (unless the hash function is bad, but let's just ignore that for this question). However, sets need to either read the full data so as to make a hash function that's guaranteed to return a unique result for every input or they need to make a comparison to make sure the data is the same otherwise. Doesn't that mean that the complexity for strings should be $O(m)$, where $m$ is the length of the string, at least if we accept that these strings can get arbitrarily large? Is there something I do not understand?
The reason I'm asking is because I solved a problem with a trie and the provided solution was solved with a set (that was the only difference), but it assumed that arbitrarily large strings can be found to exist or to not exist in a set in $O(1)$ time. The problem is to find which words in a set of words can be formed using other words in the set (words can be used multiple times) — for example in "a", "bc", "cd", "acd", "abcd", only "acd" can be formed using other words, though I don't think the specific problems matters much.

You are right in that to check membership (or to retrieve) using a hash function, you also need to check that the retrieved element is equal to the element in question. For a string, you should assume that this takes time linear in the length.
Hence checking membership in a hash set is indeed expected $O(m)$.


Using a 16-bit 2,s Complement normalised floating-point representation; 10-bit fractional mantissa and a 6-bit integer exponent: express 2.171875 So far I know how to normalize when you are given, say:
1111010010 Mantissa, and 000100 exponent
and are told that it's a positive number:

1.111010010 and the exponent value is 4
move point 3 to the right: 1111.010010
subtract exponent by 3 = 1; 000001
replace extra binary digits behind sign bit with trailing 0s
1.010010000

so 1.010010000 , 000001
is the normalized form.

Now how do I express 2.171875 under the same representation?
I started by converting it to binary: 10.0010110 but how do I represent that as 10-bits 2'C Mantissa and 6-bits exponent to begin with? Or am I completely lost?

I am lost with the given algorithm for a normalized representation.

The most significant bits should be kept, which is not what I see in your example.

1.111010010 x 2^4 = .1111010010 x 2^5 (This keeps the dot leftmost, and
one can possibly truncate bits to the right - or even round 0xxx down, and 1xxx up for positive numbers). Having a 1 immediately after the dot, allows the highest precision, compare with .00001111010010,
sign 1 bit = 0 (both ones complement, twos complement)
mantissa '1' + 8 bits = 111101001
exponent 6 bits two-complements = 000101
result: 0 11110101001 000101

This is just one possible variant: a ones complement mantissa with extra sign bit (but almost a two's complement mantissa). Here it shifted till a .1xxx
for a nonzero number. (Hence that 1 is almost redundant.)

Now your recipe:

1.111010010 x 2^4 = 1111.010010 x 2^1
sign 1 bit = 0 (both ones complement, twos complement)
mantissa 9 bits = 1111 01001
exponent 6 bits two-complements = 000001
result: 0 11110101001 000001

It only differs in the implicit +4.

For the .1 method:

2.171875 = number < 1, times 2^exp = 0,54296875 x 2^2
0,54296875 = 0.1xxx
etcetera


Reasons for choosing register number and address sizes in an Instruction Set Why would it be suitable to design an instruction set  with 2-bits allocated for the register number and 10-bits allocated for the memory address? Would introducing a cache change this? (If possible I'd like to know why or where to find an explanation on this.)

If it helps an example would look like this 0001 xxyy yyyy yyyy and an instruction would be the opcode 0001 (Load) register xx from memory address yy yyyy yyyy.

Two bits for the register and ten bits for the address makes sense when you have ~four registers and ~1024 words of memory. Any more and you can't address it all (how would you access register #5, or memory address #1025?); any less and you're wasting precious bits in every instruction (why use two bits for the register when there's only two registers to choose from?).

Generally, the purpose of a cache is to make things faster without changing the underlying model. In other words, if you don't care how fast your code is, you can just pretend the cache isn't there. Everything will work the same either way.

P.S. You can address more memory than this using various tricks like "bank switching", but I doubt you're concerned with those yet.


How many basic operations are there in an algorithm for the simple multiplication of two numbers of equal length? BACKGROUND:

Note: The following question arose in my mind when watching this lecture (watch at 5:30 minutes if you will).

Assumption: Just for the sake of this question, let's assume that the term "basic operation" means an addition or a multiplication operation between two single-digit numbers.

Now we have to calculate the number of basic operations involved in the simple multiplication (the one we learnt in 3rd grade) of any two numbers, provided that both the numbers have the same length (i.e. the number of digits).

Let's say n represents the length of the numbers.

Let the numbers be 1234 and 5678. The following image shows the multiplication:

As you can see, each row (i.e. each partial product of the first number with a digit of the second number) involves 4 multiplication operations, and 4 addition operations (think of the carries). Depending on the number of carries (and thus depending on the original numbers), in the case of any two numbers, in each row, it could be at least 0 additions (no carry) and at most 4 additions (a carry from each digit-to-digit multiplication).

In other words, each row involves ≤ 2n operations. As there are n rows, so the basic operations in all the rows are n(2n), or 2n2.

QUESTION:

Now comes that one final addition (shown in black pen in the image). From the video lecture

  The final addition requires a comparable number of operations.
  Roughly, say, another at-most 2n2 operations.

The question is

What is meant by "comparable" number of operations?
Now, there will be at-most n-1 _'s in the partial products, which means n-1 addition operations. Apart from those, there will be at-least n additions (if there isn't a carry from the addition of the left-most digits in the partial products), and at-most n+1 additions (if there IS a carry from the addition of the left-most digits in the partial products). This makes a total of, at-most, n-1+n+1 or 2n addition operations in this step. So why are they saying 2n2?

It's hard to tell what anyone means by "comparable" in a specific context. I would take it to mean "of the same order", so something like $n^2$, maybe $100\cdot n^2$ or $0.0001\cdot n^2$, but not $n$ or $n^3$.

The final addition is doing (roughly) $n$ additions of numbers of (roughly) non-$\_$ $n$ digits, and each of those additions takes (roughly) $n$ additions of single digit numbers. So that's why you end up with (roughly) $n^2$ additions.


What is the signature of a formal language? I will briefly state the context where my doubts arise.
I know the following definitions.

A formal language is a set of well-formed formulas. It's a tuple constituited by an alphabet and a formal grammar.

An alphabet of a formal  language is a set of symbols. It's usually consituited by letters (symbols whose interpretation depends on the specific context) and signs(symbols whose interpretation doesn't depend on the context and whose aim is to structure the language).

A vocabulary of a formal language is the set of all letters of the alphabet.

A formal grammar of a formal language is a set of rules specifying how to form a well-formed formula from symbols in the alphabet.

I often find the notion of a signature but it's not intuitive to me. Is that the set of signs of a formal language? If not, what is it?

In my experience a "signature" is something that puts additional constraints on a language made of syntactic terms. I'll try to provide an example.

Consider the alphabet $\Sigma = \{f,g,a,b,(,),;\}$. From this we can build the set of all the words $\Sigma^*$. This contains any word, including gibberish like "$)g;;f(($".

Then, we can craft the set of syntactic terms $T \subseteq \Sigma^*$ through an inductive definition.

We start by defining a subset $F \subseteq \Sigma$ as $F = \{f,g,a,b\}$, and we call this the set of function symbols. Then, inductively, we state that if $t_1,\ldots,t_n$ (with $n\geq 0$ are terms and $s\in F$, the word $s(t_1;\ldots;t_n)$ is a term.

Note that $n=0$ above gives the "base case" of the induction. We then have that $f()$ is a term, $a()$ is a term, $f(a();b())$ is a term, $f(f(a();b();a();a(b())))$ is a term, and so on.

Now, we might want to put more constraints on those terms. For instance, we might want to associate to each $s \in F$ a fixed nubmer of arguments, and consider only those terms respecting that. For instance, if we decide that $f$ has arity two (f is binary), then we allow $f(a();b())$ but not $f(a())$ nor $f(a();f())$. This restriction essentially defines a subset language $L\subseteq T$.

This is sometimes done by specifying a signature. E.g. something like
$$
\begin{array}{l}
f : A \times A \to A \\
g : A \to A \\
a : 1 \to A \\
b : 1 \to A \\
\end{array}
$$
The above is a fancy way to state that $f$ is binary, $g$ is unary, and $a,b$ are both constants (= zero-arity function symbols). $1$ is used to mean no-arguments.

A possible term here is $f(g(a());b())$.

The name $A$ above is called a "sort", and has no deep meaning on its own. The above is called a single-sorted signature since it uses only one sort. By contrast
$$
\begin{array}{l}
f : A \times B \to A \\
g : A \to B \\
a : 1 \to A \\
b : 1 \to A \\
\end{array}
$$
uses two sorts. This now forbids $f(g(a());b())$ since $g(a)$ has not sort $A$ as required. Instead, $f(b();g(a()))$ is still allowed.

When terms are logical formulae, it is common to use signatures to keep our words meaningful. For instance

$$
\begin{array}{l}
\land : P \times P \to P \\
{\sf prime} : \mathbb N \to P \\
0 : 1 \to \mathbb N \\
s : \mathbb N \to \mathbb N \\
\end{array}
$$
allows $\land({\sf prime}(0());{\sf prime}(s(0())))$ (i.e. ${\sf prime}(0) \land {\sf prime}(s(0))$, in more casual notation), but disallows nonsense such as
$\land({\sf prime}(0());0())$ (i.e. ${\sf prime}(0) \land 0$) which tries to use term $0()$ as if it were a proposition (a term of sort $P$).


Subset sum problem, given that a valid subset exists I have a problem at work.  I need to find a subset of a set of positive integers that sums to a certain value.  I know there is a subset but I need to find it.  Is this new problem the same as the subset sum problem?

This problem is as hard as the primary subset sum problem.

Suppose you have a polynomial time algorithm (say the time with input size $n$ is bounded by a polynomial $f(n)$) for this problem, then for any instance of size $n$ of the primary subset sum problem, you can run this algorithm directly with at most $f(n)$ time. If the instance indeed has a solution, this algorithm will return a valid solution. Otherwise, this algorithm will return nothing, a meaningless string, or a wrong solution, etc. Anyway, the algorithm returns a valid solution if and only if the instance has a valid solution, and you can check in polynomial time whether this algorithm returns a valid solution. This results in a polynomial time algorithm for the primary subset sum problem.


Binary Search Tree Property In the book 'Introduction to Algorithms 3/e', I have found the following definition of Binary Search Tree property:

  Let $x$ be a node in a binary search tree. If $y$ is a node in the left subtree
  of $x$, then $y.key \leq x.key$. If $y$ is a node in the right subtree of $x$, then $y.key \geq x.key$.

My confusion is that while implementing binary search trees we either consider that the keys of left-subtree of a node $x$ would be $\leq x.key$ or the keys of right-subtree of a node $x$ would be $\geq x.key$ but not both. That is we follow one of the two convention. But in the property they have included $=$ in both the cases. Where am I wrong?

I would appreciate any idea on this issue.

You're not wrong, but neither are they. The normal formulation is to have the left subtree values be strictly less than ($<$) the current value and the right greater than or equal to ($\geq$) the current value, or vice versa ($\leq$ and $>$), however using $\leq$ and $\geq$ still results in a working BST in the sense that the tree provides an ordering. (Try constructing a few, you'll see that the difference is that if you have repeated values, they can get spread over the right-most part of the left subtree and the left-most part of the right subtree instead of being in one or the other).

To see that it still works, consider the cases when searching the tree:

$y = x$, you've already found it, so you can stop here;
$y < x$, it must be in the left subtree (if $y <x$ then $y \leq x$);
$y > x$, it must be in the right subtree.

So you can see that the operation is identical, the choice at each node remains unambiguous.

EDIT Just to highlight Svick's excellent point in the comments, if you're searching for all nodes with the same value, the "$\leq,\geq$" case introduces complications - it may require more than one pass to find all such nodes (a full traversal will get them all of course, if it's an inorder traversal you even get them in a row).


What's the meaning of "Front" in "Pareto-Optimal Front"? I'm reading a paper about Multi-Objective Optimization Problem. I understand Optimal in Pareto sense, and I even know what is Pareto-Optimal Front somehow. But I can't find a relationship between the word Front and the concept. So, what's the meaning of this word in this context?

I think it is sort of short for "frontier" (as in boundary between one thing and another.)  The two canonical examples would be a weather front (the boundary between a cold airmass and a warm airmass) and a military front (the boundary between the areas controlled by a pair of belligerent armies).


heap data structure complexity I'm trying to count running time of build heap in heap sort algorithm

BUILD-HEAP(A)
heapsize := size(A);
  for i := floor(heapsize/2) downto 1
    do HEAPIFY(A, i);
  end for
END

 image by HostMath

 suppose this is the tree

   4    .. height2
  / \
 2   6  .. height 1
/\   /\
1 3 5 7  .. height 0

what I understand here $O(h)$ means worst case for heapify for each node, so height=ln n if the node is in the root for example to heapify node 2,1,3 it takes $ln_2 3 =1.5$ the height of root node 2 is 1, so the call to HEAPIFY is $ln_2 n=height = O(h)$

im not sure about this $\frac{n}{2^{h+1}}$ , is the number of nodes for any given height , suppose height is 1 and sum of nodes is 3 such as 2,1,3, so $\frac{n}{2^{h+1}}= \frac{3}{2^{0+1}}=1.5=2$ , when height is 0 there is at most two nodes. am i correct?

suppose given height is 0 so it is the last layer, then when sum of nodes is 7 , $\frac{n}{2^{h+1}}$ =$\frac{n}{2^{0+1}}$=$\frac{7}{2}=3.5=4?$ -> {1,3,5,7} if the root is 4

the summation is lg n because it sum the total height when it do heapify?

and last is to count the big-oh, BUILD HEAPIFY will call HEAPIFY $\frac{n}{2}$ times, and each will be $ln_2 n$ = height of the root, so $O(\frac{n}{2} * ln_2 n)$ ?

please correct me if i am wrong thanks!

https://www.growingwiththeweb.com/data-structures/binary-heap/build-heap-proof/
this is the reference i used, and also i read about this in CLRS book

Even if i don't really understand your point, i'm try to figure out an intuitive proof for building heap time complexity, starting from a simple recursive algorithm for building heap.

You have a collection of n unsorted element, called A,
you want from this collection build a heap(in your case a min-heap because you are mantaining the minimum of collection in the root).

So modelling the heap you want to create like a binary tree, it must shows some property like:

complete: the tree is "fullfilled" until second-last level and the leaves are "compatted" on the left.
logarithmic height: if the number in the heap is n then the height is O(logn) (you can proof this starting from the first property)
order relation between nodes: in particular, if v is father of w in the tree then $$ value(v)<= value(w) $$

Now think A as an unsorted binary tree you can recursively construct an heap follows this step:

Make recursive call on the left sub-tree
Make recursive call on the right sub-tree
Call heapify on the root of the current tree

heapify

Heapify on a node v simply compare v with it sons, and exchange v with the lowest son if it is less than v. Do this repeatedly until exists a son of v that have less value.

heapify complexity

So in heapify you make, at most, as many exchanges as high as the tree is, and since the only operation you perform is compare with the son(at most 2) for each level

=> time complexity is O(logn) for the 2nd property.

now for compute the overall complexity you can set a recursion function considering the worst case in wich A is a perfect binary tree (complete and with last level  fullfilled).

So let's assume A is a perfect binary tree,
the recursion function is:

$$ T(n) = T((n-1)/2) + O(log(n)) $$

because in each recursion step you consider half-part of the tree and exclude the root, and in each step with n as parameter you pay $$ O(log(n))$$ for heapify.

So by Master theorem (https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms))

$$T(n) = O(n) $$

so you can deduce that building an heap from an unsorted collection of value is linear in the number of element in the collection.

Know this maybe don't answer your question but i hope can help!


Lower upper bound on # variables in k-SAT with m clauses If I have an instance of $k$-SAT with $m$ clauses, then a trivial upper bound on the number of variables $n$ is given by $n \leq mk$. But we can only have $n = mk$ when no variable is repeated and that would be a trivial yes-case of k-SAT. I am making some running time analysis based on number of clauses, and therefore need to eliminate $n$ from my formula.

So my question is, can I make a lower upper bound on the number of variables, above which the instances will always be trivial?

I have a feeling that $\frac{1}{2}mk$ should be possible (I even think I had the argument for this in my head at some point), because $mk$ is actually an upper bound on the number of literals, not variables, but I can't be sure that all literals are present in both negated and unnegated form, and therefore can't seem to find an argument for this.

If you want to prove the worst-case running time of your algorithm, you probably don't need to prove that.  It's probably enough that there exists instances of SAT with (say) $\frac12 mk$ variables that are NP-hard; and that can be proven.

When each variable occurs only twice in the formula, SAT can be solved in polynomial time (via resolution).

With the restriction that each variable can occur up to three times in the formula, SAT remains NP-hard.  (Proof: start with an ordinary CNF formula $\varphi$.  If $x_i$ appears $k$ times, introduce variables $x_{i,1},\dots,x_{i,k}$, replace the $j$th occurrence of $x_i$ with $x_{i,j}$, and add clauses for $\neg x_{i,1} \lor x_{i,2},\neg x_{i,2} \lor x_{i,3},\dots,\neg x_{i,k-1} \lor x_{i,k}, \neg x_{i,k} \lor x_{i,1}$.)

Therefore, there exists a class of instances of $k$-SAT with $m$ clauses and $\frac{1}{3} mk$ variables, such that solving those instances is NP-hard.

To answer your original question, there is no useful answer to your original question.  For all $\varepsilon>0$, there exists a class of instances of $k$-SAT with $m$ clauses and $(1-\varepsilon)mk$ variables that is NP-hard.   In particular, take an ordinary CNF formula $\varphi$ with $n$ variables and then just append useless clauses of the form $x_{t} \lor x_{t+1} \lor \cdots \lor x_{t+k}$; each useless clause mentions $k$ new variables that appear only in that one clause and nowhere else.  The resulting formula is exactly as hard as $\varphi$, but now has a number of variables that is an arbitrarily large fraction of $mk$.


Karp reduction from optimization problems to decision problems When you consider Cook reductions, then decision and optimization versions of the problems are polynomial time reducible to each other.

Focusing on Cook reductions, there exists a natural Karp reduction from the decision version of a problem to optimization version. Is the converse also true?

Thanks to comments by Yuval Filmus, I understand that my question does not make sense as Karp reductions are defined for decision problems. Since Cook reductions allow more freeness, it makes sense to talk about a Cook reduction from a decision problem to an optimization problem, but this is not true for Karp reduction.


Time complexity of Ackermann's Function How would one go about classifying the time complexity of Ackermann's function, and can we say that all primitive-recursive functions are asymptotically bounded by the complexity of the Ackermann function as an asymptotic upper bound?

Edit: I want to make it clear that I am interested in the time complexity of computing Ackermman's function and whether the time complexity of computing any primitive recursive function is asymptotically bounded by the time complexity of computing Ackermman's function. I am not interested in the actual values of those functions.

I am asking because I remember seeing an assertion of my second question in an old book but no proof was shown and no time complexity for computing Ackermman's function was listed, so the assertion was by no means rigorous.

You are asking (or at least typing) multiple questions that are unrelated.

Time Complexity of the Ackermann function

First, understand that this is not a meaningful query. The Ackermann function, let's call it $A$ (assume a one-parameter variant), is a function, not an algorithm. You can certainly talk about $\Theta(A)$.

What you likely mean is the time $T_A(n)$ required to compute $A(n)$. I do not know of any algorithm besides explicitly computing the recurrence; the runtime of this approach can be investigated using the standard approach. It's unlikely that the result will be a meaningful $\Theta$-asymptotic in terms of the "usual" basic functions; you'd get runtime bounds expressed in $A$ itself.

That does not mean that there is no faster algorithm; it would not contradict the growth of $A(n)$ per se. Depending on your computational and cost model, you can compute huge numbers with little cost.

Are all primitive-recursive functions in $O(A)$?

Yes. That is (a consequence of) how we show that $A$ is not primitive recursive.

Note that here we are back to comparing values of the functions again; no mention of "time complexity" is being made.

Can all primitive-recursive functions be computed in time $O(T_A(n))$?

Not knowing $\Theta(T_A)$, I do not have an answer to this question.


Misconception in taking Pumping Length of language {a} to be $2$ I would like to know why the pumping length of language {a} is $2$ as said in this chat discussion.

Eventhough this discussion proves  trivially  that the pumping length of language {a} is $2$ I couldn't get by an example how the pumping length of language {a} becomes $2$.Could anyone help me with an example.

Informally, the pumping lemma for regular languages state that any sufficient large string may be pumped.

Your language is finite, meaning if you pick a pumping length that is larger than any string in your language, the lemma is trivially true. In your example the pumping length is $2$ but there are no strings in your language of length at least two. So you can pump all strings of length $2$ or longer (there are none!).

If you try and pick a smaller pumping length (the only possibility is $1$) then you will find that you can not pump. $w = a$ is your only string and the only possible decompsition $w=xyz$ is $x=\epsilon$, $y=a$, $z=\epsilon$. You can't however pump that because e.g. $\epsilon$ and $aa$ is not in your language.

Therefore; $2$ is the minimal pumping length of the language $\{a\}$


Derandomization of vertex cover algorithm I have the following randomized-algorithm for the vertex cover problem. Let $B_0$ be the output set:

Fix some order $e_1, e_2,...,e_m$ over all edges in the edge set E of G, and set $B_0=∅$.

Add to $B_0$ all isolated vertices, i.e. the ones without any incident edges.

For every edge $e$ in $e_1,e_2,...,e_m$
if both endpoints of e are not contained in $B_0$, then
flip a fair coin deciding which of the endpoints to choose, and add this endpoint to $B_0$.

I have already proved that this algorithm has $E[|B_0|] \le 2|OPT|$.

Now I don't know how to apply the method of conditional expectations (defined here) to derandomize the algorithm in order to show that we can't obtain an efficient deterministic version and that gives the same result of the expected value found previously.
Can you show me to do this?

First, let us repeat the analysis of the algorithm.

Fix some optimal vertex cover OPT, with cost $O$.

Let $S$ be the cost of the vertex cover produced by the algorithm.

Let $A_e$ be the indicator for the event "when edge $e$ was considered, the algorithm added a vertex belonging to OPT", and let $A = \sum_e A_e$.

Let $B_e$ be the indicator for the event "when edge $e$ was considered, the algorithm added a vertex not belonging to OPT", and let $B = \sum_e B_e$.

Thus $S = A+B$ and $A \leq O$.

The idea of the analysis is that $\Pr[B_e] \leq \Pr[A_e]$. To see this, consider what happens when vertex $e$ is considered. If $e$ is already covered by vertices already chosen, then $A_e = B_e = 0$. If both endpoints of $e$ belong to OPT, then $A_e = 1$ and $B_e = 0$. Otherwise, $\Pr[A_e] = \Pr[B_e] = 1/2$. In all cases, $\Pr[B_e] \leq \Pr[A_e]$.

Since $\Pr[B_e] \leq \Pr[A_e]$, we have $\mathbb{E}[B] \leq \mathbb{E}[A]$. Therefore
$$
\mathbb{E}[S] = \mathbb{E}[A+B] \leq 2\mathbb{E}[A] \leq 2O.
$$

How would we apply the method of conditional expectations? Here are two options:

Given the choice of which endpoint is taken, compute the expected value of $S$. If $z \in \{x,y\}$ was chosen, then we remove all edges adjacent to $z$, and then run the algorithm as usual. This reduces the problem to computing $\mathbb{E}[S]$, which is the expected number of edges which are not covered when their time comes. It's not so clear how to compute $\mathbb{E}[S]$.
The same, but instead of computed $\mathbb{E}[S]$ exactly, compute an approximation which is good enough to obtain a 2-approximation. Let $O_z$ be the optimum solution after removing all edges adjacent to $z$. Then
$$
\mathbb{E}[S \mid x] \leq 1 + 2O_x, \quad
\mathbb{E}[S \mid y] \leq 1 + 2O_y.
$$
If $x$ belongs to OPT then $O_x = O-1$, and otherwise $O_x \leq O$. Thus the average of both bounds is at most
$$
\frac{1+2(O-1)+1+2O}{2} = 2O,
$$
since at least one of $x,y$ belongs to OPT. Therefore, if we choose the vertex that minimizes $O_x,O_y$, then the resulting algorithm will produce a 2-approximation. Unfortunately, it's not clear how to compute $O_x,O_y$ (indeed, this ought to be hard).

In summary, it's not so clear how to apply the method of conditional expectations.


Are there any NP complete problems in SUB EXP TIME? Generally most np complete problems seem to have the best strategies operate in time $O(c^n$) for some choice of $c$

Has something like $O(2^\sqrt{n})$ (or any other less than exponential but greater than polynomial running time) ever been encountered in the wild as a run time for an algorithm that solves an NP complete problem?

The maximum clique problem on graphs with $m$ edges is solvable in time $2^{O(\sqrt m)}$. See Lemma 11.6 in F. Fomin and D. Kratsch, exact exponential algorithms, Springer, 2010. Also, note that PLANAR 3-SAT, while NP-complete, is solvable in time $2^{O(\sqrt n)}$, where $n$ denotes the number of vertices: https://cstheory.stackexchange.com/questions/30883/are-there-subexponential-algorithms-for-planar-sat-known


"Term Rewriting and All That" - Exercise 3.10 I am studying Term Rewriting by reading Baader/Nipkow's book "Term Rewriting and All That". I am in chapter 3 - Universal Algebra, in the section 3.2 - Algebras, homomorphism and congruences. I am trying to do exercise 3.10:

Let $\mathcal{Z}$ be the additive group of integers.
(a) - Determine all subalgebras of $\mathcal{Z}$ and all congruences on $\mathcal{Z}$.
(b) - Characterize those subsets of $\mathbb{Z}$ of cardinality 2 that generate $\mathcal{Z}$.
(c) - Given the integers $a, b, c \in \mathbb{Z}$, we define the mapping $h_{}: \mathbb{Z} \rightarrow \mathbb{Z}$ by: $$h_{(a, b, c)}(z) := az^2 + bz + c.$$
For what triples (a, b, c) is $h_{(a, b, c)}$ an endomorphism of $\mathcal{Z}$?
(d) - Given the integers $a, b$, we define the mapping $g_{(a, b)}: \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}$ by $$ g_{(a, b)}(z_1, z_2) := a z_1 + b z_2 .$$
Show that $g_{(a, b)}$ is a homomorphism of the direct product $\mathcal{Z} \times \mathcal{Z}$ into $\mathcal{Z}$. For what tuples $(a, b)$ is $g_{(a, b)}$ onto?

I think I was able to do items (a), (b) and (c), but I am having problems with item (d).
For item (a):

The subalgebras of $\mathcal{Z}$ are all of the form $\mathcal{nZ}$ where the carrier is $\mathbb{nZ} \ := \ \{ n z \ |\ z \in \mathbb{Z} \}$. This subalgebra is generated by $\{ n \}$.
The congruences on $\mathcal{Z}$ are all of the form $\equiv_{n} := \ \{(z_1, z_2) \ | \ n \text{ is a divisor of } z_1 - z_2 \}$.

For item (b):

A subset of cardinality 2 $\{ z_1, z_2 \}$ generates $\mathbb{Z}$ if and only if it generates {1}. This happens if and only if $gcd(z_1, z_2) = 1$. So, the subsets of $\mathbb{Z}$ of cardinality 2 that generate $\mathcal{Z}$ are of the form $\{z_1, z_2 \ | \ gcd(z_1, z_2) = 1 \}$.

For item (c):

It suffices to guarantee that $h(z_1) + h(z_2) = h(z_1 + z_2)$ for all $z_1, z_2$. Notice that:
$h(z_1) + h(z_2) = a (z_{1}^{2} + z_{2}^2) + b (z_1 + z_2) + c $
$h(z_1 + z_2) = a (z_{1} + z_{2})^2 + b (z_1 + z_2) + c$
Since this equality must hold for all $z_1, z_2$, we must have $a (z_{1}^{2} + z_{2}^2) = a (z_{1} + z_{2})^2$ for all $z_1, z_2$. This is only possible if $a = 0$. There are no restrictions on $b$ and $c$. So, the triples $\{(0, b, c) \}$ make $h_{(a, b, c)}$ an endomorphism of $\mathcal{Z}$.

For item (d), I was able to prove that $g(a, b)$ is a homomorphism of the direct product $\mathcal{Z} \times \mathcal{Z}$ into $\mathcal{Z}$:

Taking arbitraries $z = (z_1, z_2)$ and $z' = (z'_1, z'_2)$ in $\mathcal{Z} \times \mathcal{Z}$ we have:
$$g(z) + g(z') = (a z_1 + b z_2) + (a z'_1 + b z'_2) = a (z_1 + z'_1) + b (z_2 + z'_2) = g(z + z')$$

But I couldn't prove for what tuples $(a, b)$ we have that $g_{(a, b)}$ onto.
Can anyone help me with this part of item (d)?
Also, are my proofs of items (a), (b) and (c) correct? Thanks in advance.

If we can find $(z_1, z_2)$ such that $a z_1 + b z_2 = 1$ then we can take $(k z_1, k z_2)$ to obtain an arbitrary number $k (a z_1 + b z_2) = k \in \mathbb{Z}$ and then it is proved that $g_{(a, b)}$ is onto. However, every linear combination of two numbers $(a, b)$ is a multiple of their $gcd$. So, $g_{(a, b)}$ is onto if and only if $gcd(a, b) = 1$.


Mac question about flowcharting Is there a flowcharting application like Raptor for Mac. I am using the OS X (Sierra) version. I use Raptor in Windows and need a similar application
for Mac.

You could use MindNode or OmniGraffle (though OmniGraffle is more expensive), although these are more oriented towards mind-mapping than for flowcharting.

If you were looking for a free, web-based software, I've heard draw.io works pretty well. There really isn't much choice for macOS unfortunately, after all.


Closed Walk in Planar Graphs Input: Planar graph $G$ and its embedding in sphere $\Pi$, edges $e, f \in E(G)$ and integer $k$.

Output: The set of closed walks in $G$ using $e$ and $f$ which contains $k$ faces of $G$. In other words the set of close walks in $G$ via $e$ and $f$ which each one partition $\Pi$ into two set of faces which one is of size $k$.

I'm wondering if this problem is solvable in poly-time!

It's not, since there can be exponentially many such walks.

The $((2 \cdot n)+1)$ by $((2 \cdot n)+1)$ grid graph will have at least $2^n$  such paths for $k = (2\cdot n \cdot n)+(4 \cdot n)+1$, since paths can go along two sides of the grid, in from both ends of that, then connect both ends of that in a way which encloses exactly two squares of each of the $n$ non-overlapping 2-by-2 blocks on the diagonal between those ends.

However, there are at least 8 weaker versions of what you're asking about.

Enumerating them in poly(input_size, number_of_such_paths) time.
Enumerating them in poly(input_size) $\cdot$ number_of_such_paths time.
Enumerating them with polynomial delay.
Doing one of the previous three while using only poly(input_size) space.
Computing number_of_such_paths and a bijection from {0,1,2,3,...,number_of_such_paths-1} to the set of such paths.
Doing the previous thing and computing the inverse of the bijection.

I don't know anything about whether or not any of those are doable in polynomial time.


Comparing turing based programming languages According to Turing thesis, Can we say all programming languages that support turing machine like C have same power for solving problems and performing algorithms? In other words is there any algorithm or problem that one of them can solve it and the other can't?

The notion  you are looking for is probably Turing completeness.  All languages that are Turing complete are essentially equivalent in what problems they can solve (at least in principle).   Most general-purpose programming languages are Turing complete.


FSM + state data is Turing complete abstraction? I'm playing with Akka FSM.
The declaration of a an Akka FSM consists of states + data mantained during the states (the akka doc is more clear than me) + events that trigger transitions between states.
Can we say that such a formalism is Turing-complete? I can't think of a problem that can't be solved this way.

Maybe your questions should be more self-contained, but let's assume that your description together with the documentation from Akka amounts to the following description:

The input consists of events, and the output consists of actions.
Even so output actions may trigger further input events, this relation is neither fully deterministic, nor part of the machine model itself.
There are a finite number of states that determine which rules will be applied to the input event and the internally stored data, for determining the output action, the new state, and the modification of the internal data.
After an output action is performed, the machine transitions into a new state, and waits for further input events.

Under these conditions, the machine model is only Turing complete if already the rules for determining the output action, the new state, and the modification of the internal data were Turing complete.

What you have in mind is probably some mechanism for triggering input events as part of the output action. So the FSM is supposed to have some sort of first-in, first-out event queue, and the output action can post input events to this queue. In this case, this machine model would be more powerful than a queue automation, which is known to be Turing complete.


What's the value of this game (rebalancing counters)? Suppose you have the following game:

There are infinitely many counters $\{c_1,c_2,\ldots\}$, all initialized to 0.

In each step, you may choose a counter $c_i$ and increase it's value by 1.

Unfortunately, every $T$ steps, each counter that has a positive value is decremented by 1.

Also, the values of the counters are bounded by $M$, so you can't increment a counter any further.

Given as many steps as you like, can many positive valued counters can you reach?

EDIT: As this question is unanswered for two weeks, I have posted it in CSTheory as well.

Detailed buildup for $\approx T\log(M)$ positive counters:

While you have less than $T-1$ counters at value $M$:

Increment the minimal index counter whose value is strictly less than $M$.
This has to converge as the sum of the counters are bound to increase every $T$ steps.

Let $r = T$.
While ($c_0>0$)

a.  while ($c_0>c_r$)

Increment $c_r$

b. $r = r + 1$

Now for the analysis: first observation is that the number of positive counters is $r$.

Now let $m_r$ be the maximal value $c_{r}$ have reached. For $r=T$ we get $M(1-\frac{1}{T})$. For $r=T+1$ we get $m_r(1-\frac{1}{T})=M(1-\frac{1}{T})^2$, or in general $$\forall r\geq T:m_r = M(1-\frac{1}{T})^{r-T+1}$$

Next we notice that when $\forall m_r$ is achieved, $c_0=m_r$.
This means the loop will halt when $m_r < 1$ (give or take integrality and end-of-game-strategies).

This gives us
$$M(1-\frac{1}{T})^{r-T+1} < 1$$
$$(1-\frac{1}{T})^{r-T+1} < M^{-1}$$
$$({r-T+1}) \log (1-\frac{1}{T}) < -\log M$$
$${r-T+1}  < \frac{-\log M}{\log (1-\frac{1}{T})}$$
$$r  < \frac{-\log M}{\log (1-\frac{1}{T})} + T - 1$$
$$r  < \frac{\log M}{\sum_{k\geq 1}^{\infty} {\frac{1}{kT^k}}} + T - 1 < T(\log M + 1) -1$$

Does this look right?

Is it possible to do better? Can anyone prove this is optimal?

Let's collect what facts we can determine:

The sum of all counters $S$ will change by $T-P$ with each cycle of $T$ steps, where $P$ is the number of positive counters at the final step of the cycle.
If you end a cycle with $P=T-1$, you have $S\le(T-1)(M-1)$. During the following cyle you can reach $S=(T-1)M$ after $T-1$ steps, but in the next step you will have to increase a $T$-th counter, so the decrease after that step will return to $S=(T-1)(M-1)$. So $(T-1)M$ is an upper bound for $S$ (and thus also for $P$).
Assume there is an optimal strategy, that never reaches $S=(T-1)M$. The step where that strategy reached its highest value of $S$, has to be the penultimate step of a cycle, and the cycle before that one has to have ended with $P\le T-1$. By inserting a cycle that simply increases some or all of the nonzero counters before the cycle that reaches maximum $S$, we can increase the maximum value of $S$ for that strategy without influencing the maximum value of $P$.
Thus we can restrict our search for an optimal strategy to strategies that start by bringing $T-1$ counters up to $M$ and then try to distribute the sum amongst as many counters as possible.
The maximum value of $P$ will be reached at the penultimate step of a cycle. (At any other point we can raise it by increasing counters that were previously 0 until that step of the current cycle.) We denote by $X$ the number of cycles (including the incomplete one) in the distribution phase.
We can assume that any counter we increase during the distribution phase will be nonzero in the $X$-th cycle. Otherwise not spending these increases would not alter the outcome. For the same reason we can assume that each nonzero counter is at value 1 in the $X$-th cycle.
From the previous item we can conclude that any counter increased in the 1st cycle has to be increase $X$ times, any counter increased for the first time in the 2nd cycle has to be increased $X-1$ times and so on. This implies that it is beneficial to start increasing each counter as late as possible.
In the last cycle we cann set $T-1$ counters to 1. In the cycle before that, we can set $\frac T2$ counters to 2, and so on, until in the first $\frac XT$ cycles we can set one counter to $X$. This shows that it is beneficial to make $X$ as large as possible.
$X\le M$, since after the $M$-th cycle all the initial counters will reach 0 (or we have to spend increase operations on them that we could instead have spent to increase other counters).

Since the optimal moves from our considerations describe exactly the strategy from the question, we can conclude that this strategy is indeed optimal.


How to give a context-sensitive grammar for a^nba^nba^nb? I am struggling on this problem since days: $L = \{a^nba^nba^nb \mid n \in \Bbb N\}$. I have to give for this language a context-sensitive grammar.

One possible grammar is:

\begin{align}
S&\rightarrow Tb &(1)\\
T&\rightarrow AXY &(2)\\
T&\rightarrow ATXY &(3)\\
YX&\rightarrow YZ &(4)\\
YZ&\rightarrow WZ &(5)\\
WZ&\rightarrow WY &(6)\\
WY &\rightarrow XY &(7)\\
AX &\rightarrow AbA_X &(8)\\
A_XX&\rightarrow A_XA_X &(9)\\
A_XY&\rightarrow A_XbA_Y &(10)\\
A_YY&\rightarrow A_YA_Y &(11)\\
A&\rightarrow a &(12)\\
A_X&\rightarrow a &(13)\\
A_Y&\rightarrow a &(14)
\end{align}

We can generate $A^n(XY)^n$ using Rule (1) to (3). Rule (4) to (7) are used to change $YX$ to $XY$, thus we can generate $A^nX^nY^n$. At last, using Rule (8) to (14) we can generate $a^nba^nba^nb$.

Note we needn't worry that in a pattern $YX$, $Y$ yields to $A_Y$ (or $bA_Y$) before we exchange $X$ and $Y$, because otherwise there is no rule to eliminate $X$ in this pattern.


Can well-formed formulas in predicate logic for a given signature be recognized in LOGSPACE? I read that visibly pushdown languages are supposed to model the typical simple formal languages like XML better than deterministic context free languages. The visibly pushdown languages can be recognized in LOGSPACE. I wonder whether the well-formed formulas in predicate logic for a given signature are a visibly pushdown language, or can at least be recognized in LOGSPACE.
Here is a typical well-formed formula in predicate logic, for the given signature $(f(\cdot,\cdot), g(\cdot))$:
$\forall x (f(x,y)=z \land g(z)=x)$
A corresponding context free grammar would be

$P \to T=T$
$P \to (P \land P)$
$P \to (P \lor P)$
$P \to \lnot P$
$P \to \forall V P$
$P \to \exists V P$
$T \to V$
$V \to x$
$V \to y$
$V \to z$
$T \to f(T,T)$
$T \to g(T)$

Some people prefer to use reverse polish notation:
$xyfz=zgx=\land x\forall$
A corresponding context free grammar would be

$P \to TT=$
$P \to PP\land$
$P \to PP\lor$
$P \to P\lnot$
$P \to PV\forall$
$P \to PV\exists$
$T \to V$
$V \to x$
$V \to y$
$V \to z$
$T \to TTf$
$T \to Tg$

Because I have now written down two explicit grammars, let the question just be whether these two grammars generate visibly pushdown languages, or can at least be recognized in LOGSPACE.

Yes, well-formed formulas in predicate logic for a given signature be recognized in LOGSPACE, at least for the two notations (grammars) given in the question!

The normal notation is indeed a visibly pushdown language, with $\Sigma_c=\{(\}$, $\Sigma_r=\{)\}$. When we encounter the symbol $($, then we push the number of still expected occurrences of of terms or proposition (and whether we expect terms or propositions) on the stack. When we encounter the symbol $)$, then we first check that exactly the expected number of terms or proposition occurred, then overwrite the counter by the value on the stack, and decrease it by one. The counter is finite, because its maximum value is the maximum arity of the signature, and zero is its minimal value, because we reject when the counter would become negative.

The given RPN grammar is also a visibly pushdown language, because the maximum arity of the given signature doesn't exceed two. You push on the stack the variables, pop from the stack for the binary function, the quantifier and the equality relation, and do nothing for the rest. What we actually push on the stack is the type (empty, term, or proposition) of the top element of the "real RPN" stack, before the new element is pushed. Convince yourself that we can always know this type (variable is not a type here).

Also RNP formulas for signatures with higher arity can be recognized in LOGSPACE, because they can be converted in constant time and space to an equivalent signature that whose arity doesn't exceed two, by using a pair constructor.


Is this language regular Let L is a regular language then is

L' = {x$_2$x$_1$| x$_1$x$_2$ ∈ L}

regular?

Thus x$_1$x$_2$ is essentially concatenation of two strings, but can reverse concatenation of same two strings yield regular language?

The answer is yes. Suppose $A=(Q,q_0,F,\delta)$ is a deterministic finite automaton (with set of states $Q$, initial state $q_0$, set of final states $F$, and transition function $\delta$) recognizing the original language $L$. Then you can construct a nondeterministic automaton for $L'$ as follows:

For each state $q$ of $A$ create a separate copy of $A$, add $\epsilon$-transitions from its accepting states to the initial state, and then make $q$ the initial and (unique) accepting state. This gives you an NFA $A_q=(Q,q,\{q\},T)$, with transition relation $T=\{r,a,\delta(r,a)|r\in Q,a\in\Sigma\}\cup\{(r,\epsilon,q_0)|r\in F\}$. This NFA accepts a word $w$ if and only if there is a decomposition $w=uv$ such that $\delta(q,u)\in F$ and $\delta(q_0,v)=q$, which implies $vu\in L$.

Let $A'$ be the union of all the $A_q$. Then for any $uv\in L$, $vu$ is accepted by $A_q$ for $q=\delta(q_0,u)$, and therefore by $A$.


Is $n$ times $O(1)$ equivalent to $O(n)$? I am having a hard time figuring out if
$$\sum^n_{i=0} O(1) =O(n)\,.$$

I think it doesn't but I am unable to find a convincing explanation for that, does anyone have an intuitive yet mathematical answer for that?

Think in terms of the definition: $f(m)=O(g(m))$ means that there exists some constants $c>0, M\ge 0$ such that $f(m) \le c\cdot g(m)$ for all $m\ge M$ so when you write
$$
\sum_{i=1}^nO(1)
$$
you mean that there are $n$ functions, $f_1, f_2, \dotsc, f_n$ and constants $c_1, c_2, \dotsc, c_n$ such that $f_i(m)\le c_i\cdot1$ for all sufficiently large values of $m$. Your sum then is
$$
\sum_{i=1}^nO(1)=\sum_{i=1}^nf_i(m)\le \sum_{i=1}^nc_i\le \max_{1\le j\le n}\{c_j\}\cdot n
$$
for all sufficiently large $m$. The problem here is, as Hendrik and babou pointed out, the $\max$ term is a function of $n$. For instance, if $f_i(m) = i$ were constant functions, individually they are all in $O(1)$ but their sum
$$
F(n) = \sum_{i=1}^nf_i(m)= \sum_{i=1}^ni = \frac{n(n+1)}{2}\notin O(n)
$$
The constants are not the only problem here, though, even if we restricted them all to be bounded by some constant $K$. Suppose we had defined the functions $f_i(m)$ to be
$$
f_i(m) = \begin{cases}
2^i & \text{if $m<i$}\\
1 & \text{if $m\ge i$}
\end{cases}
$$
Now each $f_i(m)\in O(1)$, since for each of them we could find a $c_i>0,M_i\ge 0$ such that for all $m\ge M_i$ we have $f_i(m)\le c\cdot 1$ (just pick $c_i=1$ and $M=i$ for instance).

In this case, we also don't have $F(n)\in O(n)$: even though all the $c_i = 1$
we can't now find a fixed N so that $F(n)\le Kn$ for all $n\ge N$, since we chose the functions $f_i$ so that the "crossing point", $M_i$, is a moving target. No matter what $N$ you pick, there will be a point where beyond $N$ the sum will be larger than $Kn$.

It seems that the best you can say is that $F(n)=O(n)$ when all of the $c_i$ are less than or equal to a single fixed bound and the same holds for all the $M_i$. Useful in some cases, I suppose, but woefully wrong in general.


Tiling an orthogonal polygon with squares Given an orthogonal polygon (a polygon whose sides are parallel to the axes), I want to find the smallest set of interior-disjoint squares, whose union equals the polygon.

I found several references to slightly different problems, such as:

Covering an orthogonal polygon with squares - similar to my problem, but the covering squares are allowed to overlap. This problem has a polynomial solution (Aupperle, Conn, Keil and O'Rourke, 1988;  Bar-Yehuda and Ben-Hanoch, 1996).
Tiling/decomposing/partitioning an orthogonal polygon to rectangles. This problem has a polynomial solution (Keil, 2000; Eppstein, 2009).
Covering an orthogonal polygon with rectangles - this problem is known to be NP-complete (Culberson and Reckhow, 1988).

I am looking for an algorithm for minimal tiling with squares.

I will try to show this problem is NP-hard, by reduction from $\text{Planar-}3\text{-SAT}$.

Reduction from $\text{Planar-}3\text{-SAT}$

Some basic Gadgets

Gadgets are internal configurations of geometry that will allow us to construct gates for use in a circuit, to which we will reduce $\text{Planar-}3\text{-SAT}$.

4X3-gadget

This gadget has two valid minimal-square-partition-states:

LeftA 4X3-gadget.Middle and right:Two possible minimal-square-partition-states.

5X4-gadget

This gadget, is exactly like a 4X3-gadget, just with larger dimensions.

LeftA 5X4-gadget.Middle and right:Two possible minimal-square-partition-states.

endpoint-gadget

An endpoint-gadget is a 5X4-gadget. It is frequently used as an endpoint/pin of a gate. One of the two states of an endpoint can be valued as true, and the other false. An endpoint marks the two ends, one as $T$ and the other as $F$. The end that is covered by the large square is the value of the endpoint.

Left: Wireframe of endpoint-gadget. Center:True-valued endpoint. Right: False-valued endpoint.

i-wire gadget

An i-wire gadget is short for implication wire.

Rules:

An i-wire gadget consists of a odd-length rectangle of a length of more than $2$ and a width of $2$.
An i-wire gadget can have $3$ minimal-square-partition-states, pushed from one side, the other, or neither; an i-wire in this third state shall be called locally unconstrainted.

Example:

Figure 7: An i-wire gadget of length $7$, and width $2$.

Here is how it is used:

Figure 8,9, Left: wireframe i-wire across two endpoints. Right: Union.

Now, if one endpoint is in the right state, it forces the other endpoint into a pushed-position. Example:

Left: Square partition diagram; left switch is down, "pushes" all the squares down the i-wire and finally, pushes the other switch (endpoint). Right: Square partition diagram; left endpoint is full, "pushes" all the squares down the i-wire, and forces the endpoint on left to be "up".

This is essentially a logical implication. Consider "down" to be true, then we have $A \implies \neg B$. We can also do $A \implies B$ by simply flipping the endpoint on the right.

However, this leaves the unconstrainted case:

If we combine two i-wires, we can get a two-way implication, essentially a boolean (in)equality:

So, two i-wires can carry a full equality relationship, much like a circuit - in fact, it is a circuit. We will use these pairs to construct a usable wire.

Each i-wire gadget contributes $\frac{l-1}{2}+2$ partition-squares to the minimal-square-partition, save for the shared-corners with other gadgets.

i-wires can be oriented as needed.

wire

A wire consists a pair of i-wires that are connected to the same gates at each endpoint.

The i-wires are colored red and green.
The pair must be separated by $3$ spaces (convention).
Each gate pin will have a green and red contact; a wire must correctly connect.
Invariant rule: one i-wire be pushed in the opposite direction of the other i-wire, each gate assumes this, and makes certain of this (unless otherwise noted).
Since each wire contains a two-way implication, it carries the values from gate to gate like a wire in a circuit.
Every wire must be connected to a gate at both ends.. Failing this can ruin the assumptions of some gates that I describe, and the invariant rule above; however, gates that have endpoints across the leads are safe - you can connect stray wires to these endpoints without worrying about it ruining the gate.
wires must be of odd-length, including the leads to any circuit it connects to; however I will describe an odd-skip-gate below that allows an even-lengthed wire to become odd-lengthed.

Pictures:

Above: A wire.

Left and right: Two possible minimal-square-partition-states of a wire. Note that if the wire is only this length, it will not be able to shift off to the right or left, and will have to break one square into smaller pieces.

wires can be oriented as needed.

bend-gate: Bending a wire

Left: Wire-frame view. Right: Union view.

Note the use of the 4X3-gadget. It is used to fix the red lead to odd length.

Following are the two possible minimal-square-partition-states of the bend:

Left and right:Two possible minimal-square-square-partition-states of a bending wire.

The gate can be oriented as needed. Obviously, this gate can be mirrored to work for the other direction.

Skewing a wire

It is easy to shift a wire over. Wireframe illustration:

named-value-gate

A named-value-gate is essentially an endpoint as a gate with one wire contact:

odd-skip-gate: Odd skipping a wire

Sometimes it is inconvenient to only have odd-length wires. For example:

As you can see, that little bit of extension is a bit annoying. Here is a corresponding solution, using the 4X3-gate:

So, turning this into a gate, we get the odd-skip-gate (in wireframe):

The gate can be oriented as needed.

twist-gate: Twisting a wire

Somtimes you get the red and black i-wires on the wrong sides for use with a gate. In this case, a twist-gate is provided, to twist the red and black i-wires to the opposite sides.

Wireframe illustration:

Convince yourself it works:

Start from $A$, follow the push-arrows, everything else should be forced and consistent.

The gate can be oriented as needed.

split-gate: Splitting a wire

Splitting a wire, wireframe:

Convince yourself that it works:

Figure:Start from $A$, follow the push-arrows. Everything should be forced and consistent.

Figure:Start from $A$, follow the push-arrows. Everything should be forced and consistent.

Note: Every wire coming in and out of the splitter absolutely must connect to an endpoint somewhere, in order to maintain the invariant. Alternatively, you can add endpoints to each of the pairs of leads of the splitter.

The gate can be oriented as needed.

not-gate

The not gate takes a wire and outputs a wire that has the reverse implications. It is basically a twist-gate, except that it relabels the colorings of the wires. The not-gate looks like this:

And a view of the two possible states:

The gate can be oriented as needed.

clause-gate

For the clause-gate, we first introduce the clause-gadget:

Left to right: 1 clause-gadget. 2-4: $3$ different minimal-square-partition-states.

This is what the gate looks like:

We can demonstrate the different states of this gate (explanation underneath all $3$ illustrations):

Explanation:

Start at the clause-gadget and follow the arrows.
Non-arrow-lines mean that it is part of a circuit, but it is not forced into a state by the gate.
The state of the clause-gadget forces one of the endpoints to be valued true.

As you can see, at least one of the inputs will have to be valued as true. This is exactly what a $3\text{-CNF}$ clause requires.

The gate can be oriented as needed.

Reduction

Let $\Phi(\mathbf x)$ be a $\text{Planar-}3\text{-SAT}$ formula, where

$$\Phi\left(\mathbf x\right)={\huge\wedge}_i^n C_i,\\
C=\left\{(x_j \vee x_k \vee x_l)\right\}
$$

A visual aid (original source: Terrain Guarding is NP-Hard (PDF), reproduced in tikz):

Then:

For each variable $x_i\in\mathbf x$, place two named-variable-gates next to each-other,  name one of them $x_i$ and the other $\neg x_i$.
Connect the gates to each-other with a not-gate, so that they logically negate each-other's values.
Place the variables' gates' polygons at their locations in the planar-embedding.
For each clause, place a clause-gate at the clause's location in the planar-embedding.
Using the gates described above, connect all the variables to their clauses.
Run a minimum-square-paritioning-algorithm on the resulting union of the all of gate's polygons (the entire circuit).
If the algorithm returns the sum of all the gate's minimal-square-partition-state sizes (subtracting for shared-corners) then it is satisfiable. If it is not satisfiable, it will force a constrained gadget to split into smaller squares, thus increasing the number of squares required to partition the circuit.

Why it works

Each gadget has a minimal-square-partition-state size; that is, a minimal-square-partition of that gadget is a certain size.
Some gadgets have several states with this size; each of these states are valid minimal-square-partitions.
When gadgets are combined only in the corners, the sum of the minimal-square-partition-states of the gadgets is *still the minimUM-square-partition-state of the union of them; you can see this intuitively: joining at the corner does not give ample space for a square to expand/connect with a square from another gadget.
While combining gadgets at the corner does not decrease the total minimum-square-partition size, it does relate and constrain the gadgets with each-other.
With the gates shown above, you can constrain the states enough, so that if the logical formula is unsatisfiable, then one or more gadets will have to break into even smaller squares, and increase the minimum-square-partition size.

graph sources

squaretilings1.tex (writelatex)
squaretilings2.tex  (writelatex)
clausegate.tex (writelatex)

You can also see larger images by removing the "s", "m", "l", suffixes of the imgur urls. For example, You can see a larger image of this: http://i.stack.imgur.com/6CKlGs.jpg by going to
http://i.stack.imgur.com/6CKlG.jpg. Notice the missing "s" before the .jpg.


Question about generating functions $A(x)$ is generating function of $\{a_n\}_{n=0}^{\infty}$ and $B(x)$ is generating function of $\{b_n\}_{n=0}^{\infty}$, what is
$$A(x^2)+xB(x^2)$$?

Hint: we have $A(x^2) = \sum_{n=0}^\infty a_nx^{2n} = a_0 + a_1x^2 + a_2x^4+ \cdots$. What can we say about the coefficients of odd powers ($x, x^3, \dots$)?
Now do the same for $xB(x^2)$, what can we say about  the its even power coefficients?
What does this mean for their sum?


Distributed 6-color Vertex Coloring I am trying to understand the distributed 6-color algorithm for vertex coloring (on page 10).

Here is a short description

Idea of the algorithm: We start with color labels that have $\log n$ bits. In each synchronous round we compute a new label with exponentially smaller size than the previous label, still guaranteed to have a valid vertex coloring.

Let $i$ be the smallest index where $c_v$ and $c_p$ differ;
the new label is $i$ (as a bitstring) followed by the bit $c_v(i)$ itself

Grand-parent 0010110000 -> 10010 -> …
Parent       1010010000 -> 01010 -> 111
Child        0110010000 -> 10001 -> 001

The problem I cannot understand this example. Let's take Grand-parent($c_p$ = 0010110000) and parent($c_v$ = 1010010000), on the round when $c_v$ receives $c_p$, so we need to change $c_v$. They differ in 5th bit, counting from 0 (5 in binary is 101), so according to definition, $c_p$ is "$101$"+$c_p[5]=1010$, but in example it's 01010, what I get wrong?

The labels $c_v$ and $c_p$ are relative. So when a node (parent in your example) having $c_v = 1010010000$ receives from its parent (grandparent in your example) an id $c_p = 0010110000$, the difference, as you correctly point out, is in the fifth position.

Now, the total number of bits in the original ids is 10, so representing any index (0-9) will require 4 bits. So, the new id will have 4 bits from the position difference + 1 bit for the differing bit. Now,
$$(5)_{10} = (0101)_2$$

Note, we use 4 bits as discussed above, so that all new ids, can have the same number of bits. Then, $c_v(5) = 0$ is concatenated towards the LSB side, giving the new id: $01010$.


Limit on table size - perfect hashing Let us define a "root universal family" as a family of hash function which for every two items $k_i,k_j$ the probability $P(h(k_i)=h(k_j)) \le \frac{1}{\sqrt m}$ where $m$ is the size of the table.

Now, let us have $|U| = n$ -  (the size of the given universe, note that it is perfect hash).

Define an efficient perfect hash algorithm, for which the total sizes of the tables is $\le O(n^2)$.

Now, we note that if we have a table of size $n^2$, then the expected number of collision of a random hash function from that family is $\le \frac{n}{2}$. This is because:

$$\mathbb E[\text{number of collisions}] = \sum_{\{k_i,k_j\} \subset U, k_i\ne k_j}P(h(k_i)=h(k_j)) \le \frac{\binom{n}{2}}{\sqrt {n^2}} \le \frac{n}{2}$$

So, we define the "first-level" hash table to be of size $n^2$. The expected number of hash function we need to draw in order to have less than $n$ collisions is $2$ (since it is a geometric variable).

Now, this is where I get stuck:

After a hash family that satisfies less then $n$ collisions is chosen, for each table that has items colliding, we make a "second-level" table of size $|\text{number of collisions in table}|^4$. (It is easy to prove that in order to get no collisions when the size is $x^4$ we need again two draws for the second function.

The problem I having is showing that all the "second-level" tables + the "first-level" tables are $O(n^2)$ of total size. Would like help in proving that, Thanks!

Ok, I managed to prove it:

We note that the total size of the tables = $$n^2 + \sum_i n_i^4$$
where $n^2$ is the first table and $n_i$ is the size of the $i$th index of table with collisions.
Therefore we get:

$$n^2 + \sum_i n_i^4 = n^2 +\sum_i (n_i^2)^2 \le n^2 + \sum_i (4\binom{n_i}{2})^2 \le n^2 + 16(\sum_i \binom{n_i}{2}) = n^2 +16(\text{number of collisions})^2 = n^2 + 16n^2 = O(n^2)$$


Detecting conservation, loss, or gain in a crafting game with items and recipes Suppose we're designing a game like Minecraft where we have lots of items $i_1,i_2,...,i_n\in I$ and a bunch of recipes $r_1,r_2,...,r_m\in R$. Recipes are functions $r:(I\times\mathbb{N})^n\rightarrow I\times\mathbb{N}$, that is they take some items with non-negative integer weights and produce an integer quantity of another item.

For example, the recipe for cake in Minecraft is:

3 milk + 3 wheat + 2 sugar + 1 egg $\rightarrow$ 1 cake

... and the recipe for torches is:

1 stick + 1 coal $\rightarrow$ 4 torches

Some recipes could even be reversible, for example:
9 diamonds $\leftrightarrow$ 1 diamond block

If there's some combination of recipes we can repeatedly apply to get more of the items that we started with then the game is poorly balanced and this can be exploited by players.
It's more desirable that we design the game with recipes that conserve items or possibly lose some items (thermodynamic entropy in the real world - you can't easily un-burn the toast).

Is there an efficient algorithm that can decide if a set of recipes will:

conserve items?
lose items to inefficiency?
gain items?

Is there an efficient algorithm that can find the problematic recipes if a game is imbalanced?

My first thoughts are that there is a graph structure / maximum flow problem here but it's very complex, and that it resembles a knapsack problem. Or maybe it could be formulated as a SAT problem - this is what I'm considering to code it at the moment but something more efficient might exist.

We could encode recipes in a matrix $\mathbf{R}^{m \times n}$ where rows correspond to recipes and columns correspond to items. Column entries are negative if an item is consumed by a recipe, positive if it's produced by the recipe, and zero if it's unused. Similar to a well known matrix method for graph cycle detection, we could raise $\mathbf{R}$ to some high power and get sums of each row to see if item totals keep going up, stay balanced, or go negative. However, I'm not confident this always works.

Any discussion, code, or recommended reading is very appreciated.

Your problem is equivalent to asking whether there is some linear combination of row vectors from your $\mathbb R^{m\times n}$ matrix that has all coefficients positive and sums to a vector in which (a) every element is $\ge 0$ and (b) at least one element is $> 0$.

(Notice that the order of the operations doesn't matter: Running them in some order might cause the quantity of some item to dip below zero, but we can just look for the low-water-mark and suppose that we have at least that many of each item to start with.)

I think this can be solved by linear programming: Make a variable for each coefficient, add $\ge 0$ constraints for each element in the output vector (each element is a dot product of coefficient variables and constant coefficients from recipes), more $\ge 0$ constraints for each coefficient variable, and set the function to maximise to be the sum of all elements. To make it bounded, set the sum of coefficient variables to some constant, e.g. 1. Iff the solution value is $> 0$, you have non-conservation!

Note that fractional values are not an issue: They must be rational, so you can always multiply through by all denominators to get a pure-integer solution.


Can someone explain this diagram about Slab Allocation? I'm trying to understand how Slab Allocation works and why it is different or better than ordinary paging.

I found this diagram which I believe would be helpful if it had more explanation.

Some questions:

What do the 3KB and 7KB items represent? Must they be related somehow? Why are they packaged that way?
In the caches column, are the caches the grey boxes, or the white/blue boxes inside the grey boxes? Are the grey boxes a package of caches?
Are the slabs just the blue boxes or is the whole "Physical Contiguous Pages" a slab?

I'd really appreciate some help. THanks!

I can see why you're confused. The diagram is a bit confusing, and may actually be incorrect.

First off, let's think about why a kernel needs a memory allocator below the level of pages. This is probably already stuff that you mostly know, but I'll go through it for completeness.

Pages are the typical "unit" of memory operations. When a user-space application allocates memory, or memory-maps a file, or something like that, it typically gets a multiple of the machine page size. There are notable some exceptions; Windows uses 64k as the virtual memory allocation unit no matter what the page size of the CPU is. Nonetheless, let's think of it this way.

On a modern CPU, as far as user-space code is concerned, it has a flat address space. This is actually an illusion provided by the virtual memory system. The OS provides pages from anywhere in RAM (or possibly not in RAM at all, in the case of swapped memory or memory-mapped files) and maps them into a contiguous virtual address space.

The point of all this is that apart from a few special cases for the operating system itself (perhaps DMA buffers, maybe some special data structures set up at boot time, oh and the kernel image itself), the operating system kernel probably never has to manage any block of RAM bigger than a page. This simplifies things enormously, because it means that as far as pages go, every allocation and deallocation is the same size. It also effectively eliminates external fragmentation at the macro level.

However, kernels also need to implement some data structures of their own, and for that, they need a different kind of memory allocator. These data structures can usually be thought of as a collection of individual objects (e.g. an object may be a "thread" or a "mutex"). The size of these objects are typically far smaller than a page in size.

So, for example, an object which represents the security credentials of a process (think of the user id and group id in POSIX, say) might only be 16 bytes or so, whereas a "process" or "thread" might be up to 1kb in size. Clearly you don't want to use a whole page for these small records, so the idea is to implement an allocator on top of pages.

The lower-level allocation system has to satisfy many of the same issues as the page-level allocator: it has to be reasonably fast (including on multicore systems), you want to minimise fragmentation, and so on. But more importantly, it should be tunable and configurable depending on what kind of data structure you're storing.

Some data structures are inherently "cache-like". For example, many operating systems maintain a cache of path names to filesystem objects to avoid long chains of directory lookup (called the "name cache" or "namei cache" in Unix-speak). These objects are only needed for performance, not correctness, so you could (in theory) just forget a whole page full of entries if memory is tight and you need to free a page frame quickly.

Other data structures could be swapped to disk if memory is tight and you don't need them soon. But you don't want to do that with data structures which control swapping or the virtual memory system!

Some data structures can be moved around in memory with no penalty (e.g. if nobody refers to them with a pointer), so could "compact" themselves to avoid fragmentation if needed.

So the main idea of the slab allocator is that a page should only store data structures of the same "type". This ticks all the boxes: each object in a page is the same size, so there's no external fragmentation. Objects of the same "type" have the same performance requirements and the same semantics.

Incidentally, it's a similar story with allocation. For some types of object it's probably okay to wait if there's no memory immediately available to allocate that object. An object which represents an open file might be one example; opening a file is an expensive operation at the best of times, so waiting a little longer won't hurt that much.

For other types of object (e.g. an object which represents a real-time event that must happen a certain time from now), you really don't want to wait. So it makes sense for some types of object to over-allocate (say, have a few free pages in reserve) so that requests can be satisfied without waiting.

What you're basically doing is allowing each type of object to have its own allocator, which can be configured for the needs of that object. These per-object allocators are confusingly called "caches". You allocate one cache per type of object. (Yes, you'd typically implement a "cache of caches" as well.) Each cache only stores objects of the same type (e.g. only thread structures, or only address space structures).

Each cache, in turn, manages "slabs". A slab is a page frame which contains an array of objects of the same type. Slabs may be "full" (all objects in use), "empty" (no objects in use), or "partial" (some objects in use).

Partial slabs are probably the most interesting, since the slab allocator maintains a free list for every partial slab. (Full slabs and empty slabs need no free list.) Objects are allocated from partial slabs first (and probably from the "most full" partial slabs first) to try to avoid allocating pages that aren't needed.

The nice thing about slab allocation is that all of these allocation policy options (as well as the memory semantics) can be tuned for each kind of object. Some caches might retain a pool of empty slabs and some might not. Some might be able to be swapped to secondary storage and some might not.

Linux has has three different kinds of slab allocator, depending on whether or not you need compactness, cache-friendliness, or raw speed. There was a good presentation on this a couple of years ago which explains the tradeoffs well.

The Solaris slab allocator (see the paper for details) has a few more details to squeeze even more performance. For a start, in Solaris, everything is done with slab allocation, including page frame allocation. (This is Solaris' solution for allocating objects that are larger than half a page in size.) It manages smaller objects by nesting slab allocators in slab-allocated space.

Some objects in Solaris require complex and expensive construction and destruction (e.g. objects which have a kernel lock), and so they could be "partly free" (i.e. constructed but not allocated). Solaris also optimises free slab allocation by maintaining free lists on a per-CPU basis, ensuring that some operations are completely wait-free.

To support general-purpose allocation (e.g. for arrays whose size is not known at compile-time), most macrokernel-type operating systems also have caches which represent object sizes rather than object types. FreeBSD, for example, maintains caches for unknown objects whose sizes are powers of 2 bytes, from 4 to 256.

What I hope you can see is that slab allocation is a very flexible framework which can be tuned for the needs of different kinds of data. It doesn't compete with paging, but complements it (although in Solaris, page frames are allocated with slabs).

I hope this helps. Let me know if anything needs clarification.


Shortest path with positive edge cycle When reading about shortest paths in Cormen . I came across this paragraph which says that 'shortest path cannot contain' positive edge path even. But I don't understand the logic behind their explanation

  Can a shortest path contain a cycle? As we have just seen, it cannot contain a
  negative-weight cycle. Nor can it contain a positive-weight cycle, since removing the cycle from the path produces a path with the same source and destination
  vertices and a lower path weight. That is, if p {vo,v1,v2,.... vk} is a path and
  c = {vi; v(i+1)....vj) is a positive-weight cycle on this path (so that vi = vj and
  w(c) > 0), then the path pnew =  {v0,v1,.... vi, v(j+1) , ... vk} has weight
  w(pnew) = w(p)-w(c) < w(p), and so p cannot be a shortest path from v0 to vk.

The original snip from the book is here.

Could someone explain why it is so ?
I don't understand because any way removing an edge will cause the path length to decrease right ? why are they seeing removing positive edge cycle as different ?

For eg in the following diagram

How are they removing cycle and connecting vi and v(j+1) ?

They are just saying that if $P$ is a shortest path, in $P$ there are not positive cost cycles, since removing the cycle would led to a smaller cost (and so to a better path).

Consider your example and suppose we want the shortest path beween $s$ and $v_k$, let $P=(s,v_1,\color{red}{v_i},\color{red}{v_{i+1}},\color{red}{v_{j-1}},\color{red}{v_i},v_{i+1},v_{j-1},v_{j+1},v_k)$.

Removing the cycle from $P$ we obtain $P'=(s,v_1,v_i,v_{i+1},v_{j-1},v_{j+1},v_k)$ where $cost(P')=cost(P)-6$, so to a better path in terms of cost.


More complicated resources than time and space complexity The wikipedia page on computational resources states that there are many different resources that have been defined:

In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems.
The simplest computational resources are computation time, the number of steps necessary to solve a problem, and memory space, the amount of storage needed while solving the problem, but many more complicated resources have been defined.[citation needed]

Unfortunately, this claim doesn't have a citation.
What are these more complicated resources that have been defined?

I can imagine something like parallel processes used?

the wikipedia talk page talks about communication bandwidth: e.g. network bandwidth, and memory busses. ( this seems fairly "processor-dependent"? Not sure if there is a theoretical analysis of this).

It is interesting that claim, "many more complicated resources have been defined" has been present since the very first version of that Wikipedia page created in 2006, whose accompanying comment is "start article (will have to finish later, lightning storm)". That page is created by Wikipedia user Creidieki. That claim has never been explained on that page.

What are these more complicated resources that have been defined?

Here are some computation resources that may or may not be more complicated. Some of them may seen as variations of the computation time and memory space.

Oracles. How many queries will be answered by an oracle? For example, in quantum query complexity.
Entropy. How much entropy is needed to run a randomized algorithm or cryptographic algorithm?
Messages. How many bits are needed to be exchanged so that Alice and Bob can compute a value together?
Comparisons used in sorting in the comparison sorting model or branching in simple decision tree.
Memory accesses. How many memory accesses are used in cell probe mode?
Network bandwidth. This is critical to everyone who is reading this page or using the internet or any network.
Parallel processes. How many processes are used in the computation?
Steps of proof. How many steps does it take to prove or refute statements?
Cache hits. How many cache hits on average will happen when an algorithm runs?

We could also think of some more outlandish ones. How can we measure the complexity of lambda calculus reasonably? Could priority be considered as computation resource as well?

In addition to the resources that are needed to run algorithms to solve problems, We can also examine the resources or even techniques that are needed to build the computation machines.

Characters in source program or bytes in machine code. How long is the source code? I love code golf.
States. How many states are needed in a finite automaton to describe a regular language? From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity. Or what is the least number of states for a Turing machine to be Turing complete? Small universal Turing machines.
Boolean circuits. How large or how deep of of Boolean circuits are used to compute boolean functions?
Non-primitive recursion. When do we need non-primitive recursion to compute large growing functions?

In summary, we can check the list of complexity classes in Wikipedia or Complexity Zoo to find various computation resources that are considered in complexity analysis. Hopefully, this answer have given you a rough idea how diverse and interesting the computation resources and the complexity classes are.


If P = NP, does SAT, or any other NP-Complete poly-reduce to any language different from $\emptyset$ or $\Sigma^*$? I looked at Sipser ("Introduction to the Theory of Computation"), Problem 7.17:

  Prove that if P = NP, then every language in P, except $\emptyset$ and
  $\Sigma^*$, is NP-Complete.

The solution is as follows:

  Let $A$ be any language in NP and let $B$ be another language not
  equal to $\emptyset$ or $\Sigma^*$. Then there exist strings $x \in B$
  and $y \notin B$. To reduce an instance $w$ of $A$ to that of $B$, we
  just check in polynomial time if $w \in A$. If yes, we output $x$ and
  $y$ when $w \notin A$.

But I don't see why this reduction could not be applied to any language (except $\emptyset$ and $\Sigma^*$). It would not mean that the language is in P, but the reduction would be correct. The only point where I have doubts is the part where we say that $x$ and $y$ exist, do we somehow have to take into account some computing time for $x$ and $y$ ? Else the reduction would work even for unrecognizable languages for example.

The reduction does indeed work for any non-trivial language $B$. And that's what the claim you've quoted says: "Let... $B$ be another language not equal to $\emptyset$ or $\Sigma^*$", not "... another NP language..."

So, yes, it could be arbitrarily difficult to compute $x$ and $y$. It might even be impossible to compute them. But that doesn't affect the running time of the reduction because the reduction doesn't have to compute $x$ and $y$. Rather, the person who designs the reduction has to figure out those strings once. If you think in terms of computer programs, the reduction is a program that could be arbitrarily difficult to write but, once it's been written, it runs very quickly.  In complexity theory, we don't care how difficult it is to write the program; we only care about how efficiently it runs. If the program exists, we're happy, and these programs certainly exist.

Note that it can still be possible to concretely and explictly write down the reduction, even if $B$ is uncomputable.  For example, let $B$ be the language of descriptions of Turing machines that halt on every input. This is highly uncomputable: neither it nor its complement is recursively enumerable, for example, which means that there's no algorithm that can generate all the strings in $B$, or all the strings that are not in $B$. However, we don't need all the strings: we just need two strings.  Let $M_1$ be the Turing machine that immediately enters the halt state, regardless of its input, and let $M_2$ be the Turing machine that moves its head to the right forever, regardless of its input. We have $\langle M_1\rangle\in B$ and $\rangle M_2\rangle\notin B$ so, if you cared to figure out the values of $\langle M_1\rangle$ and $\langle M_2\rangle$ as binary strings, you could explicitly write down the reduction from an polynomial-time language to $B$.


A' not computable in A Recall A'= $\{x \mid \phi^A_x(x)$ halts and accepts $\}$

In this article, a proof that A' not computable in A is given:
http://www.math.uchicago.edu/~may/VIGRE/VIGRE2006/PAPERS/Flood.pdf

He constructs the function f(x)= $\phi_x^A(x)$ +1 if x in A and 0 if x not in A

Shouldn't it be f(x)= $\phi_x^A(x)$ +1 if x in A' and 0 if x not in A'

since we need $\phi^A_x(x)$ to halt and output a number provided it actually can?

then f will be computable in A and we can then go on to prove that f $\neq$ $\phi^A_x$ for the witness x

You are right. It seems you completely understand this already: in any case the result can be found many places, as it is a basic result about the Turing degrees.


Cross Compiler's T diagram I'm studying Bootstrapping from Red Dragon Book Compilers and found the T diagram for cross compiler pretty confusing. I can't understand what is meant by "Run compiler1 through compiler2". Can anyone provide some better explanation, analogy or an example to relate with some real world compiler?

Some notation first. By
$LSN=$
 I mean a compiler for language $L$
written in language $S$ that produces output language/machine code $N$.
This is a tombstone or T-diagrams.

  Compiling a Compiler

  Suppose we have cross-compiler for a new language L
     in implementation language S generating code for machine N.

  $LSN=$

  Suppose we also have an existing S compiler running on machine M
     implementing code for machine M:

  $SMM=$

  Run LSN through SMM to produce LMN

  Compiler Construction

  $LMN = LSN + SMM$

The T-diagrams (which you had omitted from the original version of your question) are crucial for understanding this sort of question. Let's look at the last T-diagram.

The first T describes a compiler from L to N written in S.

The second T describes a compiler from S to M written in M (or running on M). This will be your compiler compiler.

Applying the second T to the first T compiles the first T so that it runs on machine M. The result is thus a compiler from L to N running on machine M.

The fact that the second T also runs on machine M is captures that you are running the compiler compiler on the machine which you will run the compiler, rather than having to use a cross compiler (which would be the case if the bottom M were different).


Find the set of all edges which there is a cycle such that for every $e' \in C, e'\neq e$ : $w(e')\leq w(e)$ Given an undirected graph $G=(V,E)$ and weight function: $ w: E \rightarrow \{1,2,...,10\}$.
Describe an algorithm that finds the set of all edges $e\in E$ for which there is a cycle $C$ in $G$ that contains $e$ such that for every $e' \in C, e'\neq e$  :  $w(e')\leq w(e)$.

I thought maybe because the weights are bounded I can run Kruskal multiple times and each time delete edges with a specific weight, and that without changing the complexity.
Would appreciate your help:)

Suppose $E_{i}$ be the set of all edges that have weight $i$. Now, we want to check if any of these edges are part of the solution or not. Note that, we can simply delete all the edges from the graph of the weight strictly greater than $i$ since they should not come in a cycle containing $e \in E_{i}$. Let $G_{i}$ be the new graph after deletion of these edges. Now, we just have to solve the following new problem:
Updated Problem: Find all the edges in $E_{i}$ that form a cycle in $G_{i}$
Try solving this new problem on your own. In case, you need any help, check this link for the solution to this problem in $O(|V|+|E|)$ time.
Since there are only $10$ such graphs $G_{i}$. The overall time would remain $O(|E|+|V|)$.


Is Context Free Language closed under perfect shuffle? Note that this is not shuffle but perfect shuffle, defined as follows:

Let $w = a_{1}a_{2} \ldots a_{n}$ and $x = b_{1}b_{2} \ldots b_{n}$ be two strings of the same length. Then the perfect shuffle of $w$ and $x$ is defined as $a_{1}b_{1}a_{2}b_{2} \ldots a_{n}b_{n}$.

So the question is: are context free languages closed under perfect shuffle?

Nope. Shuffle $\{ a^n b^{2n} \mid n\ge1\}$ with  $\{ a^{2n} b^n \mid n\ge1\}$ .


Qubits Related to RAM? I read in this article that the amount of bits that can be emulated by a certain number of qubits is 2^(number of qubits). This is because each qubit can be in one of 2 states after it collapses, and so before all the quantum... whatevers collapse, that is the function that gets that result. At least, that was generally what it was saying, but I probably mangled the explanation myself; sorry.

Anyway, this relation (2^n) happens to be the same as the relation between memory registers and RAM in classical computers (i.e. if the computer has n bits in the register, it can have up to 2^n bytes in RAM). Is this important? Does it mean qubits will become like the memory registers and their states like the RAM when we switch to quantum computers? Or is it just something that seems important but is actually meaningless in practice?

By the way, there don't seem to be any tags for some things I referenced, like RAM & memory registers. Is that because the site is so new, or am I just not looking hard enough?

This coincidence just shows that the function $n \mapsto 2^n$ shows up in many places. For example, an $n$ bit register can store up to $2^n$ different values. If wireless frequency is parametrized using $n$ bits, then there are up to $2^n$ possible frequencies (in fact, there are probably a bit less). If an IP address is $n$ bits, then there are at most $2^n$ possible IP addresses (in fact, there are fewer). If a cryptographic key is $n$ bits long, then there are $2^n$ possible keys. And so on.


Trouble understanding how to create a grammar parse tree I'm starting an online Computer Science class called Advanced Programming Languages, and the book asks me to create a parse tree and generate a grammar from it.  Here are the exact instructions:

  To verify that a string of characters belongs to a language defined by a grammar, we must create a parse tree that shows that the string can be generated by the grammar.

<list> -> <item> , <list> | <item>
<item> -> <left> <item> <right> | <left> <right>
<left> -> A| B | C
<right> -> x | y | z

  Choose a string that is in this language and create a parse tree that demonstrates that your claim is true. Identify another string that contains some of these terminals symbols but is not in the language.

I think I know how to get started, but I keep getting confused by examples in the book and examples online.  Is there a general method to use when approaching this?

I began it this way:

            <list>
         /          \
      <item>      <list>
    /    |    \
<left> <item> <right>
  |    /
  A  <left>

But I get confused on the next iterations of the item.  Any hints?

Before expanding a grammar into a parse tree, we should first try to understand it at a higher level.

<list> -> <item> , <list> | <item>
<item> -> <left> <item> <right> | <left> <right>
<left> -> A| B | C
<right> -> x | y | z

First, <list> is a list of <item>, separated by commas if there are multiple ones.

Second, an item is either a pair of alphabets (the left is one of A | B | C; the right is one of x | y | z) or recursively, an item surrounded by such a pair.
Thus, an <item> is a word composed of, say $n$, upper-case alphabets from A | B | C, followed by the same number, $n$, of lower-case alphabets from x | y | z.

  $Q_1$: Choose a string that is in this language and create a parse tree that demonstrates that your claim is true.

ABCxyz,ACyz is in this language; can you generate a parse tree for it?

  $Q_2$: Identify another string that contains some of these terminals symbols but is not in the language.

AyCz is not in this language; can you explain why?

In addition, when you are searching for any string in a grammar by expanding the grammar into a parse tree, you can push the tree into its leaves as fast as you can, by choosing the non-recursive rules whenever possible.


Time complexity for balancing an unbalanced binary tree The question here is that: There is an unbalanced binary tree with n-nodes. What is the time complexity to balance the tree?

The solution I thought of involved solving using Recursion where for the worst-case I took a maximally unbalanced tree like this

And then try to balance this using rotations.

But I cannot come up with an expression which will give O(log(n)) time complexity.

Can I get some help in solving this?
I am stuck on how to approach this problem.

Do an inorder traversal of the BST...and store it in an array
the array will be sorted.
next construct a balanced binary search tree from this array.
1) Get the Middle of the array and make it root.
2) Recursively do same for left half and right half.
    a) Get the middle of left half and make it left child of the root
          created in step 1.
    b) Get the middle of right half and make it right child of the
          root created in step 1.

Time Complexity of both inorder traversal and AVL tree construction is O(n).