BIT: What is the intuition behind a binary indexed tree and how was it thought about? A binary indexed tree has very less or relatively no literature as compared to other data structures. The only place where it is taught is the topcoder tutorial. Although the tutorial is complete in all the explanations, I cannot understand the intuition behind such a tree? How was it invented? What is the actual proof of its correctness?

Intuitively, you can think of a binary indexed tree as a compressed representation of a binary tree that is itself an optimization of a standard array representation.  This answer goes into one possible derivation.

Let's suppose, for example, that you want to store cumulative frequencies for a total of 7 different elements.  You could start off by writing out seven buckets into which the numbers will be distributed:

[   ] [   ] [   ] [   ] [   ] [   ] [   ]
  1     2     3     4     5     6     7

Now, let's suppose that the cumulative frequencies look something like this:

[ 5 ] [ 6 ] [14 ] [25 ] [77 ] [105] [105]
  1     2     3     4     5     6     7

Using this version of the array, you can increment the cumulative frequency of any element by increasing the value of the number stored at that spot, then incrementing the frequencies of everything that come afterwards.  For example, to increase the cumulative frequency of 3 by 7, we could add 7 to each element in the array at or after position 3, as shown here:

[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
  1     2     3     4     5     6     7

The problem with this is that it takes O(n) time to do this, which is pretty slow if n is large.

One way that we can think about improving this operation would be to change what we store in the buckets.  Rather than storing the cumulative frequency up to the given point, you can instead think of just storing the amount that the current frequency has increased relative to the previous bucket.  For example, in our case, we would rewrite the above buckets as follows:

Before:
[ 5 ] [ 6 ] [21 ] [32 ] [84 ] [112] [112]
  1     2     3     4     5     6     7

After:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
  1     2     3     4     5     6     7

Now, we can increment the frequency within a bucket in time O(1) by just adding the appropriate amount to that bucket.  However, the total cost of doing a lookup now becomes O(n), since we have to recompute the total in the bucket by summing up the values in all smaller buckets.

The first major insight we need to get from here to a binary indexed tree is the following: rather than continuously recomputing the sum of the array elements that precede a particular element, what if we were to precompute the total sum of all the elements before specific points in the sequence?  If we could do that, then we could figure out the cumulative sum at a point by just summing up the right combination of these precomputed sums.

One way to do this is to change the representation from being an array of buckets to being a binary tree of nodes.  Each node will be annotated with a value that represents the cumulative sum of all the nodes to the left of that given node.  For example, suppose we construct the following binary tree from these nodes:

             4
          /     \
         2       6
        / \     / \
       1   3   5   7

Now, we can augment each node by storing the cumulative sum of all the values including that node and its left subtree.  For example, given our values, we would store the following:

Before:
[ +5] [ +1] [+15] [+11] [+52] [+28] [ +0]
  1     2     3     4     5     6     7

After:
                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
        1     3     5     7
      [ +5] [+15] [+52] [ +0]

Given this tree structure, it's easy to determine the cumulative sum up to a point.  The idea is the following: we maintain a counter, initially 0, then do a normal binary search up until we find the node in question.  As we do so, we also the following: any time that we move right, we also add in the current value to the counter.

For example, suppose we want to look up the sum for 3.  To do so, we do the following:

Start at the root (4).  Counter is 0.
Go left to node (2).  Counter is 0.
Go right to node (3).  Counter is 0 + 6 = 6.
Find node (3).  Counter is 6 + 15 = 21.

You could imagine also running this process in reverse: starting at a given node, initialize the counter to that node's value, then walk up the tree to the root.  Any time you follow a right child link upward, add in the value at the node you arrive at.  For example, to find the frequency for 3, we could do the following:

Start at node (3).  Counter is 15.
Go upward to node (2).  Counter is 15 + 6 = 21.
Go upward to node (4).  Counter is 21.

To increment the frequency of a node (and, implicitly, the frequencies of all nodes that come after it), we need to update the set of nodes in the tree that include that node in its left subtree.  To do this, we do the following: increment the frequency for that node, then start walking up to the root of the tree.  Any time you follow a link that takes you up as a left child, increment the frequency of the node you encounter by adding in the current value.

For example, to increment the frequency of node 1 by five, we would do the following:

                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
      > 1     3     5     7
      [ +5] [+15] [+52] [ +0]

Starting at node 1, increment its frequency by 5 to get

                 4
               [+32]
              /     \
           2           6
         [ +6]       [+80]
         /   \       /   \
      > 1     3     5     7
      [+10] [+15] [+52] [ +0]

Now, go to its parent:

                 4
               [+32]
              /     \
         > 2           6
         [ +6]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

We followed a left child link upward, so we increment this node's frequency as well:

                 4
               [+32]
              /     \
         > 2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

We now go to its parent:

               > 4
               [+32]
              /     \
           2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

That was a left child link, so we increment this node as well:

                 4
               [+37]
              /     \
           2           6
         [+11]       [+80]
         /   \       /   \
        1     3     5     7
      [+10] [+15] [+52] [ +0]

And now we're done!

The final step is to convert from this to a binary indexed tree, and this is where we get to do some fun things with binary numbers.  Let's rewrite each bucket index in this tree in binary:

                100
               [+37]
              /     \
          010         110
         [+11]       [+80]
         /   \       /   \
       001   011   101   111
      [+10] [+15] [+52] [ +0]

Here, we can make a very, very cool observation.  Take any of these binary numbers and find the very last 1 that was set in the number, then drop that bit off, along with all the bits that come after it.  You are now left with the following:

              (empty)
               [+37]
              /     \
           0           1
         [+11]       [+80]
         /   \       /   \
        00   01     10   11
      [+10] [+15] [+52] [ +0]

Here is a really, really cool observation: if you treat 0 to mean "left" and 1 to mean "right," the remaining bits on each number spell out exactly how to start at the root and then walk down to that number.  For example, node 5 has binary pattern 101.  The last 1 is the final bit, so we drop that to get 10.  Indeed, if you start at the root, go right (1), then go left (0), you end up at node 5!

The reason that this is significant is that our lookup and update operations depend on the access path from the node back up to the root and whether we're following left or right child links.  For example, during a lookup, we just care about the right links we follow.  During an update, we just care about the left links we follow.  This binary indexed tree does all of this super efficiently by just using the bits in the index.

The key trick is the following property of this perfect binary tree:

  Given node n, the next node on the access path back up to the root in which we go right is given by taking the binary representation of n and removing the last 1.

For example, take a look at the access path for node 7, which is 111.  The nodes on the access path to the root that we take that involve following a right pointer upward is

Node 7: 111
Node 6: 110
Node 4: 100

All of these are right links.  If we take the access path for node 3, which is 011, and look at the nodes where we go right, we get

Node 3: 011
Node 2: 010
(Node 4: 100, which follows a left link)

This means that we can very, very efficiently compute the cumulative sum up to a node as follows:

Write out node n in binary.
Set the counter to 0.
Repeat the following while n ≠ 0:

Add in the value at node n.
Clear the rightmost 1 bit from n.

Similarly, let's think about how we would do an update step.  To do this, we would want to follow the access path back up to the root, updating all nodes where we followed a left link upward.  We can do this by essentially doing the above algorithm, but switching all 1's to 0's and 0's to 1's.

The final step in the binary indexed tree is to note that because of this bitwise trickery, we don't even need to have the tree stored explicitly anymore.  We can just store all the nodes in an array of length n, then use the bitwise twiddling techniques to navigate the tree implicitly.  In fact, that's exactly what the bitwise indexed tree does - it stores the nodes in an array, then uses these bitwise tricks to efficiently simulate walking upward in this tree.

Hope this helps!

I think that the original paper by Fenwick is much clearer.
The answer above by @templatetypedef requires some "very cool observations" about the indexing of a perfect binary tree, which are confusing and magical to me.

Fenwick simply said that the responsibility range of every node in the interrogation tree would be according to its last set bit:

E.g. as the last set bit of 6==00110 is a "2-bit" it will be responsible for a range of 2 nodes. For 12==01100, it is a "4-bit", so it will be responsible for a range of 4 nodes.

So when querying F(12)==F(01100), we strip the bits one-by-one, getting F(9:12) + F(1:8). This is not nearly a rigorous proof, but I think that's it's more obvious when put so simply on the numbers axis and not on a perfect binary tree, what are the responsibilities of each node, and why is the query cost equals to the number of set bits.

If this is still unclear the paper is very recommended.


Bubble sort complexity So I have this code:

  done <- false                                     [1]
  n <- 0                                            [1]
  while (n < a) and (done = false)                  [(n+1)(1+1+1)]
    done <- true                                    [n]
    for m <- (a- 1) downto n                        [n(1+1+1+1)]
       if list[m] < list[m - 1] then                [n]
         tmp <- list[m]                             [n]
         list[m] <- list[m-1]                       [n]
         list[m - 1] <- tmp                         [n]
         done <- false                              [n]
       n <- n + 1                                   [1]
  return list                                       [1]

Am I doing this right? My conclusions are that the inne for-loop runs (n^2 + n) / 2 times and the outher while-loop runs n+1 times. I don't know how to properly argue for that the bubble sort has the complexity O(n^2)

There is just one loop in for, so the number of steps here will be proportional to n not n^2. The outer loop is running in a n proportional number of steps too. So The complexity of your algorithm is n^2.
N.B. : When speaking complexity, you don't have to state (n^2 + n) / 2,just say n^2 because they are the same for big ns.


A Question about a Question related to Graph Theory and Maximum Flow The following question is from the book "Introduction to Algorithms" By Cormen and three other authors.

$26.2-10$
Show how to find a maximum flow in a network $G = (V,E)$ by a sequence of at
most $|E|$ augmenting paths. (Hint: Determine the paths after finding the maximum
flow.)

I find this question confusing because the hint contradicts the question. Is it asking you to find the maximum flow in a graph? or is it asking you to find a path?

Recall that for a given flow graph $G$ there might be several flows that yield the maximum flow. Is this question asking you to find all the flows that produce a maximum flow? Do you think this question is properly worded?

Bob

It's asking you to prove that there exists a sequence of $|E|$ augmenting paths that yields the maximum flow.

The hint suggests: suppose you already knew the maximum flow.  Then use that information to choose $|E|$ augmenting paths, that will yield that maximum flow.

Yes, this sounds weird.  Obviously what you have proven will not be useful as a maximum-flow algorithm (you would need to know the maximum flow already, so it's no use in computing the maximum flow).  Think of it as proving a theoretical fact, rather than trying to design a useful algorithm.


How are games like chess provably harder than NP? From this question, I had the debate about how problems harder than NP are proved.
I said that intuitively I understand it as (from this video explaining that some problems are provably harder than NP):

Generalized chess is harder than NP, and is EXPTIME-complete for the
decision problem "Given an nxn board with a given position, can white
force a win?" because the proof would require an exponential amount of
steps to show that each branch of the tree eventually leads to a win.
Therefore it's not in NP.

And a user replied:

Your first paragraph is faulty. It has the form "because this one
algorithm I thought of takes exponential time, the problem must not be
in NP". That's faulty -- maybe there's some other algorithm you
haven't thought of that's better.

I'll admit I'm still new at this and the user that wrote the above comment has much more experience in the field than I do. So I trust this user is correct. However, the explanation the video gave seems very intuitive. But can anyone explain why the video's explanation is wrong?
My thought process is as-follows. One of the definitions of NP is "the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs of the fact that the answer is indeed "yes"." So let's assume I get a certificate $c$ that claims to answer the decision problem "Given an nxn board with a given position, can white force a win?" In order to do this, the verifier must check every single possible branch of the tree of moves to check that each one leads to a forced win. This cannot be done in less than exponential time and thus is provably harder than NP.

The fault lies in this statement:

  So let's assume I get a certificate $c$ that claims to answer the decision problem "Given an nxn board with a given position, can white force a win?" In order to do this, the verifier must check every single possible branch of the tree of moves to check that each one leads to a forced win.

The second sentence might be right, but it might not.  Perhaps there is a cleverer, faster way that the verifier can check a certificate, or a cleverer format for the certificate that makes it easy to check.  How do we know that's impossible?  We don't.  That would need proof.

The argument has made an assumption about how a verifier "would have to" behave, without substantiating or proving that assumption.  This is basically an argument from failure of creativity: "I can't think of any other strategy a verifier could plausibly use, so there must not exist any valid strategy".  Needless to say, this is not a persuasive form of argument.

For instance, let me give you an example.  Suppose we replace "generalized chess" by "generalized tic-tac-toe", which works as follows: we have a nxn game board, and the first person to get three in a row wins.  Try working through the same argument.  It's tempting to draw the same conclusion, that generalized tic-tac-toe is NP-hard.  But there are reasons to doubt that conclusion: for instance, this form of generalized tic-tac-toe is always a first-player win when you start from the empty board, for all $n>3$.

There are better examples.  In particular, there are games where there are in fact polynomial-time algorithms to play optimally, but the algorithm/strategy is not at all obvious, and if you weren't already aware of it, you might be inclined to be persuaded by the above reasoning that the game is NP-hard.  Examples include Nim, Brussels Sprouts, and Wythoff's game.  This illustrates that the line of reasoning can't possibly be right -- it leads you to draw conclusions that are false.

Usually running time analysis is applied to algorithms, not applications. It is possible there is some as-yet undiscovered algorithm that solves chess in polynomial time.

The reference to chess being "NP complete" assumes a tree-search algorithm, such as minimax, is being used. Brute force minimax runs in exponential time. For example, even if there are only two choices every move, then the size of the tree is a $2^N$ where N is the number of moves. Exponential running time is considered non-polynomial. (a polynomial algorithm has a running time $a_1N^b + a_2N^{b-1} + a_3N^{b-2} + ...$, where a and b are constants).


The Hindley-Milner type system plus polymorphic recursion is undecidable or semidecidable? I have often read that Hindley-Milner extended to allow polymorphic recursion is undecidable. However is the term used what is actually meant? Or do people actually mean semidecidable when they mention that?

I ask this before I've recently found a paper where such a type system is presented and an algorithm based on the search of a fixed-point allows type inference for the type system. The trick is that you can fix a number $k$ of iterations for the search to maintain decidability of such a type system. If you cannot find a fixed point you can use the usual ML rules to try to type the program disallowing polymorphic recursion.

The authors proved that, given a well-typed expression $s$ there exist $k \in \mathbb{N}$ such that you can type the expression with the correct type limiting the number of iterations to $k$.

Now, I think this implies semidecidability of type inference with polymorphic recursion in such a case. If we allow $k = +\infty$ what would happen is that the algorithm would always terminate for well-typed expression, but could not terminate for non-well typed expressions.

Am I correct in this conclusion or is there some hidden issue I didn't understand?

The answer you gave is right, but I'd like to stress the relationship between the two terms.

A formal language is decidable if and only if there exists an algorithm which correctly accepts or rejects every input in finite time. We also say it's computable.

A formal language is undecidable if and only if it is not decidable.

A formal language is semidecidable if and only if an algorithm exists that recognizing an input that is in the language. In particular, all decidable languages are semidecidable! However the halting problem is an example of a semidecidable language that is also undecidable. The complement of the halting problem is not even semidecidable.

We say type inference is undecidable rather than semidecidable (even though both characterizations are true) because the former is usually more relevant.

Yes, I was right. People in the field use the term undecidable to mean semidecidable. In fact, it seems like this is done in most fields.


Justification for neglecting constant factors in Big O Many a times if the complexities are having constants such as 3n, we neglect this constant and say O(n) and not O(3n). I am unable to understand how can we neglect such three fold change? Some thing is varying 3 times more rapidly than other! Why do we neglect this fact?

To rationalize how asymptotic notations ignore constant factors, I usually think of it like this: asymptotic complexity isn't for comparing performance of different algorithms, it's for understanding how performance of individual algorithms scales with respect to the input size.

For instance, we say that a function that takes $3n$ steps is $O(n)$, because, roughly speaking, for large enough inputs, doubling the input size will no more than double the number of steps taken. Similarly, $O(n^2)$ means that doubling the input size will at most quadruple the number of steps, and $O(\log n)$ means that doubling the input size will increase the number of steps by at most some constant.

It's a tool for saying which algorithms scale better, not which ones are absolutely faster.

Let me explain you simply. Let us take n = 100000. Now, what is 3n? It is 300000 (Yeah, it is 3 folds of n) But what is n^2 ? 10000000000. ( it is 1 lakh folds of n)..Compare n^2 with n. 3 is negligible when we compare with 1 lakh. so, we can remove it.

Think if n is some billions or trillions. In this case, again we are going to compare 3 with some billions or trillions. Now, you know why we can neglect 3.


How to check for ambiguous grammar if you don't know the string Let's say I have a CFG grammar $G$ which describes some rules for language generation. How can you tell that grammar can generate ambiguous results for a string if you don't know that string? I know how to check for ambiguity when you're given a particular string but what about the cases when it's not? Is there any algorithm to do this?

You cannot tell that a context-free grammar is ambiguous, since the problem is undecidable. This can be proved by a straightforward reduction from the Post correspondence problem, for example. What this means is that there is no algorithm that, given a context-free grammar, decides whether it is ambiguous or not.

My answer is this, you can not check for ambiguity if no string is given, because there is no algorithm till now to check for ambiguity.


Why is binary search faster than ternary search? Searching an array of $N$ elements using binary search takes, in the worst case $\log_2 N$ iterations because, at each step we trim half of our search space.
If, instead, we used 'ternary search', we'd cut away two-thirds of our search space at each iteration, so the worst case should take $\log_3 N < \log_2 N$ iterations...

It seems that ternary search is faster, so why do we use binary search?

If you apply binary search, you have $$\log_2(n)+O(1)$$ many comparisons. If you apply ternary search, you have $$ 2 \cdot \log_3(n) + O(1)$$ many comparisons, as in each step, you need to perform 2 comparisons to cut the search space into three parts. Now if you do the math, you can observe that:
 $$ 2 \cdot \log_3(n) + O(1) = 2 \cdot \frac{\log(2)}{\log(3)} \log_2(n)+ O(1) $$ Since we know that $2 \cdot \frac{\log(2)}{\log(3)} > 1$, we actually get more comparisons with ternary search.

By the way: $n$-ary search may make a lot of sense in case if comparisons are quite costly and can be parallelized, as then, parallel computers can be applied.

Note that argument can be generalized to $n$-ary search quite easily. You just need to show that the function $f(k) = (k-1) \cdot \frac{\log(2)}{\log(k)}$ is strictly monotone increasing for integer values of $k$.

Please note the log(N) vs 2 log(N) comparisons argument is based on a naive interpretation of the algorithm. If I were to actually sit down and write this in x86 assembly the results would be inverted. The problem is the use of integers for test cases combined with an insufficiently smart compiler that can't remove the redundant comparisons. Retry with strings and an appropriate string comparison function, and code it to call the comparison function once per loop and you will find the ternary search is faster again.


Is the inverse of MST cut property true? Why? If we partition the nodes of a graph into sets A and B, there is an edge e of weight larger than any other edge crossing the cut between A and B, e would never be in the minimum spanning tree?

This is not the case.
If an edge $e$ is a bridge in the graph, then every MST has to include $e$. There can exist some cut in which $e$ is the heaviest edge, but this does not change the fact that $e$ must be included (there is some other cut in which $e$ is the only - and therefore the lighest - edge).

There is some ambiguity  in the question. I would like to present some detailed versions, where we can enjoy both the cut property and its inverse.

Let $G$ be a connected, edge-weighted undirected graph, $C$ be a cut of $G$ and $e$ be an edge that crosses $C$.
The cut property of Minimum Spanning Trees (MSTs) for $(G, C, e)$: If, for any other edge $e'$ that crosses $C$, the weight of $e$ is not larger that of $e'$, then there is an MST of $G$ that contains $e$.
Here is the inverse proposition.
The inverse cut property of Minimum Spanning Trees (MSTs) for $(G, C, e)$: If there exists an edge $e'$ that crosses $C$ such that the weight of $e$ is larger than that of $e'$, then there is no MST of $G$ that contains $e$.
The inverse proposition is true. We can prove it by contradiction. Suppose there is MST $M$ that contains $e$. We can replace $e$ with $e'$ to obtain a new spanning tree. This new spanning tree has less weight than $M$, which is false since $M$ has the least weight.

Here is a different version of the cut property.
(Second version) The cut property of Minimum Spanning Trees (MSTs) for $(G, C, e)$: If, for any other edge $e'$ that crosses $C$, the weight of $e$ is smaller than that of $e'$, then every MST of $G$ contains $e$.
Here is the inverse proposition.
(Second version) The inverse cut property of Minimum Spanning Trees (MSTs) for $(G, C, e)$: If there exists an edge $e'$ that crosses $C$ such that the weight of $e$ is not smaller than that of $e'$, then there is an MST of $G$ that does not contain $e$.
The inverse proposition is true. We can prove it directly.

If there is MST $M$ that does not contains $e$, our proof is done.
Otherwise, let $M$ be an MST that does contain $e$.  We can replace $e$ with $e'$ to obtain a new spanning tree, which does not contain $e$. This new spanning tree has the same weight as $M$. Hence, the new spanning tree is an MST, too. $\quad\checkmark$


Computing the intersection of N sets over an M-element universe Suppose I have $N$ sets $S_1,\dots,S_N$ each with elements from set $\{1,\dots,M\}$.

1.) What is a good algorithm to find $S_1\cap\dots\cap S_N$?

2.) I am also looking for a good parallel and a good distributed algorithm.

Usual method is you sort all the sets, and select common elements by looking at the beginning of each sorted sequence. This gives you $O(NM)$ algorithm if you do bucket sort. Or in the bucket sort step itself you may check if all the sorted sequence has common elements by doing an operation AND on the bits.

There is even better algorithm that runs in $O(\Sigma_{i=1}^N |S_i| + M$ (i.e. $O(n+M)$) if sets are not multisets (which is the case here). Let $V[1..M]$ be a zero vector. For each $i \in 1..N$, for each $x \in S_i$ do  increment $V[x]$. Select those $x$ for which $V[x] = N$. (Note: For multisets also we can do something similar, but we need to do some housekeeping to ensure that we increment only once for a particular element $x$ in a set $S_i$ even if it occurs multiple times.)

If the elements of each sets are already stored in efficient search data structure they you can do it another way. This also works if you have domain as general values rather than values from $Z_M$. You take the smallest sized set $S_{min}$ and select elements from $S_{min}$ one by one by checking if it belongs to every set $S_i$ in time $O(\log |S_i|)$. This gives you $O(N\cdot
|S_{min}|\cdot \log(|S_{max}|))$-time algorithm, where $S_{max}$ is the largest set, and which might be better than $O(NM)$ if smallest and largest sets are small enough.

Here is an O(n) algorithm:

Create an std::unordered_set

Put all items of vector A into the set

Go through all items of vector B, checking that they are present in the unordered_set, and incrementing the count for each item that is present.
Return the final count.

Here is an implementation in C++11, using a lambda for brevity:

vector<int> a {2, 3, 5, 7, 11, 13};
vector<int> b {1, 3, 5, 7, 9, 11};
unordered_set<int> s(a.begin(), a.end());
int res = count_if(b.begin(), b.end(), [&](int k) {return s.find(k) != s.end();});
// Lambda above captures the set by reference. count_if passes each element of b
// to the lambda. The lambda returns true if there is a match, and false otherwise.


Why is writing down mathematical proofs more fault-proof than writing computer code? I have noticed that I find it far easier to write down mathematical proofs without making any mistakes, than to write down a computer program without bugs.

It seems that this is something more widespread than just my experience. Most people make software bugs all the time in their programming, and they have the compiler to tell them what the mistake is all the time. I've never heard of someone who wrote a big computer program with no mistakes in it in one go, and had full confidence that it would be bugless. (In fact, hardly any programs are bugless, even many highly debugged ones).

Yet people can write entire papers or books of mathematical proofs without any compiler ever giving them feedback that they made a mistake, and sometimes without even getting feedback from others.

Let me be clear. this is not to say that people don't make mistakes in mathematical proofs, but for even mildly experienced mathematicians, the mistakes are usually not that problematic, and can be solved without the help of some "external oracle" like a compiler pointing to your mistake.

In fact, if this wasn't the case, then mathematics would scarcely be possible it seems to me.

So this led me to ask the question: What is so different about writing faultless mathematical proofs and writing faultless computer code that makes it so that the former is so much more tractable than the latter?

One could say that it is simply the fact that people have the "external oracle" of a compiler pointing them to their mistakes that makes programmers lazy, preventing them from doing what's necessary to write code rigorously. This view would mean that if they didn't have a compiler, they  would be able to be as faultless as mathematicians.

You  might find this persuasive, but based on my experience programming and writing down mathematical proofs, it seems intuitively to me that this is really not explanation. There seems to be something more fundamentally different about the two endeavours.

My initial thought is, that what might be the difference, is that for a mathematician, a correct proof only requires every single logical step to be correct. If every step is correct, the entire proof is correct. On the other hand, for a program to be bugless, not only every line of code has to be correct, but its relation to every other line of code in the program has to work as well.

In other words, if step $X$ in a proof is correct, then making a mistake in step $Y$ will not mess up step $X$ ever. But if a line of code $X$ is correctly written down, then making a mistake in line $Y$ will influence the working of line $X$, so that whenever we write line $X$ we have to take into account its relation to all other lines. We can use encapsulation and all those things to kind of limit this, but it cannot be removed completely.

This means that the procedure for checking for errors in a mathematical proof is essentially linear in the number of proof-steps, but the procedure for checking for errors in computer code is essentially exponential in the number of lines of code.

What do you think?

Note: This question has a large number of answers that explore a large variety of facts and viewpoints. Before you answer, please read all of them and answer only if you have something new to add. Redundant answers, or answers that don't back up opinions with facts, may be deleted.

Let me offer one reason and one misconception as an answer to your question.

The main reason that it is easier to write (seemingly) correct mathematical proofs is that they are written at a very high level. Suppose that you could write a program like this:

function MaximumWindow(A, n, w):
    using a sliding window, calculate (in O(n)) the sums of all length-w windows
    return the maximum sum (be smart and use only O(1) memory)

It would be much harder to go wrong when programming this way, since the specification of the program is much more succinct than its implementation. Indeed, every programmer who tries to convert pseudocode to code, especially to efficient code, encounters this large chasm between the idea of an algorithm and its implementation details. Mathematical proofs concentrate more on the ideas and less on the detail.

The real counterpart of code for mathematical proofs is computer-aided proofs. These are much harder to develop than the usual textual proofs, and one often discovers various hidden corners which are "obvious" to the reader (who usually doesn't even notice them), but not so obvious to the computer. Also, since the computer can only fill in relatively small gaps at present, the proofs must be elaborated to such a level that a human reading them will miss the forest for the trees.

An important misconception is that mathematical proofs are often correct. In fact, this is probably rather optimistic. It is very hard to write complicated proofs without mistakes, and papers often contain errors. Perhaps the most celebrated recent cases are Wiles' first attempt at (a special case of) the modularity theorem (which implies Fermat's last theorem), and various gaps in the classification of finite simple groups, including some 1000+ pages on quasithin groups which were written 20 years after the classification was supposedly finished.

A mistake in a paper of Voevodsky made him doubt written proofs so much that he started developing homotopy type theory, a logical framework useful for developing homotopy theory formally, and henceforth used a computer to verify all his subsequent work (at least according to his own admission). While this is an extreme (and at present, impractical) position, it is still the case that when using a result, one ought to go over the proof and check whether it is correct. In my area there are a few papers which are known to be wrong but have never been retracted, whose status is relayed from mouth to ear among experts.

a) Because computer programs are waaay bigger than math proofs

a.1) I believe that there's more people used during writting complex computer program than during writting math proof. It means that mistake margin is higher.

b) Because CEOs/Shareholders care more about money than fixing small bugs, meanwhile you (as developer) have to do your tasks to meet some requirements / deadlines / demos

c) Because you can be programmer without "deep" knowledge in comp sci, meanwhile it'd be hard to do in math ( I believe )

Additionally:

NASA:

  This software is bug-free. It is perfect, as perfect as human beings have achieved. Consider these stats: the last three versions of
  the program -- each 420,000 lines long - had just one error each. The
  last 11 versions of this software had a total of 17 errors.

  Take the upgrade of the software to permit the shuttle to navigate with Global Positioning Satellites, a change that involves just 1.5%
  of the program, or 6,366 lines of code. The specifications for that
  one change run 2,500 pages, a volume thicker than a phone book. The
  specifications for the current program fill 30 volumes and run 40,000
  pages.

https://www.fastcompany.com/28121/they-write-right-stuff


XOR-like behavior in flow networks XOR is not the correct name, but I am looking for some kind of exclusive behavior.

I am currently solving a set of different (assignment) problems by modeling flow networks and running a min-cost-max-flow algorithm. Flow networks are quite handy because a lot of problems can be reduced to them in an easy and understandable way. In my case these are matchings with some additional constraints. As these constraints are getting more complex I've been wondering if there are some existing constructions to model specific behaviors.

In this case I want to restrict the outgoing flow of a node to a single edge.

Given a graph $G=(V, E)$, integral capacities $c(u,v)$ and costs $k(u,v)$. An arbitrary node is called $A$. It's direct neighbors are called $B_1, ..B_n$. Can we replace the edges $AB_1,...AB_n$ (red) with some construction so that only one edge can receive flow? Which means that if $AB_1$ gets some flow (e.g. $5/10$) no other (red) edge can receive flow.

We could add intermediate nodes/edges and play with costs and capacities. The total capacity of our new construction has to stay the same and the cost of the different alternatives have to stay somehow proportional.

So my questions are:

Are there constructions like this in general? (Any keywords, links, papers)
Can you suggest a solution to my specific problem?

In general, the answer is no. If we put XOR-like restrictions on the out-going edges of a vertex, we can prove that finding a min-cut-max-flow is NP-Hard. The technique is to reduce 3-SAT to it.

Let's assume there are $n$ variables $x_1, x_2, ..., x_n$ in the 3-SAT and $m$ clauses $c_1, c_2, ..., c_m$. We create a graph $G(V,E)$ encoding the instance of the 3-SAT problem. For each variable $x_i$, we create a vertex $v_i$ connected to the source $s$ with an edge of $\infty$ capacity. Two more vertices $u_i, w_i$, which are connected to $v_i$, are created to represent $x_i$ taking the value 0 or 1 also with edges of capacity $\infty$.

For each of the clauses $c_i$, we create a vertex $o_i \in G$ corresponding to it and $o_i$ is connected to the variables or their negations in the clause with edges of capacity $1$. For example, if $c_i = (x_3 \lor x_4 \lor \neg x_5)$, we connect it to $u_3, u_4, w_5$ with edges of capacity. All $o_i$ are connected to the sink with edges of capacity 1.

Since $x_i$ and $\neg x_i$ cannot take the same value, we put the XOR restriction on edges $(v_i, u_i)$, $(v_i, w_i)$, $\forall i = 1,2,3,...,n$. It can be proved that there is a maximum flow of size $m$ if and only if the 3-SAT instance is satisfiable. Since the problem is trivially in $NP$ and the reduction is polynomial, we conclude the decision version of XOR restriction network flow is NP-Complete.

In general, the answer is unknown, not impossible!

we conclude the decision version of XOR restriction network flow is NP-Complete.
therefore (it's possible, we can do that) if and only if P=NP.


Minimum number of tests to identify subset of modules that trigger a bug? I have an ordered set of $M$ software modules compiled together. The interaction of some  $N$-tuple of these modules is causing a bug when the program is run.

I can run the program with any desired subset of the modules enabled/disabled, so I can test the program by running it with a certain subset of modules enabled and seeing whether it crashes or not (call that "a test"). I would like to identify which $N$ modules are causing this issue with the minimal number of tests.  Assume that any particular test will lead to a crash if and only if it includes all of the $N$ problematic modules (and possibly others; but at least those $N$).

$N$ is known ahead of time.

For $N=1$, I can efficiently identify the culprit in $\log_2(M)$ tests by binary search.

For other values of $N$, what approach can I take to identify the $N$ culprits?

Now that the question has been edited to make it clearer what you are asking, there is a simple and elegant answer.  The solution is: delta debugging.  Delta debugging solves exactly this problem.

Let me elaborate.

Problem statement

I am interpreting your question as asking about the following problem:

We have $M$ software modules, and some way to run the program in a way where only a subset of them are active (and we can choose the subset freely).
There is a subset $S$ of $N$ of the modules.  There's a fault that is triggered whenever we run the program with all of those modules active.  In other words, if the set of active modules is a superset of $S$, a fault will occur; otherwise, no fault will occur.
The fault is perfectly reproducible and detectable.
Now, we want to find the set $S$ using as few tests (invocations of the program) as possible.

Solution: delta debugging

Delta debugging will solve this problem.  If you have $M$ software modules, and some subset of $N$ of them are responsible for the fault, delta debugging can find the minimal subset that trigger the fault.

Delta debugging works by starting with all of the modules active, and gradually removing some of them.  It picks out some chunk of modules, and tries running the program with those modules inactive.  If the fault still occurs, then we know that none of them are responsible for the fault, so they can be permanently deactivated in all future tests.  Delta debugging starts with large chunks, and gradually reduces the chunk size: it first tries deactivating the first $M/2$ modules, then deactivating the second $M/2$ modules; if neither of those offers any progress, then it tries deactivating the first $M/4$ modules, then the second $M/4$ modules, then the third $M/4$ modules, and then the last $M/4$ modules; then it moves on to chunks of size $M/8$; and so on.

For more details, allow me to point you to a nice description of delta debugging.

Delta debugging is efficient

Delta debugging is expected to take about $O(N \lg M)$ tests, to find the subset.

You might notice how this is a nice generalization of binary search.  When $N=1$, binary search needs $O(\lg M)$ tests, just as delta debugging does.  The difference is that delta debugging also scales nicely when $N>1$.

You might also notice that this is close to optimum.  We can prove a $\Omega(N \lg(M/N))$ lower bound (roughly).  In particular, there are ${M \choose N}$ possibilities for the subset $S$, and each test provides one bit of information (either it triggers a fault or not), so it is easy to see that we need at least $\lg {M \choose N}$ tests.  Now

$$\lg {M \choose N} \approx \lg (M^N/N!) \approx N \lg M - N \log N \approx N \lg M - 0.7 N \lg N \ge N (\lg M - \lg N).$$

Therefore, delta debugging is approximately asymptotically optimal, in terms of the number of tests required.

For a more detailed performance analysis, see this analysis by Jesse Ruderman.

Discussion

That said, I am somewhat skeptical of whether this will be useful in practice.  A crucial assumption here is that you could run the program with a chosen subset of its modules active, and the rest artificially deactivated.  I don't see how to do that in practice.  Therefore, I do not see how this can be applied in practice.

I suspect your theoretical model of the problem probably needs to be adjusted, but since you didn't tell us anything about your particular application setting or the justification for your model, I don't have enough information to specify how to fix the model.

Typically, delta debugging is used for a different purpose.  Normally, delta debugging is used to reduce the size of the test case (not the size of the program).  Say you have a test case with $M$ lines that crashes your program, but only a subset of $N$ of the lines are actually necessary to trigger the crash (the rest are all irrelevant), and you want to find the minimal subset of lines needed. In other words, given a long complex test case that crashes your program, you want to "minimize" it: to find a smaller, shortest test case that also crashes the program -- because small test cases usually make the debugging process easier.  Then delta debugging can be used to solve that problem; in fact, that's what it was invented for, and what it's most commonly used for.

The problematic set of modules is an $N$-tuple. Checking every distinct $N$-tuple would take $\binom{M}{N}$ tests (an upper bound).

You can do binary search on the union of $N$-tuples, which takes $\log_2 \binom{M}{N}$ tests - at the expense of some temporary storage to hold the tuples.

This reduces the problem to the $N=1$ case in the problem statement.

Aside:

(It can be done in $M$ tests even for unknown $N$ by leaving all modules enabled, and running $M$ tests each with one module disabled.)


Proof that regular languages are closed against taking the even-length subset This question is on the GRE Computer Science test booklet (not homework). I tried applying closure properties of regular languages but no success.

Suppose $L$ is a regular language over $\Sigma = \{0, 1\}$. Show that the language

$\qquad L' = \{w \in L \mid |w| \in 2\mathbb{N}\}$

is also regular.

What I find surprising is that the booklet mentions that the language $\{w \in L \mid |w| = 2^k, k \in \mathbb{N}\}$ is not necessarily a regular language.

The language $Even = \{w\in\Sigma^{\ast}\mid \text{length of }w\text{ is even}\}$ is regular. user5507's answer demonstrates this with an NFA, and it's a basic exercise in most texts.

Then given that $L$ is regular, if we know that regular languages are closed under intersection for the purposes of the question, then the language $L'=L\cap Even$ is also regular.

If we're not allowed to use these closure properties, we can recapitulate the construction that gives the closure property (I'll just sketch it). Given a DFA $M_{L}$ for $L$ and a DFA $M_{Even}$ for $Even$, we can construct a DFA for $L' = L\cap Even$ that has a state space that is the product of the state spaces of $M_{L}$ and $M_{Even}$, with the follow transition rule: if $\delta_{L}(\sigma, q_{i}) = q_{j}$ and $\delta_{Even}(\sigma, p_{m})=p_{n}$ where $\sigma \in \Sigma$ and the $p$s and $q$s are states of the appropriate machines, then the product machine has a transition $\delta_{prod}(\sigma,(q_{i}, p_{m})) = (q_{j}, p_{n})$. Our accepting states are those states $(q_{i},p_{j})$ where $q_{i}$ and $p_{j}$ are accepting states in their respective machines.

That's the long an fiddly way around.

The second question depends on $L$, that is, if $L$ is not regular, then the intersection of $L$ and $Even$ may is not necessarily regular - the $w\in L$ in the definition is key.

EDIT: actually, reading vonbrand's answer, I misunderstood the second part. He is quite correct - the second language is the intersection of $L$ and $X=\{w\in\Sigma^{\ast}\mid \exists i \in \mathbb{N} \text{ such that } |w| = 2^{i}\}$ - not $Even$. So while what I said about $L \cap Even$ with $L$ not regular holds, $X$ isn't regular to begin with, so we get the same situation, but $L$ is regular and $X$ isn't.

We need to show that

$\{w ∈ L |$ length of w is even$\}$ is regular.

In order to show that, it is enough to construct an NFA/DFA for that. You can construct an NFA for this like


Word factorization in $O(n^2 \log n)$ time Given two strings $S_1, S_2$, we write $S_1S_2$ for their concatenation. Given a string $S$ and integer $k\geq 1$, we write $(S)^k = SS\cdots S$ for the concatenation of $k$ copies of $S$. Now given a string, we can use this notation to 'compress' it, i.e. $AABAAB$ may be written as $((A)^2 B)^2$. Let's call the weight of a compression the number of characters appearing in it, so the weight of $((A)^2 B^2)$ is two, and the weight of $(AB)^2 A$ (a compression of $ABABA$) is three (separate $A$s are counted separately).

Now consider the problem of computing the 'lightest' compression of a given string $S$ with $|S|=n$. After some thinking there is an obvious dynamic programming approach which runs in $O(n^3 \log n)$ or $O(n^3)$ depending on the exact approach.

However, I have been told this problem can be solved in $O(n^2 \log n)$ time, though I cannot find any sources on how to do this. Specifically, this problem was given in a recent programming contest (problem K here, last two pages). During the analysis an $O(n^3 \log n)$ algorithm was presented, and at the end the pseudo quadratic bound was mentioned (here at the four minute mark). Sadly the presenter only referred to 'a complicated word combinatorics lemma', so now I have come here to ask for the solution :-)

If I'm not misunderstanding you, I think the minimum cost factorization can be calculated in $O(n^2)$ time as follows.

For each index i, we will calculate a bunch of values $(p_i^\ell, r_i^\ell)$ for $\ell=1,2,\ldots$ as follows. Let $p_i^1\ge 1$ be the smallest integer such that there is an integer $r\ge 2$ satisfying $$S[i-rp_i^1+1, i-p_i^1] = S[i-(r-1)p_i^1+1, i].$$ For this particular $p_i^1$, let $r_i^1$ be the largest $r$ with this property.
If no such $p_i$ exists, set $L_i=0$ so we know there are zero $(p_i^\ell,r_i^\ell)$ values for this index.

Let $p_i^2$ be the smallest integer strictly bigger than $(r_i^1-1)p_i^1$ satisfying, likewise,
$$S[i-r_i^2p_i^2+1, i-p_i^2] = S[i-(r_i^2-1)p_i^2+1, i]$$
for some $r_i^2\ge 2$. Like before, take $r_i^2$ to be the maximal one having fixed $p_i^2$.
In general $p_i^\ell$ is the smallest such number strictly bigger than $(r_i^{\ell-1}-1)p_i^{\ell-1}$. If no such $p_i^\ell$ exists, then $L_i=\ell-1$.

Note that for each index i, we have $L_i=O(\log (i+1))$ due to $p_i^\ell$ values increasing geometrically with $\ell$. (if $p_i^{\ell+1}$ exists, it's not just strictly bigger than $(r_i^\ell-1)p_i^\ell$ but bigger than that by at least $p_i^\ell/2$. This establishes the geometric increase.)

  Suppose now all $(p_i^\ell,r_i^\ell)$ values are given to us. The minimum cost is given by the recurrence
  $$\mathrm{dp}(i,j) = \min\left\{\mathrm{dp}(i, j-1) + 1, \min_\ell \left(\mathrm{dp}\left(i,j - r_j^\ell p_j^\ell\right) + \mathrm{dp}(j-r_j^\ell p_j^\ell+1,j-p_j^\ell)\right)\right\}$$
  with the understanding that for $i>j$ we set $\mathrm{dp}(i,j) = +\infty$.
  The table can be filled in $O(n^2 + n\sum_j L_j)$ time.

We already observed above that $\sum_j L_j = O(\sum_j \log (j+1)) = \Theta(n\log n)$ by bounding the sum term by term. But actually if we look at the whole sum, we can prove something sharper.

Consider the suffix tree $T(\overleftarrow{S})$ of the reverse of $S$ (i.e., the prefix tree of S). We will charge each contribution to the sum $\sum_i L_i$ to an edge of $T(\overleftarrow{S})$ so that each edge will be charged at most once. Charge each $p_i^j$ to the edge emanating from $\mathrm{nca}(v(i), v(i-p_i^j))$ and going towards $v(i-p_i^j)$. Here $v(i)$ is the leaf of the prefix tree corresponding to $S[1..i]$ and nca denotes the nearest common ancestor.

This shows that $O(\sum_i L_i)=O(n)$. The values $(p_i^j,r_i^j)$ can be calculated in time $O(n+\sum_i L_i)$ by a traversal of the suffix tree but  I will leave the details to a later edit if anyone is interested.

Let me know if this makes sense.

There is your initial string S of length n.
Here is the pseudo-code of the method.

next_end_bracket = n
for i in [0:n]: # main loop

    break if i >= length(S) # due to compression
    w = (next_end_bracket - i)# width to analyse

    for j in [w/2:0:-1]: # period loop, look for largest period first
        for r in [1:n]: # number of repetition loop
            if i+j*(r+1) > w:
                break r loop

            for k in [0:j-i]:
                # compare term to term and break at first difference
                if S[i+k] != S[i+r*j+k]:
                    break r loop

        if r > 1:
            # compress
            replace S[i:i+j*(r+1)] with ( S[i:i+j] )^r
            # don't forget to record end bracket...
            # and reduce w for the i-run, carrying on the j-loop for eventual smaller periods.
            w = j-i

I intentionally gave little details on "end brackets" as it needs lot of steps to stack and unstack which would let the core method unclear.
The idea is to test an eventual further contraction inside the first one. for exemple ABCBCABCBC => (ABCBC)² => (A(BC)²)².

So the main point is to look for large periods first. Note that S[i] is the ith term of S skipping any "(", ")" or power.

i-loop is O(n)
j-loop is O(n)
r+k-loops is O(log(n)) as it stops at first difference

This is globally O(n²log(n)).


Why aren't primality tests easily linear in time complexity? Why don't we consider them as linear? I don't understand. You just have to check for factorization up to sqrt of n.  So it's even faster than linear.
I assume it's not linear only if we compare the number of operations relative to the input in terms of binary representation.  But why would we do so?
It seems to me wrong.  The growth in calculation should be calculated compared to the number itself.  Why do we compare it to the binary representation?

It seems that the main sticking point of the question here is: Why express runtime in terms of the size of the input, rather than the numeric value that the input represents? And indeed in some cases it doesn't make much difference which way you choose to express it. For instance, we could say that the time to read all values in an $N\times N$ matrix is quadratic in the number of columns, or we could say it is linear in the number of cells, and the meaning of these is the same, just with different conventions.
So let's look at some reasons why it is conventional to express operations on numbers in terms of the length of the number rather than its numeric value:

It is more easily comparable to operations on other kinds of data, since every possible form of input has a length but not all forms of input have a numeric value. By consistently using the length of the input as our reference point across a variety of problem types, we also get some nice properties like "the runtime of an algorithm that reads the entire input can never be better than linear."

It provides more useful time complexities in context. For instance, a common use for primality testing is for cryptography. When we're doing cryptography, we might use say a 512-bit number as a key. We would like to have algorithms that scale proportional to the length of the number (512), rather than its numeric value (about $2^{512}$), since $2^{512}$ is such an astronomically large number that even a "linear" time algorithm would never realistically finish.

It relates better to the actual operations performed by the computer. Many people are accustomed to implicitly treating all numbers as capped at some fairly large constant like $2^{64}$, and thus all arithmetic operations are constant-time and the actual internal representation of the number is irrelevant. But when we are analyzing the big-O performance of operations on the number itself we cannot assume that numbers are always small enough to ignore their internal representation. Ultimately, these operations are performed on bits so the number of bits is a good reference point to use for describing the performance.
As a thought experiment, try analyzing the performance of the addition operation. You may have always considered it a constant-time operation, but what happens if the numbers in question get arbitrarily large? Ultimately, you'll need to sum each digit one-by-one, carrying as necessary. It makes sense to describe this as a linear-time operation based on the length of the input, rather than logarithmic time based on the numeric value of the input.

I just got a couple of students curious on this confusion and I tried answering it as follows. (Different to above responses).

First, note that if we were not concerned about the magnitude of input value but only its n-bit representation then the same would apply to analysing sorting algorithms too. But irrespective of what the input numbers magnitude or bits are sorting is nlgn. Agreed?

So why bother on n-bit when dealing with primality or GCD?

To me (and I can be wrong) this is done so to have a worst case complexity analysis. Notice that this part is where my response is different from above.

So going back to sorting, when we say to analyse an input array of size 10^6 we see different cases. And give our big-oh analysis for the worst case of size 10^6. Stay with me!

If we were to plot the nlgn time complexity on x-y what we will do is that we will take an array of size 1, 2, 3,..., 100, 101,..., 1000, ..., 10^5.... and for each of them find the number of basic operation count.

The size of array goes on x-axis and count of basic operation on y-axis. Right? We don't do that too often but that's how we would do it. This would give us an increasing function. I hope you are still reading.

So now back to primality testing. If I plot the same x-y time complexity function and take magnitude on x-axis and count of steps on y-axis, can you imagine what will happen? (Raise of hands, how many of you have guessed the next part?)

For above plot we get following values:

x |  y

2 |  1

3 |  2

4 |  1

5 |  4

...

1000 |  2 (why? its divisible by 2)

So we get a zig-zag shape like efficiency function. That's not right, order of growth were supposed to be monotonically increasing, I mean, they should GROW not SHRINK.

So what's actually needed in this case is that we take the number of digits of number of bits of input as the size of input. Now our analysis is meaningful like the sorting example. Why?

It's because for every n-bit (or n-digit) number we take the worst case from the variety of cases. What we can say is that any even number of size n is a best case for primality and any prime number of size n is its worst case.

So we plot the time complexity as a function of bits of the input and not its magnitude.


Isn't polynomial identity testing over arithmetic *expressions* trivial? Polynomial identity testing is the standard example of a problem known to be in co-RP but not known to be in P. Over arithmetic circuits, it does indeed seem hard, since the degree of the polynomial can be made exponentially large by repeated squaring. This question addresses the issue of how to work around this and keep the problem in randomized polynomial time.

On the other hand, when the problem is initially presented (e.g. here), it is often illustrated over arithmetic expressions containing only constants, variables, addition, and multiplication. Such polynomials have total degree at most polynomial in the length of the input expression, and for any such polynomial the size of the output value is polynomial in the size of the input values. But since a polynomial of degree $d$ has at most $d$ roots, isn't this trivial? Just evaluate the polynomial over the rationals at any $d + 1$ distinct points and check whether the result is zero at each point. This should take only polynomial time. Is this correct? If so, why are arithmetic expressions without shared subexpressions often used as examples, when sharing is essential to the difficulty of the problem?

For a univariate polynomial $p(x)$, yes, it's that easy.

For a multivariate polynomial $p(x_1,x_2,\dots,x_k)$, no, no such algorithm works.

In particular, when you write "a polynomial of degree $d$ has at most $d$ roots", that is true for univariate polynomials $p(x)$, but it is not true in general for multivariate polynomials.  Ricky Demer gives a simple example: $p(x,y) = xy$ is of degree two, but has infinitely many roots.

heres a more general/ abstract way to understand the significance/ hardness of polynomial identity testing in CS. one reason polynomial identity testing is under intense study right now because it has long been known to be closely linked to boolean circuit complexity. imagine taking two arbitrary boolean circuits and then converting them (ie basically setting up a 1-1 mapping) to multivariate polynomials. this is not so hard. basically one uses values of 0/1 to represent false/ true and the constructions are set up in old papers. then the roots of the polynomial correspond to T/F variable assignments that satisfy the formulas/ circuits.

after this setup, PIT is basically nearly the same problem as determining if two binary circuits are equivalent. there are also other (newer) deep proofs that say its nearly equivalent in complexity to factoring polynomials.[1] so one ends up with a result like the following: if one can solve PIT "quickly" it means that two large circuits can be compared for equivalence "quickly" which is unlikely. so a rough way to understand the problem is that its nearly equivalent to nontrivial problems in boolean circuit theory.


Can area-partitioning lose included points due to floating point precision? I'm currently partitioning a big area $A$ into $n$  areas $B_i$ such that
 $$\bigcup_{i=1}^n B_i  = A$$

I have geo-coordinates which I know are in $A$ (also with the finite precision of floats).

Obviously, for every point $p$ in $A$ there has to be an area $B_i$ such that the point is in $B_i$. Formally:

$$p \in A \Rightarrow \exists i: p \in B_i$$

But due to floating point precision, I wonder if it could happen that for all $B_i$ the B_i.intersects(p) method returns false. Formally:

$$\forall i: \neg B_i.\texttt{intersects}(p)$$

All areas are polygons and neighboring polygons share some points which define the polygons.

If the answer is yes, then an example would be good. It would be awesome if one could also quantify the probability of this.

(In my current case, I use shapely.)

This is a problem for anyone making graphics cards: To draw an area, it will usually be split into triangles, and for many drawing methods it is important that every point is drawn exactly once.

At some point you'll have use an algorithm that decides whether a point x is on or above a line l, and at some other point you'll have an algorithm that decides whether x is below the line l. For good results, you need to design this algorithm carefully so it is guaranteed to say "YES" once and "NO" once. It doesn't matter too much whether the result is correct (not saying YES when the point is actually just a tiny bit below the curve), what's important is that the answer is "YES" exactly once and not twice.

Yes it is possible.

For example, look at this C code.

#include <stdio.h>

int main ()
 {
  float a=10.3346714;
  float b=10.3346711;
  printf("a=%.15f\nb=%.15f\n",a,b);
 }

It outputs the following upon execution.

  a=10.334671020507812
  b=10.334671020507812

Lets say your area $A$ was defined as $\{ -10.3346714 \lt x \lt 10.3346714, -20.6693428 \lt y \lt 20.6693428\}$
and it is divided into two equal regions by the line $x=0$
Lets call these two regions $B_{left},B_{right}$.
Now we have our point $p = (10.3346711,2.0000000)$.

From a purely mathematical point of view, we can see that
$p \in A\space and \space p \in B_{right}$.
But if a computer were to perform this check using floating point numbers, for the region $B_{right}$, i.e $p \in B_{right}$, it would do so by comparing $p$ with the rightmost boundary of $B_{right}$ like $10.3346711\lt10.3346714$, which would be false, since both floating point numbers are the same when stored in memory.
The same would happen for checking $p \in A$. Which means $p \notin A \space and \space p \notin B_{right}$ (Atleast as per the computer).

Note
This check would fail only if $p$ lies very close to the boundary of $A$. Other interior points would ultimately reside on either sides of a boundary i.e. in either regions around a boundary.


Is there any data structure that can't be represented or described inside a computer? We all know that, at least theoretically, there are several possible models of computation, varying in structure.

Strictly speaking, there are several (not just one) models of computation that exist or have been implemented in real life. Some machines (for example, amplifier circuits), though inexact, can be considered analog computers, but that's not what we commonly think of as 'computers', is it?

The machines that we usually think of as 'computers' are implementations of a computation model with discrete parts (discrete memory slots, discrete instructions and clock cycles, etc.) I've always wondered if there's some form of data that can't be represented/stored inside these discrete structures.

I've brought up this question in many websites, but I usually only find people who approach this issue with an incomplete picture of the problem, and without the required logical rigor.

I've been told that nothing with a continuous structure can be stored inside a computer, but from what I've gathered, this is not always true. Take the example of a circle (a geometrical shape). It's true that it has an infinite number of points in its circumference, but I can't say that they represent an infinite amount of information, since they can be derived from a very small number of parameters (center and radius) and a bunch of simple laws (algebra and symbolic math). My intuition tells me that this is the case for any geometrical shape, unless it has an infinite number of parameters, in which case I don't really know what to think.

Is my intuition accurate? Is this the case for any structure with a finite number of parameters? Are Von-Neumann/Harvard/... computers unfit to store certain data structure(s)? Has this been mathematically proven? Is the proof constructive? Are there any data structures that can't be stored in any known model of computation (or, for that matter, any model of computation)?

Note: I'm asking all of this from intuition. Even though I write code for a living, and harbor a great interest in Computer Science (and have a little knowledge of it through self-study), I am not a CS or Math graduate. From my limited, newbie perspective, I would think that this question belongs to the Theoretical Computer Science Stack Exchange, but I genuinely don't know if it's too basic, so I'll just play it safe for now.

There is a systematic way of computing datatype representations of mathematical objects: anything that can be described in higher-order intuitionistic logic has a representation as a datatype. Because we are talking about descriptions, and not about proofs of theorems, it does not even matter much that the logic is intuitionistic and not classical. Pretty much any mathematical object you encounter in practice can be represented. Some examples that can be done easily: real numbers, the space of square-integrable measurable functions $L^2[0,1]$ and other infinite-dimensional Hilbert spaces, Banach spaces, the space of compact subspaces of $\mathbb{R}^n$, etc.

Roughly, the process goes as follows. Take you favorite model of computation and build a realizability topos from it. Then take your description of the mathematical object and interpret it in the topos. It will tell you how to represent data, because the topos is built in such a way that every object is equipped with a data representation, and every statement is witnessed by a program. In most cases we do not actually need the entire topos, the much smaller and easier subcategory of modest sets suffices.

There is an important caveat: in intuitionistic logic an object may have several inequivalent descriptions which are classically equivalent. These will lead to different data representations (and this is good, as it means we can express more computational distinctions).

The process of interpretation is automatic. To make that point, Chris Stone and I wrote a tool rz which does this. You can feed it the definition of real numbers, or an infinitely dimensional Banach space, or anything like that, and it spits out a specification. (The software experienced bitrot, I should update it, but the paper has many examples.)

Let me also address the common misconception that "non-computable objects cannot be represented in a computer". There is a difference between non-computable and non-representable. For example, the digits of a real number may be written down on the tape of a Turing machine. It doesn't matter whether the real number in question is computable, it can be stored on the tape. The question of "who stored it onto the tape" is a separate concern. You may object that the tape is not infinite. Actually, it is infinite in most textbooks. But people like to press this point, to which I have two responses.

First, we may replace the infinite tape with a potentially infinite tape, i.e., think of the real number as a process which emits digits on demand. This can be some sort of a physical process, say a quantum-mechanics experiment that produces bits by making measurements. Would anyone like to presuppose that the real number so obtained is computable? In this case they have to produce some evidence for such a claim. Good luck with that. The moral here is that it is largely irrelevant whether "all reals in this universe are computable". What is important is that we can represent whatever reals there are, and that would by definition be all of them.

Second, we can study models of computation that have no infinite components, for example the $\lambda$-calculus. In such models infinite data, say a real number, is represented by a program that produces the data, say the digits of the real number. So obviously only computable reals may be represented. But this doesn't matter! The corresponding realizability topos still thinks there are uncountably many reals, and is a self-consistent world of mathematics.

For further explanation on how to represent uncountable data, I refer to my blog post Representations of uncomputable and uncountable sets. It's a bit of a rant, actually.

The takeaway is the motto from my PhD thesis:

  Data are continuous, programs are computable.

This is a hard question to answer, given the vagueness of your notion of "parameter". For example, a typical real number as it is defined mathematically cannot be represented in a computer, using any number of standard arguments (see, e.g. the answers to this question).

Does this mean that a real number has an infinite number of parameters? In particular, your circle example is also faulty, since you need already 2 reals to represent one (which, as mentioned, are not representable).

If you then object that you are only interested in parameters which are themselves representable on a computer, then yes, all data structures that only require a finite number of parameters to describe can be represented on a computer. But this seems to beg the question a bit.

In general, all computable data structures are representable by an idealized VN computer, though often one has to decide how to represent the elements before determining whether they are computable. This paper by Casanova and Santini seems to address some of those issues, but it presupposes knowledge of the mathematical notion of computability.

Finally, I should note that figuring out the number of parameters to represent geometric objects like circles, parabola, etc is a very popular question in algebraic geometry which falls (mostly) outside the purview of computer science.


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

To formalize this more precisely, let

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

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

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

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

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

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

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

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

Where each clause is only given as $(x_i\oplus x_j)$, create a vertex for each literal $x_i$, create an edge between two vertices if there exists an XOR relationship between them. For the statement $x_i\oplus x_j$ to be true, it should satisfy $x_i\neq x_j$. Now we can adopt the vertex coloring problem (no two vertices connected by an edge are assigned the same color, we have additional constraint of 2 colors only if we want to satisfy the equation). The clause $x_i\oplus x_j$ is true iff the corresponding vertices have been assigned different colors in the graph.

If all the vertices of the graph can be colored using 2 colors and none of two vertices with a common edge share are assigned the same color then the equation is satisfiable.

But a graph is 2-colorable iff it is a bipartite graph. And determining whether a graph is bipartite can be done in polynomial time. Therefore the problem is in P, because if we can determine in polynomial time that the graph is bipartite graph then it is solvable, otherwise it is not solvable.


Can we create recursive functions only by using if-else statements? I have to show whether a program containing only if-else statements but no loops is able to calculate the following type of functions: $f^n(x)$. The function $f$ is applied $n$ times to $x$, so I guess this is a recursive function.

How can I prove that formally?

If a program doesn't include any loop, recursion or equivalent construct, then it cannot express recursive computations.

In order to write a formal proof, you'd need to define your language formally. “Equivalent construct” can include some exotic things such as parallel execution, exception handlers, higher-order functions (leading to fixpoint combinators), meta-execution facilities (eval), etc. that let recursion in through a backdoor.

Suppose that a language contains only the following constructs: constants, assignments, sequence (do a then do b), functions operating on base types (but not functions taking functions as arguments), conditionals (if (x == y)), some primitives on base types (e.g. +, *). Then the execution of the program takes a time that is at most exponential, and in particular bounded, in the size of the program (the unit of time is an elementary expression, e.g. x := y takes one unit, x := y + z takes two units). In a nutshell, function application at most multiplies the complexity of the function by the complexity of the program, and the rest is linear.

Since this language can only express bounded-time computations, it cannot express all recursive programs (and in fact it cannot even express all primitive recursive programs).

In Elixir, this would be as easy as

def nthApply(f, x, n) do
  if n < 1 do
    x
  else
    nthApply(f, f.(x), n-1)
  end
end


Are algorithms (and efficiency in general) getting less important? Since buying computation power is much affordable than in the past, are the knowledge of algorithms and being efficient getting less important? It's clear that you would want to avoid an infinite loop, so, not everything goes. But if you have better hardware, could you have somehow worse software?

On the contrary. At the same time that hardware is getting cheaper, several other developments take place.

First, the amount of data to be processed is growing exponentially. This has led to the study of quasilinear time algorithms, and the area of big data. Think for example about search engines - they have to handle large volumes of queries, process large amounts of data, and do it quickly. Algorithms are more important than ever.

Second, the area of machine learning is growing strong, and full of algorithms (albeit of a different kind than what you learn in your BA). The area is thriving, and every so often a truly new algorithm is invented, and improves performance significantly.

Third, distributed algorithms have become more important, since we are hitting a roadblock in increasing CPU processing speed. Nowadays computing power is being increased by parallelizing, and that involves dedicated algorithms.

Fourth, to counterbalance the increasing power of CPUs, modern programming paradigms employ virtual machine methods to combat security loopholes. That slows these programs down by an appreciable factor. Adding to the conundrum, your operating system is investing more CPU time on bells and whistles, leaving less CPU time for your actual programs, which could include CPU-intensive algorithms such as video compression and decompression. So while hardware is faster, it's not used as efficiently.

Summarizing, efficient algorithms are necessary to handle large amounts of data; new kinds of algorithms are popping up in the area of artificial intelligence; distributed algorithms are coming into focus; and CPU power is harnessed less efficiently for various reasons (but mainly, because computers are getting more powerful). Algorithms are not dead yet.

No, mostly while considering space complexity! Storage capacity of a normal computer is growing exponentially.


Most efficient known priority queue for inserts In terms of asymptotic space and time complexity, what is the most efficient priority-queue?
Specifically I am looking for priority queues which minimize the complexity of inserts, it's ok if deletes are a little slower.

 If you're looking for a survey of priority-queues which minimises complexity of deletes over inserts, see: Does there exist a priority queue with $O(1)$ extracts?.

Worst-case complexity
Insert: $\mathcal{O}(1)$
Find-min: $\mathcal{O}(1)$
Decrease-key: $\mathcal{O}(1)$
Delete: $\mathcal{O}(\log \log n)$
Space: $\mathcal{O}(n)$
Proof

THEOREM 1. We can implement a priority queue that with n integer keys in the range $[0 , N )$ in linear space supporting ﬁnd-min, insert, and dec-key in constant time, and delete in $\mathrm{\mathcal{O}(log\ log\ min \{n, N\})}$ time.

Which is established with a combination of:

LEMMA 3. Let $\tau(n, N)$ be the delete time for a priority queue for up to $n$ integers in the range $[0 , N)$ supporting insert and dec-key in constant time. Then $\tau ( n, N ) \le τ ( N, N)$. This holds whether $\tau$ is amortized or worst-case.

and:

THEOREM 6. Theorem 6. We can implement a priority queue that with $n$ integer keys in the range $[0 , N)$ in linear space supporting ﬁnd-min, insert, and dec-key in constant time, and delete in $\mathrm{\mathcal{O}(1 + log\ log\ n − log\ log\ q)}$ time for a key of rank $q$.

Reference
Thorup, Mikkel. “Integer Priority Queues with Decrease Key in Constant Time and the Single Source Shortest Paths Problem.” In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, 149–158. STOC  ’03. New York, NY, USA: ACM, 2003.

Worst-case complexity
$\boldsymbol{\mathcal{O}(1)}$ insertion
$\boldsymbol{\mathcal{O}(log\ \textbf{min}\{w_x, q_x\})}$  get-min, extract-min, delete, and decrease of an element $\boldsymbol{x}$
Where $w_x$ (respectively, $q_x$) is the number of elements that were accessed after (respectively, before) the last access to $x$ and are still in the priority queue at the time when the corresponding operation is performed.
A. Elmasry, A. Farzan, and J. Iacono, “A priority queue with the time-finger property,” J. of Discrete Algorithms, vol. 16, pp. 206–212, Oct. 2012.
1


What is the meaning of uniform distribution of elements in an array? I was going through the concept of Interpolation search and it stated that when the elements are "uniformly distributed", it takes O(loglogn) to search an element using interpolation search. Can someone please explain me this?

Suppose that the array $A$ is chosen in the following way:

Sample $n$ real numbers uniformly from the interval $[0,1]$.
Sort the $n$ samples.

Suppose that you choose a further uniform random variable $x$ from the interval $[0,1]$. The expected running time of interpolation search on $A$ and $x$ is $O(\log\log n)$, where the expectation is over the choices of both $A$ and $x$.

In fact, if I understand Gonnet's thesis correctly, the expectation is still $O(\log\log n)$ even for any fixed $x$. See also Gonnet et al.

Usually an array is considered as uniformly distributed when the difference between the elements are equal or almost same.
Example 1: 1,2,3,4,5,6 (Difference is 1)

Example 2: 10,20,31,40,55,60,73,80(Here the difference between the two adjacent elements are almost close to 10).

Interpolation search is to be used when the given array is both sorted and uniformly distributed to have log(log n) time complexity.


What was the first programming language with loop break? While tracing the history of the BREAK and CONTINUE statements found in popular languages, I ran into a dead end right around ALGOL.

Algol _? -> CPL -> BCPL -> C -> C++ -> Java -> JavaScript

What was the first programming language to introduce the feature of being able to break out of a loop from the body?

This feature existed in BCPL and is implied to have existed (from its manual) in CPL which was introduced in 1963.

ALGOL 60 was CPL's main influence, but ALGOL 60 did not have the feature.

The structured programming movement started around 1966.

Given the turmoil in the committee between ALGOL 60 and ALGOL 68 (which spawned many languages), was this the source of the feature? Did it exist under a different form at the time as a block EXIT perhaps?

I sent an email to Martin Richards to try and get some details/context about CPL and he gave me a reply. To partially quote:

  "CPL did have a break command to cause an exit from a repetitive command such as while or until. As far as I remember it did not have an equivalent of continue, but the equivalent loop command was added to BCPL early in 1967."

[...]

  "The introduction of break in CPL was almost certainly influenced by Dijkstra's paper..."

He also pointed me to the following document (see page 5):

http://www.cl.cam.ac.uk/~mr10/cpl2bcpl.pdf

I nominate Konrad Zuse's Plankalkül, developed in the early 1940s. It is somewhat
debatable whether this is a valid answer, since the language was not actually implemented
until the '70s. But it had the equivalent to a break (actually closer to return in
Lisp, which doesn't mean "return from the current function" as it does in other
languages). Here is Zuse's description from his book about the
language
(translated to English):

Some plans[1] can be canceled before they have been fully calculated, because the
desired result has already been produced, or because further computation turns out to be
unnecessary. For example, a multi-part disjunction can be terminated as soon as one part
is true, and a multi-part conjunction as soon as one part is false. Therefore an
end-marking variable[2] $\mathrm{Fin}$ is introduced.
[Confusing example omitted.]
However, this kind of representation makes sense only if repetition plans[3] are
used or if individual conjunctive/disjunctive elements making up a plan are very
complicated.
Normally, the range of the $\mathrm{Fin}$ sign extends over the whole plan. But the
intention may be to skip only part of the plan, while still calculating the following
parts. In this case, it is necessary to separate the plan into groups of partial plans, so
that the $\mathrm{Fin}$ applies only to the desired part.
Plans containing $\mathrm{Fin}$ may be nested multiple times. It can then be indicated by
$\mathrm{Fin}^1$, $\mathrm{Fin}^2$, etc. whether the symbol applies only once or also at a
higher level. This is particularly important in repetition plans.
An expression following a ${\lower{2pt}{\rightarrow}\atop\kern{-1.5pt}\raise{2pt}{.}}$ sign[4] is considered to be a closed
part of the plan.

Notes:

Zuse used "plan" (German Plan) to mean what we today might call an "expression",
"statement", "program", "subprogram", etc. Note that the language is named Plankalkül,
which means something like "plan calculus" (the calculus of plans).

I think you can read "variable" as "identifier" or "symbol" here.

A repetition plan (German Wiederholungsplan) is a loop.

In Zuse's language, conditional execution is expressed in a way remarkably like
McCarthy's M-Expressions: An expression of the form
$x{\lower{2pt}{\rightarrow}\atop\kern{-1.5pt}\raise{2pt}{.}}y$ causes $y$ to be executed
only if $x$ is true.


Show that $\log n = o(n^\epsilon)$ I am trying to understand how to prove that a polynomial will always grow faster than a logarithm.

$\log n = o(n^\epsilon), \epsilon>0$

Intuitively, it is obvious, and plugging in a few numbers always yields true, but how can I prove this?

Maybe this can be done inductively (I would prefer this method if someone would explain it), but I attempted to prove through the use of derivatives and L'Hôpital's rule, namely:

$\lim_{n\rightarrow\infty}\frac{\log n}{n^\epsilon} = \lim_{n\rightarrow\infty}\frac{\frac{1}{n}}{\epsilon n^{\epsilon-1}}$ = 0

Is this getting me in the right direction to prove that the upper bound of $\log n$ it is strictly less than $n^\epsilon$?

Here is a simple proof which avoids L'Hôpital's rule.

We start with the observation
$$
\log n = \int_1^n \frac{dx}{x} \leq \int_1^n dx \leq n,
$$
and so
$$
\frac{\log n}{n^2} \leq \frac{1}{n} \xrightarrow{n\to\infty} 0.
$$

Given $\epsilon > 0$, using the fact that $\lim_{n\to\infty} n^{\epsilon/2} = \infty$, we see that
$$
0 = \lim_{n\to\infty} \frac{\log (n^{\epsilon/2})}{(n^{\epsilon/2})^2} =
\lim_{n\to\infty} \frac{\frac{\epsilon}{2} \log n}{n^\epsilon}.
$$
It follows that
$$
\lim_{n\to\infty} \frac{\log n}{n^\epsilon} = 0.
$$

Your solution is one tiny step away from proving that the limit is zero.

But obviously log n has no upper limit. And if eps is small, it will take a very large n to make n^eps < log n.

I recommend that you use a spreadsheet and try this. If eps = 0.001 then n must be as large as 10^1000 just to make n^eps = 10.


Does exist any horn formula that is equisatisfiable to the clause that is disjunction of two literals? Does also exist equivalent? I just and simply want to know if whether or not exist any horn formula that is equisatisfiable to $(p\lor q)$. I would also be interested to know if there also exists equivalent.

The answer is no: this is not possible. I assume a horn formula is a CNF formula with at most one positive literal (=nonnegated variable) in each clause. Now, for the sake of contradiction, suppose we have a horn formula $\phi$ that is equisatisfiable to $p\vee q$. Since $\phi$ is a horn formula, each clause in it contains a negative literal OR there is a clause consisting of only one (positive) variable. If the latter is the case, that positive variable must be a helper variable, since if it were p, it would mean that p must be necessarily true for satisfaction, which is not the case in "$p\vee q$" (same argument for q). So in this case, we derive an equisatisfiable formula by replacing that variable with true. In this new formula, we have one less clause that contains only a positive variable. We repeat this process until this is no longer the case, until we have a formula that has a negative literal in each clause. But such a formula is satisfiable by setting every variable to false. However, that's not the case in $p\vee q$, hence the contradiction.

If $p,q$ are atomic then the answer is trivial. I'll assume otherwise below.

Any Horn formula is satisfiable: $a_1 \land \cdots \land a_n \rightarrow b$ can be satisfied letting $b$ to be true.

$p\lor q$ is not necessarily satisfiable, so no Horn clause can be equisatisfiable with it, in general.


Find the nearest sum to a given number of two elements in sorted matrix Given a sorted  $n\times n$ matrix $A$ of real values. That is $a_{ki}<a_{kj}$ and $a_{it}<a_{jt}$, when $i<j$. Propose and algorithm, finding two elements of this matrix with the sum nearest to a given value $q$. The restriction of memory is $\mathcal{O}(n)$. It is not allowed to change a given matrix.

The naive approach  is $\mathcal{O}(n^4)$  brute force algorithm.

Also I can propose $\mathcal{O}(n^3)$ algorithm. Which use the following idea. Let we have two sorted arrays $c_1\leq c_2\le \cdots \leq c_{k}$ and $d_1\leq d_2\le \cdots \leq d_s$ and we need to find a sum of the form $c_i$ + $d_j$ nearest to a given $q$. We can do this by $\mathcal{O}(k+s)$ algorithm by imaginary merging two arrays:
$$
c_1\leq c_2\leq \cdots \le c_{k}; \ \ q-d_s\leq q-d_{s-1}\leq \cdots\le q-d_{1}
$$
in one array.
So to solve the problem we can iterate the set of row-pairs  of our matrix and to use the above idea. Of course this algorithm will have a complexity $\mathcal{O}(n^3)$.

  My question. How can we do this more effectively?

Try something like binary search since it is sorted
i.e. check a[n/2,n]+a [n/2 +1,1] if equal done
-smaller check the lower half
-greater check the upper half
(Keep the last checked value to compare how close with the next one)
Probably O ( log n2)


Push-down automaton for a language with number of 1s double than 0s This questions is taken from a complexity theory course.

  Design a push-down automaton that recognize $L = x \in \{0,1\}^* $
  such that $x$ contains a number of ones double than a number of zeros.

Example: x = 011011, 100011111, 011011110.

My approach

I tried to push on the stack a symbol "A" every time I read "0", than pop "A" from the stack when I read two consecutive "1" but this approach works not for every string $x$ in the language. Maybe the final PDA is non-deterministic. Any hints?

Consider this algorithm:

Initialize a variable $x := 0$.
Scan the string, left to right. If you see $1$, set $x := x + 1$, if you see $0$, set $x := x - 2$.
When you are done, accept iff $x = 0$.

It should be obvious that it recognizes your language. Can you figure out a way to implement it replacing the counter with the stack?

You need a 2-stack PDA to solve this problem.

Since the language you've given is non-context free, it's more powerful than a single stack PDA. More specifically, your language the union of many CFLs and non-CFLs.
The inputs that seem to be working with your way can be recognized by a single stack PDA. e.g.: S -> 0A11    A -> S    which is the language {0^n1^2n, n>=0}
                 S -> 11A0    A -> S    which is the language {1^2n1^n, n>=0}
                               .
                               .
                               .
However, there is no way to describe others with a context-free grammar.


Misunderstanding Turing's Halting-Problem Argument I just watched a video by Computerphile on the halting problem (https://www.youtube.com/watch?v=macM_MtS_w4) .  I’m having some difficulty understanding the argument as it is made.  Let me explain it as I see it:

So that our terminology is the same, H is a (hypothetical) program which can analyze another program to see if it halts.  H+ is a modified version of H which loops forever if the analyzed program halts and halts if the analyzed program does loops forever.

In order to run H, you need to specify 2 things – a program and the input to that program.  The Input to the analyzed program is necessary because the program’s behavior will depend on its input.

According to Computerphile’s explanation of Turing’s argument, we are asked to consider what would happen if H+ were to analyze H+ with H+ as its input.  Since there are a lot of H+’s being thrown around, let’s define H+1 as the program that I am running, H+2 as the program being analyzed, and H+3 as the input to H+2.  (Of course, H+1, H+2, and H+3 have the exact same code; they are just being used in different ways.)    My question is this:  if we require H+3 as an input to H+2, then shouldn’t we require an input to H+3?  And if we continue the pattern and use H+4 as an input to H+3, then wouldn’t this mean that we require an H+5 as an input to H+4?  And so on?

If you counter by saying that Turing’s argument doesn’t require H+3 to have an input (or that its input doesn’t have to be H+), then doesn’t this break the whole symmetry of the problem?  After all, the whole point of Turing’s argument (as I currently understand it) is that if H+2 runs on H+3 and halts then it would be a contradiction to have H+1 loop forever on H+2 since H+1,H+2,and H+3 are all identical (and vice versa were H+2 to loop forever on H+3).  But the situation isn’t identical.  In one case H+2 is running on H+3.  In the other, H+1 is running on "H+2-running-on-H+3".

I guess you could say that each H+ maybe can only look one step in front of it, so that H+1 only “sees” H+2 and H+2 only sees H+3.  But then what does H+3 see?  Doesn’t it need some input of its own? After all, whether or not H+3 halts depends on the program it’s given.    If so, this brings it back to my first point (that we would need an H+4).

It seems to me this whole argument falls apart.  Either you would need an infinite stack of H+’s which can’t happen, or you have a finite stack which because of the discontinuity at the end means that the symmetry of each level doesn’t translate to the one below it.

So what am I missing?

"So what am I missing?"  Nothing.    Computerphile should have defined H++ by  H++(x) = H+(x,x) ,  and then run H++ on itself.

I wonder if it will be easier to understand the real issue if there is a sly version of the Halts(program,input) program that instead was HaltsInUnderTenOperations(x,i).

Maybe you can use the same argument against Halts(x,i) to prove HaltsInUnderTenOperations(x,i) is not possible either, if you feed it to a program that halts it if it says no (would have taken ten or more operations) but makes it take ten or more operations if it says yes (would have halted in under ten operations).

Or rather than ten, choose an appropriately small finite number for which it would be self-evident that you can easily tell what the output of HaltsInUnderTenOperations will be - in other words, you can solve it but it is a logical contradiction and therefore an impossible program.

The fact there is nothing wrong with the program that halts or doesn't based on the simple "yes/no" input, means the program that has something wrong with it is the Halts (or the HaltsInUnderTenOperations).

This may seem confusing but it is similar to how the Busy Beaver problem is easily solvable from 1 or 2 states.


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

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

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

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

Thanks in advance

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

it is CFL. consider this CFG

S --> X | Y

X --> aXb | aX | a

Y --> aYb | Yb | b