Why are non-relativizing proofs preferred to relativizing ones? I apologize, but even after these two other posts: here and here
I'm still having trouble understanding oracle TMs and relativization.  This question comes at the issue from a different angle:

Why are non-relativizing proofs considered more valid than arguments based on relativized results?

For example, we have a non-relativizing proof of IP = PSPACE, but couldn't we just as well say an argument for the opposite by the fact that there exists an oracle separating them (I realize from an answer to a question I previously asked that this oracle exists due to a structural difference between the two complexity classes, but I see that as even more evidence that the classes are different in important ways and may not be equal).

On the flip side, why do we conclude from the fact that there exist oracles $A$ and $B$ such that $P^A = NP^A$ and $P^B \neq NP^B$ that non-relativizing techniques will be needed to resolve P vs. NP and not just resolve that oracles lead to inherent contradictions since we cannot have both P = NP and P $\neq$ NP?  Again, I realize from a previous post that we can view oracle TMs as different models of computation that can solve problems ordinary TMs cannot, but I see this as similar to the "theory of types tactic" used in Principia Mathematica which, according to my understanding, Godel (through the Incompleteness theorems) proved to be insufficient to resolving issues of the completeness and consistency of axiomatic systems.

Let me try to answer your multifaceted question using an analogy from number theory (or rather, Peano arithmetic). The platonist point of view holds that every question about natural numbers has a YES/NO answer. This is known as "true arithmetic". However, as Gödel showed, some propositions concerning natural numbers can be neither proved nor disproved. The platonist point of view still holds that these propositions have a definite truth value with respect to the "true" set of natural numbers; Gödel just showed that the no finite list of axioms1 can specify the true set of natural numbers.

Let's see what this implies regarding the P vs. NP question. The platonist point of view holds that either P=NP or P$\neq$NP. It might be that P vs. NP is independent of the foundations of mathematics (say, ZFC), in which case we will be able to prove neither P=NP nor P$\neq$NP. But according to most researchers, this possibility is unlikely. Therefore we would really like to know whether P=NP or not in the real world, which is the same as2 whether P=NP or not according to the standard foundations of mathematics. This is the research question.

What about relativized models? Let me offer another analogy from number theory. If a polynomial identity is true over the integers then it is also true modulo $p$ for every prime $p$. So in order to disprove an identity, it is enough to show that it doesn't hold for some $p$. We can think of the integers modulo $p$ as a "relativized model". Let's consider an example: $1 + 1 = 0$ modulo $2$ but not modulo $3$. Does it mean that we are no longer sure whether $1 + 1 = 0$ or not? Not at all. We know that $1 + 1 = 2$, and in particular $1 + 1 \neq 0$. But in some relativized models, this equation fails to hold.

The (informal) local-global principle states that in some situations, there is a set of "relativized models" which is complete for some number-theoretic statements. The classical example is quadratic forms: given a quadratic form $Q$ and a number $n$, then $Q$ represents $n$ over the rationals (that is, $n$ is in the image of $Q$ when the inputs are arbitrary rational numbers) iff it represents $n$ over the real numbers and the $p$-adics.

Unfortunately, we have no similar theorems for complexity theory. In particular, given the truth value of relativized statements, we can deduce nothing about the original statement. The situation is even worse: it is not longer the case that a result true in the "true" world also holds relativized to any oracle. So we cannot even expect statements like the local-global principle to hold here.

Something like "relativized techniques" also occurs in Peano arithmetic. There are statements regarding the natural numbers which can be proved in ZFC but not in Peano arithmetic. The classical examples are the Paris–Harrington theorem and Goodstein's theorem. All proofs in Peano arithmetic are "relativizing" in the sense that they hold in all models of Peano arithmetic. The Paris–Harrington and Goodstein theorems fail in some non-standard models of Peano arithmetic, but these don't represent true arithmetic; in true arithmetic the theorems hold. The problem is with Peano arithmetic rather than with the statements themselves: there are some properties of the natural numbers that it doesn't describe, allowing these non-standard models to creep in. Gödel showed that this problem happens in all first-order models of arithmetic.

Now we can address your questions:

Why is a non-relativizing proof of IP=PSPACE preferred over oracle separations of the same two classes? We only care about the question IP=PSPACE? in the "true" world. It doesn't matter what happens in relativized worlds. Since there exist oracles which separate IP and PSPACE, proofs of IP=PSPACE must be non-relativizing. The situation is analogous to the one involving the Paris–Harrington and Goodstein theorems.  A different problem is that it is perhaps not clear how to define the relativized versions of these classes. This precludes presenting relativized results even as evidence.
P=NP holds with respect to some oracle and fails to hold with respect to another; why do we conclude that non-relativizing techniques are needed rather than that oracles lead to inherent contradictions? This is the same as the situation of $1+1 \neq 0$ above. This theorem is true, but has different truth values in different "relativized worlds" corresponding to the integers modulo $p$ for different values of $p$. This means that a proof of $1+1 \neq 0$ must include some step that doesn't hold modulo all $p$. It doesn't mean that working modulo $p$ "leads to inherent contradictions".
Aren't we seeing something similar in the "theory of types" developed in Principia Mathematica? The theory of types was developed as a consistent foundation for mathematics, after Russell discovered that naive set theory is inconsistent (using his paradox). No such foundational difficulties have been encountered in complexity theory.
What are the implications of Gödel's incompleteness theorem? The incompleteness theorem raises the possibility that P vs. NP is independent of the current foundations of mathematics. But this is considered unlikely by most researchers. Many difficult theorems have been proved in the past; some of them had been open for centuries (for example Fermat's last theorem). The fact that a theorem is difficult is no reason to think that it is beyond solution.

This leaves one question which you haven't asked: Why do we care about relativized results? I don't know the historical reason. It might be that these techniques are commonplace in related ares that served as sources of inspiration. At the very beginning, people might have expected that relativized results do imply absolute results. A good example is the random oracle hypothesis, which states that if a complexity theory statement holds with respect to a random oracle, then it holds absolutely. For example, although the P vs. NP is "undecided" with respect to an arbitrary oracle, Baker, Gill and Solovay showed that P$\neq$NP with respect to a random oracle. Does that imply that P$\neq$NP? The fact that IP=PSPACE disproved this hypothesis. Since that point, much less attention has been given to oracle results, and they are now quite unfashionable. They have become an object of study in their own right, but with no pretensions to be relevant for separating P from NP.

Endnotes:

The usual axiomatization of Peano arithmetic actually uses a finite number of axiom schemes. Gödel's result holds in even greater generality, as Andrej Bauer indicates in his thoughtful comments.
See Andrej Bauer's comments for a dissenting opinion.


Language of the graph of an affine function Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). Let : be a symbol distinct from any digit. Let $a$ and $b$ be integers, with $a > 0$. Consider the language of solutions of the Diophantine equation $y=ax+b$:

$$L = \{ \bar{x} \mathtt: \bar{y} \mid y = a\,x + b \}$$

Is $L$ regular? context-free?

(Contrast with Language of the values of an affine function)

(Follows on How can solutions of a Diophantine equation be expressed as a language?)

 I think this would make a good homework question, so answers that start with a hint or two and explain not just how to solve the question but also how to decide what techniques to use would be appreciated.

Hint:

$53 \cdot 100000010000000000 + 4 = 5300000530000000004$.

Sketch:

   Assume $a$ has $n$ digits and $b$ has $m$ digits.

 If $\overline{x}=10^k \underbrace{00\dots01}_{n}0^l\underbrace{00\dots0}_{m}$ for some $k,l$ then

 $\overline{ax+b}=\overline{a}0^k \overline{a} 0^l \overline{b}$.

 If $L$ was context-free, then

 $$L'=L \cap 10^{\ast}0^{n-1}10^{\ast}0^m \mathtt: (0+1+2+...+9)^{\ast} = \{10^{k+n-1}10^{l+m} \mathtt: \overline{a}0^k\overline{a}0^l\overline{b}:k,l \in \mathbb N\}$$
 would be context-free as well.

 Given a PDA $M$ for $L'$ we could construct a PDA $N$ for $\{a^n b^m c^n d^m\}$ , a well-known non-context-free language. $N$ simulates $M$, but it is "feeding" different letters; it is a composition of $M$ with a transducer. Initially, $N$ behaves as if $M$ read $1$. Then, consecutive $a$'s are interpreted as $0$'s. Next, $N$ behaves as if $M$ read $0^{n-1}1$, and treats consecutive $b$'s as $0$'s, then as if it read $0^m \mathtt: \overline{a}$ etc.


Finding any $\epsilon$ vs finding minimal $\epsilon$ for case 3 of Master theorem I have a recurrence relation:
$$T(n) = 3T(\frac{n}{4}) + n\lg n$$

and I want to prove that $T(n) = \Theta(f(n))$ using Master theorem. There's also an example in my textbook on this relation, they're choosing  $\epsilon = 0.2$. For example:

$$n^{\log_b a}=n^{\log_4 3} \Rightarrow   n\lg n = \Omega(n^{0.79+\epsilon})$$

Why would we choose $\epsilon = 0.2$, why couldn't we have chosen something like $\epsilon = 0.0001$, wouldn't this already be enough?

First, note that $\log_4 3 = 0.792...$.  Now the key observation is that $n^{0.792..}$ grows asymptotically slower than $n \lg n$, i.e., $n^{0.792...} = O(n \lg n)$, or if you prefer, $n \lg n = \Omega(n^{0.792...})$.  Why?  Well, one way to see it is to notice that $n^{0.792...} = O(n)$ and $n = O(n \lg n)$: $n^{0.792...}$ grows asymptotically slower than $n$, because the exponent is smaller; and $n$ grows asymptotically slower than $n \lg n$.

What's up with the $\epsilon=0.2$? That's probably a clunky way of getting at the fact that $n^{0.792...}$ is smaller than $n^{1.000...}$.  In particular, $0.792 + 0.2 < 1.0000$.  Personally, I don't find it a particularly helpful explanation for why $n^{0.792...} = O(n)$, so I would suggest you ignore it.  If you find it confusing, it's not just you, and it doesn't represent some shortcoming in your understanding; it just seems like a confusing way to explain it to me.


Why is the tape not part of the definition of a Turing Machine? I've wondered why the tape/tapes are not part of the formal definition of a Turing Machine.  Consider, for example, the formal definition of a Turing machine on Wikipedia page.  The definition, following Hopcroft and Ullman, includes: the finite set of states $Q$, the tape alphabet $\Gamma$, the blank symbol $b \in \Gamma$, the initial state $q_0\in Q$, the set of final states $F\subseteq Q$, and the the transition function $\delta:(Q\backslash F)\times \Gamma\rightarrow Q\times\Gamma\times\{L,R\}$.  None of which is the tape itself.

A Turing Machine is always considered to work on a tape, and the transition function is interpreted as moving its head, substitution of symbol and changing state. So, why is the tape left out of the mathematical definition of a Turing machine?

From what I can see, the formal definition in itself doesn't seem to imply that the Turing Machine operates like it's often described informally (with a head moving around on a tape).  Or does it?

To formally define an instance of a Turing machine (not the general concept) you don't need to explicitly mention the tape itself, or its contents. To denote a configuration of this particular machine, or a computation performed by it, that is when you need some form of notation to describe the contents of the tape.


Is NP-hard closed against cartesian product with arbitrary languages? If $L_1$ is NP-hard, $L_1 \times L_2$ is NP-hard for every $L_2 \neq \emptyset$, where

$\qquad \displaystyle L_1 \times L_2 = \{(w_1,w_2) \mid w_1 \in L_1, w_2 \in L_2\}$

Is it true or false and why?

I can't prove it but I also don't find counter example.

$L_1 \times L_2$ is NP-hard.

Proof: Let $L$ be a language in NP, let $f$ be a reduction of $L$ to $L_1$ and let $w_2$ be in $L_2$. Define $g(x) = (f(x), w_2)$. Now $g$ is a polynomial time many-to-one reduction of $L$ to $L_1 \times L_2$ because clearly:

$x \in L \quad \Longleftrightarrow\quad (f(x), w_2) \in L_1\times L_2$


Smallest multiple of a number that gives a specific remainder modulo another number Given three positive integers $a, b$ and $c$, my task to find the smallest positive integer $k$ such that $(k * a) \mod b = c$.
I can obviously try values of $k$ from $1$ and higher, until I find the right value. My question is, can this computation be done in $O(1)$ time? That is, is there a direct way to calculate the smallest integer value of $k$ such that $k*a - c$ is a multiple of $b$?

Using Congruent Modulo Notation, one can rewrite the problem as:

$$a*k \equiv c\pmod{b}$$
This is a simple linear congruence, that can be solved using the Extended Euclidean Algorithm

There are other algorithms, but this one is the simplest.

According to Wikipedia:

  In big O notation, this algorithm runs in time $O(\log(m)^2)$, assuming
  $|a| < m$, and is considered to be very fast and generally more
  efficient than its alternative, exponentiation.

Where $m$ is the letter $b$ in your example


Concept of reduction and algorithm Suppose that someone found an algorithm A for a NP problem (that is not NP-complete) that uses an algorithm B for PSPACE-complete or #P-complete problem during execution. (Remaining part of the algorithm takes polynomial time.)

Then suppose there is also an algorithm C for a NP problem that uses the polynomial-consuming part of the algorithm A. The rest of the algorithm C is actually an algorithm that solves NP-complete problems.

Then would this mean that PSPACE-complete or #P-complete collapse to NP-complete?

If so or if not, why would it be like that?

I am asking this question, because I seem to get confused during reading my computation textbook.

Edit:
I was a bit confused as in (or more accurately scalar function) math, if g(x)=f(h(x)) and g(x)=f(q(x)), h(x) and q(x) must be virtually the same. So, my question was virtually the aforementioned. That was the parallel I was making between algorithm A and C.

I think I see where your confusion arises. Hopefully ;).

Suppose you have a problem $\Pi \in NP$, and two algorithms $\mathcal{A}$ and $\mathcal{B}$ that both solve $\Pi$.

Assume that $\mathcal{A}$ uses algorithm $\mathcal{A'}$ as a sub-algorithm, where $\mathcal{A'}$ is acutally an algorithm for a $PSPACE$-complete problem.

Also assume that $\mathcal{B}$ is the same as $\mathcal{A}$, but instead of using $\mathcal{A'}$ as a sub-algorithm, it uses $\mathcal{B'}$, which is sufficient to solve $\Pi$, but not to solve the $PSPACE$-complete problem.

I think this is the situation you want to describe?

Now I think your confusion comes from assume that because a problem has two different algorithms, that the algorithms must have the same complexity - at least this is what I get from the analogy with the functions.

This isn't true, you can quite happily have an algorithm which solves a problem, but is actually far more powerful (i.e. it can solve a much bigger super-problem) and another algorithm that can only solve the smaller problem. These two algorithms don't really say anything about one another (at least without a lot more information).

To stretch the function analogy to its breaking point, the situation is more like $g(x) \leq f(x)+h(x)$ and $g(x) \leq f(x)+ q(x)$. Sort of. But not really.


Making sure the Branch Target Buffer stays accurate As i've been told , a Branch Target Buffer (BTB) acts a lot like a cache for Branches , keeping a map of where branches are in the address space.

If implemented well , it should allow the processor to detect branches before even decoding them , redirecting the PC to the presumed target ( with the help of the branch predictor proper).

But the BTB is presumed to be accurate about where the branches are. You don't want the processor to jump when encountering an ADD instruction for example , meaning the instruction PC has to be an exact match with what is in the BTB.

Here's my question :

Most Processors support self modifying code (for better or for worse). This means that a branch instruction in main memory has the potential to be overwritten by data or another instruction.
If said branch is already present in the BTB , this could result in BTB information being stale. In such a case , the processor might jump in response to a non-existent branch , resulting in an incorrect program result.

My initial solution to this was to just compare every memory write against what is present in the BTB. But this would be inefficient (requiring additional ports and potentially slowing down the machine) and most memory writes to not overwrite branch instructions or instructions at all for that matter.

Is there a better way to do this? something i've missed ?

I've looked around already , but couldn't find any information .

The BTB is not really presumed to be accurate. It cannot be accurate. Even putting SMC aside, indirect and other variable-target jumps cannot have their target predicted perfectly. That is not a correctness problem though, the control flow instructions can be executed and at that point it becomes possible to verify the actual target and do the usual front-end-redirect and pipeline flush if the target does not match.

But that does not solve the SMC problem in general. If you need to make SMC work as if the processor is strictly serial, some extra checks are necessary. The checks can be quite conservative and still perform well when SMC isn't happening, which is usually the main case. For example, you can check whether a write is to a code page, and insert an appropriate flush (after the write) if it does. Of course such a coarse test is easily fooled by just marking a data page executable, even if it is never jumped into, needlessly degrading performance. An other strategy might be to check, at retirement of any instruction, whether its page is marked dirty (this makes SMC have a "long shadow", any modification "ruins" a code page until its dirty bit is reset). More precise mechanisms are possible.


NFA designing for strings starting with $01$ The question was asked

Construct an NFA with set of all strings that start with $10$.

The solution provided to me is

But my question is what if the automaton receives an input $0$ at the starting? Also there is no option for $q_1$ to transit after receiving $1$. So I think the solution should be

Please correct me if I am wrong.

Since this is an NFA, the solutions are equivalent. When you are in a state without any transition for the current input you receive, you terminate (equivalent to getting stuck in a non-accepting state without going out of it).


Kleene star closure of a context free grammar I have this question about closure of a context free grammar, and if someone can check my answer and see if it makes sense, and if not, what is missing, I would be very grateful.

  Give an counter-example to show that the following contruction fails in to proof that class of languages free of context is closed under the operation star. By A a language free of context that it is generated by the GLC G = {V,,R,S}. Add the new rule S -> SS e call the resulting grammar G'. That grammar is expected to generate a*"

I have only a superficial comprehension, I believe it is necessary that Rg', the set of production rules of G' must be equal to Rg united with {Sg'->SgSg'|e} or in another words Rg': Rg U {Sg'->SgSg'|e}. Even if that it is correct I don't understand why {Sg'->SgSg'|e} is necessary

There is a silly problem that you might need to add a production of the form $S\to\epsilon$, since otherwise you don't necessarily generate $\epsilon$. But the real problem is that $S$ can be used in the right-hand side of productions, and when you add the rule $S\to SS$, things could break. The "correct" way to turn a grammar of $A$ into a grammar of $A^*$ is to add a new start symbol $S'$ and the productions $S' \to S'S|\epsilon$.

In order to find a counterexample, think of the problems mentioned in the previous paragraphs, and try to find an example which manifests them. All it requires is some experimentation.


Max clique in interval graph According to Efficient algorithms for interval graphs and circular arc graphs there is an $O(n \log n)$ algorithm for finding the max clique in an interval graph, assuming you have the interval model. Unfortunately, neither the paper nor the references actually elaborate on what the algorithm is, beyond saying that you can modify the well-known algorithm for optimally coloring interval graphs (where you greedily color the graph in the order generated by sorting the intervals lexicographically) to compute the max clique. This makes sense, as the largest color used in an optimal coloring is the size of the max clique in a perfect graph (and interval graphs are perfect). Unfortunately, beyond that, I am lost as to how to compute the max clique. The obvious approach is to modify some data structure every time the max color increases, but I can't figure out precisely what data structure to use or how to modify it.

Does anyone know a reference for this algorithm or can reinvent a description of it?

Interval graphs are chordal graphs, so you can use a linear time algorithm for finding max clique in a chordal graph. This can be done by first finding a perfect elimination ordering, and then using the fact that every time a vertex is eliminated it forms a clique together with its neighbors that are not eliminated yet. Furthermore all maximal cliques appear in this process.

To find the perfect elimination ordering, maximum cardinality search (MCS) is the simplest algorithm and it works in linear time. (I don't know why Wikipedia mentions lexbfs first, it is much more complicated.)


first intersection of two arrays of integers - double binary search feasible? I'm interested to find the fastest possible way to find the first element of an intersection of two integers arrays (first match)

Looking for the 'fastest' algorithm I have seen different methods with different time complexities (to calculate the arrays intersection)

i.e: $O(N+M)$, $O(N * log(M)$,...

Also I have seen some references to an algorithm able to do this by implementing a double binary search to find the first match with time complexity $O(log(n)+log(m))$

Do you know about some reliable source or pseudo-code about this algorithm if such exists?

There is a double binary search algorithm.  It will only work is both lists are sorted.  It is basically as follows.

Check the first, lowest number on each list. Compare the numbers to find which number is higher. Assume that higher number is in List A
Take that higher number and do a binary search for it in list B.
If found done.
If not found take the number above the last search location in list B
For example, assume list A had a 5, and in list B you do a binary search and find 6 and 4 with no five in between.  Take the 6 from list B.
Do a binary search for that value is list A.
If found done
If not found take the number above the last search location in list A.
Repeat steps 3–7 switching back and forth between lists.

That is the basic idea, if you want further information, let me know.


What is the fastest and most elegant way to change a matrix dimension? I have been writing code for a paper and I'm reading an image in RGB space in OpenCV which means that its read as a 3D matrix (HEIGHT x WIDTH x 3 (RGB) ).
I'm reshaping the image into a 2D matrix ( NB_PIXELS x 3 (RGB) ) using this code :
image = image.reshape(len(image) * len(image[0]), len(image[0][0]))

This reshaping process is an important step in the method that I'm going over in the paper.
Since I can't have the paper depend on a library like NumPy I would like a more elegant way to explain the reshaping. Are there any papers that I can reference or any equations, methods ..etc that I can use as a replacement to the code that I shared ?
Thank you!

I would consider a sentence such as this to be unambiguous:

We flattened the $h \times w \times 3$ input data down to a two-dimensional $hw \times 3$ shape.

I don't believe a reference explaining this would be necessary.


What is the complexity of the emptiness problem for 2-way DFAs? I'm wondering, what is the time-complexity of determining emptiness for 2-way DFAs? That is, finite automata which can move backwards on their read-only input tape.

According to Wikipedia, they are equivalent to DFAs, though the equivalent DFA might be exponentially larger. I've found state complexity for their complements and intersections, but not for their emptiness-testing.

Does anyone know of a paper where I could find this?

Friend Google suggests the following "The PSPACE-completeness of the emptiness problem for two-way deterministic finite-state automata in Exercise 5.5.4 is due to Hunt (1973)."
(An Introduction to the Theory of Computation, Eitan Gurari, Computer Science Press, 1989, online)

Hunt, H. (1973). "On the time and tape complexity of languages," Proceedings of the 5th Annual ACM Symposium on Theory of Computing, 10-19.

(I have now looked at the reference) The paper is written in an abstract way as you note. The crucial part for us is the proof of Thm 3.7, where it is suggested that one can construct a 2FSA $\cal A$ that accepts valid computations of a linear bounded automaton $\cal M$ on a fixed(!) string $x$ (which is close to the definition of PSPACE). The 2FSA $\cal A$ is constructable in polynomial time (in the size of $\cal M$ and $x$). A computation of a LBA can be written as $x\$x_1\$\dots\$x_n$ where the $x_i$ are all of the same length as $x$ and are consecutive steps of $\cal M$. How does $\cal A$ check that $x_i$ and $x_{i+1}$ are equal (up to a very local change of a state and a single symbol as the operation of a LBA)? By checking letter by letter, going both ways on the tape. For that we need a counter of size $|x|$ implemented in the finite state control of $\cal A$.

It turns out that the problem is mentioned in the appendix of the classic reference by Garey & Johnson, Computers and Intractability, problem [AL2] "Two-way finite state automaton non-emptiness" with the explicit remark "PSPACE-complete even if $\cal A$ is deterministic". Reference again Hunt, with the clarification "Transformation from Linear Bounded Automaton Acceptance" (Given LBA $\cal A$ and input $x$, does $\cal A$ accept $x$?). The latter problem is [AL3] with reference to the famous Karp (1972) paper "Reducibility Among Combinatorial Problems" (where LBA Acceptance is mentioned as Context-Sensitive Recognition).


Recommendation for good book or online course on distributed programming I am a computer science student in his final year on the university with several years of experience in software engineering. I want to take me to the next level in programming web applications.
I am looking for a good book or online course on the subject of distributed programming with in-depth understanding, and how to design and build large and scaled web applications professionally like facebook, amazon, google from scratch.
By the way, I will be happy to hear also about a good book or online course which explain about all the new technologist that web application can connect/interact with like: AI analysis, databases, cloud computing and so on.
Thanks in advance.

This is awesome book:
Designing Data-Intensive Applications
https://www.amazon.com/Designing-Data-Intensive-Applications-Reliable-Maintainable/dp/1449373321
You may find the review here:
https://www.goodreads.com/book/show/23463279-designing-data-intensive-applications


Algorithm chalenge: find minimum range to cover all houses with light N houses are located on a straight street which has K streetlights. Each streetlight has range R. Given N and K how to find minimum value for R?
N is an array containing location of each house.
K is an integer value.
I am unable to identify the algo for this. I tried solving by taking location of 1st and last house, then dividing by K, this will give me max range of each streetlight. However, assume N=[3,4,5,10,13] and K=3. With division this wont work.

This is a known problem: https://binarysearch.com/problems/Minimum-Light-Radius
Key Idea: Binary search for the diameter, then use that to find the radius.


Understanding SLDNF-forest I am trying to understand this program and the respective forest. This is from the book Logic,Programming and Prolog by Ulf Nilsson.

Question:

In the main tree, why from ←off_gound(a) can you derive ⧠ ?
In the main tree, why was chosed on(b,a) first instead of on(c,b)?

Could someone please explain this?

Thank you so much in advance.

To answer your first question: SLDNF resolution employs negation as failure to deal with negation.

So from ←$\neg$off_ground(a) we derive ⧠ by trying to derive ←off_ground(a) and failing (i.e. deriving FF).
This is done in the upper tree on the right hand side.


Follow set confusion about inclusion The book I am learning about compilers from states that $M \to \alpha N \beta$
will generate a constraint that $\mathrm{FOLLOW}(M)$ is contained in $\mathrm{FOLLOW}(N)$ when $\beta$ is nullable.

This is a bit confusing because there can be other productions such as $M\to \gamma K \theta $.  Logically, then, the set of symbols which can follow $M$  can also be the set of set of symbols that can follow $k$ if $\theta$ is nullable and can be different from $\mathrm{FOLLOW}(N)$.

As such both $\mathrm{FOLLOW}(N)$  and $\mathrm{FOLLOW}(K)$ should be included in $\mathrm{FOLLOW}(M)$. Shouldn't it be like this?
What might be the reasons behind the statement in the book?

If the grammar includes $M \to \alpha N \beta$ and $\beta$ is nullable then anything which could follow $M$ could also follow $N$. In other words,

$FOLLOW(M) \subset FOLLOW(N)$

So we need to add everything in $FOLLOW(M)$ to $FOLLOW(N)$. It does  not oblige us to alter $M$'s follow set.

If there is also $M \to \gamma K \theta$ with $\theta$ nullable, then similarly we have

$FOLLOW(M) \subset FOLLOW(K)$

so we also have to add everything in $FOLLOW(M)$ to $FOLLOW(K)$. That implies that the FOLLOW sets for $N$ and $K$ are not disjoint, but it really says nothing interesting about $M$'s FOLLOW set.


Nyquist theorem, sample meaning Given that this wave was sampled at a sampling frequency f:

Why does the wave sampled at a sampling frequency 3f/2 look like this?

What does 3f/2 mean? Does it mean that we sample every 2 waves 3 times?

The wave is the whole curve: you shouldn't think of your first diagram as showing "four waves" as if you were counting waves from the sea hitting the beach. Although your graphs aren't labelled, the horizontal axis is likely intended to be time, not distance, and the graph shows the oscillation of a single particle over time.  So the dashed line shows the movement of the particle over time: think of it as moving up and down.

The sampling frequency is the number of times per second that you measure the particle's position. In the first diagram, the measurements all happen when the particle is in the same place so sampling at that particular frequency causes you to believe that the particle isn't moving at all (the orange line). In the second diagram, we're sampling $3/2=1.5$ times more often so, now we see the particle in different positions and, in particular, we see that it's not stationary.

Note that the two diagrams are drawn at different scales, which isn't very helpful.


Polynomial-Time reduction from Partition to MakeSpan Partition Problem:

Input: $A:=$ {$a_{1}, ..., a_{n} $}. $a_{i} \in \mathbb{N}$ $\forall i \in$ $\{1, \ldots, n\}$.

Question: Exists a subset $A_{1} \subset A$ with: $\sum_{a_{i} \in A_{1}} a_{i} = \sum_{a_{i} \in A\setminus A_{1}} a_{i}$ ?

Output: Yes or No.

Makespan Problem:

Input: Jobs $J$ and $b \in \mathbb{N}$.

Question: Exists a Schedule $S$ with $\text{FinishTime}(S) \leq b$ ?

Output: Yes or No.

So I have to change the Makespan Problem in a way that the Partition Problem gives me the correct answers for the Makespan Problem. $Partition \leq_{p} Makespan$

First Problem: When the Makespan Problem has $m$ machines and not two, I don't know how I can use Partition for that scenario. I could recursive iterate the jobs (so that I split Makespan in several Partition Problems) but then I had to use the Partition Problem several times and with my understanding, I am only allowed to change the Input for a Polynomial-Time Reduction.

But let's say we have $m= 2$ machines. If Partition has the Output "Yes", I know that there exists an optimal solution for the Makespan, so that I have an optimal Schedule with value= $\dfrac{1}{m} \cdot \sum_{a_{i} \in A}$. If $b \leq \dfrac{1}{m} \cdot \sum_{a_{i} \in A}$, the result for Makespan is also Yes.

Second problem: But what happens if there is no optimal solution? I only receive "No" from Partition but I don't know how bad the Partition result is.

I would be really happy if someone has an idea for this, I don't know how to I could find a solution for this.

Given an instance of partition (i.e., a set of numbers) $\{a_1, \dots, a_n\}$ create an instance of Job Scheduling (what you call Makespan) with $2$ machines and $n$ jobs $j_1, \dots, j_n$, where the execution time of the $i$-th job is $a_i$.
Pick $b = \frac{1}{2} \sum_{i=1}^n a_i$.

If there is a solution to the partition problem, i.e., a set $A \subseteq \{a_1, \dots, a_n\}$ such that $\sum_{a \in A} a = \frac{1}{2} \sum_{i=1}^n a_i$, then there is a solution for the job scheduling problem: simply assign $j_i$ to machine $1$ if $a_i \in A$, and to machine 2 otherwise.

If there is a solution to the job scheduling problem, i.e., a partition of jobs into $M_1$ and $M_2$ such that $\max\{ \sum_{j_i \in M_1} a_i, \sum_{j_i \in M_2} a_i \} \le b$ then there is a solution $A$ to the partition problem.
The choice of $b$ implies $\sum_{j_i \in M_1} a_i = b = \frac{1}{2} \sum_{i=1}^n a_i$, therefore it suffices to select $A = \{a_i \, : \; j_i \in M_1 \}$.


What is the best complexity of finding a minimum in a matrix? Given a matrix $\mathsf{a}$ of size $K\times N$, what is the best complexity of finding the minimum value?

Here is a pseudo code:

function find_min(a)
    imin, jmin = 1, 1
    for k = 1 to K
        for n = 1 to N
            if a[k, n] < a[imin, jmin]
                imin = k
                jmin = n
    return imin, jmin

The above function needs $O(K\cdot N)$ operations. However, I think we can reduce the complexity to $O(\lg K\cdot N)$ using a heap. Am I right? Can we do better than a heap? If so, what is the best complexity of such a function?

You can't find the minimum without reading all values, due to an adversary argument. The adversary pretends that the matrix is the zero matrix, that is, whenever you ask for some value in the matrix, it answers zero. If you haven't queried some entry, then the algorithm cannot distinguish between two possibilities: that the matrix is entirely zero, or that it is zero apart from the entry, which has value –1. The minimum in both cases is different, so the algorithm can't be correct.


Path cover with paths of bounded length, in the plane I have a weighted, undirected, Euclidean complete graph $G$, a special vertex $r$, and an upper bound $b$.  I want to find a minimum-cost path cover that covers all vertices of $G$, subject to the restriction that every path must have length at most $b$ and every path must start at the vertex $r$.  In other words, I want to minimize the sum of the lengths of the paths, subject to the requirement that the paths cover every vertex at least once and each path starts at $r$ and has bounded length.

Are there any algorithms for this problem that will be effective on medium-size graphs (with, say, at most 200 vertices)?  This problem smells likely to be NP-hard; if so, are there exact algorithms that are more efficient than naive exhaustive search or heuristics that are likely to work well in practice?

Recall that the length of a path is the sum of the lengths of the edges it contains.  Also, a path cover is a collection of paths such that every vertex belongs to at least one path.  A Euclidean complete graph is a graph where each vertex represents a point in the plane, there is an edge between every pair of vertices, and the length of that edge whose length is given by the Euclidean distance between those two points.  (It follows that, without loss of generality, we can assume no two paths have any vertex in common other than $r$.)

This question is motivated by Location Selection Algorithm in Solar Engineering.

This smells like a problem that might be NP-hard, so you'll probably have to
use one of the standard methods for dealing with intractability: e.g., devise
a heuristic, or formulate it so you can apply an existing solver.

I suggest that you try formulating it as a mixed integer linear programming
(ILP) problem, and if that's too slow, try simulated annealing.  I'll sketch
both approaches.

Integer programming

We'll think of our task as selecting a subset of the edges, so that they can
be pieced together into paths as required.  Introduce a zero-or-one variable
for each edge to indicate whether or not it is selected.  In other words, for
each pair of vertices $i,j$, introduce a zero-or-one variable $x_{i,j}$, with
the intended meaning that $x_{i,j}=1$ implies the edge $(i,j$) is included.

We'll add a bunch of inequalities that capture the requirement that the
selected edges form a bunch of paths of the desired form:

Each vertex (other than $r$) has exactly one edge out of it:
$\sum_j x_{i,j} = 1$ for each $i \ne r$.
Each vertex (other than $r$) has at most one edge into it:
$\sum_i x_{i,j} \le 1$ for each $j \ne r$.
$r$ has no edges coming out of it: $x_{r,j} = 0$ for all $j$.
For each vertex $i$ introduce a variable $y_i$ (not restricted to integer
values), with the intended meaning that $y_i$ captures the distance from
$r$ to $i$ along the harness that connects the two.  We'll require that
no harness is longer than the limit: $y_i \le b$ for all $i$.  Also
$y_r = 0$.
Finally, we'll ensure the consistency of the $x$'s and $y$'s by adding

$$y_i \ge y_j + \ell(i,j) - (b + \ell(i,j)) (1-x_{i,j})$$

for all $i,j$, where $\ell(i,j)$ is the length of the edge $(i,j)$.
(Notice how this works: if edge $(i,j)$ is not selected, i.e., $x_{i,j}=0$,
this inequality implies only $y_i \ge 0$; but if edge $(i,j)$ is
selected, this inequality ensures that $i$'s distance from $r$ is
$j$'s distance from $r$ plus the length of the edge between $i$ and $j$.)

Now ask an ILP solver to minimize the objective function
$\sum_{i,j} \ell(i,j) x_{i,j} $, subject to these inequalities.
The solution will correspond the optimal solution to the original problem.

You'll have to test to see whether existing off-the-shelf ILP solvers
(e.g., CPLEX) are able to solve this ILP instance efficiently.  You end
up with an ILP instance with about $|V|^2$ variables and inequalities.  If it takes too long, some solvers will have an option to specify a "timeout", so they give you the best solution they've found so far within the specified time, even if it isn't necessarily the globally optimal solution.

Some minor optimizations are possible.  For instance, we can omit any
edge $(i,j)$ whose length exceeds $b$ (eliminating the variable $x_{i,j}$
from the linear program, as it is forced to be zero).  Also, for any pair
of edges $(i,j),(k,l)$ that "cross" (i.e., their line segments intersect),
we know they can't both be simultaneously selected, i.e., we can add the
inequality $x_{i,j}+x_{k,l}\le 1$.  You probably don't want to add all
such inequalities, but you could try adding a small number (e.g., for
all pairs of short edges).  You can also add the inequality $y_i \ge \ell(r,i)$ for all $i$, in case that helps the solver.

This approach is also fairly flexible: for instance, we can limit the number of
paths that are allowed to be used (by adding an inequality to upper-bound
$\sum_i x_{i,r}$) or make other minor adjustments.  You can limit the number of edges allowed in each path by adding variables $z_i$ that count the number of hops between $i$ and $r$ along the harness connecting the two, and adding the inequality $z_i \ge z_j + 1 - K (1-x_{i,j})$ where $K$ is a suitably large constant (larger than the maximum number of edges per path) and then adding inequalities to upper-bound all of the $z_i$'s.

Simulated annealing

Another option is to use some form of local search, such as simulated
annealing.  The idea is that we start from a candidate solution and at
each step try making a small, randomly selected, local change and check
whether it is an improvement or not.

Part of the art of simulated annealing is to choose a set of allowable
changes; at each step, you'll randomly select from this set to obtain
your candidate change.  In this case, one reasonable class of "changes"
is: Pick a pair of vertices (probably ones that aren't too far apart),
and swap which paths they are in.  For example, suppose I've selected
vertex $b$ and vertex $e$, where the path containing $b$ looks like
$\cdots \to a \to b \to c \to \cdots$ and the path containing $e$ looks
like $\cdots \to d \to e \to f \to \cdots$.  Then after the swap operation
you'll end up with the two paths $\cdots \to a \to e \to c \to \cdots$
and $\cdots \to d \to b \to f \to \cdots$.  You can then evaluate whether
this increased or decreased the objective function.  You might want to
experiment with the distribution on pairs of vertices (do you try to
make nearby vertices more likely to be selected than far-apart ones?).

There may be other operations that would be useful to add and make
simulated annealing work better.  Selecting an appropriate set of
operations and choosing the parameters for simulated annealing is largely an art, and may require some experimentation.  It's hard to predict how well this will work without trying it.


Intuition behind min cut in a flow network? Whether it's baseball elimination or project selection I was wondering if someone can give me a general definition of a min-cut besides it being the max flow of a network.

For example, in the baseball elimination problem, if we wanted to find out if team z is eliminated, the min cut represents the team(s) that will beat team z out of the 1st place if the edges aren't full saturated. If the edges are fully saturated, then min-cut is everything except t, and team z still has a chance.

For the project selection, the min cut contains the projects you should do to maximize your return.

How do people figure out that min-cut can be applied to these problems? What is it about min-cut that gives it such power?

Thank you!

Given a weighted directed graph and two nodes $s,t$, an $s$-$t$ cut is a set of edges, upon whose removal $t$ is not reachable from $s$. The weight of the cut is the total weight of edges removed. A minimum $s$-$t$ cut is one of minimum weight.

A similar definition works for undirected graphs and in the special case in which the graph is unweighted, in which all edges have unit weight.

If we think of a weighted digraph as a flow network with source $s$ and sink $t$, then any $s$-$t$ cut gives a restriction on the weight of any flow in the network, which must be at most the weight of the cut. The min cut max flow theorems states that the weight of a minimum $s$-$t$ cut coincides with the weight of the maximum flow. However, a cut and a flow are two very different things.

There's a related definition of cut which works just for undirected graphs.
A cut in an undirected graph is a set of edges whose removal disconnects the graph. (Any $s$-$t$ cut is a cut.) A minimum cut is one of minimum total weight (or, in the unweighted case, of minimum cardinality).

One reason that cuts are so powerful is that they can be found efficiently.


Creating sum of all numbers within a sequence Write an algorithm that, given sequence seq of n numbers where 3 <= n <= 1000 and each number k in seq 1 <= k <= 200, finds maximum sum by repeatedly removing one number from seq, except for first and last number in seq, and adding its value to sum of two adjacent numbers. Algorithm ends when there are only two numbers left.

For example:
Max sum for sequence [2, 1, 5, 3, 4] is 31.

So far I've written brute force algorithm checking all possible combinations but it's not well suited for large sequences.

public static int solve(ArrayList<Integer> seq, int sumOfRemoved) {
  if (seq.size() == 3) {
    return seq.get(0) + seq.get(1) + seq.get(2) + sumOfRemoved;
  }
  LinkedList<Integer> maxValues = new LinkedList<>();
  for (int i = 1; i < seq.size() - 1; i++) {
    ArrayList<Integer> clone = (ArrayList<Integer>) seq.clone();
    clone.remove(i);
    int sum = seq.get(i - 1) + seq.get(i) + seq.get(i + 1);
    maxValues.add(solve(clone, sum));
  }
  int max = 0;
  for (int val : maxValues) {
    max = Math.max(max, val + sumOfRemoved);
  }
  return max;
}

My question is, is there more efficient algorithm solving this problem?

From the top of my head I would use a greedy approach, always remove the lowest available number so the potential sum of later steps lessens the least this way. But I do not have a proof for this finding the top possible sum, especially not at 0:21 on Monday :-).

With 2,1,5,3,4(0) it would go to 2,5,3,4(2+1+5=8), then to 2,5,4(8+5+3+4=20), and end at 2,4(20+2+5+4=31). So it finds your sum, but this is just one case.


Can not understand idea of the KMP algorithm I am using Sedgewick's Algorithms (4th ed) to learn Knuth-Morris-Pratt substring search algorithm. The key step is construct the DFA array corresponding to a given pattern. The authors say:

  The key observation is that the characters in the text that would need to be rescanned are precisely pat.charAt(1) through pat.charAt(j-1): we drop the first character to shift right one position and the last character because of the mismatch.

I can't understand the above, for example. If the pattern is ABABAC, and the text string is ABACABABACA.  and there are two pointers i and j for text string and pattern respectively.

If $i=3$, the character $c$ in the text string is mismatch, where the pattern is $b$. then we need to rescan from the beginning of the pattern. not the second character : pat.charAt(1) .

I think I am misunderstanding what the author intended to express. What does the author mean?

Sedgewick continues: "These are
pattern characters that we know, so we can ﬁgure out ahead of
time, for each possible mismatch position, the state where we
need to restart the DFA."

What I understand is that this quote tries to explain that if you encounter a mismatch at letter at position $j$ of the pattern you have to shift the patterns by one position against the text and see where that leads us. The point there is that we do not need to know the actual text at that moment, because we know that so far the patterns has matched the text and we can match the pattern to itself (shifted).


Characterizing the range of a polytime function Is it true that an infinite language is in P iff it is the range of a length increasing polytime function?  I ask because I know that it is a basic result in computability theory that a set is recursive iff it is the range of an increasing recursive function and I was wondering if there might be an analogue in complexity theory.

I know that the "length increasing" (or at least monotone increasing) is a necessary one because otherwise we could construct the Halting Problem:  Just have a polytime algorithm test computation histories for a given Turing machine $M$ on input $x$ and map valid halting ones to $(M,x)$.   I also know that every language in P reduces to any NP-complete language and these languages are not in P (unless of course P=NP), but I think my question might be different: I am interested in the exact image of a function over ${\Sigma}^{*}$ and not if it happens to be properly contained in an NP-complete set.  However, I don't know where to go from there. I would greatly appreciate any hints or counterexamples to demonstrate that my conjecture is false.  Thanks.

Your statement (with length increasing replaced with length non-decreasing and with functions allowed to return $\bot$, i.e. nothing) is equivalent to $\mathsf{P}=\mathsf{NP}$.

We start with two observations:

Every language in $\mathsf{P}$ is trivially the image of a length non-decreasing function (that's why we allow returning $\bot$).
If $f$ is a length non-decreasing polytime function then $y$ is in the range of $f$ iff there exists $x$ of length at most $|y|$ such that $f(x) = y$, and so the range of a length non-decreasing polytime function is always an $\mathsf{NP}$ set.

If $\mathsf{P}=\mathsf{NP}$ then the range of a length non-decreasing polytime function is always in $\mathsf{P}$, and so your (modified) statement is correct.

Suppose now that $\mathsf{P} \neq \mathsf{NP}$. Consider the language $\mathsf{SAT'}$, obtained from $\mathsf{SAT}$ by padding a formula of length $n$ with $n$ zeroes. The language $\mathsf{SAT'}$ is still $\mathsf{NP}$-complete and so not in $\mathsf{P}$. On the other hand, it is in the range of a length non-decreasing polytime function: the polytime function accepts a formula $\varphi$ and an assignment $x$, and if $x$ satisfies $\varphi$ it outputs the padded version of $\varphi$.

As I mentioned, you to allow the function to not decrease the length if you want $\Sigma^*$ to be the range of some function. On the other hand, the reasoning above works as long as the function doesn't decrease the length by too much: any polynomial amount (which could depend on the function!) would work.

You can also get rid of $\bot$ if you assume that the languages you consider are not too (efficiently) sparse, that is, given a length $n$, one can find in polytime some word in the language of length at least $n$. This is the correct counterpart of the condition of being infinite.


3SAT and directed graph Given a 3SAT instance (a Boolean expression in three conjunctural normal form), we draw a directed graph, where for each Boolean variable $x_{i}$ we have the nodes $x_{i}$ and $!x_{i}$; for each clause, for example $\left(x_{a} \vee x_{b} \vee x_{c}\right)$, we draw the following arrows $!x_{a}x_{b}$, $!x_{a}x_{c}$, $!x_{b}x_{a}$, $!x_{b}x_{c}$, $!x_{c}x_{a}$, $!x_{c}x_{b}$.
Is it possible understand from the graph if there is a variable $x_{i}$ such that $x_{i}\Leftrightarrow !x_{i}$ ($!x_{i}$ is $not\left(x_{i}\right)$)?

I think you are trying to build the 2-SAT implication graph for 3-SAT.
In 2-SAT, $(x_a \vee x_b)$ may indeed be considered as 2 implications, $\neg x_a \Rightarrow x_b$ and $\neg x_b \Rightarrow x_a$.
The problem is that $(x_a \vee x_b \vee x_c)$ is not equivalent to any of the 6 implications like $\neg x_b \Rightarrow x_a$, as $x_c$ is sufficient to satisfy the clause.
You may eventually have $(\neg x_a \wedge \neg x_b) \Rightarrow x_c$ or $\neg x_a \Rightarrow (x_b \vee x_c)$, but neither let you build such implication graph.


CFG for $L=\{ \omega \in \{ a,b,c,d \}^* : |\omega|_a = |\omega|_b \}$ Given the language:

  $$ L=\{ \omega \in \{ a,b,c,d \}^* : |\omega|_a = |\omega|_b \} $$

I propose the following grammar:
$$ \begin{align*}
S &\to \varepsilon \mid aSbS \mid bSaS \\
S &\to cS \mid dS \mid Sc \mid Sd
\end{align*} $$

I want to know if this is correct or if there exists a smarter grammar (a shorter grammar).

I'm going to address the second part of the question first, about a "smarter grammar." One improvement that can be made is omitting the rules

$$S \rightarrow Sc \hspace{10px}| \hspace{10px} Sd.$$

Assuming we have made that change, to answer the first part, if the grammar is correct we need to answer two questions.

Does $S$ only generate strings within $L$?
Can every string in $L$ be generated by $S$?

If the answer to these questions is both yes, then a string is in $L$ if and only if it is generated by $S$, which means that $S$ is a correct grammar for the language.

The answer to 1. is clearly yes because every string generated by $S$ must have the same number of $a$'s as it does $b$'s because in every rule where an $a$ is present a $b$ is also present, and vise versa.

The answer to number 2 is a bit trickier. We will use induction on $|\omega|_a = |\omega|_b$ to show that any string in $L$ can be generated by $S$

(Base case $n=0$) If $|\omega|_a = |\omega|_b = 0$, then $\omega$ consists of a sequence of $c$'s and $d$'s, and can be generated by scanning over it using the rules

$$S \rightarrow cS \hspace{10px} | \hspace{10px} dS$$

until we terminate with $S \rightarrow \epsilon$.

($n$ implies $n+1$) Assume by induction that for all $\omega \in L$ with $|\omega|_a = |\omega|_b \leq n$ that $\omega$ can be generated by $S$. Now let $\omega' \in L$ be such that $|\omega'|_a = |\omega'|_b = n+1$.

At some point in $\omega'$ there must be at least one time that an $a$ comes before a $b$ (with only $c$'s and $d$'s between them) or a $b$ comes before an $a$ (with only $c$'s and $d$'s between them). Without loss of generality, we can assume there is an $a$ that comes before a $b$.

Now, we can decompose $\omega' = XaYbZ$ where $|X|_a + |Z|_a = |XZ|_a = n$  (and the same for $b$) and $Y \in \{c,d\}^*$ . This holds because we are taking one $a$ and one $b$ from $\omega'$ which had $n+1$ of each which leaves $n$ in the rest of the string, and we know that there is a pair of $a$ and $b$ with just $c$ and $d$ between.

Now we can get a little clever and observe that the string $XcZ \in L$ and $|XcZ|_a = |XcZ|_b = n$ and therefore, by the inductive hypothesis, $XcZ$ can be generated by $S$.

Now here's the tricky part. Consider the process that generated $XcZ$. At some point in the generation, we must have used the rule $S \rightarrow cS$ to generate the $c$ between $X$ and $Z$. If we instead chose to use

$$S \rightarrow aS^*bS$$

as the expansion where $S^*$ generates $Y$ as in the case where $n = 0$, and did everything else exactly the same, then what happens is we replace the $c$ in $XcZ$ with $aYb$, and get the string $XaYbZ$. This demonstrates that $\omega'$ can be generated by $L$ because we have just found a process by which it can be generated by $S$.

Therefore by induction on $|\omega|_a = |\omega|_b$ every string in $L$ can be generated by $S$.


Formulating the master theorem with Little-O- and Little-Omega notation In a lecture of Algorithms of Data Structures (based on Cormen et al.), we defined the master theorem like this:

  Let $a \geq 1$ and $b \gt 1$ be constants, and let $T : \mathbb{N} \rightarrow \mathbb{R}$ where $T(n) = aT(\frac{n}{b}) + f(n)$, then
  $ \\ T\in\left\{\begin{matrix}
\Theta(n^{\log_b{a}}), & \text{ if } f \in O(n^{log_b{a}-\epsilon}) \text{ for some } \epsilon > 0. \\
\Theta(n^{\log_b{a}} \log{n}), & \text{ if } f \in \Theta(n^{\log_b{a}}). \\
\Theta(f), & \text{ if } f \in \Omega(n^{\log_b{a}+\epsilon}) \text{ for some } \epsilon > 0 \\
& \text{ and if the regularity condition holds. }
\end{matrix}\right.$

When I first had to study this theorem, I found that for me personally, the meaning of $\epsilon$ was somewhat difficult to understand and memorise. I believe to have found a simpler way to write this theorem, and I am wondering if it can be used equivalently, or if there is a flaw in my reasoning.

Let's look at the first case in particular, $f \in O(n^{log_b{a}-\epsilon})$. For simplicitly, let's assume $\log_b(a) = 2$. If we choose an infinitesimally small value for $\epsilon$, then this case basically expresses that $f$ must be asymptotically less than or equal to $n^{1.999 \ldots}$. In other words, $f$ must be asymptotically strictly less than $n^2$. I am wondering if this means that we can write this first case of the theorem as $f \in o(n^{\log_b{a}})$ (and following the same logic, $f \in \omega(n^{\log_b{a}})$ for the third case), rather than the (IMO) more convoluted alternative?

I am wondering if this means that we can write this first case of the theorem as $f \in o(n^{\log_b{a}})$ (and following the same logic, $f \in \omega(n^{\log_b{a}})$ for the third case), rather than the more convoluted alternative?

That is indeed a natural attempt to understand that "convoluted" condition in simple terms. Unfortunately, it is not correct.
Here is a simple counterexample. Let $a=1$ and $b=2$, and let $T : \mathbb{N} \rightarrow \mathbb{R}$ where $T(n) = T(\frac{n}{2}) + f(n)$ and $T(1)=0$, where $f(n)=\frac1{\ln n} \in o(1)=o(n^{\log_21})$.
If the first case of master theorem still holds, we should have $T(n) \in \Theta(n^{\log_21})=\Theta(1)$. However,
$$T(2^m)=T(2^{m-1})+\frac1m=T(2^{m-2})+\frac1m+\frac1{m-1}=\cdots=\frac1m+\frac1{m-1}+\cdots+1.$$
Letting $m$ goes to infinity, we see that $T(n)$ is not bounded because the harmonic series diverges.

For the same or a variety of other reasons, the usage of an arbitrarily small positive constant, which is usually denoted by $\epsilon$ pops up constantly in different places, especially in asymptotic estimate and complexity analysis.  You may want to get used to it or even get addicted to it.

Exercise 1. Verify that for any $\epsilon>0$, it is not true that $\frac1{\ln n}\in o(n^{-\epsilon})$ although  $\frac1{\ln n}\in o(n^0).$
Exercise 2. Construct a counterexample for the master theorem where $a=4$, $b=2$ for

the first case where $f \in o(n^{\log_b{a}})$ instead of $ f \in O(n^{log_b{a}-\epsilon})$ for some  $\epsilon > 0$ and
the third case where $f \in \omega(n^{\log_b{a}})$ instead of $f \in \Omega(n^{\log_b{a}+\epsilon})$ for some $\epsilon > 0$

respectively.


Are there two kinds of polynomial hierarchy collapses? It seems to me that there are two different situations which get called ``PH collapse",

(1) That $\exists i \geq 1$ s.t $\Sigma_i ^p = \Sigma_{i+1}^p$
(2) That $\exists i \geq 1$ s.t $\Sigma_i^p = \Pi_i^p$

Are these two different independent situations?

AFAIK the only natural relation is that $\Sigma_i^p \subseteq \Pi_{i+1}^p \subseteq \Sigma_{i+2}^p$ and I don't think this is enough to make the two above scenarios be equivalent.

Is there any natural relation even between $\Sigma_i^p$ and $\Sigma_{i+1}^p$ or between $\Pi_i^p$ and $\Pi_{i+1}^p$? For some $k > i$, if one shows that $\Sigma_k^p \subseteq \Sigma_i^p$ does that say anything about $\Pi_k^p$ vs $\Sigma_i^p$ ?

Do both these scenarios lead to the conclusion that $PH = \cup _{j \geq 1} \Sigma_j^p = \Sigma_i ^p$ ? (If yes, then can someone kindly help with the proof?)

Roughly I guess the proof has to go like this :

That inductively assume that for some $k > i$ one has shown that $\Sigma_j^p \subseteq \Sigma_i^p$ $\forall j$ s.t  $i\leq j \leq k$. Now sit at the threshold of the inductive hypothesis — and take some $L \in \Sigma_{k+1}^p$ and by truncating the first quantifier construct a language $L'$ such that $\langle x,u_1\rangle \in L'$ iff $x \in \Sigma_{k+1}^p$ with its first existential quantifier fixed to $u_1$. This makes $L' \in \Pi_{k}^p$

Now I don't know... something needs to be claimed about $L' \in \Pi_{k}^p$ to show that $L \in \Sigma_i^p$. But I don't see what goes here.

Suppose that $\Sigma_i^p = \Sigma_{i+1}^p$ (and so $\Pi_i^p = \Pi_{i+1}^p$). Then every statement of the form $(\exists y_1) \cdots (Q y_{i+1}) f(x,\vec{y})$ for polytime $f$ is equivalent to another statement $(\exists y_1) \cdots (Q y_i) g(x,\vec{y})$ for polytime $g$.

Now suppose you have a predicate in $\Sigma_{i+2}^p$, say $(\exists y) (\forall z_1) \cdots (Q z_{i+1}) f(x,y,\vec{z})$. The inner $i+1$ quantifiers are a $\Pi_{i+1}^p$ predicate, and so they are equivalent to a $\Pi_i^p$ predicate $(\forall z_1) \cdots (Q z_i) g(x,y,\vec{z})$. Adding back the outer quantifier $(\exists y)$, we find that the original predicate is equivalent to a $\Sigma_{i+1}^p$ predicate, and so $\Sigma_{i+2}^p = \Sigma_{i+1}^p = \Sigma_i^p$.

In the same way, we show that $\Sigma_i^p = \Sigma_{i+1}^p$ implies $\Sigma_i^p = \Sigma_{i+j}^p$ for all $j$, so that $\mathsf{PH} = \Sigma_i^p$.

Note that $\Pi_i^p \subseteq \Sigma_{i+1}^p$. Indeed, if $(\forall y_1) \cdots (Q y_i) f(x,\vec{y})$ is a $\Pi_i^p$ predicate, then the equivalent $(\exists w) (\forall y_1) \cdots (Q y_i) f(x,\vec{y})$ is a $\Sigma_{i+1}^p$ predicate.

Since $\Pi_i^p \subseteq \Sigma_{i+1}^p$, we see that $\Sigma_i^p = \Sigma_{i+1}^p$ implies that $\Pi_i^p \subseteq \Sigma_i^p$ and so $\Pi_i^p = \Sigma_i^p$.

Now for the other direction. Suppose that $\Pi_i^p = \Sigma_i^p$, and consider some $\Sigma_{i+1}^p$ predicate $(\exists y_1) (\forall y_2) \cdots (Q y_{i+1}) f(x,\vec{y})$. The inner $i$ quantifiers are a $\Pi_i^p$ predicate, and so they are equivalent to some $\Sigma_i^p$ predicate $(\exists z_2) \cdots (Q z_{i+1}) g(x,\vec{y})$. Adding back the outer quantifier $(\exists y_1)$ and folding $y_1,z_2$, we obtain a $\Sigma_i^p$ predicate equivalent to our original $\Sigma_{i+1}^p$ predicate.

Summarizing, if $\Pi_i^p = \Sigma_i^p$ then $\Sigma_i^p = \Sigma_{i+1}^p$, and so (as we have seen above) $\mathsf{PH} = \Sigma_i^p$.


Are compilers able to detect alternating accesses to arrays and interleave them in memory? Is it possible to design a compiler which optimizes a loop in which arrays are accessed in alternate fashion? For example like this:

// int[] a,b
int sum = 0;
for(int i = 0; i < n; i++)
{
  sum += a[i] + b[i];
}

With the usual sequential array storage, a[i] and b[i] may be far away from each other in memory. Therefore, I think a good compiler optimization would detect that a[i] and b[i] are always accesses at the "same" time, and store the arrays interleaved, that is a[0] b[0] a[1] b[1] ... so that one memory access may retrieve both a[i] and b[i].

Some work has been done that matches your description. For instance:

Compiler-directed array interleaving for reducing energy in multi-bank memories. by Delaluz, V.  Design Automation Conference, 2002. Proceedings of ASP-DAC 2002. 7th Asia and South Pacific and the 15th International Conference on VLSI Design. Proceedings.

describes a such an optimization.


How to prove properties about a specific modular arithmetic equivalence Ever since I was introduced to modular arithmetic, I've had some trouble with it. I think it uses a part of my brain that I haven't used often. Anyways, I've been thinking about this specific equivalence:
$$a^3 \equiv 5 \, (\text{mod } 7)$$
And I have a hunch that no $a$ exists s.t. this equivalence is true. Simulating it, it's clear that there is a pattern: 6, 1, 6, 6, 0, 1, 1, 6, 1, 6, 6, 0, 1, 1, 6, 1, 6, 6, 0...

But I can't figure out how to formally prove 1. that this pattern is the actual pattern and as an extension, 2. that the equivalence above doesn't hold (it should be trivial if I can prove 1).

Can anyone help? Thanks so much.

You can prove it by calculating the value of $a^3 \bmod 7$ for $a=0,1,2,3,4,5,6$; if none of those yield 5, then you have proven the claim.

Why is this sufficient?  Well, if $a \equiv b \pmod 7$, then $a^3 \equiv b^3 \pmod 7$.  So, if there was any solution to $a^3 \equiv 5 \pmod 7$, then you could take $b = a \bmod 7$, and that would be another solution.  Now $b$ is one of $0,1,2,3,4,5,6$, so we've proven that if there is any solution, then one of $0,1,2,3,4,5,6$ must be a solution.  Conversely, if none of $0,1,2,3,4,5,6$ is a solution, then there is no solution whatsoever.

For the special case of squaring (rather than cubing), you might be interested in quadratic reciprocity, which is a more advanced technique that allows to check for the existence of solutions to such an equation.  There is also cubic reciprocity, though I'm not sure whether it leads to an efficient algorithm to check for solutions when you have a cube instead of a square.


Show that (2,3)-satisfability is np-complete First of all, I introduce (2,3)-satisfability:
Formulas are in CNF form, the special property is that each clause has $2$ or $3$ literals. Formula is satisfied iff only and only if there exists valuation such that:

clauses with two literals are treated normally - it sufficient to
satisfy one literal (also $2$ literals can be satisfied).
clauses    with three literals are treated specially - there are must
be    satisfied exactly $2/3$ of literals (no more, no less)

Show that checking if such formula is (2,3)-satisfable is np-complete.
I have no idea how to do it. Obviously, it is easy to show that it is in np,  but hardness doesn't seem that easy to show.

1-in-3-SAT is NP Complete: given a set of clauses, find a value assignment such that exactly 1 literal in each clause is made true (http://cs.nyu.edu/courses/fall14/CSCI-UA.0310-001/1in3sat.pdf).

Reduction from 1-in-3-SAT: negate every literal in every clause of the 1-in-3-sat instance. Now exactly two literals need to be made true in each clause instead of one to have an equivalent solution set. This is your (2,3)-satisfiabililty instance. We don't even need the clauses with two literals.

Example

1-in-3-SAT instance: (a,-b,c), (a, b, -c), (d, e, f)
equivalent (2,3)-satisfiability instance: (-a,b,-c), (-a, -b, c), (-d, -e, -f)


RSA encryption why does ed=1? So I fully understand the how the RSA algorithm works, but now I am trying to reason with the formula. I want to know:

  why the public key e and the private key d in the RSA encryption have
  to satisfy the equation ed = 1 mod (p − 1)(q − 1)?

Is it because of the standard modular arithmetic rule where 1 mod anything is 1, or is there a more to this answer?

The relation of $e$ and $d$ is set so that encryption and decryption are inverses of each other, that is, if you encrypt a message then the ciphertext decrypts to the original message. Encryption and decryption are
$$ c = m^e \pmod{n}, \quad p = c^d \pmod{n}, $$
where $n = pq$ is part of the public key, $m$ is the message, $c$ the ciphertext, and $p$ the decrypted plaintext. We want $p = m$, i.e.,
$$ m = m^{ed} \pmod{n}. $$
This equation holds for all $m$ iff $ed \equiv 1 \pmod{\lambda(n)}$, where $\lambda(n)$ is Carmichael's function. For $n = pq$, $\lambda(n) = \mathrm{lcm}(p-1,q-1)$. In practice, $\lambda(n)$ is replaced by Euler's function $\varphi(n) = (p-1)(q-1)$.


Using pumping lemma to prove irregularity of regular language - what is my error? I have a vital misunderstanding of the pumping lemma. In the following example I show an example of using it on a regular language to come to incorrect conclusions. What am I doing wrong?

L={ab}, assume the language is regular so by the pumping lemma there exists some n, and σ = αβγ and σ' = αβ^kγ ∈ L for all non negative k.

σ = aaabbb

α = aa

β = ab

γ = bb

then σ'= αβ^2γ for k=2, σ' =aaababbb

σ'∉ L, a contradiction, thus L is not regular.

L as described I know to be a regular language so I would expect to find ∈ L. This is due to my choice of β spanning across two characters but there is nothing I can find in the pumping lemma which forbids this.

The pumping lemma gives you a pumping length $n$ and $\alpha, \beta, \gamma$ under the conditions specified in it so that $\alpha \beta^k \gamma \in L$ for all $k \ge 0$. You do not get to choose $\alpha, \beta, \gamma$ as you please. Also, the pumping lemma works for all words of length at least $n$, not simply an arbitrary word $\sigma$.

The trick when using the pumping lemma, then, is picking a word longer than the pumping length and such that any decomposition into $\alpha, \beta, \gamma$ (obeying the conditions specified in the lemma) can be used to derive the contradiction that you need.


Time quantum assignment to processes In a book I am reading it is stated that an input/output intensive process should receive a higher time quantum whereas a computing intensive process on the other hand should receive a lower one. Here however, it is stated that:

  A short quantum is good because it allows many processes to circulate through the processor quickly, each getting a brief chance to run. This way, highly interactive jobs that usually do not use up their quantum will not have to wait as long before they get the CPU again, hence improving interactive performance.

That's basically the exact opposite to what's stated in the book. So my question is should the quanta for input/output intensive processes and computing intensive processes be high or low and why?

It depends on what you are trying to achieve, but generally i/o intensive jobs should receive a higher priority, and a small time quantum.

I assume you are asking about some variety of multilevel feedback queuing.  The idea behind multilevel feedback queue-based schedulers is to try to approximate shortest remaining time first scheduling, where you are trying to minimize the average time each process spends waiting while it is ready-to-run.

We assume each process goes through the following cycle:

ready-to-run: waiting for all higher-priority processes to finish using cpu.
running: for some amount of cpu time then perform a blocking i/o request.
sleeping: after making a blocking i/o request, the process sleeps, waiting for the response from the i/o system.

When the response comes back from the i/o system the process wakes up and is ready-to-run again.  We call the set of processes that are ready to run (the processes not blocked waiting for a response from the i/o system), the run queue.

If we were able to predict exactly how long each process needed the cpu before its next i/o request, then we wouldn't need to have quanta at all.  Every time a process made an i/o request (moving it from state running to state sleeping) or got a response from i/o (moving it from sleeping to ready-to-run) we would just find the process with the shortest remaining time to its next i/o request, and run it.

But we don't know exactly how long each process will use the cpu before its next i/o request.  So we have to guess (e.g., by keeping track of how long it took the last few times, and using the average of those as the guess), but we might be way off.  So we also start a timer with a length somewhat larger than our guess for the expected cpu usage.  If our guesses are very good, then the timer will never fire.  Instead, each process will either make an i/o request, causing itself to block and allowing some other process to run, or a response to an i/o request will return, preempting the currently running job and allowing us to perform a new scheduling decision.

Multilevel feedback queues approximate shortest remaining time first by having a few priority levels and moving jobs to lower priority when they use more than their allotted quantum.  The idea is over 50 years old:

Corbató, FJ; Daggett, MM; Daley, RC: An Experimental Time-Sharing System, AFIPS Conference Proceedings, Vol. 21, pp. 335-344, 1962.


How is Grover's Algorithm useful? I am at a loss when it comes to understanding how Grover's Algorithm gives any useful information. Suppose we have a 4-qubit states (|0⟩ to |15⟩), and we are searching for the state |3⟩. The oracle would thus be
O=I−2|3⟩⟨3|

And then, at the end, after all the amplitude amplification steps, we would get the state |3⟩ with a high probability, but does this give any new information, since we already used |3⟩ inside the oracle?

I know I am missing out something crucial, but I absolutely cannot put my finger on it.

Please help. Thank you.

The thing you're missing is that you aren't search for $|3\rangle$, you're searching for "the input that makes $f$ return true" where $f$ is some function.

For example, maybe $f$ is a discrete logarithm checker like $x \rightarrow 2^x \equiv^? 432821 \pmod{7438927891}$. Or $f$ could interpret its input as a claimed proof of the Riemann hypothesis, and check if that proof is correct. Anything you can imagine checking, $f$ could be that.

So Grover's algorithm is very very widely applicable. But unfortunately it also only gives a quadratic advantage, so "applicable" often doesn't translate into "useful". For example, the space of (reasonably sized) possible Riemann-hypothesis proofs is so huge that it laughs at square roots.


How many states when converting CFG to PDA When converting a CFG to a PDA I know that you get three main states, Qstart, Qloop and Qaccept. But Qloops will need a various amount of states, and my question is how many? Is there a way to find out the "worst case scenario" of how many states there can potentially be? I don't mean for one particular CFG, but in general. I'm having difficulties trying to figure out how I can calculate this...

When converting CFG to NPDA ,then to simplify the process, first convert the CFG to Greibach Normal Form(GNF). Now using three states: Qstart, Qloop and Qaccept, you can generate all transition rules for the NPDA.

To start the process add the transition: $ δ(Qstart,λ,z)=\{(Qloop,Sz)\}$ where S start variable and z is stack start symbol.

And add the following transition to get the NPDA into a final state:$ δ(Qloop,λ,z)=\{(Qaccept,z)\}$.

Now using the production rules of the CFG you can easily generate all the other transitions which includes only $Qloop$. And here the number of transitions depend on the number of production rules.


Procedure to automatically solve field theorems in a SMT solver I'm working with the Welder proof assistant. Basically, this system uses basic inference rules to modify the goal one wants to proof. At a latter step, the modified goals are passed to a SMT solver to see if it can prove them. I have already written automatic induction tactics that generate by themselves the induction hypothesis.

Now I want to write a procedure that will allow me to solve automatically the following problem:

  Proof basic field theory statements using the axioms of group and
  already proved lemmas.

Could you describe successful approaches to solve this problem?

Here I leave you the kind of axioms that I want to use:

And here you have the kind of goals I would like to proof automatically:

The idea is that the procedure is given the theorem, a list of lemmas (axioms of other proved theorems) and is able to deduce by itself the goal.

All of the theorems you want to prove (except uniqueAddNeutral) are of the form $\forall x . \phi(x)$ where $\phi(x)$ is quantifier-free.  Herbrandization is typically the first step towards proving those theorems: replace $x$ with an arbitrary constant $c$, with no assumptions made about $x$, and prove $\phi(c)$ holds without making any assumptions about $c$.

The theorems you want to prove are simple enough that exhaustive search over candidate proof trees might suffice to find a proof.  At each step, you apply one of the axioms, instantiating the universally-quantified variables in the axiom with appropriately chosen values.  You have to choose which axiom to apply and how to instantiate the variables; typically you instantiate each variable in the axiom with one of the subexpressions in the current expression/goal, so there are only finitely many choices at each step, and you can simply exhaustively search over all possibilities (up to a given size/depth).


Design an algorithm,have polynomial complexity for deciding satisfiability of a 1-conjective Normal Form boolean formula I undetstand each part of the word group in this question. I have search for a while but I still can't understand what the whole question want me to do. I will state what I know and give an assumption of what I should do, I would be appreciate if someone can guide me.

First a boolean formula is satisfiable if it can be made TRUE by assigning appropriate logical values, so "deciding the satisfiability" means to decide whether this boolean formula can be made a TRUE result.

Then for conjunctive normal form is means a conjunctive of clauses which are disjunctive inside. and 1-conjunctive normal form means each clause contains one variable, such like A\wedge B.

Now is the problem, what means an algorithm to decide it? I mean isn't the way to decide the satifiability of a boolean formula is try ture and false assiagnments to find whether it can be TRUE as a result? For example: since it is conjunctive normal form so each result of clauses needs to be TRUE, and it is 1-conjunctive normal form, so each variables need to be TRUE. Is this one an accpaptable algorithm to deal with the question?

Most satisfiability algorithms do actually find an assignment for the variables to satisfy the equation, but in your case (a conjunction of single variables) this is not necessary.

When the entire logic formula is just a single conjunction of variables, the only way it is not satisfiable is if it contains both $a$ and $\neg a$. If there is no variable which is contained both positive and negatively in the formula, the formula is satisfiable.


Given a regular language, show another language is regular I was hoping someone could help me with this question, since I'm having trouble determining what approach to take.

Let $L \subseteq \{0,1\}^*$ be a regular language. Show the language $\{w \in \{0,1\}^* | 1w \in L\}$ is also regular.

My idea is that whenever we're at the start state to compensate for the lack of the 1, you do an additional transition as if 1 was part of the input and then carry on reading the input as normal.

Since L is regular it has a NFA that accepts it $(Q,\Sigma, \delta, q_0, F)$. Then construct a new NFA $(Q,\Sigma, \delta', q_0, F)$ such that $\delta'(q,a) = \delta(q,a)$ for $q \ne q_0$ and $\delta'(q,a) = \delta(\delta(q,a),1)$ for $q = q_0$

Is this correct?

Your idea is right.

However, in general the initial state $q_0$ of a finite state automaton may also be used in other ways than just as a starting position, so the automaton may return to the state. Those later visits do not want to loose the letter $1$.

Are you sure the order $δ(δ(q,a),1)$ is correct?


Prove, using only the definition of $O()$, that $2^{\sqrt{x}}$ is not $O(x^{10})$ Prove, using only the definition of $O()$, that $2^{\sqrt{x}}$ is not $O(x^{10})$.

I have been doing a few exercises on Big O and this is the first time I have encountered the variable in the exponent.  I was wondering how to disprove this function.  Any help would be appreciated

Hint: Try converting both functions to the form $e^{f'(x)}$.


Is it decidable whether one language is polytime reducible to another? Let $L_1$ and $L_2$ be two decision problems.

Is there an algorithm deciding whether $L_1 \leq_P L_2$, that is, whether $L_1$ is reducible to $L_2$ in polynomial time?

I'm going to assume that your question is whether the language $$L = \{\langle M_1\rangle; \langle M_2\rangle\mid L(M_1)\leq_\mathrm{p} L(M_2)\}$$ is decidable, where $\langle M\rangle$ is the description of Turing machine $M$ and $\leq_\mathrm{p}$ denotes polynomial-time many-one reducibility.

This language is undecidable.

The only language that is many-one reducible to $\Sigma^*$ is $\Sigma^*$ itself.  This is because a many-one reduction from $X$ to $\Sigma^*$ must, by definition, map all "no" instances of $X$ to "no" instances of $\Sigma^*$. However, $\Sigma^*$  has no "no" instances, so the reduction can only exist if $X$ also has no "no" instances, i.e., if $X=\Sigma^*$.

So, now let $Y$ be any Turing machine that accepts every input.  The language $H=\{\langle M\rangle\mid \langle M\rangle;\langle Y\rangle\in L\}$ is clearly reducible to $L$. But $H$ is the language of Turing machines that accept every input, which is undecidable.


What parts of linear algebra are used in computer science? I've been reading Linear Algebra and its Applications to help understand computer science material (mainly machine learning), but I'm concerned that a lot of the information isn't useful to CS. For example, knowing how to efficiently solve systems of linear equations doesn't seem very useful unless you're trying to program a new equation solver. Additionally, the book has talked a lot about span, linear dependence and independence, when a matrix has an inverse, and the relationships between these, but I can't think of any application of this in CS. So, what parts of linear algebra are used in CS?

The parts that you mentioned are basic concepts of linear algebra. You cannot understand the more advanced concepts (say, eigenvalues and eigenvectors) before first understanding the basic concepts. There are no shortcuts in mathematics. Without an intuitive understanding of the concepts of span and linear independence you won't get far in linear algebra.

Some algorithms only work with full rank matrices – Do you know what that means? Do you know what can make a matrix not full rank? How to handle this? You will have no clue if you don't know what linear independence is.

The Gaussian elimination algorithm that is used to solve linear equations can actually be numerically unstable if implemented improperly, and this is something that you might have to worry about in some cases. Without understanding the algorithm you won't know where the problem comes from and whether there's anything you can do about it – not at the level of algorithms for solving linear equations, but at the level of coming up with the correct linear equations to solve.

In short, don't be lazy, and take it on faith that these things are useful.


The choice of programming language and the length of a program I wonder how it's possible that:

  it can be shown that all reasonable choices of programming
  languages lead to quantification of the amount of absolute information in
  individual objects that is invariant up to an additive constant.

from the Preface to the First Edition, An Introduction to Kolmogorov Complexity and Its Applications by Li & Vitanyi.

I don't know how they defined "reasonable choice of programming language", but in my sense, it seems natural that the choice of programming language could mix the rank of the complexity. If the programming language fits the object, the program would be shorter, and if not, it would be longer.

But, if I understood it all right, the paragraph above says that no matter which programming language you choose for the strings(objects), the rank of the length of the programs would not change!

Is it really possible? and could someone explain how it's possible?

It is well known that either AND and NOT or OR and NOT can be a primitive function for a computer,

and if I want to implement AND with (OR and NOT), it goes like

NOT(NOT a OR NOT b) instead of just AND!!!

What Li and Vitanyi mean by a reasonable programming language is one that is Turing-complete. This means that you can simulate it on a Turing machine and you can simulate a Turing machine on it, so it has the same expressive power as a Turing machine. This gives you a kind of class of languages. I can prove that C is equivalent to a Turing machine, and that Java is equivalent to C, so Java is equivalent to a TM. In over fifty years, no-one has found a reasonable mechanism that is more powerful than a Turing machine (without resorting to things like time travel). This means that the Turing complete languages are considered those that are most reasonable for expressing the principle of computation (see the Church -Turing thesis).

This means that if we agree that the information content of a string should be defined as the length of the shortest program in a Turing complete language, we can never disagree much beyond that. Say that we have a string $x$ and you recon that this string contains only fifteen bits of information. I can then simulate your Turing-complete language in my Turing-complete language and run your fifteen bit program. Since my simulation of your language does not depend on $x$, we can never disagree by more than a constant amount, and for large enough $x$, the difference will become negligable.

So up to a constant term, the information content is a property of the string itself.


traverse direct graph with multiplicative edges I have a graph like this one:

Each step from one node to another is a multiplication.

So for instance given the entry node TE and an entry value of 1.

TE = 1

TB = 1/10010

GB = 999/(10010*1000)

GE = (19990*999)/(10010*1000)

and so on.

I want to find the best path from TE to TE to return the highest value.

In this case is

TE TB GB GE TE = 1,993010988

I tried to apply Dijkstra's SPF but it doesn't work because each step can
increment or decrement so it's not monotone

neither Bellman–Ford algorithm is applicable here because the graph contains negative cycle. (e.g. TE TB TE).

Anyone has some clue if this problem has a solution ?

The fact that the weights are multiplicative is essentially irrelevant – you can always take logs, add the logs, then exponentiate. However, looking for the shortest simple path (i.e., no repeated vertices, so you're not whizzing round negative cycles) is an NP-hard problem when there are negative-weight cycles, as explained by Danny Pflughoeft on CS Theory SE. Essentially, longest path in a graph where all weights are non-negative becomes shortest path if you negate all the edge weights, but Hamiltonian path reduces easily to longest path.

You're now allowed to complain that I'm a complexity theorist, since you asked for an algorithm and I said "There's no fast one" as if that was the complete answer.

Wait, now I'm allowed to complain. You tagged your question "shortest-path" but you're actually looking for longest paths. That's straight-up NP-hard. Just give every edge weight $2$ and the longest simple path has weight $2^n$ if, and only if, the graph has a Hamiltonian cycle.


How is a hypergraph different from a bipartite graph? How is a hypergraph different from the bipartite graph generated from the hypergraph by introducing new vertices for each hyperedge, and connecting these vertices with the vertices connected by the original hyperedge. Alternatively, I could also start with a bipartite graph, designate one of the sets of vertices as the hyperedges, and connect these hyperedges with the vertices connected to the original vertices.

Is there anything wrong with this construction? Are there theorems about hypergraphs that don't have a natural interpretation in terms of the bipartite graph just described?

I haven't read in detail what vzn is proposing here, but this got me interested in the question whether hypergraphs are really non-trivial generalizations of graphs. I googled for hypergraphs (and Wikipedia indeed also described the construction given above) and searched stackexchange and mathoverflow, but somehow hypergraphs are always treated as a non-trivial generalization of graphs, and somehow considered to be much more complicated than graphs. Don't read too much into this question, I have neither done an excessive literature research nor thought too deeply about hypergraphs. (Perhaps I even accidentally searched for multigraph instead of hypergraph, but I don't think so.)

Essentially, a hypergraph may be "nice" in some sense, but there may be no equivalent (or at least natural) corresponding notion of niceness for the associated bipartite graph.

One way to approach the question is by analogy with graphs.  Every graph can be represented by its incidence graph, a bipartite graph with vertices in one partition, and edges in the other.  Yet we seldom want to use this "standardised" bipartite representation of graphs, for a variety of reasons.  The same reasons (and more) apply to keeping hypergraphs as they are.

You comment below that this analogy with the graph case was your starting point.  Perhaps we have a different set of intuitions about why turning every graph into a bipartite graph is unnatural, so instead let me try another tack.

First, there are many different notions of what a hypergraph is, depending on the application.

One rather general definition is a set system, which allows the set of edges of the hypergraph to be a subset of the powerset of the vertices.  This allows empty edges, edges with size one, edges that are strictly contained in other edges, and some vertices may also not participate in any edge.  There are versions of hypergraphs that disallow some combination of each of these "features".  These features are important for some applications, and authors tend to rely on them implicitly, so it is worth checking the definition each time.

The best reference I know is Berge's book.  Note that it is essentially a reprint of the second half of his 1973 book on graphs and hypergraphs, and is quite hard to use: it is a useful reference but I can't wholeheartedly recommend it.  Berge requires in a hypergraph that there are no empty edges and that every vertex should be part of some edge, but allows repeated edges (giving a multiset of subsets of the powerset).  He calls a hypergraph with no edge contained in another a simple hypergraph.

Claude Berge, Hypergraphs: Combinatorics of Finite Sets, 1989, Elsevier.

If one disallows edges that are contained in other edges, but allows empty or singleton edges and repeated edges, then the dual graph of the hypergraph that you describe (usually called the incidence graph of the hypergraph, or sometimes referred to as its Levi graph) is a bipartite graph.  Further, the hypergraph can be reconstructed from its incidence graph.

Sometimes this is perfectly appropriate.  However, useful things do get scrambled if one breaks this particular shell.  As an example, various notions of colouring are interesting for hypergraphs, but these are highly unnatural in the bipartite graph setting.  Many other properties of classes of hypergraphs are also scrambled going to the incidence graph.

Perhaps the best part of Berge's book is its continual insistence (with many examples) that hypergraphs really are worth studying, and that they do nontrivially extend graphs.

Edit: clarified terminology, as suggested by vzn's answer.


How "meaningful" is Turing test? Are there better measures? How "meaningful" is Turing test?

Because even though it's sometimes presented as a "scientific" way of classifying the goodness of AI, I do view it as a sort of naive, left-handed way for defining or measuring computer intelligence.

Because there are many more aspects to computer intelligence than mere "whether it can trick some people into believing that they talk with a human". Sure if the computer can answer any question similarly to how a humans expert would, then that would be pretty "hard", but computer intelligence is not there yet and it's unsure, whether it'll ever be due to the long-known differences between formal and informal semantics. It could be just a problem of inhuman system design capability. That is, no-one can ever in practice develop a computer program that's that good. It would just be too large.

Nowadays intelligence of computer programs could be measured by e.g. quantities of statements that they can evalute. That is, just the number of possibilities that they're able to process. Because even the goal of the Turing test would be a computer program with large enough database and large enough semantic analyzer and reasoner.

So, are there better measures?

Nowadays intelligence of computer programs could be measured by e.g. quantities of statements that they can evaluate.

So, the trick, is that the Turing Test was meant for an evaluation of strong AI: could there be a computer program that was as intelligent as a human? So evaluating statements isn't enough, since humans can do much more than that.

There are some things to keep in mind. First, while some people use the Turing Test as a metric of the quality of chatbots today, that wasn't necessarily its original intent. It was more of a thought experiment, trying to answer the question of "what does it mean for an AI to be intelligent?"

Secondly, the test wasn't mean to strictly evaluate the "question and answer" ability of an AI. It was more saying, "if there's an AI so good we can't distinguish it from a human, is there any meaningful difference?" It was a way to define sentience without bringing in complex philosophical (or possibly even religious) arguments about what is and isn't alive. The Turing Test says "if it looks sentient, we'll say it is, because there's no meaningful way to tell otherwise".

  That is, no-one can ever in practice develop a computer program that's that good. It would just be too large.

There are many possible ways around this. One is that we might not write every aspect of a program, but evolve one. We could write a program that writes a program that writes a program etc, each one being slightly more intelligent until it converges on something powerful.

Or, an AI could be developed from machine learning. With enough time and data, something close to human intelligence could grow from statistical observations, having the headstart of hand-coded AI at its core.

If a human brain is enough for human intelligence, a comparably complex program should be as well. But even if no such program is ever developed, the Turing Test still holds meaning as a thought experiment.


How the operating system allocated to dual-channels memory? I learned that the boot loader transmit the operating system from Hard Disk to Main Memory during the booting process.

I wonder, today's computers are equipped with multiple slice of memory of dual-channels.

How the Operating System is allocated to each channel?

I guess it should not clone twice.

You are completely misunderstanding what dual channel memory means; it is an implementation detail that is supposed to make memory access faster but completely invisible during operation.

Let's say you have (simplified) a computer with two RAM chips. The computer could have one connection to both chips, or two connections, one to each chip. The CPU issues a command to read say 256 bit. With single channel memory, one command to transfer 256 bit is sent to the two RAM chips, and it takes some time to transfer 256 bit. With dual channel memory, the CPU automatically (without the OS doing _anything) sends two commands, one to each RAM chip, and each chip transmits 128 bits through its channel. Both commands run in parallel, so the time for memory transfer will be half the time.


Is $O(\log_2 n)$ close to $O(n)$ or $O(1)$? We know that asymptotically $O(1)$< $O(\log_2 n)$ < $O(n)$, but $O(\log_2 n)$ is asymptotically close to $O(n)$ or $O(1)$?

As far as I understand your question, you have to take a look at the differences: $O(\log n - 1) = O(\log n)$ versus $O(n - \log n)$. Since

\begin{eqnarray}
n - \log n & \stackrel!> & \log n\\
n & > & 2 \log n\\
\end{eqnarray}

you have $O(\log n) \subset{} O(n - \log n)$. The difference to $O(n)$ grows faster than the difference to $O(1)$.

Thus, $O(\log n)$ is closer to $O(1)$ than $O(n)$.


Does the following modified Two-Phase Locking protocol ensure serializability and freedom from deadlock? Consider the following variant of the two phase locking protocol. Suppose a transaction $T$ accesses (for read or write operations), a certain set of objects ${O_1,...,O_k}$.

The modified algorithm works as :

Step 1. $T$ acquires exclusive locks to $O_1, . . . , O_k$
in increasing order of their ids.

Step 2. The required operations are performed.

Step 3. All locks are released.

Does this protocol ensure serializability and freedom from deadlock?

Since the locks are being obtained in an increasing order of their ids, the circular wait condition cannot prevail and a deadlock can thus be avoided. But does it ensure serializability? How to argue with respect to the serialization aspect?

The question is not clear about the details, but assuming said resources are always locked-then-accessed sequentially, then a deadlock is not possible to occur. Since the locks are always obtained in the same order, precedence would prevent any cross-lock scenarios. Once a transaction acquires the lock for the first item in the list, other transactions will have to wait for that lock to be released.

Even if the locks are acquired-released on one-by-one basis, deadlocks would not occur. Supposing 2 transactions T1 and T2 are concurring the locks for the resources A, B, C, the sequence of events would be:

T1 acquires A
T2 waits    A
T1 releases A
T2 acquires A
T1 acquires B
T2 releases A
T2 waits    B

Then there's the scenario where T2 overtakes T1. In that case nothing would change, T2 would then be the contentious transaction (holding everyone else behind). But no deadlocks.

T1 acquires A
T2 waits    A
T1 releases A
T2 acquires A
T2 releases A
T2 acquires B
T1 waits    B
T2 releases B
T2 acquires C
T1 acquires B

The number of concurrent transactions is not important. Possibly, the great the numbers of transactions concurring, the greater the number of overtakes. It would be contentious and some transactions, even though they entered first, could possibly lag way behind other transactions that arrived later. In edge cases, some transactions could give the impression they are deadlocked when in fact they are not (they are just being thrown around by the OS scheduler).

Also, in most (all?) Systems locks are not served on the the same order they are requested.
T1, T2, T3 could request a lock for the resource A, but T3 could be the first to get it. It's very likely the locks will be given in the order they were requested, but it's not guaranteed, especially if the system running the process is already dealing with too many threads. In such cases the OS can reorder the threads, thus changing the order the locks are acquired. No deadlocks still, but some transactions could take abnormally longer than others.

The case you describe (all locks being acquired and released at once) could be even more contentious, and could become a pain in the arse as the load in the system increases - because strange (and often *un-*debuggable) things starts to happen.

Still no deadlocks though.