Differences in Postfix Syntax A question about postfix/RPN came up in my class due to the current ACSL competition. Is it a rule or convention that 4 + (5 * 6) in infix is written 4 5 6 * + in postfix, as opposed to 5 6 * 4 + in postfix? When the second postfix example is translated into infix, the order of the arguments is switched, but should that matter for operators with the commutative property?

There are no "rules", you make the rules yourself. The rule used in class has the property that the numbers appear in the same order in both expressions. The rule is also pretty natural:

$$ T(\alpha \circ \beta) = T(\alpha) T(\beta) \circ $$

Here $\alpha$ is an infix expression, $T(\alpha)$ is the translation of $\alpha$, and $\circ$ is a binary operation. The corresponding rule for unary expressions is $T(\circ \alpha) = T(\alpha) \circ$, and there is also a deparenthesizing rule, $T((\alpha)) = T(\alpha)$. If you apply these rules to the expression $4 + (5 * 6)$ you will get $4 \; 5 \; 6 * + $.

Keeping the order is important for operations which are not commutative, such as subtraction and division; that's assuming on the convention that $3 \; 2 \; - = 1$ and so on, rather than the other way around.


About the turing machine's non-deterministic branches I have three different cases of non-deterministic turing machine.
The first machine has:
Branch "accept" and branch "loop".
The second has:
Branch "rejecte" & branch "loop".
Third has:
Three branchs "rejecte" "loop" "accept".
The question is which machines will  rejecte and which ones will accept and which ones will enter a loop?
Thank you so much

I guess, with branches you mean the computation branches (the sequence of the konfigurations M has in its computation) of $M$. Then in general a NTM $M$ will accept an input x, if there exists one computation branch in the computation tree, which leads to accept x, no matter, where other branches may lead to (even if there infinite long). So, Machine 1 and 3 will accept.

I am definitely not sure about the following: I guess, the question, what Machine 2 will do is not decidable (please correct me, if I am wrong)


sorting with noisy but persistent answers Given a set of elements $A$ and a probability of noise $p<0.5$. For any two elements $x,y\in A$ we can ask the oracle $O$ to know where $x$ stands w.r.t $y$ (0 means $x$ is smaller than $y$ and 1 means the other way).

The oracle answers correctly with probability $1-p$. The noise is random and independent but persistent in a sense that if the oracle answers incorrectly for one pair $(x,y)$ it will give the same answer if questioned on the same pair again.

Is there any known strategy to sort $A$ with high probability?

For constant $p>0$ there is no way to exactly sort $A$ with high probability. Think, e.g., of the first two elements: they will seem to be in the wrong order with probability $p$ and no other comparison provides any information on their order.

In fact, if an algorithm returns a permutation of $A$ that has maximum dislocation1 $D$ with high probability, then $D = \Omega(\log |A|)$.

The algorithm in the paper by Braverman and Mossel suggested by Yuval returns a permutation with maximum dislocation $O(\log |A|)$ and, in particular, returns the maximum-likelihood permutation. However, its running time can be quite large.

The following papers have improved the time complexity (in chronological order) for the problem of sorting with (asymptotically) optimal $O(\log |A|)$ maximum dislocation. Here the returned permutation does not need to be the maximum-likelihood one and $p$ needs to be smaller than some constant ($1/32$, $1/20$, or $1/16$):

Tolerant algorithms: Lowers the complexity to $O(|A|^2)$.
Sorting with recurrent comparison errors Lowers the complexity to $O(|A|^2)$. The returned permutation also has $O(|A|)$ total dislocation in expectation. This is probably the easiest algorithm to implement.
Optimal Dislocation with Persistent Errors in Subquadratic Time Same dislocation bounds as the above paper but in $\tilde{O}(|A|^{3/2})$ time.
Optimal Sorting with Persistent Comparison Errors. Lowers the complexity to $O(|A| \log |A|)$. The returned permutation has $O(|A|)$ total dislocation, w.h.p.

1 The dislocation of an element in a permutation is the absolute difference between its position and its rank (position in the sorted sequence).


Hard disk scheduling - N-set-SCAN vs FSCAN I'm wondering which is a better scheduling algorithm to use. The only real difference I can see is that in FSCAN there are two queues, and when a scan begins all requests are put in one queue and the other left empty. Then during the scan the other queue is used to store new requests and deferred until all the old requests have been processed.

If you take a peek at how real operating systems do it, the answer is that they use algorithms that are orders of magnitude more complex than either.

If I told you the dirty secret behind operating systems (and compiler, and...) text books, I'd have to kill you afterwards.

  Text books only show you the parts where there is some hints of order (some theory behind the algorithms). Most of an operating system's code is battling unruly hardware, work around device bugs, get some half-decent answer out of woefully inadequate data, and do all that fast. Many algorithms are heuristics, derived by trying many ideas, keeping and refining those that worked best. For compilers, the authors of the book describing lcc say that the contents of most compiler books was around 5% of the code of the compiler, and the bug rate in that negligible. I'd say operating systems aren't much different.


Show Recognizing two Regular Expressions as equal is in PSPACE If I have $EQ_{REX} = \{\langle R,S \rangle|\text{ $R$ and $S$ are equivalent regular expressions}\}$, how do I show that $EQ_{REX}\in PSPACE$ ?

What I know so far is that there are decidable algorithms for transforming a regular expression into a NFA and then into a DFA, but these algorithms can take a long time and produce a DFA that takes up exponential space. I also know that $EQ_{DFA}$ is decidable.

So $EQ_{REX}$ is provably decidable because you can turn R and S into DFAs and then show that the DFAs are equivalent. But I'm not sure how to analyze the complexity of a machine like this, and something tells me that it is not in NP.

Is there a way to show that this particular machine is in PSPACE (or NPSPACE, because they are equivalent)? How would I analyze its complexity? Or am I taking the wrong approach entirely, and should instead try to show that this problem is reducible to some other PSPACE-complete problem?

Hint: One obvious algorithm for this problems goes as follows. Given two regular expressions $R,S$, convert them to NFAs $N_R,N_S$ and then to DFAs $D_R,D_S$. Using the product construction, construct a DFA for $D_R \Delta D_S$ (here $A \Delta B$ is the symmetric difference), and check whether the language it accepts is empty.

While this algorithm doesn't quite use polynomial space (why?), you can follow the same general plan to solve your problem. It might be helpful to use NPSPACE=PSPACE or perhaps coNPSPACE=PSPACE.

Here is a complete answer. Let $R,S$ be two regular expressions. The idea is that if $L(R) \neq L(S)$ then there is a word in $L(R) \Delta L(S)$ whose length is at most exponential in $|R| + |S|$ (where $|R|$ is the length of $R$). This puts your problem in coNPSPACE=PSPACE, since you can guess and verify such a word.

Indeed, once you convert $R$ and $S$ to (polynomial size) NFAs, you can keep track of the set of possible states in both NFAs, and so verify that a word is accepted by one or not the other. You also need your machine to terminate if it guessed wrong, so you need to limit the length of the word to exponential in $|R| + |S|$. Fortunately, counting up to $\exp(|R|+|S|)$ takes only a polynomial size counter.

It remains to show that if $L(R) \neq L(S)$ then there is an exponential size witness. Indeed, the DFA for $L(R) \Delta L(S)$ has exponential size: the DFAs for $L(R)$ and $L(S)$, constructed from the corresponding NFAs, have exponential size, and the product construction maintains this property for $L(R) \Delta L(S)$. Finally, it is known that if a DFA with $n$ steps accepts some word, then it accepts some word of length less than $n$.


checking configuration history of Turing machine using PDA I am trying to understand the technique of using configuration history in proofs.
To prove that:
$\{<M>|M\,\,\,is\,\,\,a\,\,\,TM\,\,\,and\,\,\,L(M)=\sum^* \}\notin RE$
given $<M,w>$ we have built a Turing machine that accepts all words except M accepting configuration on w. (and then simple reduction)
To prove that:
$\{<P>|P is\,\,\, a\,\,\, PDA\,\,\, and\,\,\, L(P)=\sum^*\}\notin RE$
we showed the same proof, only that we built a PDA that accepts all the words except the accepting configuration of M on w.
Does PDA's ability to determine whether input is an accepting configuration of M on w actually means that I can simulate M's run on w with a PDA? Or testing whether configuration is an accepting configuration is different from a simulation

PDAs are strictly weaker than TMs. For instance, PDAs always halt after precisely $|w|$ steps, but there are algorithms (aka TM) for questions that take more steps than that.
sorting an array for example, would take definitely more than $\Omega(|w|log(|w|))$ which is larger than $|w|$ at some point.
It cannot simulate running a machine on a word as it simply takes more time! Checking configuration history takes less time because it's length is proportional to the running time of $M$ on $w$.


Chomsky form for language of single alphabet member I'm a bit confused as to how to represent the Chomsky form for the language L that generates all strings with the alphabet {a}

My approach was

S -> AB | e
A -> a

Now here's the part I'm confused, how do I represent B? If B -> a then I get only even strings, if B -> e then it's not in normal form. :| Any help would be appreciated.

The grammar is similar to what you say:
$$
S \rightarrow S S \mid a
$$
This can't generate $\epsilon$, which any true CFG can't.


Difference between Computing Architecture and Platform in Computer Science I was looking for an appropriate term to call my proposal. I knew it is either platform or architecture. But could not simply and clearly distinguish them in an academic manner. So, I searched the web and the literature and found few definitions on architecture and platform as follows that sound logical.

Software Architecture: A set of system elements and relations associated with them [reference: documenting software architecture: views and beyond]
Platform: A set of subsystems and technologies providing a coherent set of functionalities through interfaces and specified usage pattern that any subsystem that depends on the platform can use without concern of the detail of how the functionality provided by the platform is implemented1.

However, still is it not clear what are the differences. I guess researchers often use these two terms interchangeably with marginal consideration on their differentiations. Looking at the definitions, I figured out that architecture likely specifies structural properties of systems and usually tries to describe the structure of a system and its consisting components and their relationship. Using architecture, developers cannot produce a system that works according to that architecture. However, platform is trying to specify structural and behavioural attribute of a system by describing its subsystems and their relationship. Platform also provides an abstract by which developers can create new software systems that rely upon the platform.
Is this interpretation accurate enough? One may argue that platform is prepared on top of an architecture and without architecture one may not be able to propose platform.
In your idea, what else are the differences and distinguishing lines between these two terms?

Architecture generally refers to a design-level structure or organization for an entire system.

Platform generally refers to something (an operating system, a library, a programming language, a programming environment) which you can build other things on.


why is the NL solution PATH negated unsufficient to prove unreachability I'm currently reading into complexity classes and one think will not fit into my head.
We are investigating NLogSpace with the Path/reachability problem.
There is a nondeterministic LogSpace algorithm which can solve reachability, but its inversion does not prove nonreachability because "it could miss a path". How is it possible to miss a path? Wouldn't it imply that the reachability test might doesn't work?
Can somebody please explain it to me? Thank you.

maybe i was a bit to specific, i had a general misunderstanding in how non-deterministic machines work. Here is what i figured:

an accepting nondeterministic turing machine always gives the right answer ("found something, therefore a solution exists",
on the other hand, a reject means "did not find anything" which is not the same as "there is no solution"

therefore a reject can't be trusted and any algorithm which uses a reject from a non deterministic (Existance) machine has to double check. Also this implies, that a non-deterministic machine could give a false negative.


Extension of Rice's theorem How can one prove that every nontrivial property of pairs of
semi-decidable sets is undecidable? (This is an extension of Rice's theorem that "Every nontrivial property of the r.e. sets is undecidable")

Let $C$ be the collection of all c.e. sets.
One way to understand Rice's theorem is to say that every computable map $f : C \to \mathsf{bool}$ which preserves equality of sets is constant. (By "respects equality of sets" we mean that $f$ actually accepts codes of c.e. sets, but it maps any two codes for the same set to equal values).

Let's answer your question. Suppose we have a computable map $g : C \times C \to \mathsf{bool}$ which respects equality of sets. We want to prove it is constant. Then for every $y \in C$, the map $x \mapsto g(x,y)$ is constant by Rice's theorem. Likewise, for every $x \in C$, the map $y \mapsto g(x,y)$ is constant by Rice's theorem. But a map $g$ which is constant in each argument separately is constant.


Is it possible to turn an eulerian NFA into a linear size DFA? In general, there exists NFAs of size n whose smallest equivalent DFA requires 2^n states.

But if we restrict ourselves to NFAs whose graph is eulerian, is it possible to turn any such NFA of size n into a DFA of size at most O(n) ?

If so, does it hold also for a NFAs whose graph is strongly connected ?

I would appreciate some counter example, proof or any reference to research papers dealing with this problem.

Many thanks, Luz

I don't think so.

Suppose you could. Then you can also do this:

Take any NFA $\mathcal A$ with alphabet $\Sigma$, states $Q$, transitions $\Delta$, initial states $I$ and final / acception states $F$.
Add transitions to make the graph eulerian in the following way. Take any enumeration of the transition $p_i\overset{a_i}{\to}q_i$. For each $i$, add a transition $q_i\overset{b_i}{\to}p_{i+1}$ where $b_i$ is a new letter (and the indices are modulo the number of transitions). Note that you add $|\Delta|$ letters and transitions so this transformation is linear.
Add transitions to make the graph strongly connected in the following way. Take any enumeration of the states $s_j$. Add a new letter $c$. For each $j$, add a transition $s_i\overset{c}{\to}s_{i+1}$. In other words, add a Hamiltonian cycle using only the new letter $c$. Note that this transformation adds $1$ letter and $|Q|$ transitions so it's linear.
Use your magic procedure to build a new deterministic automaton $\mathcal B'$ so that it recognizes the same language as $\mathcal A'$ (the modified automaton) and $|\mathcal B'|=O(|\mathcal A|)$.
Remove added letters ($b_i$ for each $i$ and $c$) and all transitions using them. Call the new automaton $\mathcal B$.

Since $\mathcal L (\mathcal A) = \mathcal L (\mathcal A')\cap \Sigma^* $ (because if you don't use the new letters, then you're taking a path that already existed), and similarly $\mathcal L (\mathcal B) = \mathcal L (\mathcal B')\cap \Sigma^* $, we have $\mathcal L (\mathcal A) = \mathcal L (\mathcal A')\cap \Sigma^*=\mathcal L (\mathcal B')\cap \Sigma^*=\mathcal L (\mathcal B)$ with $\mathcal B$ a DFA so that $|\mathcal B|=O(|\mathcal A|)$.

But this can not be because of the usual counterexample where the size of the corresponding DFA is of exponential size. To get an explicit counterexample, you can apply the procedure to that counterexample.


Why doesn't A* give the optimal path for navigating from A to R in this state space? Well, I have heard that the A* algorithm is optimal and complete. However, when trying to navigate from A to R using A*, it outputs the path, A --> E --> R, although there is a shorter path, A --> M --> R. My question is, is that possible for A* to be not optimal sometimes? if not, what am I doing wrong here? Any helpful advice is highly appreciated.

The question: In the following diagram, A is the start node and R is the goal node. Arcs are labeled with the value of the cost function; the number gives the cost of traversing the arc. Heuristic function value for each node is given within brackets. Using A*, find the route from A to R.

This is what I tried. But what I'm getting is not the optimal path.

For A* to be optimal, the heuristic needs to be admissible (and this example shows why). This heuristic is not admissible because the heuristic value at M is 40, while the shortest path from M to R has length 30.


Determine if an NFA accepts infinite language in polynomial time Question Statement: Given a NFA $N$, design an algorithm that runs in polynomial time such that it determines if $L(N)$ is infinite.
(Note that converting NFA to DFA is exponential time).

For any DFA, By pumping lemma, I am very sure that the following algorithm works:

T = Upon input <M> (a DFA)
  Accept if any state q in DFA has the property:
    1. There is a path from starting state to some final state through q
    2. There is a (directed) cycle that loops from q back to q.
  (Reject if neither property is satisfied)

I intend to prove that this algorithm can be directly applied to NFA. After all, if there is no loop in this NFA, then every accepted string is bounded by the number of states (by pumping lemma). Therefore to make sure the NFA accepts infinite language, a loop is necessary.

Is the thinking correct? Further, what would be the optimal algorithm to see if an NFA generates infinite language?

Your algorithm is incorrect.  Think about the minimal DFA for $ab^*c$.

Related: Do self-loops in DFA cause infinite languages?, Do all DFA's containing an "accepting path containing a cycle" accept infinite languages?.


CLRS - Maxflow Augmented Flow Lemma 26.1 - don't understand use of def. in proof In Cormen et. al., Introduction to Algorithms (3rd ed.), I don't get a line in the proof of Lemma 26.1  which states that the augmented flow $f\uparrow f'$ is a flow in $G$ and is s.t. $|f\uparrow f'| =|f|+|f'|$ (this is pp. 717-718).

My confusion: When arguing flow-conservation they use the definition of $f\uparrow f'$ in the first line to say that for each $u\in V\setminus\{s,t\}$

$$ \sum_{v\in V} (f\uparrow f')(u,v) = \sum_{v\in V} (f(u,v)+f'(u,v) - f'(v,u)), $$

where the augmented path is defined as

$$ (f\uparrow f')(u,v) = \begin{cases} f(u,v)+f'(u,v) - f'(v,u) & \text{if $(u,v)\in E$}, \\
0 & \text{otherwise}. \end{cases} $$

Why can they ignore the 'otherwise' clause in the summation? I don't think the first clause evaluates to zero in all such cases. Do they use flow-conservation of $f$ and $f'$ in some way?

Note: The notations and definitions used below are borrowed from the third edition of the book.

To answer this question, first, observe that if $(u,v) \notin E$, then by flow definition,

$$f(u,v) = f'(u,v) = (f \uparrow f')(u,v) = 0 \, .$$

Furthermore, since $f'(v,u) \le c_f(u,v) = f(u,v)$, it is obtained that $f'(v,u) = 0$. This simply implies that $\forall (u,v) \notin E$,

$$(f \uparrow f')(u,v) = f(u,v) + f'(u,v) - f'(v,u) = 0 \, .$$

Therefore, the definition of augmented flow can be generalized for all $(u,v) \in V \times V$ to be as follows:

$$ (f \uparrow f')(u,v) = f(u,v) + f'(u,v) - f'(v,u) \, .$$

The rest of the proof follows from this observation which, of course, is not explicitly explained in the text.

P.S. Please note that the formal definition of flow in the third edition of the book is significantly different from that in the second edition. In particular, in the second edition, there is a flow property named skew symmetry that requires $f(u,v) = - f(v,u), \forall u,v \in V$. This property has been removed in the third edition due to the assumptions that $(v,u) \notin E$ if $(u,v) \in E$ and $f(v,u) = 0$ if $(v,u) \notin E$. Because of this, the definitions of flow conservation in two editions are also different. Lots of such confusions, in fact, come from this change of definition that is presumably intended to simplify the proofs, but turned out being more perplexing. I personally would rather to stick to the second edition of the book for this particular chapter.


Assumptions of One Way Functions I try to get the intuition behind the notion of strong one way function and weak one way function by reading the scribe One-Way Functions. Particularly, I am interested in examples and definitions of the weak and strong one way function. I known it's very broad notion, therefore I will be as specific as possible in my questions.

Strong one way function. $\forall$ nonuniform PPT $A$, $\exists \epsilon s.t. \forall n \in N, Pr_{x\in\{0,1\}^n}[A(1^n, f(x)) \in f^{-1}(f(x))] \leq \epsilon(n)$

  Q:$1^n$ as the first parameter of the PPT $A$ represent the length of the initial input, the usage of it is justified as "this ensures that the output of A doesn't shrink the size if its too must as in the f(x)=|x| example". Unfortunately I didn't get the previous explanation (may be because the lost the sign, which takes an additional bit). In my opinion putting in A the size of $x$ might help $A$ get the right output $x$.

  Q: in the lecture it mentioned that $f(x)=|x|$ is hard, "because it will take $2^c$ time to write a valid inverse of something such that $f(x)=c$". It happens because we cannot find $x$ with probability with negligible more than 0.5,  but it's due to another problem not a computational but rather information theory problem, by running the function we lost the information about the sign of the input $x$, if it's a correct reasoning, why actually it would take $2^c$ time?  In addition for  me it looks like the great discover to find the strong one way function, however do have more assumption of hard function like $f(x)=|x|$?

Definition of weak one way function.$\exists$ $q(x)$, $\forall$ nonunoform PPT A, $\forall$ n $\in$ N,
$Pr_{x \in \{0,1\}^n}[A(1^n,f(x)) \in f^{-1}(f(x))] \leq 1-\frac{1}{q(n)}$

  Q: in the lecture there was an assumption that the multiplication is weak one function, how we can actually show that the multiplication is weak one way function, and do we have more assumptions of examples of weak one way functions?

I am very sorry for being naive, even though I will appreciate any help.

As for your first question, the reason behind adding $1^n$ as an input to $A$ is to allow it a running time of (at least) a polynomial in $n$. In most applications of one-way functions, $n$ is not a secret, so there is no reason to hide it; in fact, for most functions you can determine $n$ from the output size.

To see what fails if we leave $1^n$ out, consider the situation in the second question. You're misreading the notation - $|x|$ is the length of the string $x$. If $x$ is $n$ bits long then $|x|$ is $O(\log n)$ bits long, and so no machine can find a preimage in time polynomial in $|x|$. However, it is easy to find a preimage in time polynomial in $n$. Add ing$1^n$ as a parameter to the adversary $A$ ensures that $|x|$ is not considered a hard function.

Finally, one-way functions, weak or strong, are not known to exist, even assuming P$\neq$NP. This is similar to the situation in computational complexity, where no worst-case hard functions are known. However, some functions are conjectured to be one-way - ask your professor for their favorite ones.


defining a programming language grammar for doing arithmetic I'm studying programming language design, and I've been taught the grammar below which lets you write basic math expressions.

Exp ::= Num | Exp Op Exp
Op ::= + | - | * | Div
Num ::= Digit | Digit Num
Digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

According to the lecturer things like 1 - (2 -3) are not valid as it can't generate expressions with brackets and it can't do -1 because it can't start with -1.

While I understand the first one, the second is a little harder to understand.

Also could you show me how I could modify the above grammar to add the ability to group operations, and start with a -1?

Finally, I'm told that a grammar is a set of symbols, rules, and an initial symbol? But I'm struggling to find more info on what an initial symbol is/should be.

With Num you can only generate digits, so the only choice left is (starting with Exp) to produce Exp Op Exp. However, Exp and Op must both produce at least one symbol each (i.e., producing the empty word is not allowed). Hence, even if you replace Op with -, you get Exp - 1 and Exp must produce another valid expression (or number), so you cannot get -1 on its own.

  Also could you show me how I could modify the above grammar to add the ability to group operations, and start with a -1?

There are several ways of doing so. Check out, for instance, how Java does it (the "Expression3" there is roughly equivalent to your Exp).

  Finally, I'm told that a grammar is a set of symbols, rules, and an initial symbol? But I'm struggling to find more info on what an initial symbol is/should be.

The initial symbol is an arbitrary non-terminal symbol. Read more here on what terminal and non-terminal symbols are.


Give a $3$-state DFA for $(01 \cup 1)^∗$ How do I change the design to accept the given language, because I think my DFA can accept $001$ as well. Is that correct?

It is correct that your DFA accepts 001, which is wrong.

Here is a strong hint. The three sets of strings accepted by the states should be the set of accepted strings, the set of accepted strings with one "0" attached at the end, the set of the strings that contains two consecutive "0"s. (From that description, you can see how to construct simple DFA by the Myhill–Nerode relation.)

In case the above hint does not ring a bell, here is the full answer, which you can reveal by hovering your mouse over it.

   Let state $S_1$ be the set of all strings having no consecutive "0"s and ending in "1". Let state $S_0$ be the set of all strings having no consecutive "0"s and ending in "0". Let state $S_{00}$ be the set of all strings having two consecutive "0"s. $S_1$ is the start state and the accepted state. Here are the transitions.

 $\quad(S_1, 0)\mapsto S_0$
 $\quad(S_1, 1)\mapsto S_1$
 $\quad(S_0, 0)\mapsto S_{00}$
 $\quad(S_0, 1)\mapsto S_1$
 $\quad(S_{00}, 0)\mapsto S_{00}$
 $\quad(S_{00}, 1)\mapsto S_{00}$

 It should be easy to see that the above DFA accepts the given set of strings, $(01\cup 1)^*$.


MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard? What is the complexity of $\text{MIN-2-XOR-SAT}$ and $\text{MAX-2-XOR-SAT}$?  Are they in P?  Are they NP-hard?

To formalize this more precisely, let

$$\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{n}C_i,$$

where $\mathbf{x} = (x_1,\dots,x_m)$ and each clause $C_i$ is of the form $(x_i \oplus x_j)$ or $(x_i \oplus \neg x_j)$.

The $\text{2-XOR-SAT}$ problem is to find an assignment to $\mathbf{x}$ that satisfies $\Phi$.  This problem is in $P$, as it corresponds to a system of linear equations mod $2$.

The $\text{MAX-2-XOR-SAT}$ problem is to find an assignment to $\mathbf{x}$ that maximizes the number of clauses that are satisfied.  The $\text{MIN-2-XOR-SAT}$ problem is to find an assignment to $\mathbf{x}$ that minimizes the number of clauses that are satisfied.  What are the complexities of these problems?

Inspired by Is MIN or MAX-True-2-XOR-SAT NP-hard?

Sorry for answering an old post
The problem of determining if a MONOTONE-2-XOR-SAT (all clauses are of the kind $({x_i}\oplus x_j)$)  instance is satisfiable can be reduced to the problem of determining if a graph is bipartite, see this.
To do that we create a graph $G$ with a node for each literal of the formula and we connect each literal with another if they are in the same clause (edges are clauses)
For instance:
If we have an unsatisfiable formula that is $({x_1}\oplus x_2) \wedge ({x_1}\oplus x_3) \wedge({x_2}\oplus x_3) \wedge ({x_1}\oplus x_4) $
We have a graph like this:

that is not bipartite
There are three clauses that are satisfiable and so we have just to eliminate an edge
Now, we can reduce the problem of determining if we can find a maximum bipartite subgraph with $k$ vertex  to the problem of determining if we can satisfy $k$ clauses in a MONOTONE-MAX-2XOR-SAT formula, see this. And the maximum bipartite subgraph problem is equivalent to max cut
To do the reduction we simply create a new literal for each vertex and we create a clause for each edge connecting two literals
For instance:
We have this graph,

We create the follwing formula $({x_1}\oplus x_2) \wedge ({x_1}\oplus x_4) \wedge({x_2}\oplus x_4) \wedge ({x_2}\oplus x_3) \wedge ({x_4}\oplus x_5) \wedge ({x_3}\oplus x_5) $
So, if we can find an assignment that satisfies $k$ clauses that will mean that there is a bipartite subgraph with at least $k$ edges.


Proof that locality is sufficient in showing two graphs are isomorphic Using the graph representation with (node, [list of neighbours]), to show that two graphs are isomorphic it is sufficient to:

show that the vertices have the same degree and
for every pair of vertices with the same degree, the degrees of the nodes in their adjacency list must be the same.

The last point was a bit ambiguous, in the sense that in two graphs many vertices could have the same degree, but between two isomorphic graphs their is a bijective function (an exact one to one mapping) between them such that their adjacency list maps correctly.

My question is what's the proof behind this? Why is this sufficient? For me, this is not clear at all, because this is, overall, a local property and I can't understand how this generalizes to the whole graph.

If it's easier to track what I said on code...Prolog it's pretty verbose at this part.

:- dynamic p/2.
graph1([n(1,[2,3,4]),n(2,[1,3]),n(3,[1,2,4]),n(4,[1,3])]).
graph2([n(a,[b,d]),n(b,[a,d,c]),n(c,[d,b]),n(d,[a,b,c])]).
eq_perm([H1|T1],L2,EQ):-
    delete(H2,L2,T2), % we generate a solution here
    P = ..[EQ, H1, H2],
    P,
    eq_perm(T1,T2,EQ).
eq_node(N1,N2):-
    p(N1,N2).
eq_node(N1,_):-
    p(N1,_), !, fail.
eq_node(_,N2):-
    p(_,N2), !, fail.
eq_node(N1,N2):-
    asserta(p(N1,N2)).
eq_node(N1,N2):-
    retract(p(N1,N2)).
iso_graph(G1,G2):-
    eq_perm(G1,G2,eq_neighb).
eq_neighb(n(N1,L1),n(N2,L2)):-
    eq_node(N1,N2),
    eq_perm(L1,L2,eq_node).

This method fails on regular graphs. For example, it fails on the following two graphs: the hexagon, and two disconnected triangles.

More generally, if you continue to explore neighbors' neighbors and so on, you get the 1-dimensional Weisfeiler–Lehman method. If you start with $k$-tuples of vertices, you get the $k$-dimensional Weisfeiler–Lehman method. Cai, Fürer and Immerman proved in An optimal lower bound on the number of variables for graph identification that there exist non-isomorphic graphs on $n$ vertices which fail to be distinguished by the $k$-dimensional Weisfeiler–Lehman method unless $k = \Omega(n)$. Since the running time of the method in the worst case is asymptotically $n^{k+1}$, this shows that the Weisfeiler–Lehman method doesn't yield a subexponential time algorithm for graph isomorphism.

For more on the Weisfeiler–Lehman method, check a paper of Douglas, or the recent work of Neuen and Schweitzer.


2-Approximation algorithm for for messages across a cyclic network Question
There are $n$ computers arranged in a cycle ($1,2,3..,n,1$), with undirected edges between adjacent computers. There are $m$ messages that need to be delivered. Message $i$ ($1 \le i \le m$) has to be sent from computer $s_i$ to computer $t_i$. There are two ways to deliver a message $i$: clockwise from $s_i$ to $t_i$ or anti-clockwise from $s_i$ to $t_i$. Aim is to send all messages in such a way that the number of messages going through the most frequently used edge is minimized. We need to devise a $2$-Approximation algorithm for the same.
Example
Let $n=4$. Let $m=2$. And let $s_1=1,t_1=4$ and $s_2=2,t_2=3$. Then if we send message $1$ in the following way: $1 \to 2 \to 3 \to 4$ and message $2$ as: $2 \to 3$. The most frequently edge used is $2 \to 3$, through which $2$ messages go. We can do better than this.
Message $1$:  $1 \to 4$ and delivery of message $2$ remains same $2 \to 3$. Then both the edges are most frequently used. But only $1$ message goes through most frequently used edges.
My approach 1
For every message with probability $\frac{1}{2}$ send it in clockwise direction and with $\frac{1}{2}$ in anti-clockwise direction.
But this gives a bad performance, which can be seen with the help of the following example:
$n=10000$, $m=200$ and $s_i = i,t_i=i+1$ for $1 \le i \le 200$. Then the optimal answer is $1$ (ie. every edge has at most $1$ message going through it). Which can be achieved by sending message $i$ as $i \to (i+1)$.
Also this is the only way to achieve the optimal. If anyone of the messages were sent in the other direction the answer increases. For eg. if $x$ of the $200$ messages were sent in other direction, all these $x$ would use say edge $800 \to 801$. So the answer would be at least $x$. Thus in this case the random solution picks the optimal arrangement with only probability $\frac{1}{2^{200}}$, which is very less and for other arrangements answer gets bigger.
My approach 2
I turned towards greedy. Where for message $i$ we send it in the direction where it will travel through lesser number of edges, ie. we send it along the shorter route. Then I argued as below
(I consider $n$ odd for now, and also don't consider some other corner cases)
For an arbitrary input $n$, $m$ (and the respective source and sinks) let the optimal be $p$ (that is $p$ is the number of messages going through the most frequent used edge), then the optimal arrangement cannot have more than $2p$ messages for which longer routes were chosen. Reason: longer routes have at least $\frac{n+1}{2}$ contiguous edges, for example for $n=7$, if I list all thecontiguous subsets of size $\frac{n+1}{2}$ (the possibilities of longer route)
$$
1,2,3,4 \\
3,4,5,6 \\
4,5,6,7 \\
6,7,1,2 \\
7,1,2,3 \\
$$
and lets say $p=1$. Then as first two subsets (nearly the half) have a common element $4$, and so do the last three subsets (again nearly the half) have common element $7$ (this is true for arbitrary odd $n$).
There can be a case where (in the optimal arrangement) $p$ of the longer routes lie in first half of subsets and another $p$ of longer routes in the second half of subsets. But if more than $2p$ are there. There would be at least $p+1$ in a single half of subsets, making the answer $p+1$ which is a contradiction.
And as changing direction of a message can at worst increase the answer by $1$. The greedy should have answer $\le 3p$ (change all $2p$ longer routes to short, to get to what greedy outputs).
But I seem to be stuck beyond this. As this gives approximation factor of $3$ (I did not consider $n$ is even case, as I think if odd case is handled it will be just about the corner case of source and sink being at exactly $\frac{n}{2}$ distance).
Maybe in my reasoning I overestimated somewhere.
I had also tried tried to obtain bounds using weak duality by expressing problem as LP relaxation. Assuming my working was correct what I could get is $1\le$ optimal. Which is trivially true.
PS: I would highly appreciate hints only.

Start with an integer program for your problem.
For each $i$, there is a variable $x_i \in \{0,1\}$ which represents which way the $i$'th message is routed. You can express the number of messages going through an edge $e$ as some linear combination $y_e$ of the $x_i$'s. Your goal is to minimize $\max(y_e)$. Equivalently, you want to minimize $m$ under the constraints $m \geq y_e$.
Now consider the LP relaxation. Determine which way to route the $i$'th message by rounding $x_i$.


Does there exist a problem that is hard to do in parallel? I am looking for a workload which is hard to paralellise/distribute between multiple machines.

For example, integer factorization does not go 10 times faster if you have 10 machines to split the load, but is there a better example?

Linear programming is P-complete with respect to either logspace or NC reductions (I'm not sure which).  As such, it's unlikely to be efficiently parallelizable because, for either kind of reductions, that would imply that P$\,=\,$NC. It's generally believed that P$\,\neq\,$NC.

There's more information on Wikipedia's P-completeness page.


Banker's Algorithm and deadlocks So we have the following table of processes , where A, B and $\Gamma$ are the resources.

Here is a pic that i drew with the processes and the resources.

So the exact question is this: Using banker's algorithm, calculate the minimum values of $x$ and $y$ in order the system is Deadlock free.

I have done pretty much huge paper work and found that $x,y$ should be the numbers 2 and 3. But in order to find this I run the algorithm on paper several times ; for $[x,y] = [0,0],[0,1],[1,0],[1,1],[1,2]$ etc. until I found that for pair $[x=2, y=3]$ the system is deadlock free!

So, I think that I am missing the point. All this took me like 1 hour or so. Is there a simple method with less paperwork?

Thanks a lot in advance!

A "shortcut" to the solution; first calculate the NEEDED = MAX - ALLOCATEDresources:

    ALLOCATED MAX      NEEDED
    A B C     A B C    A B C
P1  0 1 0     7 5 3    7 4 3
P2  2 0 0     3 2 2    1 2 2
P3  3 0 2     9 0 2    6 0 0
P4  2 1 1     2 2 2    0 1 1
P5  0 0 2     4 3 3    4 3 1

AVAILABLE: x y 2

In order to complete P1 we need 4 Bs. But if you observe the column B of ALLOCATED, we see that we can only gain a single B if P4 is executed before P1. So whatever the execution order is, we need more than 3 new Bs (y >= 3).

Furthermore in order to complete P3 we need 6 As, but if you look at column A of ALLOCATED, we see that we can only gain 4 Bs if P2 and P4 are executed before P3. So whatever the execution order is, we need more than 2 new As (x >= 2).

So we have:

AVAILABLE: 2+x' 3+y' 2

and we can start completing processes that need less than (2 3 2) (P4 and P2)

P4: (2 3 2) - (0 1 1) + (2 2 2) = (4 4 3)
P2: (4 4 3) - (1 2 2) + (3 2 2) = (6 4 3)
now also P3 can be completed:
P3: (6 4 3) - (6 0 0) + (9 0 2) = (9 4 5) which are enough resources for
both P1 and P5

So the state is safe even with x'=0 and y'=0 and the solution is x=2, y=3


DFA & RE from descriptive definition of given regular language I am trying to make the DFA and RE of a regular language which is define on the alphabet = {1,0} and all the strings present in these languages have exactly one 010 substring in them.

Some strings which are accepted by the above regular language are;

{010, 0100, 0101, 1010, 0010 .......0101110.....}

In the above strings there is only one 010 substring. If there is more than one 010 substring in a string such as.

{01010, 01011010... }

then the DFA of the above language should not accept that string.

If someone provide me ony DFA of the above lang. then i would be able to make the RE by state elimination. Or if someone provide me the RE of the above lang. then i could make the DFA by other kleene theorem.

My work: I made the following DFA for that language;

This DFA is accepting all the strings like 010, 0100, 0101, 1010, 0010.... and its also rejecting the string with more than 010 like 01010. But with that its rejecting 0101110 string which is part of the language.

Note: I go through the question which is already on the CS stackexchange as previously my question was marked duplicate. This question is about "How we can prove that a given language is regular or not". But in my question i have provided the descriptive definition of a regular language. And i am trying to get its RE or DFA.

You can always use the current state of the automaton to remember the last three characters you've seen.  Now, you can implement two phases.  In the first phase, you're happy if you're ever in the situation where the last three characters were $010$.  In the second phase, you become unhappy if you ever see $010$ again.


Adding two numbers in base 2(floating point) vs Multiplying two numbers in base 2(floating point) Is it true that adding two numbers in base 2 is more complex than multiplying them? If so can someone please explain why this is the case?

Floating point numbers are stored as $x \cdot 2^e$, where typically $1 \leq x < 2$ (unless your number is denormalized). When multiplying $x \cdot 2^e$ and $y \cdot 2^f$, we simply compute $xy \cdot 2^{e+f}$ (we have to truncate $xy$). When adding $x \cdot 2^e$ and $y \cdot 2^f$, we first have to shift one of the numbers (the one with smaller exponent) so that we have a "common denominator". For example, to add $1 \cdot 2^0$ and $1 \cdot 2^{-3}$, you have to rewrite the latter as $0.125 \cdot 2^0$.
Whether this makes addition more complex than multiplication is a matter of opinion. Multiplying $x$ and $y$ is still harder than addition.


Max-Heap PriorityQueue to keep the k highest items and return them in descending order I have created a custom implementation for PriorityQueue using max-heap and everything works fine.
But now i want to change it and keep only the k highest objects in the heap after every insertion. I have to use only one instance of my PriorityQueue and no other helping data structure.
So my problem is how should i know if the object that I want to insert is "better" than the "worst" in the priority queue. It's max-heap implemention so the get(first) returns the "best" object and the get(last) it is not the "worst" necessarily.
I need to keep the complexity of insertion at O(nlogn).
Any idea?

If what you want is to keep the top $k$ items at all times what you need is a min-heap, not a max-heap. After every insert you should check if the length is longer than $k$, and if yes, pop.
If you use numbers as your priorities you can turn a max-heap into a min-heap by simply negating the priority.


3-Approximation for General position subset I am currently studying for an exam and stumbled upon the following task:
Given the following problem:

Input A set of points $P \subseteq \mathcal{Q}^2$ and $k \in \mathbb{N}$

Question Find the maximum subset $S \subseteq P$ such that no three points in $S$ are collinear.

The task is to find a polynomial time 3-approximation algorithm that is an algorithm that deletes at most $3$-times as many points as an optimal solution. Unfortunately, I am totally clueless here. How would such an algorithm look like?

Find any line containing $\geq 3$ points. Delete all points on this line. Repeat.

This is a $3$-approximation, since on any line containing $m\geq 3$ points we must delete at least $m-2\geq 1$ points and we delete at most $2$ points too many. Meanwhile, the objective value decreases by at least $m-2\geq 1$.

If we know that the true objective value is $K$, then the instance obtained by deleting all points on this line will have objective value $\leq K-(m-2)$ and thus the recursive application will, by induction, return a solution removing at most $3(K-(m-2))$ points. Thus, we remove at most $3(K-(m-2))+m=3K-2m+6\leq 3K$ points.


CPU time and execution time Why should computer designers trade off clock rate against cycle count? Can somebody explain this sentence for me? Shouldn't it be that when the clock rate increases the cycle count decreases?

I don't understand why the cycle rate and the cycle count are not proportional.

I am not sure I understand the question.

When designing a CPU, you decide how many pipeline stages it will have and accordingly how much work is done at each stage.

Often, all the parts of the CPU work at the same frequency (well, this is not really true, but...), so the most complex part will be what limits the frequency that the CPU will be able to achieve.

Some CPUs are optimised for high frequency and have many pipeline levels (ex : Intel Pentium IV, AMD Steamroller). Good for number crunchers.

Some CPUs are optimised for lower frequencies but cram more work for each pipeline level (ex. : Intel Core, Apple A8...). This option is often more power efficient.

Deeply pipelined CPUs waste more cycles than narrow ones when the pipeline must be emptied : mispredicted branch, interrupt... The number of cycles wasted is higher, but as the frequency should also be higher, the delay for each cycle should be a bit shorter than for a short-pipelined CPU.

[Maybe you should give more context to your question. This answer was probably not what you were looking for ;-)]


A Problem on Time Complexity of Algorithms For every integer $t$, is there a problem whose solutions can be verified in $O(n^{s})$ time but cannot be found in $O(n^{st})$ time?

By verifying, I mean that given a candidate solution $y$, we can judge whether $y$ is correct or not in time $O(n^s)$.

For $k = \left\lceil \dfrac{r}{2} \right\rceil$, it is conjectured (and proven in some simpler models of computation by JeffE) that $r$-SUM problem has lower bounds $\Omega(n^k)$, the solution for which can be verified in $O(n)$ time.

Pick an $r$ such that $k \gt t$, implying $\omega(n^t)$ bounds.


Satisfiability 2 CNF-SAT to 3 CNF-SAT transformation/reduction This Reduction is trying to prove that 2CNF-SAT is also NP-Complete, after proving 3CNF-SAT is NP-Complete.

If we had a reduction that given an instance of 2CNF-SAT with k clauses over 'i' number of variables, and we create an instance of 3CNF-SAT with 2n clauses by introducing for clause i a new variable y; then for the i'th 2SAT clause we generate two 3SAT clauses.  This is a reduction from a 2CNF-SAT to a 3CNF-SAT.

Is this not a correct reduction because all of the other clauses after the transformation are still 2CNF-SAT except for the i'th clause?

It looks like you are trying to prove either that 2CNF-SAT is NP-Complete, or that 3CNF-SAT has a polynomial algorithm, by reducing 2SAT to 3SAT. But that's not how it goes! If you're trying to do what I think you're trying to do, then you should reduce 3SAT to 2SAT. Unfortunately, if you can reduce 3SAT to 2SAT, then that would imply P=NP, so that's probably very hard.

It's very easy to get confused about which way a reduction should go, and how you should make one. Please read my answer to this related question: Implications of Halting Problem being undecidable, in particular the 'cheat sheet' section, where I try to clear up some confusion around the topic, and let me know if you have questions after reading that, then I might edit this answer tailored specifically to whatever question you have afterwards.


Convergence of Markov model I was learning Hidden Markov model, and encountered this theory about convergence of Markov model.

For example, consider a weather model, where on a first-day probability of weather being sunny was 0.9 while that of being rainy - 0.1. The transition distribution probabilities were - probability of sunny on current day given weather was sunny on previous day - i.e P(sun/sun) = 0.9. Similarly other probabilities were - P(sun/rain) = 0.3, P(rain/rain) = 0.7, and P(rain/sun) = 0.1.

Using bayes inference, we can find probability of distribution of weather on day Xt. It was mentioned that, after some point (i.e at state t = infinite), the probability distribution of weather on a day converges to p(sun) = 0.75 and p(rain) = 0.25.

Can someone explain this convergence mathematically? How does it converge to this distribution? It doesn't matter what's the distribution on day 1, the model always converges to the same values.

This isn't a hidden Markov model; this is an ordinary Markov model.  Take a look at Wikipedia's article on Markov chains and specifically the notion of a steady-state distribution (or stationary distribution), or read about the subject in your favorite textbook -- there are many that cover Markov chains.


Does closure against countable union survive union of classes? A class of languages $\mathcal{C}$ is closed under countable union (cucu) if for all series of languages in $\mathcal{C}$ ($(L_i)_{i\in\mathbb{N}} \in \mathcal{C}^\mathbb{N}$) the language $\bigcup_{i\in\mathbb{N}}L_i = \{x\mid \exists i\in\mathbb{N}: x \in L_i\}$ is an element of $\mathcal{C}$.

As we know most (if not all but $\mathsf{ALL} = \wp(\Sigma^*)$) interesting complexity classes are not closed under countable union as every Language $L$ is the countable union of some singleton Laguages $\{w_i\}$.

However there are some classes of decidable languages which are cucu like:

$\{\{w\in\Sigma^*\mid |w| \leq i\}\mid i\in\mathbb{N}\}$
$\{n\text{-}\mathrm{SAT}\mid n\in\mathbb{N}\}$
every $\mathcal{C}$ s.t. every $L \in \mathcal{C}$ is cofinite

My questions:

Let $\mathcal{C},\mathcal{C'} \subset \mathsf{REC}$ be two classes of decidable languages s.t. both are cucu. Is $\mathcal{C} \cup \mathcal{C'}$ cucu?
Is there some "real" complexity class (i.e. defined by some machine model, grammar type, $\lambda$-calculus restriction etc.) that is cucu? (You may restrict it artificially (e.g. NFA, where each final state has a path to another final state), if it fits otherwise.)
Edit (after Yuval Filmus' answer): Given $\mathcal{C},\mathcal{C'}$, as in (1), does the closure of  $\mathcal{C} \cup \mathcal{C'}$ under countable union only contain decidable languages?

(1) is the main question, (2+3) only addenda.

The answer to (3) is yes. Suppose that $S \subseteq \mathcal{C} \cup \mathcal{C}'$. Then $S$ is countable, because $\mathcal{C}\cup\mathcal{C'}$ contains only decidable languages of which there are only countable many. Now let $T = S \cap \mathcal{C}$, $T' = S \cap \mathcal{C}'$. By assumption $L = \bigcup T \in \mathcal{C}$, $L' = \bigcup T' \in \mathcal{C}'$. Since $L,L'$ are decidable, $L \cup L'$ is decidable.


Turing reduction problem, intersection is equal to an empty set $L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)=\emptyset\}$ prove to be undecidable.
My approach:
We will prove this by reduction $L_{\emptyset} \leq_T L_c$  We begin by assuming that $L_c$ is decidable and that we have access to a black box $Q$ which decides it. We want to construct another Turing machine $H$ which decides $L_{\emptyset}$.

H = “On input (< M >, w).
    Construct the following machine M’
M’ = “On input w.
    Ignore input w and reject.
    Run decider Q on (< M >,< M’>)
    If Q accepts, reject.
    If Q reject, accept.

I'm mainly concerned about my choice of $L_{\emptyset}$ (maybe $L_{halt}$ is better suited here?) and the part where I run the decider $Q$ on ($\langle M \rangle, \langle M'\rangle)$. Any help would be much appreciated, Thank you!

Assume $L_c$ is decidable. We will reduce $A_{TM} =\{x\mid M_x \text{ halts on } x\}$ (the Halting problem language) to $L_c$. On input $x $ create a TM $M'$ which halts on only $x$. Then $L(M') = \{x\}$ and $M_x$ halts on $x$ iff $L(M_x) \cap L(M') = \{x\} \neq \emptyset$ iff $\left(\langle M_x \rangle, \langle M' \rangle \right) \notin L_c$. Thus, to check if $M_x$ halts on $x$ we check if $\left(\langle M_x \rangle, \langle M' \rangle \right) \notin L_c$.


Resizing and aliasing in computer science If you resize an 1000x1000 raster image to 10x10 and resize it back to 1000x1000 is this considered to be an example of aliasing?

When you resize to a lower resolution, there are several ways to do
it. If you average values of the pixels that merge into a single one,
you simply have a loss of resolution, which amounts to keeping only
the lower spatial frequencies (counting frequencies relative to image
size, not to pixel size).  However, if you reduce resoution by
sampling, i.e. replacing a bunch of pixels by the value of one of
them, you may overplay high frequencies, not meaningful at the given sampling (spatial) frequency, leading to all kinds of
artefacts such as moiré effects for images.

When you recreate the image at former resolution, you cannot in
principle recreate
lost information. But you try to make educated guess as to the effect
most likely to occur or not to occur in most images. Hence, you apply
some reprocessing to the image so as to eliminate unlikely phenomena,
or play down phenomena that you know could not have survived the initial size
reduction (they may or may not have been there, but you know that
later presence is not due to original existence).

Typically, as you know that the image reduction has necessarily lost
some higher spatial frequencies, or distorted their role, you can
choose to eliminate or play doen those frequencies at the recreated higher
resolution, as they do not originate from the initial image.

For example, if you had a large geometric image, reduction and back
resizing will produce a staircase effect on most straight lines. These
abrupt changes correspond to high spatial bandwith. By removing these high
frequencies, you will recreate shaded areas that smooth down the staircase effect on the
straight lines.

Aliasing has to do with the artefact due to the combined effect of
sampling and reproducing back a sampled observation of a theoretically
continuous phenomenon (or considered as such because its initial resolution is
significantly greater than the sampling rate), may be an image, a
sound, a film,etc. As seen above, the sampling technique does matter.
Antialiasing consist of the techniques used to eliminate
artefacts known as likely to occur.  It cannot recreate lost
information unless you knew separately that the processed information
has to satisfy some constraints, which antialiasing can then use to
improve the image. For example, you may know that geometric images use
straight lines more often than small staircases.

Wikipedia has more technical information.


Does instruction which control unit fetch contain both what to do and where to do (in which unit of processor)? What instruction really means? I am facing problem in understanding it. If the instruction is to copy this and create a new file and place there so it seems it d doesn't need processing so what will control unit do?

In computer architecture (the current tag, but I wonder if it is really adapted), an instruction is whatever the computer architect decide to be.  It is the most basic bit string having a independent meaning.  Some instructions may be quite simple (add two registers and put the result in the first one), some may be strange (provide the most significant bits of a constant value used in the next instruction) and the boundary between being one instruction or several may be not that clear (you could consider the previous example and the instruction which follow it as a single instruction).

I don't know any processor which provides instructions like the one you are describing.  Those seems to me to be at the abstraction level of an operating system, not of a processor architecture.  It could be that mainframes provide such instruction (in the channel control part), but even there my guess is that it would need to be the combination of several more basic instructions.  That guess holds also for operating system.


Clustering of Songs (The Joe Walsh Problem) The Eagles are a rock supergroup from the 70s and 80s, responsible for such classics as Hotel California. They have two quite distinctive sounds, one where guitarist Joe Walsh is present (for example, in Life in the Fast Lane) and one where he is absent. The latter songs have a markedly more sombre/boring feel.

I'm curious to understand the degree to which an (unsupervised) learning algorithm would be able to detect the difference between the two sounds. One could imagine that it would be easy to tell the difference between speed metal and classical music, but what about sounds by the same band.

  How would I set up such an experiment? Assume that I already have the relevant audio files in some standard format.

Note that this should also apply to other rock groups, such as AC/DC who had a change of lead singer in 1980, and possibly even to other genres, possibly even more modern music.

What you want to do seems to be known as Audio Feature Extraction or, more specifically, Music Information Retrieval, that is automated methods that distill characteristics out of (sets of) music files. You would have to extract features of samples of both equivalence classes and look at differences that can inform song choice.

Researchy tools are available for instance here and here. A finalist of Google Science Fair 2011 presented interesting stuff but I can not find his tools anywhere.


How do I show that $a^n w b^n$ is not regular? Given $ \Sigma= \{a,b\} $, show that $ L:= \{a^nwb^n: m,n \in \mathbb N, m\geqslant n, w\in\Sigma^m\} $ is not regular.

I'm trying to proof this with the Pumping Lemma, but I'm kind of confused because of the middle part $w$.

I would pick the symbols $\ a^na^mb^mb^n $ as a starting point and show that this does breach at least one of the three properties of the pumping lemma. At this point I don't know if this is the right word to pick & how I do continue from here.

It's reasonable to conjecture that $L=\{a^nwb^n\mid w\in (a+b)^*, |w|=m\ge n>0\}$ is not regular, since it looks a lot like the $a^nb^n$ language, which we know isn't regular. However, $L$ is indeed regular and is in fact the language denoted by the regular expression
$$
a(a+b)(a+b)^*b,
$$
assuming that $0 \notin \mathbb{N}$ (otherwise the language is just $\Sigma^*$).
The key idea here is that $L$ is defined to be "all strings over $\Sigma=\{a, b\}$ which can be expressed as $a^nwb^n$ where $|w|\ge n>0$". This means that strings in $L$ might not obviously be of the right form, but can be expressed in other ways that are of the right form.

We'll show that $L$ is the same language as $M=\{axb\mid x\in (a+b)^*, |x|\ge 1\}$. Here's a proof that $L=M$:

($M\subseteq L$): Let $s\in M$, then $s=axb=a^1xb^1$ with $|x|\ge 1=n>0$, so $s\in L$.
($L\subseteq M$): Let $s\in L$, then $s=a^nwb^n$ with $|w|=m\ge n > 0$. We also have
$$
s=a^{n-i}(a^iwb^i)b^{n-i}=a^{n-i}xb^{n-i}\qquad\text{with $x=a^iwb^i$}
$$
for any $0\le i \le n-1$. If we pick $i=n-1$ we'll have $s=a^1(a^{n-1}wb^{n-1})b^1$ and we'll have $|x|=2(n-1)+m\ge 2n-2+n=3n-2\ge 1$ and so $s\in M$, completing the proof.


Who (and when) first defined interval graphs? I've been searching google scholar for references and narrowed down the first mention to somewhere around 1963 with a very weird jitter in 1949.

So, I'm trying to track down the original paper introducing interval graphs for citation, but it's been rather elusive so far.

I was able to track the first occurences of interval graphs down to

G. Hajos, Über eine Art von Graphen, Int. Math. Nachr. 11 (1957) page 65

This reference refers to a book of (talk) abstracts. In the abstract of Hajos  interval graphs are defined, without actually calling them interval graphs. Moreover it says, that he gives conditions whether a graph is a interval graph and he discusses how to reconstruct the intervals defining the graph, when the graph fulfills these conditions.


Formally modelling and describing access rights Is there a formal theory or framework described in text books that models access rights in a mathematical way. I would expect things similar to the following:

We have data (objects).
We have operations on these objects (CRUD, create, read, update delete)
We have actors (users, principals)
We might model access rights as triples like (user, operation, object) which describe which user can do what to which object.
We have a potential hierarchy of objects: a folder has files, a file has meta data and rights may be inherited according to certain rules down the hierarchy.
We have a hierarchy of actors too.
Rights may be stored more efficiently by creating triples of (user set, operation set, object set) based on attributes of the objects and the users.

Apart from the pure theory I would expect to read about efficient implementation strategies, data structures etc.

EDIT on: Once access rights are modelled, I would like to read about how these are enforced in real code. Where and when must an operation of some data make the decision whether this is allowed in the given context or not.
EDIT off

Further I would expect to see how this maps to real world access control systems in file shares, databases, web applications. Maybe I am just missing the right keywords for a search.

The one paper I found, http://www.sciencedirect.com/science/article/pii/S1877050916301764, is not exactly convincing.

The Harrison-Ruzzo-Ullman model has this form.  It has principals (e.g., users) and objects (e.g., files), and a matrix that indicates which types of access each principal has for each object.  It also models how the sets of access rights can evolve over time.  It has no notion of hierarchy for principals or objects built into the model, but you could of course regard the set of principals and objects as hierarchical in the way you want -- that's compatible with the HRU model.

The HRU model concerns itself only with semantics: with who has access to what.  It is not concerned with efficiency.

You might also enjoy digging up a textbook that covers this.  The catchphrase you want is the foundations of computer security".  For instance, you might find Matt Bishop's book Computer Security: Art and Science very relevant.


Inclusion of complexity classes (Deterministic Turing Machine) I can't understand what my professor wrote about these inclusions concerning deterministic classes:

$$
DTIME(f) \subseteq DSPACE(f) \subseteq \sum_{c\in\Bbb N}DTIME(2^{c(log+f)})
$$

I understood the first inclusion:

  The Turing Machine needs to do at least one step in order to check the
  next cell on tape

I didn't get the second one:

  The number of configurations of the Turing Machine with fixed space is finite, and the computation must stop within a maximum number of steps equal to these settings, otherwise wewould have a cycle.

I don't understand the argument of the summation: why that $2$ and that $c(log+f)$?
Why is it written like that?

Expanding on the comments, the idea is that if a Turing machine has $M$ possible configurations then if it halts, it must do so within $M$ steps. The reason is that once the machine has stepped through $M+1$ different configurations, it must have stepped on the same configuration $C$ twice. Since the machine is deterministic, each time it reaches configuration $C$, it will work its way in the same manner and reach $C$ again, and again, and again, indefinitely.

How many different configurations are there? Suppose the tape alphabet is $\Sigma$ (include the blank symbol), the space is $S$ (assume for simplicity that the tape is one-way infinite so there is a unique chunk of space $S$), and there are $N$ states. Then the number of configurations is $NS|\Sigma|^S$, since a configuration is given by the state, the position of the head, and the contents of the tape. We can write this bound as
$$ NS|\Sigma|^S = 2^{\log N + \log S + (\log |\Sigma|) S} \leq 2^{c(1+\log S + S)} $$
for $c = \max(\log N, \log |\Sigma|)$. Assuming $S \geq 2$, we can further simplify this to $2^{c(1+\log S+S)} \leq 2^{c'(\log S+S)}$ for $c' = 2c$.


the number of arrangements of N players around a round table, where each player can sit on one of 3 contiguous chairs Consider the fact that each player can either sit on their desired chair or on the neighbouring chair. Two configurations are distinct if at least one person is sitting in another chair.
My attempt
For example, if there are 4 players sitting around a  circular table there can be 9 distinct arrangements.

F1,F2,F3,F4
F2,F1,F3,F4
F2,F1,F4,F3
F4,F2,F3,F1
F1,F3,F2,F4
F1,F2,F4,F3
F4,F1,F2,F3
F2,F3,F4,F1
F4,F3,F2,F1

Now, I am stuck here. How can calculate this and what about larger values of N such as 50?
I tried using vectors and pushing back every element and do the reverse operators and swap elements but I am not sure whether this is correct or not.

Consider the variant of the problem in which the people are arranged in a segment instead of circle and let $S(n)$ be the number feasible arrangements for $n$ people.
Now lets go back to your original problem, and let's name $C(n)$ the number of feasible arrangements of $n$ people.
Clearly $C(0)=C(1)=1$ and $C(2)=2$, so we will henceforth suppose that $n \ge 3$.
Let's name the people $p_1, \dots, p_n$ where the assigned position of $p_i$ is $i$.
If $p_1$ is sitting in position 1 then the number of possible arrangements of $p_2, \dots, p_n$ is exactly $S(n-1)$.
Otherwise, $p_1$ is sitting either in position $2$ or in position $n \neq 2$. We will only consider the former case since the latter one is symmetric.
Clearly $p_2$ cannot sit in position $2$, so he/she must either sit in position $1$ or in position $3$. If $p_2$ is sitting in position $1$, then the number of possible arrangements of $p_3, \dots, p_n$ is exactly $S(n-2)$.
Otherwise, $p_2$ must be sitting in position $3$, which means that $p_3$ must be sitting in position $4$ (since position $2$ and $3$ are occupied) and, in general, $p_i$ must be sitting in position $(i \bmod n) + 1$. Since this completely determines everyone's position, this case only contributes $1$ to the total number of configurations.
To summarize, we have that:
$$
C(n) = S(n-1) + 2(S(n-2)+1) = S(n-1) + 2S(n-2) + 2.
$$
We are left with figuring out what $S(n)$ is. Clearly $S(0) = S(1) = 1$, so we consider $n \ge 2$.
In this case $p_1$ can only sit in position $1$ or $2$.
If $p_1$ is sitting in position $1$ then there are $S(n-1)$ possible arrangements of $p_2, \dots, p_n$. If $p_1$ is sitting in position $2$, then $p_2$ must be sitting in position $1$ (as it is the only other person that can sit there) and there are $S(n-2)$ possible arrangements for $p_3, \dots, p_n$.
We hence have:
$$S(n) = \begin{cases} 1 & \mbox{if } n \in \{0,1\} \\ S(n-1) + S(n-2) & \mbox{otherwise} \end{cases} = \mathcal{F}_{n+1},$$
where $\mathcal{F}_{i}$ denotes the $i$-th Fibonacci number. Substituting back, we obtain:
$$
C(n) =
\begin{cases}
1 & \mbox{if } n \in \{0,1\} \\
2 & \mbox{if } n = 2 \\
\mathcal{F}_n + 2 \mathcal{F}_{n-1} + 2 & \mbox{otherwise}
\end{cases}.
$$


How does the processing happen in a CPU when it uses Virtual Memory? I am just trying to visualize how computers work with Virtual Memory/Address.

Assume there is a program on the disk that looks like this:

a b c d e f g h i j k l m n o p where the a .. p are instructions and their address is from 0 to 15.

What happens inside the CPU while executing this program? Assume that the operating system uses pages of 8 bytes.

To begin with, my understanding is that the operating system loads the program into physical memory in page-sized chunks and creates a mapping to the pages of the program numbered from 0..n which looks like:

# assume it is in reverse in the real memory (16-31)!

[i j k l m n o p] [a b c d e f g h]

# cpu's view of the program

  page1 (24-31)     page2 (16-31)
[a b c d e f g h] [i j k l m n o p]
 |
 PC

Depending on the program size, program-size/page-size page's
will be created. So here it would be 16B/8B = 2 pages numbered as
page1 and page2.
Now, the Program Counter (PC) would be set to the Virtual Address of
a which is 0 and the CPU will somehow resolve it and load the
corresponding instruction from the real physical address of a
which is 24 here.
But wait, how did CPU know that it has to look up into a certain
page map, page1 in this case? The operating system knows that but
how does the CPU know that? Is it something like the Virtual Address
of a program corresponds to one and only one page map and that can
be determined directly from the Virtual Address itself? For example,
0x00 automatically means to lookup in page1, 0x08 means to
lookup in page2. Divide by 8 and look into the page{quotient}
with the remainder indicating the offset to look into the real
memory?
Suppose there is an instruction d that refers to the memory
corresponding to o which is in page2, how will that be resolved?
Is it using the same principle? If you know the Virtual Address,
then you know the place to look up for the real address?
Now, when there are multiple programs how do we uniquely determine
what is page1? Could another program have a page1 as well? Is it
like page maps are unique (which I think is complex because I
thought it has to be sequential and starting from 1 so that given a
Virtual Address you can calculate the page map + offset) or is there
a per process Page Table managed by the Operating System?
Suppose we finished executing the instruction h, the PC would
automatically load the Virtual Address of i, which gets
automatically resolved to page2 using the same above principle?

Virtual memory is handled just in the part of the CPU that handles reading and writing memory.

At some point, the CPU has calculated a memory address and has decided to read or write memory at that location. If there is no virtual memory used, then the memory address is the actual address in the physical memory connected to the CPU. With virtual memory, the memory access part of the CPU will first translate the virtual memory address to a real memory address.


How can I analyze the time complexity of this Dynamic Time Warping algorithm implemented in MATLAB? I have a rough idea that the time complexity is O(mn) where m and n are based on the length of signals, as per this http://en.wikipedia.org/wiki/Dynamic_time_warping.

How can I determine the time complexity of the following code (source)

function [Dist,D,k,w,rw,tw]=dtw3(t,r)
%
% [Dist,D,k,w,rw,tw]=dtw(r,t,pflag)
%
% Dynamic Time Warping Algorithm
% Dist is unnormalized distance between t and r
% D is the accumulated distance matrix
% k is the normalizing factor
% w is the optimal path
% t is the vector you are testing against
% r is the vector you are testing
% rw is the warped r vector
% tw is the warped t vector

[row,M]=size(r);
if (row > M)
     M=row;
     r=r';
end;
[row,N]=size(t);
if (row > N)
     N=row;
     t=t';
end;

d=((repmat(r',1,N)-repmat(t,M,1)).^2);

D=zeros(size(d));
D(1,1)=d(1,1);

for m=2:M
    D(m,1)=d(m,1)+D(m-1,1);
end
for n=2:N
    D(1,n)=d(1,n)+D(1,n-1);
end
for m=2:M
    for n=2:N
        D(m,n)=d(m,n)+min(D(m-1,n),min(D(m-1,n-1),D(m,n-1)));
    end
end

Dist=D(M,N);
n=N;
m=M;
k=1;
w=[M N];
while ((n+m)~=2)
    if (n-1)==0
        m=m-1;
    elseif (m-1)==0
        n=n-1;
    else
      [values,number]=min([D(m-1,n),D(m,n-1),D(m-1,n-1)]);
      switch number
      case 1
        m=m-1;
      case 2
        n=n-1;
      case 3
        m=m-1;
        n=n-1;
      end
    end
    k=k+1;
    w=[m n; w];
end

% warped waves
rw=r(w(:,1));
tw=t(w(:,2));
end

Look at the main double for loop that does all the work. It loops for m from 2 to M and then inside that for n from 2 to N. This is O(MN) like you expected.


Is there a way to reflect small edge-weight changes after computing Floyd-Warshall on a large graph? I am working on a hex-based game in which I'm trying to pre-calculate pathfinding for a given map using the Floyd-Warshall algorithm. The map size is on the order of thousands of hexes (so maximum tens of thousands of edges).

The map represents an arena in which two teams fight, and both have the ability to change the map, either by creating complete walls (removing a vertex from the graph), or changing weights on the edges (i.e. by temporarily making a hex difficult to walk over).

The reason I'm considering using all-pairs-shortest-path algorithm is because I need to simulate the game as fast as possible, and thus I can't waste time with actual pathfinding during the simulation.

Is there a way to detect which paths need to be re-calculated when a change is made to the graph? It seems that if I only increased the weights/removed vertices, I could only re-calculate the affected paths, is that true? And what if I'm also decreasing weights/adding new vertices/edges?

Yes.  The phrase to search for in the literature is "dynamic shortest paths".  "Dynamic" refers to the path that the graph might change, and we want to efficiently update the shortest paths (more efficiently than recomputing them from scratch).

There are different ways one might change the graph.  Some papers consider the case where edges can be added.  Others consider where edges can be removed.  You can also find algorithms that can handle both kinds of changes; that might go under the name "fully dynamic shortest paths".

Search the literature.  You'll find many algorithms, with different tradeoffs between running time, simplicity of implementation, and types of graph updates supported.


Why does bubble sort do $\Theta(n^2)$ comparisons on an $n$ element list? I have a quick question on the bubble sort algorithm. Why does it perform $\Theta(n^2)$ comparisons on an $n$ element list?

I looked at the Wikipedia page and it does not seem to tell me. I know that because of its magnitude it takes a lot of work with large numbers.

Consider the worst case analysis: when the array is completely sorted, but from largest to smallest. In this case, bubble sort will make $n-i$ swaps in iteration $i$ (and in particular, there will be a swap in every iteration), and repeat that for $n-1$ times. This gives a total runtime of $(n-1)^2=\Theta(n^2)$.

Observe that even under some optimizations of the naive bubble sort, the runtime is still ${n\choose 2}=\theta(n^2)$.


A Turing Machine that Doesn't Move to the left My question is if the following statement is true or false:

Does every turing-recognized $B$ language has a turing machine $M$ that recognizes $B$ and fullfiles the following statement:
For every word $w$ the belongs to $B$, $w \in B$, the writing-reading head never moves to the left?
Notice that the condition is required only for words in the language. if $w \notin B$ then the head can move to the left as usual.

The statemet seems correct to me. I think I can simulate a regular $TM$ with this "special" $TM$, while saying that every time the head moves left, it will stay put. Couldn't prove it, though.

If you only allow moving right (and no external memory), all your TM "knows" about the input already seen is the finite amount of information in its state. I.e., it can't do more than a finite state automaton.


Convert integer of mixed radix to standard positional numeral system and vice versa I have multiple numbers (e.g. [1, 4, 2]) where each number can be one of a specified range of numbers (e.g. [0-1, 0-5, 0-3]). I think one can represent my so chosen numbers by seeing them as digits of a number in the mixed radix numeral system with different bases for each position. In the above example, the bases would be [2, 6, 4] and the number would be 1 4 2.

With the bases given in this example one could specify 48 different numbers (2 * 6 * 4).
If I know the bases, how can I construct an algorithm that converts such a number to another number in a standard positional numeral system (like e.g. decimal, binary or hexadecimal) without just building a big generated lookup table? The conversion has to be bijective and there should not be any gaps - so for this example the mixed radix numbers should be represented by the integers from 0 to (inclusive) 47 in the decimal system.

Actually I want to encode these mixed radix numbers in binary data, so a gapless and bijective conversion to the binary system would be sufficient.

If you have numbers $x_1,\ldots,x_n$ in the ranges $x_1 \in \{0,\ldots,b_1-1\},\ldots,x_n \in \{0,\ldots,b_n-1\}$, you can get a number in the range $\{0,\ldots,b_1\ldots b_n-1\}$ using the formula
$$
x_n + b_n x_{n-1} + b_n b_{n-1} x_{n-2} + \cdots + b_n b_{n-1} \cdots b_2 x_1 = \\
x_n + b_n (x_{n-1} + b_{n-1} (x_{n-2} + \cdots )).
$$
The second formula gives an efficient way of calculating the transformation (from inside out), and also hints at calculating the inverse transformation efficiently.


NP-completeness of testing whether a SAT formula does not contain any redundant clause This paper explains that testing the irredundancy of a SAT instance is NP-complete.
But I don't understand the theorem/reduction.
How would one reduce 3SAT or k-SAT to this problem, for example?

The proof in theorem 1 in [Liberatore'02] shows that irredundancy is NP-hard by reducing SAT to it. Considering any set of non-tautological clauses $\Gamma=\{\gamma_1,\dots,\gamma_m\}$ (think of this as the set of clauses of a CNF boolean formula), it builds in polytime a set of clauses $\Pi_\Gamma$ which is irrendundant iff $\Gamma$ is satisfiable (again, $\Gamma$ being satisfiable means the CNF formula $\bigwedge_{j=1}^m \gamma_1$ is). Therefore if you can solve irredundancy you can solve SAT.
[Liberatore'02]: Paolo Liberatore. 2002. The complexity of checking redundancy of CNF propositional formulae. In Proceedings of the 15th European Conference on Artificial Intelligence (ECAI'02). IOS Press, NLD, 262–266.


Without primes in $P$ does integer factorization lie in $coNP$? In integer factorization we ask 'Given $N$ is there a $a\in[2,\sqrt{N}+1]$ such that $a|N$?'.

Is the above problem in coNP because we know primes is in $P$?

That is there is no such factor $a$ of $N$ iff $N$ is prime and we have AKS certificate.

So was it not known prior to 2004 that integer factoring was in coNP?

First of all, you're misstating integer factorization: your version is completely equivalent to primality.

Second, there were primality certificates which could stand for a polytime primality testing algorithm. These are polytime verifiable certificates of primality.


Showing the the language represented by a set is regular Is the language $L = \{ w \mid w $ is $ 3^n - 1 $ in some given representation $, n > 0 \}$ regular? I know that it is regular. If each element in $L$ is represented as decimal numbers, $L = \{ 2, 8, 26, 80, 242, \ldots \}$. If in binary, $L = \{ 10, 1000, 11010, 1010000, 11110010, \ldots \}$. However, if in ternary, $L = \{ 2, 22, 222, 2222, 22222, \ldots \}$. From there, it is clear that a DFA can be designed to show that $L$ is regular. But what if it wasn't ternary that it became clear, but instead base 59 or base 1009?

My question is that for other sets, does there exist a clear method to determine if the language based on that set is regular or not? Or does it just depend on the cleverness of the solver?

See DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$.

The proof for $L'=\{w \mid w \in \{0,1\}^*, w $ is $3^n$ in binary for some $ n > 0 \}$ is not regular can be easily modified to prove that $L'=\{w \mid w \in \{0,1\}^*, w $ is $3^n - 1$ in binary for some $ n > 0\}$ is not regular.

However in ternary the same language is regular. It is similar to case of $2^n$ and $2^n-1$. So for some bases you might be able to prove these kind of languages regular but for others you may not.


About codes over $\mathbb{F}_2$ I was looking through these notes but I am not sure I can locate the answer to these questions of mine - it would be great if someone can just even point out what to look for!

So any set of binary vectors can be seen as "code"?

Let $M$ be a $d\times m$ matrix over $\mathbb{F}_2$ and let $X(M)$ be the graph on the binary vectors of length $d$, where two vectors are adjacent if their difference is a column of $M$. (does this mean that before comparing when one is taking a bit-wise difference of the vectors one is equating $-1$ to $1$ as would be inside $\mathbb{F}_2$?)
Does this above construction have a name? Any motivations?

What is this NP-hard question about finding a "minimum weight code" among a set of binary vectors? Can someone kindly give the precise definition?

A binary code is a set of vectors in $\mathbb{F}_2^n$ for some $n$.
Presumably the context in which you encountered this construction is a motivation for it. It's a particular case of a more general construction known as a Cayley graph, though perhaps this particular case has a specific name. You are right that all arithmetic is done in $\mathbb{F}_2$.
There are several NP-complete problems related to codes; Madhu Sudan has an entire lecture on these. One of them is, given a generator matrix for a linear code, determine the minimum weight of a non-zero codeword (i.e., the minimum distance).


Prove that $\{\langle M, n, w\rangle \mid \text{$M$ has $n$ states, $w ∈ \Sigma^*$ and $M ∈ B(n,w)$}\}$ is undecidable I want to prove that:
$\{\langle M, n, w\rangle \mid \text{$M$ has $n$ states, $w ∈ \Sigma^*$ and $M ∈ B(n,w)$}\}$ is undecidable.

Here $w$ is a string and $B(n,w)$ is the set of all $n$-state machines that halt on input $w$ after exactly the maximum number of steps. I don't know how to prove this. I tried finding another language to apply the reduction method but also to no avail. Can anybody help me with this?

Given a Turing machine $M$ of $n$ states and a word $w$, you could solve the halting problem for $(M,w)$ if you knew the maximal number of steps $f(n,w)$ that a Turing machine $M$ with $n$ states can spend on $w$. If your language were decidable then you could compute $f(n,w)$ by trying all Turing machines on $n$ states until you find one in $B(n,w)$.

I'll let you figure out the details on your own.


Time complexity of a language whose alphabet has a single symbol Consider a language $L$ such that $L \subseteq \Sigma^*$, where the cardinality of $\Sigma$ is $1$ (i.e. the alphabet has only one symbol). E.g. $L \subseteq \{a\}^*$.

Can anything be said about the time complexity of $L$? Is it the case that $L \in P$?

I can't come up with any example of a language with a single symbol that is not in $P$.

The language $\{a^n : \text{ the $n$th Turing machine halts on the empty string} \}$ is undecidable.

In fact, a random unary language is undecidable almost surely, for the simple reason that there are only countably many computable languages.


A Turing machine going to the right by the first $2 |w|$ steps A single-tape Turing machine $M$ has the property that, for every input $w$, during the first $2 |w|$ steps, the head of $M$ moves only right (it does not move left nor stays in place); the machine is also allowed to halt at any moment during these first $2|w|$ steps.
Prove that the language of $M$ is in $DTIME(n)$.

Perhaps I don't understand the problem because I don't know how to start. My intuition is following:

$L$ reconized by $M$ is $= K \cup M$ where $K$ is a set of such words $s$ that $|s| < |w|$. $M \cap K = \emptyset$.

We can consider two situation:

1) $M$ stops before $2|w|$ steps. It means that such word $w$ can be represented by regular expression. Therefore, such words can be accepted/rejected in $DTIME$.

2) $M$ stpes $2|w|$ to the right (or more) and now it can come back to the beginning. But, if machine is able to reach $2|w|$ steps without memory it means that $M$ can compute steps in any way. It cannot be "solved" using a tape- the machine cannot move left so the tape is useless. So, the information must be encoded in states. But, number of states is finite. So, let $|Q| = n$.

Then, there is limited number of such words that cannot be recognized using a deterministic automata.  The limited language can be recognized in $DTIME$. Other words can be recognized by deterministic automata.

It is my idea. I am not sure if is ok.

1) Is it?

2) Probably there is a better (one-sentence) solution. Please say me.

Suppose that the Turing machine has $N$ states. We call a state $q$ reachable if for some word $w$ of size at least $N$, when the Turing machine runs on $w$, it finds itself in state $q$ after reading $w$. During the following $N$ steps, the machine must go to the right. If it doesn't halt during these $N$ steps, then some state is repeated, and so the machine never halts. Since we assume that it does always halt, it follows that when the Turing machine is in state $q$ with an empty symbol under the head, it stops within $N$ steps, during which it continues traveling to the right.

The discussion above shows that if $w$ has size at least $N$, then the Turing machine halts within $|w|+N$ steps. This shows that the machine runs in linear time $O(|w|)$, which implies your exercise.

With a bit more work, you can show that the language accepted by the machine is in fact regular. Indeed, if we only consider words of length at least $N$, then we have a machine moving only to the right, so we know that $L(M) \cap \Sigma^N \Sigma^*$ is regular. Since $L(M)$ differs from this language by finitely many words, it follows that $L(M)$ is regular.


Prove that { ⟨M⟩ ∣ ⟨M⟩ ∉ L(M) } is undecidable Prove that $L = \{\langle M \rangle \mid \langle M \rangle \notin L(M)\}$ is undecidable. Hint: If there were a decider TM DL for L, what would happen if we gave DL its own description as input?

Here's what I've got so far:

$\mathrm{ATM} ≤_M M$ (with $\leq_M$ being mapping reducible)

Find a map : $f: \langle M \rangle \to \langle DL \rangle$
such that DL doesn't recognize w if and only of x is M's own description.

DL(w):
 if w != description:
    run on M(w)
    if M(w) accepts:
       return accept

I couldn't figure out how to relate DL to ATM to prove that L is unrecognizable. My answer might be partially wrong, but I tried my best.
Any help is appreciated.

You do not need to reduce $ATM$ to $L$. As it hints, Let $L$ is recognized by a TM $M_L$, and note that $L = L(M_L)$ ($L(M_L)$ denotes the language recognized by $M_L$). Then you have the following contradictions
$$\langle M_L \rangle \in L \implies \langle M_L \rangle \notin L(M_L) \implies \langle M_L \rangle \notin L$$
and
$$\langle M_L \rangle \notin L \implies \langle M_L \rangle \in L(M_L) \implies \langle M_L \rangle \in L$$
This completes the proof.


Formal Verification of Functional Programs So I've been interested in learning more about formal verification, and I've seen a lot of interesting things like ACSL and JML which are based on the concept of Hoare triples.

My question is, that these seem to be a way to describe the behaviour of imperative programs via specification languages that are mostly functional (plus universal and existential quantifiers).  But I don't even know the keywords to search to start learning how one would perform formal verification of code in a pure functional language like Haskell.

Could anyone provide a link to material or the name of the equivalent/analogue of Hoare triples for pure functional computation?  Or do you need a fundamentally different approach in the purely-functional realm?

There is probably a lot that can be said about this subject.

I'll just mention one broad approach: types. Sufficiently expressive type systems allow you to express interesting constraints on your programs. This isn't unique to pure functional programming, but such languages have a reputation of taking it farther than statically typed imperative languages. Haskell already has an expressive type system, and compiler-specific extensions allow you to write even more expressive types.

Ideally, you would be able to write a function and its type signature and if the code compiled, then you would have verified that the implementation of your function corresponds to your specification, namely your type signature. It's not quite that simple in Haskell, though, since its type system is unsound:

x :: a -> b
x = x

The above code will compile, even though that might seem a bit objectionable.

The problem is that Haskell allows such functions to potentially be non-terminating, or to effectively crash. In turn, it lets all types be inhabited by bottom, the computation that never completes successfully.

But, if we crank up the types to 8, we are able to transcend such inconsistencies by imposing some limitations on what our programs can express. Namely, if we are willing to force certain types of functions to be terminating, and to only use such terminating functions as building blocks in other terminating functions, we have gained some of our ability to reason about types back. This is called total functional programming, and now we might with more confidence equate our types with being theorems, and our programs with being proofs of such theorems.

Now we just need to crank up our types to 11 in order to reach the heights of the most expressive types that seem to have been implemented in programming languages to this day, namely dependent types. Such type systems lets you express arbitrary properties about your programs. The backside to such power is responsibility - you might have to take care to prove that your code actually implements whatever your types states that it should.

I think that types are very natural path to take for people who are both interested in static functional programming languages and some level of formal verification. Static functional programming languages, like Haskell, already try to encourage a certain rigour with regards to how one structures one's programs such as to take maximum benefit from the capabilities of the type system. Exploring the power and expressibility that types can bring - either as type system extensions in Haskell, or as in full-on proof assistants - can be a very natural extension of that.


Which definition of PRFs is correct? Assume the $\mathcal{F} = \{\, f_{s} \,\}_{s \in \{\, 0,1 \,\}^{*}}$ be a family of computable functions, where $f_{s} \colon \{\, 0,1 \,\}^{|s|} \rightarrow \{\, 0,1 \,\}^{|s|}$.

Let $F_{n}$ be a distribution of functions $f_s$ where $s$ is uniformly distributed over $\{\, 0,1 \,\}^{n}$, and let $RF_n$ denote the uniform distribution over the set of all functions from $\{\, 0,1 \,\}^n$ to $\{\, 0,1 \,\}^n$.

So, $F_{n} = f_{\{\, 0,1 \,\}^{n}}(x)$ for a fixed $x \in \{\, 0,1 \,\}^{n}$, right?

Then we say $\mathcal{F}$ is a family of PRFs if for every PPT $A$,
$$\left\vert \Pr \left[ A^{F_{n}}\left( 1^{n} \right) = 1 \right] - \Pr \left[ A^{RF_{n}}\left( 1^{n} \right) = 1 \right] \right\vert < \varepsilon \left( n \right)$$

This definition is seems correct, but it implies that $A$ can ask the query of $f_{s}$ for at most $poly(n)$ times, $s$ may be different, but $x$ is always the same. It looks strange.

How about let $F^{\prime}_{n}$ be distribution of functions $f_s$ whose input $x$ is uniformly distributed over $\{\, 0,1 \,\}^{n}$ with any fixed $s$, and let $RF^{\prime}_n$ denote the uniform distribution over the set $\{\, 0,1 \,\}^n$.

So $F^{\prime}_{n} = f_{s}\left( \{\, 0,1 \,\}^{n} \right)$ for a fixed $s \in \{\, 0,1 \,\}^{n}$, right?

Then we say $\mathcal{F}$ is a family of PRFs if for every PPT $A$,
$$\left\vert \Pr \left[ A^{F^{\prime}_{n}}\left( 1^{n} \right) = 1 \right] - \Pr \left[ A^{RF^{\prime}_{n}}\left( 1^{n} \right) = 1 \right] \right\vert < \varepsilon \left( n \right)$$

This definition implies that $A$ can ask the query of $f_{s}$ for a fixed key $s$ at most $poly(n)$ times.

Is the first definition is correct? Why not choose the another one?

Or even they are both wrong, $F_{n} = f_{\{\, 0,1 \,\}^{n}}\left( \{\, 0,1 \,\}^{n} \right)$?? It makes me confused.

So, $F_{n} = f_{\{\, 0,1 \,\}^{n}}(x)$ for a fixed $x \in \{\, 0,1 \,\}^{n}$, right?

Nope. That's not right.  Consider the set of functions $\{f_s : s \in \{0,1\}^n\}$.  According to what you have written, $F_n$ is a random variable that is drawn uniformly at random from that set.  (I find this a confusing choice of notation, but I'm going with your proposed definitions.)

  This definition is seems correct, but it implies that $A$ can ask the query of $f_{s}$ for at most $poly(n)$ times, $s$ may be different, but $x$ is always the same. It looks strange.

Actually, what it means is that $s$ is the same for every query, but $x$ can be different for each query.  Yes, $A$ can only ask polynomially queries -- that's a crucial restriction.

  How about let $F_{n}$ be distribution of functions $f_s$ whose input $x$ is uniformly distributed over $\{\, 0,1 \,\}^{n}$

First off: Please don't redefine the meaning of existing notation.  $F_n$ was already defined to mean something else.  Don't define it to mean two different things in two different parts of your post.  That's just confusing.

Second, that definition doesn't make sense.  There's nothing such thing as a function whose input is uniformly distributed over something.  That doesn't make sense.  A function is a function; its a mapping from inputs to outputs.  You don't get to specify an input distribution; a function is whatever it is.  Think of a function as a truth table -- there's no way to specify an input distribution, as that's not part of the definition of a function.

I suggest finding a textbook on theoretical cryptography -- e.g., Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell -- and follow the definitions there.  I wouldn't recommend relying upon Wikipedia for definitions or to learn from.


Asymptotic behavior of functions with not analytic expression Is it in general acceptable by computer science community, if the run-time or space consumption of an algorithm is derived by experiment and not analytically?

For example let's say we have an algorithm for which it's running time is given by function $f(n)$, where $n$ is the size of the problem. There is no way to derive its asymptotic behaviour (respecting run time) analytically but only using numerical methods. In other words we have no analytical expression for $f(n)$ but we can probe it using specific values for $n$. Making some trials (trying a wide range of n) we see that run time follows for example very closely a line. Let's say that doing least square method we observe that $t= an+b$ is a good fit for the run time t of the problem (of size n). Good fit is a vague term, and I mean that residuals are within acceptable ranges.

So is it safe to say that the run time of this algorithm is $\Theta(n)$, at least in the range we made the trials?
Moreover can we state that this algorithm is faster than another one whose asymptotic behavior is for example $O(n^2)$.

If the answer is negative, what other methods should I search for?

Is it safe?  No, of course, it's not safe.  There could always be ways that your experiments are misleading.  Maybe the worst case wasn't triggered by your particular workload or in your particular experiments.  Maybe there's a quadratic term with a small constant, which is negligible for the values of $n$ you tested in your experiments but becomes dominant for very large values of $n$.  You can't rule out those possibilities with experiments.

Are the experiments good enough?  That depends on the community, and for what purpose you want to use them, and what conclusions you want to support.  Can you conclude that the worst-case running time, over all possible inputs, is linear?  No.  Can you conclude that for workloads that are likely to arise in practice, the running time appears to be linear?  Perhaps.  Is this enough to conclude that your system or your method has merit or is a significant contribution over the state of the art?  Quite possibly.

There is no single answer about what is "acceptable".  Instead, I suggest you take a broader, more nuanced view.  Understand the strengths and limits of any method of analysis; understand what conclusions you can and can't support, using those methods; understand what claims you want to be able to make; understand the values of your audience nad the community you are targetting; and go from there.


Proving the language of words with equal numbers of symbols non-context-free Possible Duplicate:
  How to prove that a language is not context-free?

I'm having a hard time figuring this out, any help is appreciated.

Let EQUAL be the language of all words over $\Sigma = \{a,b,c\}$ that have the same number of $a$’s, $b$’s and $c$’s

$\qquad \text{EQUAL} = \{ w \in \Sigma^* \mid |w|_a = |w|_b = |w|_c \}$

The order of the letters doesn't matter. How can you prove that EQUAL is non-context-free?

It is known that the intersection of a context-free language with a regular language is context-free. If EQUAL were context-free, so would be its intersection with $a^*b^*c^*$, which is the well-known non-context-free $\{a^nb^nc^n : n \in \mathbb{N}\}$.


Complexity of division The article Computational complexity of mathematical operations mentions that the complexity of division in $O(M(n))$, and that "$M(n)$ below stands in for the complexity of the chosen multiplication algorithm".

But I'm not sure how to read that $M(n)$ embedded in $O(M(n))$: does it mean that the division has the same complexity as multiplication?

If I use, say, Karatsuba multiplication algorithm, will the division also take $O(n^{1.585})$

The paper

  Torbjörn Granlund and Peter L. Montgomery; "Division by Invariant Integers using Multiplication", Proceedings of the ACM SIGPLAN '94 conference on Programming Language Design and Implementation (PLDI):61-72, 1994.

gives the method used, in practice, to calculate (exact) integer division by producing an appropriate reciprocal (accurate to $n$ bits) of the divisor and also a shift amount.  The division is then done by multiplying the dividend by the reciprocal and shifting.

The reciprocal can be found by Newton's method or Goldschmidt's method, as @Yuval stated in the comments.  Those methods produce the reciprocal accurate to $n$ bits in $O(\log n)$ iterations.  Each iteration requires a constant number of multiplications, and once you have the reciprocal you need one more multiplication to multiply the reciprocal by the dividend.

As pointed out by @gnasher729 in the comments, however, you don't need to do each iteration with full precision.  Newton's iteration doubles the number of useful digits each iteration.  So you can use, for example, 32 bit multiplies in the firsts iteration, 64 bit multiplies in the second, etc.  Since that's a geometric sum it sums to a constant and you get $O(M(n))$.