Packing unsplittable flows problem For a single stream of elements as input every elements should be routed into a fixed number of $k$ output streams trying to keep them balanced. In the following example $k=3$ :

Let's define as flow a sequence of element of the same type represented in the following diagrams using the same colour. Every flow must be routed into the same output stream keeping the elements ordered as found on the input stream:

Another correct solution that is more balanced than the previous one:

Considering also that:

After a number of elements (called $timeout$) on the input stream without any element of the type of a specific flow, that flow should be considered ended and the element found should be the starting point of a new flow

I have some questions:

Do you know any paper covering this kind of problems?
What is a good algorithm that maximise the throughput, in other words keeping the output stream balanced?

Update

Thanks to @D.W. for the comments, here some clarifications:

I am looking for an "online algorithm" where a "reasonable" latency is allowed therefore a lookahead-buffer/moving-window is definitely allowed
I am not looking for theoretical guarantees, I am looking for an approximate algorithm to try against few hundreds test cases made of [millions..billion] elements with a mix of few elephant flows and many mice ones.
The stream balance I am looking for should be considered over a period of time and not in an "absolute sense". In other words an algorithm that fills the first stream only then the second and then the third is as balanced as an algorithm that fill only the first stream

The obvious algorithm is the greedy algorithm.  Each time you see a new element that's not part of an existing flow, you identify which output stream currently has lowest occupancy, and route that element to that output stream.  When you see an element that is part of an existing flow, you obviously have no freedom about where to route it; it has to go to the same output stream as the rest of the flow.

In an online setting where you must decide immediately where to route each element and where you have no information about the distribution of flow sizes or other domain knowledge, this is the natural strategy.  When you see the first element of a flow, you have no information about how large the flow will be, and you must decide immediately where to route it based only upon the current state of the output streams.  It's not clear whether there is any theoretical sense in which one can provably do better, if we have zero knowledge.

Now in practice I suspect you will typically have some a priori knowledge about the distribution of flow sizes.  In this case, you can do bit better.

For instance, suppose you knew that all flows were either mice (they have 1 element) or elephants (they have 1000 elements).  Then it would be easy to do better.  When you get a new element that's not part of an existing flow, look at the existing flows in the output streams.  For each existing flow in an output stream that has more than 1 element, you know exactly how many more elements are yet to be received in that flow, so you get a lower bound on how full that output stream will become once all of the remaining packets in the existing flows arrive (it is a lower bound since for the flows where you've only seen one packet you don't know yet whether they are mice or elephants).  Call this the degree to which that output stream is "committed".  Now you can use these lower bounds to pick which output stream is least committed, and route the new element to that output stream.

If you additionally know what fraction of flows are mice and what fraction are mice, instead of computing a lower bound you can compute an expected value and choose which output stream to route to by going for the choice where the expected value of the imbalance is minimized.

In general, you can use a greedy algorithm that uses expected output stream commitment as the basis for choosing an output stream.  Let the random variable $X$ be distributed according to the distribution on flow sizes, i.e., $X$ is a random variable that counts the number of elements in a randomly chosen flow.  Suppose you have seen $k$ elements in a particular flow, so far.  Then the conditional expectation $\mathbb{E}(X | X\ge k)$ is in some sense your "best guess" at what the total flow size will be; it is the expected flow size, given that the flow contains at least $k$ elements.  Thus, you can compute this for each active flow, and compute the sum of these values for each output stream, and route the new flow to the least-committed output stream.  If you know the distribution of $X$, you should be able to compute $\mathbb{E}(X | X\ge k)$ easily.

This algorithm is fairly simple and should be pretty efficient: it requires $O(1)$ state per active flow (a counter to keep track of the number of elements seen in that flow so far).  Assuming you can compute the conditional expectation in $O(1)$ time, the algorithm requires $O(1)$ time per element.

Whether this algorithm is sufficiently better than the simple greedy (choose the lightest output stream, based only upon its current size, not its expected commitment) in practice can only be answered by experimenting on some realistic data sets.


maximum flow with all or nothing through each edge Consider a maximum flow problem, where each edge has a small integer capacity. Now, I want a solution that for each edge uses the entire capacity, or no flow through that edge at all. To avoid the subset-sum problem, the capacities are small. Is this solvable in polynomial time or is it NP-Complete?

Your problem is NP-hard. There is a reduction from Independent Set to its decision version.

Consider an instance $G=(V,E)$ of Independent Set, you construct a network with vertices $\{s,t\}\cup V\cup V'$ where each vertex in $V'$ corresponds to a pair of vertices in $V$. For example, if $V=\{1,2,3\}$, then $V'=\{v_{12},v_{23},v_{13}\}$. Then we construct the edges as follows:

For each vertex $x\in V$, add an edge $(s,x)$ with capacity $|V|-1$.
For each vertex $v_{xy}\in V'$, add two edges $(x,v_{xy})$ and $(y,v_{xy})$. Both edges have capacity 1.
For each vertex $v_{xy}\in V'$ where $(x,y)\in E$, add an edge $(v_{xy},t)$ with capacity 1.
For each vertex $v_{xy}\in V'$ where $(x,y)\notin E$, add two edges $(v_{xy},t)$ with capacity 1 (if multiple edges are not allowed, we can add another two vertices $u_1,u_2$ and add two paths $v_{xy}\rightarrow u_1\rightarrow t$ and $v_{xy}\rightarrow u_2\rightarrow t$, which has the same effect).

Now $G$ has an independent set of size $k$ if and only if the constructed network has a flow of value $(|V|-1)k$.

Consider the following decision problem.
Determine if the network N has a flow of size at least k, but with the restriction that some (fixed pre-determined) edges must either have 0 flow, or be at maximal capacity.
This problem is NP-complete, I have a proof written up here (arxiv).


Edit distance (Levenshtein-Distance) algorithm explanation I want to calculate the edit distance (aka Levenshtein-Distance) between two words: «solo» and «oslo».

According to this site we'll get the result matrix:

What I don't understand is: In case of comparison the last «o» from «solo» with the first «o» of «oslo» will see the submatrix:

3 2
4 3

As far as I understand, in order to calculate the bottom right value, which is equal in this example to 3 of this submatrix, we'll get the min(3, 2, 4) + (0 if the letters are the same, otherwise 1). So, why in this example the bottom right value is equal to 3 and not to 2?

You got the recursive definition wrong. It's

$\qquad\displaystyle d_{ij} =
  \min \begin{cases}
         d_{i-1, j}  + c_\mathrm{del}(b_{i}) \\
         d_{i,j-1}   + c_\mathrm{ins}(a_{j}) \\
         d_{i-1,j-1} + [a_j \neq b_i] \cdot c_\mathrm{sub}(a_{j}, b_{i}) \end{cases}$

where the $c_{\mathrm{op}}$ are fixed costs for the respective operations, all of which are $1$ here. You'll note that for alternatives one and two, insertion and deletion (which correspond to a vertical resp. horizontal step in the matrix), don't care if the current symbol matches any other -- you introduce a gap symbol, anyway!

Following this definition, clearly $2+1$ (insertion of $o$) results in the entry you highlight. Note that the alignment computed (implicitly) up until this point is

$\qquad\begin{array}{cccc}
  - & o & - & - \\
  s & o & l & o
\end{array}$

If we look deeply at algorithm implementation in C:
http://en.m.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C

we'll see the main string which fills the matrix:

matrix[x][y] = MIN3(matrix[x-1][y] + 1, matrix[x][y-1] + 1,
                    matrix[x-1][y-1] + (s1[y-1] == s2[x-1] ? 0 : 1));

as we can see, the value of cells with indexes matrix[x-1][y] (upper cell) and matrix[x][y-1] (left cell) in automatically increased, the upper-left cell (by diagonal) with index matrix[x-1][y-1] is increased by 1 only if the letters are different and only after that we'll take a minimum from these 3 values. In other words:

3 2
4 min(3+0, 2+1, 4+1) = 3


Does programming language detection need more input than natural language detection? I wonder which one of the two needs a larger input to achieve a decent accuracy:

programming language detection or natural language detection?

More details:

Definition of Language detection:

  In natural language processing, language identification or language
  guessing is the problem of determining which natural language given
  content is in. Computational approaches to this problem view it as a
  special case of text categorization, solved with various statistical
  methods.

The question I was asking can be written bit more formally as: let $x$ be a substring from some text $X$ written in natural language, and $y$ a substring from some source code $Y$ written a programming language. Assume a $X$ and $Y$ are each written in one language only (natural language or programming language).

Let $f(X)$ be the size of $x$ so that on average (i.e. trying on a bunch of different X) I correctly predict the language with accuracy $p$. Does $f(X) < f(Y)$ or $f(X) > f(Y)$ ?

Answering knowingly this question would require experiments. I am sure
there is some data for natural languages, where it is a common
problem. I recall from memory that one study gave ridiculously small
figures for natural language, which is not too surprising. If you take
5 consecutive word in a sentence (the figure I recall, without being
sure), there is a good chance that one of them belongs to a single
language, and even more that the fragment can syntactically belong to
only one language (parsing fragments without context is possible with
existing technology). To me the problem is not so much the size of the
input as the size of the recognition program and its data. There is a
compromise there. Actually my guess is that keeping all the relevant
data is far too costly, and that the actual techniques are statistical
ones, such as checking n-grams of letters. (see Wikipedia), which are
extremely effective.

Regarding programming languages, the problem is a bit different. The
size of the vocabulary is ridiculously small, and identifiers do not
give any indication (or very little with the allowed mophology: a
language could forbid to use dask inside identifiers, for example).
Furthermore, what fixed vocabulary there is (keywords) is often the
same in many programming languages.  However, programming languages
have a very strict syntax, which will certainly distinguish them
rather quickly.  It is not so much how long a fragment as the kind of
fragment. A long succession of assignments might look the same in many
programming languages. Buit I would not venture any figure, and I am
not even sure statistics would make sense.

Then there is the issue of parenthood. A fragment of Pascal may look
very much like a fragment of Algol 60 or Simula 67. Is American
English to be distinguished from British or Autralian English?

To conclude, without any hard knowledge on facts:

The problem should be stated with a word regarding the space cost (and
possibly time-cost) of the identification program.

Identification for natural language is essentially morphology or
lexically based, and will use statistical techniques if space costs
are to be acceptable. They can recognize fairly short sequences (a few
words as I recall) with good accuracy.

Identification for programming languages is essentially syntax based,
and probably needs larger fragments in number of tokens, in order to
have enough syntax substance, despite the intentional similarities
between programming languages. But it can probably be 100% accurate,
without excessive size of the identification program. I would however
be more confident if I had actual data to back my guesswork. I do not know of any work on this topic.

Considering only fragments is not an issue. It is obviously not an
issue when only lexical information is used. It is not an issue either
when syntactic information dominates, as the technology to parse
fragments is working well.

Afterthoughts, after the question was completed.

One minor remark concerns the concept of substring size: is it measured in
characters, in bytes, in lexical elements? Size of character encoding
is variable. Characters take diacritical marks. Lexical elements have
different average size in natural and programming languages.

A more important remark concerns the mode of measurement. Natural
language will use statistical methods to avoid the problem of natural
language huge specification. Hence the answer is accordingly accurate
with some probability that may depend on substring length (different
techniques produce different types of mis-detection).

In the case of programming languages, the specifications are small
enough that they can probably be used exactly. Hence the answer could
possibly be always 100% exact at acceptable cost. The problem would
not be with the detection procedure inaccuracies as in natural
language, but in the question itself. If a string does not
discriminate two languages because it can belong to both, no amount of
technology will help you solve the problem. In such a case, the
detection software should not guess, which would be meaningless, but it should just list, with a 100% accuracy, all the
programming languages the substring can belong to.

In other words, the case of natural language and the case of
programming languages are very different technically. I am not sure it
makes sense to compare them.

the idea that human languages are similar to programming languages is encouraged by the use of the term "language" in theoretical computer science but there which (also) has a very specific technical/mathematical meaning. this blurring was encouraged by ideology associated with one of the rare crosscutting pioneers in CS/linguistics, Chomsky. a computer science "language" refers to a set of strings, possibly infinite. however, there is no ambiguity involved in these mathematical sets. human language has ambiguity. human language recognition is an imperfect/ imprecise/ inaccurate exercise even for humans and it is an open question in AI whether there is an algorithm for it.

a similar analogy can be made to Turing machines. real PCs are alternatively sometimes considered equivalent, or inequivalent. sometimes the analogy breaks down. another case study here is ambiguity in CFLs. programming languages, all basically/roughly CFLs, are carefully built to avoid ambiguity. all human languages have ambiguity that even humans imperfectly parse. so in short, the question mixes up apples and oranges. but this is not uncommon in even some professional/ scientific writing on the subject of AI-related topics.


Could anyone prove why O(n^(log n)) < O((log n)^n)? Could someone provide a rigorous proof of why $O(n^{log n}) \leq O((\log n)^n)$ is true? I'm trying to do this by induction but it isn't working. Thanks.

Using $ < $ with the big-oh notation is a bit of abuse of notation.
Formally, I take your statement to mean $\forall f(n) \in O(n^{\log n}), \; f(n) \in O((\log n)^n)$.

Let $f(n) \in O(n^{\log n})$, by definition of big-oh we know that the function is eventually bounded from above by $c n^{\log n}$ for some constant $c > 0$.
Then, for sufficiently large $n$,
$$
f(n) \le c n^{\log n} = c 2^{\log(n^{\log n})} = c2^{\log^2 n} < c2^n < c (\log n)^n,
$$
showing that $f(n) \in O((\log n)^n)$.

In particular the constant c in the last term can be made arbitrarily small. Indeed $n^{\log n} \in o((\log n)^n)$. A simple way to see this is by taking the limit of the ratio of the two functions:

$$
\lim_{n \to \infty} \frac{n^{\log n}}{(\log n)^n} =
\lim_{n \to \infty} \frac{2^{\log^2 n}}{2^{n \log n}} =
2^{\lim_{n \to \infty} \log^2 n - n \log n} = 0
$$

Try to check for large values of n
Suppose n = 1000 and base of log = 10.
i.e
for n^(logn) = (1000)^3 = 1000000000
(logn)^n     = (3)^100  = 5.1537752e+47

Thus results are speaking for itself.


How is the computational power of a human brain comparing to a turing machine? This seems related to these questions at a glance:

What are some problems which are easily solved by human brain but which would take more time computers?

What would show a human mind is/is not reducible to a Turing machine?

But not quite, I am not asking about "time", but power. Also, I am not interested in the turing test. That said, my question can also be expressed as two parts:

Is there a language, which cannot be recognized by any turing machine, that can be recognized by a human?
Is there a language, which cannot be decided by any turing machine, that can be decided by a human?

And vice versa. The "language" I am talking about is the "mathematical" language, not only a "human" or "programming" language:

$$L \subseteq \Sigma^*$$

Since this is a question about computational power, I would make the following assumptions:

Human do not make mistakes
(here I mean mistakes like copying the wrong character or computing arithmetics incorrectly, typical human errors)
There is no space limit (turing machine gets infinite tape, you get infinite medium to write)
There are no time constraints
However, the recognition/decision must be achieved within finite time.
And of course, in finite space

Please give an example if you have an answer. Remember, this is a theoretical question, so practical issues are not in concern.

EDIT 1

OK, as someone pointed out, I will add the following assumptions.

Human is probably not easy to define in precise mathematical words, so let's just assume "you".

About a human recognizing a string in a language, I am talking about performing the same task the turing machine is "programmed" to do. Say, given a string, whether you (a human) can recognize it when it conforms to a set of rules, or decide whether it conforms to a set of rules or not. I am not sure if I can make the point clear enough...

EDIT 2

OK, to clarify, this is a question about model of computation, so yes, like André Souza Lemos mensioned, I am talking about "given a word $w$ and a language $L$, is sentence $w\in L$ decidable". I am not talking about a physical computer.

EDIT 3

OK, this is another idea I came up with. Does model of computation theory include inputs that are volatile by itself? That is, the input changes itself? That is probably not the "language recognition" problem though...

Given that Alan Turing devised the Turing Machine model of computation by abstracting what humans actually do when they compute by hand, I think one would be very hard-pressed to prove that a Turing Machine is more powerful than a human.

[note: by 'human' I assume a person augmented by a writing implement and an unbounded supply of scratch paper (which corresponds to the tape of course).  Without that I believe a human is actually a (dynamically self-reconfigurable) finite-state machine with an extraordinarily large number of states]

My take:
If by Turing Machine you mean "a plane" Deterministic Turing Machine (DTM), then, a human brain would be strictly more powerful as long as a brain can be

a non-deterministic TM: in this case, the same set of problems can be solved by both, but for some of them, the running time of the brain is faster ¿P machine = NP brain?

a non-deterministic TM using randomized algorithms. Here: the brain can solve, with high probability, problems that a DTM can't.

a non-deterministic TM using randomized algorithms and quantum algorithms.


Proving that $NPSPACE\subseteq PSPACE$ using the proof of Savitch's Theorem We were shown a proof of $NPSPACE\subseteq PSPACE$ in class. In short, the proof says:

Let $L\in NPSPACE$.
Then there exists a non-deterministic polynomial space bounded Turing machine $M$ that accepts $L$.
For every input word $w$, the number of vertices in the configuration graph of $M$ is exponential in $|w|$.
Nevertheless, using the algorithm from Savitch's proof, we can check whether there exists a path in the graph from the initial state to the accepting state, using space polynomial in $|w|$.

My problem is the memory required to store the graph. How can we store the graph using space polynomial in $|w|$?

I had the same thoughts when i did Complexity course myself.
Its a very simple answer - the graph is stored on the tape and even though it is part of the input, its not calculated as part of the space complexity of the machine.
This is by definition of space complexity analysis.


How to measure "sortedness" I'm wondering if there is a standard way of measuring the "sortedness" of an array?  Would an array which has the median number of possible inversions be considered maximally unsorted?  By that I mean it's basically as far as possible from being either sorted or reverse sorted.

No, it depends on your application. The measures of sortedness are often refered to as measures of disorder, which are functions from $N^{<N}$ to $\mathbb{R}$, where $N^{<N}$ is the collection of all finite sequences of distinct nonnegative integers. The survey by Estivill-Castro and Wood [1] lists and discusses 11 different measures of disorder in the context of adaptive sorting algorithms.

The number of inversions might work for some cases, but is sometimes insufficient. An example given in [1] is the sequence

$$\langle \lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \ldots, n, 1, \ldots, \lfloor n/2 \rfloor \rangle$$

that has a quadratic number of inversions, but only consists of two ascending runs. It is nearly sorted, but this is not captured by inversions.

[1] Estivill-Castro, Vladmir, and Derick Wood. "A survey of adaptive sorting algorithms." ACM Computing Surveys (CSUR) 24.4 (1992): 441-476.

If you need something quick and dirty (summation signs scare me) I wrote a super easy disorder function in C++ for a Class named Array which generates int arrays filled with randomly generated numbers:

void Array::disorder() {
    double disorderValue = 0;
    int counter = this->arraySize;
    for (int n = 0; n < this->arraySize; n++) {
        disorderValue += abs(((n + 1) - array[n]));
//      cout << "disorderValue variable test value = " << disorderValue << endl;
        counter++;
    }
    cout << "Disorder Value = " << (disorderValue / this->arraySize) / (this->arraySize / 2) << "\n" << endl;
}

Function simply compares the value in each element to the index of the element + 1 so that an array in reverse order has a disorder value of 1, and a sorted array has a disorder value of 0. Not sophisticated, but working.

Michael


Contraint with three variables into three binary constraints I'm having a hard time tackling the following problem (perhaps some key data is missing). We have a constraint:

$A+B= C$

One is supposed to represent this one constraint using three binary constraints. Is this even possible? No domain is given, but even if it was, I really don't see how this could be achieved...

Good question.  Your instinctive reaction is quite valid: if you stick with the variables $A,B,C$, there is no way to introduce some set of binary constraints that will be equivalent to $A+B=C$ (where each constraint is only allowed to mention two of $A,B,C$).

The trick is to introduce new variables, or change the set of variables.  If you do that, it can be done.  For instance, see the reference that hengxin suggests: http://ktiml.mff.cuni.cz/~bartak/constraints/binary.html.  However, it would be understandable if you feel that this is in some sense "cheating"... which might be why you didn't think of this approach.

agreed there is not enough info. please clarify. lacking that here is one interpretation; your ref may be using "+" to refer to binary OR ($\vee$), this is common in many refs. then we have the table

a + b = c
0   0   0
0   1   1
1   0   1
1   1   1

leading to a truth table (x is true iff the eqn A + B = C holds)

a b c x
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1

this can be encoded as four binary constraints but not fewer (proof exercise for reader):

$(A \vee B \vee \bar{C}) \wedge (A \vee \bar{B} \vee C) \wedge (\bar{A} \vee B \vee C) \wedge (\bar{A} + \bar{B} + C)$

however introducing auxiliary (free) variable D one can write using 3 boolean constraints:

$(C \vee \bar{D}) \wedge (\bar{A} \vee D) \wedge (\bar{B} \vee D)$

background: this is basically the same construction used in the Tseitin transform (exercise for reader to show the correspondence).


Can all languages have semantic and logical errors? I have been reading about PHP and many authors mention semantic and logical errors separately. As an example of a semantic error, they give a function called with incorrect number of parameters: this will not be caught by the parser, but will throw an error when run.

Yet in languages such as C++, this will be caught by the compiler. I would say that it's a syntax error then. What is the difference then between a semantic and a logical error?

For example, in How to think like a computer scientist, the author uses "logic error" and "semantic error" interchangeably. On the other hand, in the Visual Basic .NET. Primer Plus, "logic error" is separated from "semantic error".

I think most likely the explanation for some authors using "logic error" and "semantic error" interchangeably and some authors drawing a distinction is simply that they don't have a precise universally accepted definition, and so people are using the terminology slightly differently. I wouldn't get hung up on it.

Both "logic" and "semantic" imply something to do with the meaning of the programming, so it would be easy to regard them as the same.

If I were to draw a distinction, a useful one I can see is that a logic error is when the program ends up meaning something other than what the programmer intended, and a semantic error is when the program ends up not meaning anything (consistent) at all. With those definitions, you could either regard logic errors as a superset of semantic errors, or that logic errors exclude errors that result in the program being inconsistent.

For example, the following pseudo code contains only a logic error:

x = read_number_from_user("x: ")
y = read_number_from_user("x: ")
print("The product of x and y is: ")
print(stringify(x + y))

The meaning of this program (taken solely as-is and without considering the programmer's intent) is perfectly straightforward and consistent. But it doesn't mean what the programmer intended it to mean.

OTOH, the following pseudo code contains a semantic error:

name = read_string_from_user("What is your name?")
print(name + 1)

At least, it does if we assume that adding a string and a number doesn't mean anything. In languages like PHP it does mean something, and this wouldn't be a semantic error.

Your example of a semantic error in PHP as calling a function with an incorrect number of parameters is actually interesting, because it's debatable whether you should call that a semantic error (with the definition I'm using).

Functions are defined dynamically at runtime in PHP. So calling a function with an incorrect number of parameters could be regarded as a logic error; perhaps the wrong include statement was executed, causing a different function with the same name to be included than the one the call was supposed to go to. Even if not, calling a function with the wrong number of arguments does mean something; it means lookup the function with this name and pass it these arguments. It's only operationally at runtime that it turns out the interpreter is unable to carry out those requests; just as x / y means something, but may be impossible to carry out if y happens to be 0 at runtime.

Ultimately, how you classify errors using a distinction like the one I'm making here between logic and semantic errors (even if it's not exactly the one I'm making) depends very much on the particular language you're talking about and how you assign meaning to programs in the language. Most commonly used languages do not have a standard way of assigning meaning to their programs, which means that everyone uses a slightly different way of doing so (though everyone's interpretation would agree very closely on almost all operational effects), and would analyse the "logical" vs "semantic" distinction differently.

Another similar way of looking at it would be to say that semantic errors are whatever causes the programming language to reject the program as invalid (apart from syntactic errors, though again you could call those a subset of semantic errors if you want). If the programming language accepts the program then it means something, and if it fails at runtime then that is the result of a logic error. This is pretty much assigning the programming language implementation (interpreter, compiler + runtime system, whatever) as the definition of what programs mean.

According to my higher computing course notes, semantic errors and logical errors are just different names for the same thing.


Is unary language with polynomial power context sensitive? I suppose that $\Sigma = \{a\}$.

Prove or Disprove: For every polynomial $p(n)$ with coefficients in $\mathbb{N}$, $L = \{a^{p(n)} \; | \; n \in \mathbb{N}\}$ is a context sensitive language.

It seems that it is a context sensitive language. I guess making LBA or context sensitive grammar is not easy for this language.  Can I prove this with closure property of CSL for example like complement?  Can any one help me to prove for instance $L_1 = \{a^{n^7+n^5+n^3+n^2+1} | n\in \mathbb{N}\}$ is context sensitive. Maybe I can get an idea from this to prove my first question.

Not true for linear polynomials.  E.g let $p(n)$ be $3n+2$, then L is generated by the regular grammar  'S --> aaaS | aa'.  [unless you mean 'at most context-sensitive', not 'exactly context-sensitive']

The Pumping Lemmas for both regular and context-free grammars seem to imply that any language over a 1-letter alphabet can be decomposed into a (not necessarily disjoint) union of sub-languages corresponding to linear polynomials.  If the set of linear polynomials in question can be made finite (which I suspect must be true, but I can't prove or disprove off the top of my head [and I am not sure it even matters]), then any higher-degree polynomial must take on values not achieved by any polynomial in the linear set, in which case such languages must be at least context-sensitive.

Also: A strategy for building a context-sensitive grammar for a polynomial language over one alphabet is to construct a sequence of $k$ sub-grammars, each of which takes $m$ consecutive $a$'s and transforms it into $b_km+c_k$ consecutive $a$s for some constants $b_k$, $c_k$ [think "Horner's Method"] and then 'cascades' to the next sub-grammar.

So if you mean 'at most context-sensitive', then yes.


3SAT solvable in polynomial time...but with exponential tuning? Suppose there exists an algorithm that solves 3SAT in a polynomial number of steps.  However, this algorithm requires some 'tuning' parameters, and the value of these tuning parameters take an exponential number of steps(given the input) to determine.

Would this place 3SAT in P? (since it can be solved in polynomial time given the appropriate parameters)

Or would 3SAT remain in NP? (since it still takes an exponential number of steps to ultimately solve)

Edit: just to clarify, the question is about whether or not 3SAT would 'move' to P or 'remain' where it currently is...NP.  If 3SAT 'moves' to P it obviously would still be contained in NP.

If the tuning parameters depend on the entire input, then it's not a self-contained algorithm, so it says nothing about whether 3SAT is in P.

After all, I can give you an algorithm that has that property: in my algorithm, the 'tuning parameter' for a 3SAT formula $\varphi$ is 0 or 1, according to whether the formula $\varphi$ is satisfiable or not.  My algorithm ignores the formula on its input and just outputs its tuning parameter.  Sure, it may take exponential time to find the right tuning parameter for any particular formula, but once you've got it, my algorithm can output the right solution in polynomial time -- in fact, in just $O(1)$ time.  Yet this says nothing about whether 3SAT is in P or not.

https://arxiv.org/abs/cs/0205064
SAT is a question about a set under constraint. If one approaches it as a set under constraint problem not a search for a constraint solution problem it is easy to solve. 3SAT is P space time. Irrespective how one structures the data for an algorithm one is faced with determining if for the entire set of possible assignments to the set of all possible 3-tubles of variable there exists a non-empty set of assignments. The set of assignments is empty if and only if all possible assignments to any one 3-tuple are excluded under constraints. For each constraint simply eliminate all assignments not allowed by constraint. Determine is new constraints are admitted. Repeat until either (a) no new constraints are admitted or (b) some 3-tuple if fully constrained (has no allowed assignments). It is a monotonic decreasing operation on a finite enumerable set. It runs in approximate order X^3 for 3SAT. It was never hard.


Efficient algorithm for edit distance for short sequences I have an application that needs to compute billions of levenshtein distance between pairs of strings. The strings are short (70 in length) DNA sequences, consisting only of 4 characters. Also it can be assumed that one of the strings is fixed, i.e., we are comparing one fixed string to a billion other strings.

I know that the dynamic programming implementation of the levenshtein distance is $\mathcal{O}(m n)$, would like to know if there are any room for improvement. I found these two algorithms:

$\mathcal{O}(n + d^2)$ algorithm, in which $d$ is the edit distance by  Berghel et al. However I can't make the assumption that $d$ is small so it might not give any advantage
$log(n)^{\mathcal{O}(1/\epsilon)}$  approximation in $n^{1+\epsilon}$ time by Andoni et al. But I have two concerns regarding this:

Is this algorithm also fast in practice?
Does $log(n)^{\mathcal{O}(1/\epsilon)}$ mean the computed edit distance in worst case is $log(n)^{\mathcal{O}(1/\epsilon)}$ times the actual one? In that case it's too much.

Do you know of any other algorithm/idea/approach that might be applicable?

One approach is to build a Levenshtein automaton for the fixed string (see, e.g., here).  Given a string $x$ and a distance $D$, you can build a DFA that recognizes all strings that are at distance $\le D$ from $x$.  Thus, you can test whether a string is close to $x$ in $O(n)$ time, where $n$ is the length of the string.  I'm not sure what the space requirements are to store the DFA (they are linear in $m,n$, but might be exponential in $D$).

Alternatively, you could use an "early-out" algorithm for computing the edit distance.  You mentioned that you are only interested in the edit distance if it is less than some threshold $D$.  There is an "early-out" algorithm for computing the edit distance whose running time is $O(\max(n,m) \times D)$, which computes the edit distance if it is $\le D$ or else outputs "too big" if it is $>D$.  Basically, you do the standard dynamic programming algorithm for the edit distance, but only compute the elements of the matrix that are $\le D$ away from the diagonal.  In your case this might or might not be better than the other alternatives.

If I had to do billions and it was only 4 characters I would represent the characters as
1000
0100
0010
0001
It is then a 35 byte integer

Dot a bit-wise and and count the 1's

Not perfect but billions is a lot unless you throw a lot of CPU at it.


Finding number of edges with weight less than k on the path between two nodes in a tree You are given a tree with $n$ nodes and $n-1$ edges. Each edge has a weight. There are $m$ queries. In each query you have to answer the following question:

How many edges are there in the path between node $a$ and node $b$ with weight less than $k$?

$a$, $b$, and $k$ vary in each query.  You're allowed to preprocess the tree to make it easy to answer each query.

Consider the tree with edges

          1
 weight=4/ \weight=5
        2   3
weight=4|
        4
weight=4|
        5

Between nodes 3 and 5, the total number of edges with weight less than 5 is 3, i.e. {1-2, 2-4, 4-5}.

I was trying to solve by brute force method by checking each path.

I want to know if there is a better way of solving this.

You can answer each query in time $O(\log^3 n)$, plus whatever time is needed to answer a lowest-common-ancestor query (a tricky $O(1)$-time solution exists, but you might as well go with the easier $O(\log n)$-time solution, since it doesn't hurt the final time complexity), after doing $O(n\log^3 n)$ preprocessing.

We only need counts from each vertex to the root

Let's call the number of edges of weight less than $k$ on the path from a vertex $v$ to the root $f(v, k)$.  We can calculate the desired final answer -- the number of edges of weight less than $k$ on the path from $a$ to $b$ -- using $f(a, k) + f(b, k) - 2f(lca(a, b), k)$, where $lca(u, v)$ is a the lowest common ancestor of $u$ and $v$.

From now on we will focus on answering the simpler question of computing $f(v, k)$.

Heavy-light decomposition

The heavy-light decomposition decomposes the tree into disjoint paths in such a way that at most $O(\log n)$ such "heavy paths" are visited on the path from any vertex to the root.  This can be accomplished with a DFS in $O(n)$ time.  The idea here is that, since the heavy paths are disjoint, if we have a way to quickly compute the number of edges of weight less than any given $k$ for each one, then we can nearly compute $f(v, k)$ for any $v$ and $k$ just by summing these counts over all heavy paths that we visit on the way from $v$ to the root.  And we do have a way to do this counting: Simply by sorting the edges within each heavy path by weight in a preprocessing step, we can later binary-search for any $k$ to count the number of edges of weight less than $k$ in this particular heavy path in $O(\log n)$ time.

But why only "nearly"?  Because we have so far ignored the possibility that $v$ might not begin exactly at the bottom of a heavy path -- it could begin part-way up.  We could try to "patch things up" by walking down to the bottom of the heavy path containing $v$, subtracting 1 from the count for each edge of weight less than $k$ that we see -- but this won't be worst-case efficient, since an individual heavy path can be as long as $n-1$ edges.  We need a way to handle this bottommost heavy path efficiently.

As noted by commenter xskxzr, the issue of beginning part-way up a heavy path is not only confined to the bottommost vertex $v$ in a path to the root -- it can also happen in the middle of such a path, such as in the path from 11 to 0 in the figure on the linked page.  Fortunately, the same trick, described next, works for both cases.

Fenwick trees of sorted lists

The subproblem we are now focussed on is: Given the ordered list of edge weights $x_1, \dots, x_m$ encountered while traversing down a particular heavy path, we want to preprocess this list to enable us to be able to later efficiently answer queries of the form "How many of the first $r$ elements are less than $k$?", with both $r$ and $k$ part of the query.  One way is to use a Fenwick tree which has as its elements not individual integers, but sorted lists of integers.

A "regular" Fenwick tree with single-integer elements takes $O(n)$ space.  Since each $x_i$ belongs to at most $O(\log n)$ buckets, increasing the size of the Fenwick tree's elements from single integers to sorted lists of integers fortunately only increases space usage by a $\log n$ factor.  The associative operation in a "regular" Fenwick tree is usually addition; in our Fenwick tree it's "set union".  For efficiency, all lists should be populated in a first pass, and then only sorted once, in a second pass.  This can be done in $O(n\log^2 n)$ time for a single heavy path, so $O(n\log^3 n)$ overall.

To process an $(r, k)$-query for a particular heavy path, a subquery in that heavy path's Fenwick tree is performed on each of the sequence of buckets found by stripping least-significant 1-bits from $r$, and the counts from these subqueries are summed.  That much is standard for Fenwick trees, but the individual subqueries are more complicated: Instead of just reading out the integer value from each bucket, we must binary-search the sorted list in that bucket for $k$; the leftmost position where $k$ appears (or would appear) tells us the number of edges of weight less than $k$ in that bucket.

An example might help: Suppose $r = 43$.  In binary, 43 is 101011 (32 + 8 + 2 + 1).  To answer a query for $r = 43$ (and some $k$ value), we would binary-search for $k$ in the following 4 buckets: 101011, 101010, 101000, 100000.  Each bucket is found by stripping the least-significant 1-bit from the previous bucket, so there cannot be more than $\log n$ subqueries.  Each subquery is a binary search, so cannot take longer than $O(\log n)$ time.  Finally, there are at most $O(\log n)$ heavy paths encountered on the path from any vertex to the root, so the worst-case time to compute $f(v, k)$ is $O(\log^3 n)$.

Judging by the comments so far, your best bet is probably to build a dictionary with each pair of nodes as keys, and any info about their path that you need.

You can build this in a systematic way by traversing the tree and reusing the partial paths as you go on. This way you can reuse partial results to improve on time complexity.

Being more specific: use Floyd-Warshall algorithm to systematically explore all shortest paths between each pair of nodes. Since this is a tree, there will only be one such path for each pair.
While computing the partial solutions, also keep an extra matrix that keeps track of how many edges are less than 5.
Any time you include a new path the number of edges with weights less than 5 is the sum of the number of such edges in the partial solutions. If the current edge being added is less than 5, add 1 to this calculated value.


What is a safe programming language? Safe programming languages (PL) are gaining popularity. I wonder what is the formal definition of safe PL. For example, C is not safe, but Java is safe. I suspect that the property “safe” should be applied to a PL implementation rather than to the PL itself. If so, let’s discuss a definition of safe PL implementation. My own attempts to formalize this notion led to a strange outcome, so I would like to hear other opinions. Please, do not say that every PL has unsafe commands. We can always take a safe subset.

There is no formal definition of "safe programming language"; it's an informal notion.  Rather, languages that claim to provide safety usually provide a precise formal statement of what kind of safety is being claimed/guaranteed/provided.  For instance, the language might provide type safety, memory safety, or some other similar guarantee.

This answer is a bit more broad. The words safe and safety have in recent decades been mutilated by certain politically oriented parts of English speaking society, such that their common usage has almost no definition. However, for technical subjects I still go back to define "safety" and "safe" as: a device that prevents the unintentional use of something or that makes accidental use substantially more difficult, and the state of being under the protection of such a device.
So a safe language has some device to limit a particular class of bugs. Of course limits come with inconvenience or even inability in some cases, and that isn't to say that "unsafe" languages will result in bugs. eg I don't have safety corks on my forks and have for decades managed, without much effort, to avoid stabbing my eye while eating. Certainly less effort than would have been expended using the corks. So Safety comes with some cost against which it must be judged. (cork fork is a reference to a Steve Martin character)


Minimum number of adjacent swaps needed to sort a circle of elements I have been thinking about some problems in combinatorics and I came across a problem I'm having trouble with.

Suppose you have a list $L$ of length $n$ (wlog the elements of the list are 1,2,3,...,n) and you want to sort it circularly (meaning [3,1,2] is sorted) with swaps of adjacent elements, but you are also allowed to consider the first and last elements as adjacent. What is the minimal number of swaps required?

The way to think about this, I think, is to consider the elements of $L$ arranged around a circle, in order. There are $n$ ways to do this, each with a different element at the top. What I want to do is just arrange $L$ in each way, sort it while counting the swaps, then take the minimum.

The problem I have is that elements of the list don't stay fixed: for example I can move 1 into the correct place, but when I move 2 into the correct place, I might move it past 1, which would mess up the position of 1. I am not really sure this is a good idea, since I'm not sure where the "correct place" of an element is, since any place around the circle could be correct.

Another idea I have is to fix 1 and sort the circle around 1 (i.e. I move 2 into place relative to 1, then 3 and so on). Then do it for 2 and so on, then take the minimum of the number of swaps I did while fixing each element. But is it true that this gives the optimal sequence of swaps?

This doesn't seem like an efficient solution either, since I am actually doing swaps on a list rather than some clever calculation. I know that the number of swaps in e.g. bubble sort is the number of inversions in the list. Is there a similar calculation I can do for circular lists?

Suppose we have two lists $L$ and $M$ of length $n$. They are identified as circular lists if and only if, when you write out $(L_1 \ldots L_n)$ and $(M_1 \ldots M_n)$, they give the same permutation, when considered as an element of $S_n$.

We can consider the graph $\Gamma$ with vertex set $(123\ldots n)^{S_n}$ (that is, the $n$-cycles in $S_n$). $\Gamma$ has an edge $(v, w)$ iff there is a transposition of adjacent elements (adjacent when we write $v$ down as $(v_1, \ldots, v_n)$) taking $v$ to $w$. This is well-defined since the only different way to write a cycle is by cyclically permuting it - the adjacent elements stay adjacent.

Given a circular list $L$, the problem is now finding the distance in $\Gamma$ from $L$ to $(1\ldots n)$.

To actually compute this, I used the GAP algebra system. We can take some steps to define the edges in a nicer way.

Let $G = S_n$. $G$ acts on the vertex set $V$:

$$\sigma \cdot (v_k)_{k=1}^n = (v_{\sigma(k)})_{k=1}^n$$

Also notice there is one vertex orbit, since any vertex can be relabelled to any other vertex.

Using this, we can define the group action in GAP:

G := SymmetricGroup(n);
ncycle := PermList(Concatenation([2..n], [1]));
all_ncycles := ncycle^G;
action := function(cycle, g)
    list := WritePermAsList(cycle);
    result := [1..n];
    for i in [1..n] do
        result[i] := list[i^g];
    od;
    return WriteListAsPerm(result);
end;

where WritePermAsList just writes e.g. the permutation (1,2) as the list [1,2] and so on.

Now we have the action, we can define a graph Gamma with vertex set $V$ with NullGraph and use AddEdgeOrbit to add all edges corresponding to the permutations we want to allow. In this case, we want to allow permutations of the form $(i\;i+1)$ and $(1 \; n)$. So we do AddEdgeOrbit(Gamma, [1, 1^Permutation(sigma, ncycles, action)]) for each sigma we want to allow.

Now computing the answer to the question I asked: "What is the minimal number of swaps required [to sort $L$]?" is just Distance(Gamma, 1, i) where i is the vertex representing our circular list $L$ since 1 represents $(1\ldots n)$ in our graph and we want to sort meaning get to $(1\ldots n)$.

I think this method isn't even that bad since I only really need this for small (length less than 10) lists. The simple structure of the graph means that we don't actually need to store all that much information about it (certainly we don't need to keep a huge list of vertices and edges in memory).

There are probably more insights about how to reduce this problem to something else, but this was good enough for me.

Even if you want to sort circularly, you definitely need a point of reference.
Deciding where it should be implies you'll need to look around.
If you don't want to look at every position, you can try skipping the pre-sorted intervals and sort the blocks rather than the individual elements.
Notice this doesn't remove the circularity problem, it just reduces input size.

To be honest, looking at this problem gets me more tempted to show that as long as you have an answer with exactly one inversion, then you point of reference does not matter, than trying to show there is an optimal point to choose.


How Do Common Pathfinding Algorithms Compare To Human Process This might border on computational cognitive science, but I am curious as to how the process followed by common pathfinding algorithms (such as A*) compares to the process humans use in different pathfinding situations (given the same information). Are these processes similar?

Humans tend to choose not strictly optimal, but close to shortest solutions. So you'll need to look at fuzzy (approximate) algorithms, not at A*.

The closest algorithm to human thinking I've aware of is a Contaction hierarchies on par with a Reach pruning algorithm. When I need to find a path between A and B on the map, I do a quick overview, taking into account if there is crossing river or something else and looking for some general ways and then adding details that could shorten path.

Have you watched a child learning to navigate a room? You have to tell them, "Go around the table. AROUND".

Human path planning is a grab bag of heuristics, some innate and some learned. Lookahead is probably fixed to a small number, certainly not a general recursion like A*.


How to prove that Ambiguity is still present in Resolved Production of Dangling Else Problem? $\textbf{stmt} \to$ $ \textbf{if} $expr$ \textbf{then}$ stmt
                           $\mid $ $\textbf{if}$ expr $ \textbf{then}$ stmt$ \textbf{else}$ stmt
                           $\mid \textbf{other} $

This grammar is called as Dangling Else Problem . However the ambiguity is resolved by parser as described as follows

  In all programming languages with conditional statements of this form, the first parse tree is preferred.
  The general rule is, "Match each else with the  closest unmatched then"

It is rarely built into productions

$\textbf{stmt} \to$ $ \textbf{matched_stmt}$
                          $\mid $ $\textbf{open_stmt}$

$\textbf{matched_stmt} \to$ $ \textbf{if} $expr$ \textbf{then}$ matched_stmt $ \textbf{else}$ matched_stmt
                          $\mid $ $\textbf{other}$

$\textbf{open_stmt} \to$ $ \textbf{if} $expr$ \textbf{then}$ stmt
                           $\mid $ $\textbf{if}$ expr $ \textbf{then}$ matched_stmt$ \textbf{else}$ open_stmt

However this grammar is also ambiguous . Moreover no grammar is there that could eliminate ambiguity problem of Dangling else problem . Hence we can say that dangling else problem in also inherently ambiguous

Source : Compilers: Principles, Techniques, & Tools -Aho & Ullman

My question is How to prove that  Ambiguity is still present  in this resolved Production of Dangling Else Problem   ? What I know is that if two different parse trees are possible then the grammar in ambiguous . Does any such parse trees possible for the resolved grammar ? If so could u please give an example parse tree for the same

A grammar $G$ for a language $L$ is ambiguous if there is a string $w \in L$ which has two different parse trees (with respect to $G$). Hence in order to show that ambiguity is still present, all you have to do is to come up with a string generated by your grammar that has two different parse trees.

To prove some Grammar is Ambiguous You have find Atleast 2 or more $LMD or RMD$(Left or right most derivative tree) for a string $w$ which belongs to the grammar.

There is small catch here, it is not necessary that if a string has two derivation it will produce a ambiguity but if the derivation of the string has more than two parse tree it surely produce ambiguity.

If we talk about the Inherently ambiguous here are some explanation given by friend Rahul I think Its worth reading it.

let's say we have

$S \to A\mid B $

A generates all the strings where m=n

B generates all the strings where n=p

Now, we can observe that both A and B can generate common strings which are
m=n=p.

So while deriving such strings we can either go by

$S \to A$

  Or

$S \to B$

We have two possible derivations (LMD or RMD doesn't matter because in either case we derive only one non-terminal).
Hence it is inherently ambiguous.

We can have 2 parse trees to generate the common strings.
Remember this rule of thumb,

If you find a production of the form

$S\to A \mid B$

Of a grammar that generates a language AND A&B can generate strings that are common AND you can't MODIfy the grammar to eliminate this commonality then it is inherently ambiguous.


Complexity class for polynomial algorithm for 3SAT, but with exponentially large values? I have a hypothetical question: suppose there exists an algorithm that solves an NP-Complete problem polynomial time, but requires the computation
of values that grow exponentially big (or small).

For example, suppose POLY-3SAT solves 3-SAT in N^17, however to do so it must compute/evaluate the value of a number C whose value grows as N^1000 (or 1/N^1000).

What would this imply?  Does computing/evaluating an exponentially large value automatically place the algorithm in EXP-SPACE (or some other complexity class)?  It seems like this would be a different complexity class than just ordinary P.

Complexity classes are classes of problems, not classes of algorithms. For example, the existence of Dijkstra's algorithm means that the problem of computing shortest paths in graphs is in P, but it doesn't make sense to say that "Dijkstra's algorithm is in P".

Exponentially large values can be stored in binary in a polynomial numebr of bits, and we can compute on such numbers using a polynomial number of operations. This notwithstanding, it seems that you're trying to get a polnomial-time algorithm that somehow dows exponentially much work, which is an oxymoron.

If there exists an algorithm that solves NP-complete in P time and space then the values computed cannot grow exponentially. A problem in which the values computed grew exponentially would not be an NP-complete problem, as it could not be reduced to SAT by any P complexity algorithm.

The answers that the problem and not the algorithm are defining of complexity are incorrect. The problem has no inherent complexity. We say a problem is of X complexity based on the best known algorithm that can solve all possible instances of it. SAT defines the set of problems for which the best publicly known means to solve all possible instance was exponential in the number of variables (bits in the case of Boolean expressions).

However, given the time frame mentioned in arxiv.org/abs/cs/0205064 there existed a solution not publicly known to the specific problem before it the problem was publicly known and determined to not have a known P complexity solution.


Beginner help with Arrays & Complexity My goal is to create a method that gets an array that only has 1's and 0's in it, and then turns every number into the amount of 'steps' it is away from the closest 0, left or right.

So for example [1] - [1] - [0] - [1] - [1] - [1] - [1] - [1] - [0] - [1]  would be
[2] - [1] - [0] - [1] - [2] - [3] - [2] - [1] - [0] - [1]

I also need to do it as simple as possible in terms of time and space complexity.

I'm not sure how to make it count how far a certain spot is from a 0 if it's from the right of the 0, or if there's another 0 nearby I'm not sure how to make it count which one is closest.

I'm assuming two for loops are needed?

Made a sketch: no idea if it makes sense.

 for (int i=0; i<a.length; i++)
{

    for (int j=i; j<a.length; j++)
    {
     if (a[j]==0)
      {
       if (i<j)
         {
           a[i]=j-i;
         }
        if(j<i)
         {
           a[i]=i-j;
         }
       }
    }
 }

Let's try to solve a simpler problem first:

Given an array that only has 1's and 0's in it, the method turns every number into the amount of 'steps' it is away from the closest 0 to the left.

Now this problem is easy. A simple solution is: traverse the array from left to right, keeping track of the distance from the last zero encountered and updating each element with the distance.

A simple code:

dist = INF
for(i=0;i<a.length;i++){
    if(a[i] == 0)
       dist = 0;
    else
       dist++;
    b[i] = dist;
}

Now once you have solved the simpler problem for closest 0 to the left, you can similarly solve the problem for closest 0 to the right. With these two solutions, you should be able to easily get a solution for the original problem (by taking a min of the two solutions).

The solution evidently has O(n) time complexity, and can be easily coded to use only O(1) space by carefully manipulating the updates in the original array only.

Just iterate in each direction and track the distance from the last zero

You could get fancier with some back tracking to only go one direction but would not be much faster

2n is still O(n)

lastZero is the distance from the last zero

int[] result  //this store the answer / calculation
int lastZero = null
for(i = 0; i < len; i++)
{
    if(input[i] = 0)
    {
        lastZero = 0
        result[i] = 0
    }
    else if (lastZero != null)
    {
        lastZero++
        result[i] = lastZero
    }
}
//now go from right to left
lastZero = null
for(i = len - 1; i <= 0; i--)
{
    if(input[i] = 0)
    {
        lastZero = 0
    }
    else if (lastZero != null)
    {
        lastZero++
        if(result[i] > lastZero or result[i] = null)
           result[i] = lastZero
    }
}


Infinite calculations in finite time This is probably a silly thought, but suppose we have a computer that's programmed to perform an infinite sequence of calculations and suppose the $i^\text{th}$ calculation takes $1/2^i$ seconds to complete.  Then this computer can do an infinite number of calculations in a finite amount of time.

Why is this impossible?  Is there a lower bound on how long it takes to carry out a non-trivial calculation?

This "kind" of computer is known as a Zeno Machine. Its computational model falls into a category called Hypercomputation. Hypercomputational models are mathematical abstractions, and because of the ways in which they are defined to work, they aren't physically possible.

Take your Zeno Machine for example. If we imagine the Zeno Machine to be a calculating machine of any kind, whether it uses an abacus or integrated circuit doesn't matter. Say the program data used by the machine is fed to it by an infinitely long tape of symbols (just like a Turing Machine).

Of course, we know from mathematics that:

$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}... = \sum_{n=1}^{\infty}(\frac{1}{2})^n $

which we say is equal to $1$. Thus the computation should complete in 1 second because the sum absolutely converges.

But this convergence is, of course,  dependent on $n$ going to (and reaching) infinity. In the physical sense, this means that as the time required for each calculation gets smaller, the "read head" of the calculating machine will have to zip along the symbols in the tape faster and faster. At some point, this speed will exceed the speed of light.

So answering your second question, the absolute lowest-possible bound on a calculation would probably be on the order of the Planck time, given the speed of light as the primary limiting factor in theoretical, but physically-plausible models of computation.

"Theory of Everything"'s answer is good, but I want to add some intuition as to why $\Sigma_{n=1}^\infty (\frac{1}{2})^n$ converges to $1$, which we can translate into an answer to this question:

Imagine that you have a red and a blue bucket; the blue bucket contains one liter of water and the red bucket is empty. You pour half of the water from the blue into the red. Now both buckets have $\frac{1}{2}$ liter of water in them. You again pour half of what is in the blue bucket into the red, there is now $\frac{1}{4}$ liter of water in the blue bucket and $\frac{3}{4}$ liter in the red. Now you continue, always pouring half of what is in the blue bucket into the red bucket. Clearly you will never get more than one liter into the red bucket, and just as clearly you will always have more water in the blue bucket to pour over.

To complete the analogy; the blue bucket contains time, exactly twice as much time as the first computation $c_1$ takes. For each step of the computation you use up half of the remaining computation-time and pour it into the red bucket of used time. Just as the red bucket of water can't contain more water than the blue contained, the red bucket of used time can not contain more than twice the computation time of $c_1$. And just as there were always water left in the blue bucket we will always have a tiny bit of computation-time left for the next computation.

Edit: As noted by @aroth, this analogy assumes that we can keep dividing water forever; that there is no smallest indivisible atom. Which raises the interesting (I think) point that we must also assume time to be arbitrarily divisible for the computation to finish in finite time.


Demonstrate that DPDA is closed under complement by construction I've been trying for quite some extended time to find a construction so that I can formally demonstrate that a deterministic PDA is closed under complementation. However, it happens that every idea I got has something that at the end does not fit. Could you give me a hand?

The main problem happens with the ε-moves. A PDA could finish reading its input in a non-final (rejecting state) but can still move to a final (accepting) state through an ε-move and end up accepting the string. This means that just adding a dead state and complementing the states does not work. I already solved the problem of possible infinite sequences of ε-moves, so that is not a main part of my question.

EDIT: As far as I understand, if the DPDA reaches end of input and is in an accepting state and moves to a rejecting state through an ε-move it would still accept it (as it reached a final state with no input symbol left to read).

Please let me know if I can be more clear.

I didn't have time to write this before but I found an answer. Here is what I did:

Let $O$ be the original $PDA$. We will construct a new $PDA$, call it $M$ ($M$ stands for modified).

To find the complement of $O$, we can flip final states to be non-final states and vice-versa. It is the same procedure as for finite automatas. However, there is a subtlety. The main problem is that in the original PDA $O$ the input $w$ can lead to a state $S$ which is not a final state but could perform an $\epsilon-move$ and get to an accepting state $S'$. Flipping states as mentioned above, would make $M$ end in $S$ with the input $w$ which would be a final state (causing $M$ to accept accept the input) even though it will later make an $\epsilon-move$ to $S'$, a non-accepting state. Therefore, both $O$ and $M$ will accept $w$. Something similar happens if $S$ was a final state and $S'$ a non-final state reachable from $S$ through an $\epsilon-move$.

In order to overcome this problem, we must make sure that all $\epsilon$-moves happen before we read the next symbol. That is, we will enter a reading state only when a path of $\epsilon$-moves is followed and we reach a state which has no $\epsilon$-move available. We call these latter states reading states, as they need an actual symbol to perform a new transition.

Define $M$'s states to be tuples of the form $<q, n>$ where $q \in Q$ ($Q$ is the set of states of the original $PDA$) and $n \in \{1, 2, 3, 4\}$.

If $\delta(q, \epsilon, X) = <q', \alpha>$ in $O$, let $\delta(<q, 3>, \epsilon, X) = <<q', 2>, \alpha>$ in $M$ if $q \in F_O$.
If $\delta(q, \epsilon, X) = <q', \alpha>$ in $O$, let $\delta(<q, 3>, \epsilon, X) = <<q', 3>, \alpha>$ in $M$ if $q \notin F_O$.
If $\delta(q, \epsilon, X) = <q', \alpha>$ in $O$, let $\delta(<q, 2>, \epsilon, X) = <<q', 2>, \alpha>$ in $M$.
If $\delta(q, \epsilon, X)$ is $undefined$ in $O$, $\delta(<q, 2>, \epsilon, X) = <<q, 1>, X>$ in $M$
If $\delta(q, \epsilon, X)$ is $undefined$ in $O$, $\delta(<q, 3>, \epsilon, X) = <<q, 4>, X>$ in $M$

In those definitions, we let states of the form $<q, 2>$ and $<q, 3>$ consume $\epsilon$-moves imitating $\epsilon$-moves of $O$ until there are no more. Then, perform an $\epsilon$-move to a reading state. Now for the reading states,

If $\delta(q, a, X) = <q', \alpha>$ in $O$, let $\delta(<q, 1>, a, X) =  \delta(<q, 4>, a, X) = <<q', 3>, \alpha>$ in $M$.

By making this definition, we consume a symbol of the input and move to a state of the form $<q, 3>$ to begin a new series of $\epsilon$-moves.

Finally, make states of the form $<q, 4>$ be accepting states of $M$ if $q \notin F_O$. Also, make $<q_0, 3>$ the initial state of $M$ if $q_0$ is the initial state of $O$.

What we did is the following:

Create 4 "floors" of states (the second element of the tuple in states of $M$ determines in which floor we are). Floor 3 imitates $\epsilon$-moves of $O$ possibly reaching an accepting state $q$ of $O$. If that is the case, we move to floor 2; otherwise, we remain in floor 3. When there are no more $\epsilon$-moves to follow of $O$, we define $\epsilon$-moves of $M$ to reach a reading state. Floors 1 and 4 correspond to reading states. If we were on floor 3, we go to floor 4. If we were in floor 2, we reach floor 1. Only states $<q, 4>$ (states that are in floor 4) are accepting states of $M$, provided that $q$ is not an accepting state of $O$.

Please let me know if I made a typo at writing this. I could've easily mistaken. Also, my English is not very good so feel free to edit and rephrase things better.

You can assume the automaton to be free of $\varepsilon$-transitions without loss of generality.

This can be shown by using the standard construction from CFG to PDA applied to a Greibach normal form.
In Silent Transitions in Automata with Storage, G. Zetzsche has recently presented a construction directly on automata.

Potential caveat: I kind of assume that said standard construction yields a DPDA if we apply it to a suitable, i.e. "deterministic", grammar and that this suitability survives transformation in Greibach normal form.


O(·) is not a function, so how can a function be equal to it? I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$.

I understand semantics of it. But $T(n)$ and $O(f(n))$ are two different things.

$T(n)$ is an exact number, But $O(f(n))$ is not a function that spits out a number, so technically we can't say $T(n)$ equals $O(f(n))$, if one asks you what's the value of $O(f(n))$, what would be your answer? There is no answer.

Strictly speaking, $O(f(n))$ is a set of functions. So the value of $O(f(n))$ is simply the set of all functions that grow asymptotically not faster than $f(n)$. The notation $T(n) = O(f(n))$ is just a conventional way to write that $T(n) \in O(f(n))$.

Note that this also clarifies some caveats of the $O$ notation.
For example, we write that $(1/2) n^2 + n = O(n^2)$, but we never write that $O(n^2)=(1/2)n^2 + n$. To quote Donald Knuth (The Art of Computer Programming, 1.2.11.1):

  The most important consideration is the idea of one-way equalities. [...] If $\alpha(n)$ and $\beta(n)$ are formulas that involve the $O$-notation, then the notation $\alpha(n)=\beta(n)$ means that the set of functions denoted by $\alpha(n)$ is contained in the set denoted by $\beta(n)$.

I went over this on stackoverflow; while perhaps the most correct answer to OP's has already been stated above (equivalence classes, restated below as #1), here is a complete answer:

sets: "$f= O(\cdot)$" means $f \in O(\cdot)$, i.e. membership in a set, e.g. $\{\frac{1}{2} x^2, (5 x^2-x+5), 2.5x,...\}$ "the set of functions asymptotically bounded by $x^2$". This is the standard mathematical treatment of asymptotic notation that I am aware of. This set has a partial order corresponding to subset-of, e.g. $O(x^2) < O(x^3) = O(x^3 + x)$ (some sets may be incomparable; DAG; see polynomial hierarchy for an interesting example).
note. "$f= \Theta(\cdot)$" means $f \in \Theta(\cdot)$. However, note that unlike the above, this is an equivalence relation (obviously the naive relation X as in f X g iff $f \in O(g)$ is not an equivalence class, since $f \in O(g)$ does not imply $g \in f(g)$; the trivial equivalence relation "both an element of $O(g)$" is perhaps amusing to conceptualize but mathematically uninteresting, whereas with $\Theta$ the multiple equivalence classes partition the space of functions).

wildcard expression: You can backwards-engineer the definition of $f \in \Theta(g)$: after some radius of uncaring near the origin (i.e. there exists an $x_0$, such that for all $x>x_0$...), there exists a band bounded constant multiples of $g$ that bounds $f$ (i.e. $LOW*g(x) \le f(x) \le HIGH*g(x)$)... and so we can backwards-engineer this to merely replace any expression $O(g)$ with the expression $k_1g(x)+err(x)$, that is, replace it with the bound itself plus an error term we don't care about (an error term bounded by $0 \le err(x) \le k_2g(x)$ for $x>x_0$ and potentially unbounded for $x\le x_0$)..... so for example if we said $f = 2^{\Theta(x^2)}$, we could equivalently say $f(x)=2^{k_1x^2+err(x)}$ where this error term is $0 \le err(x) \le k_2x^2$. We would never ever write this down though... because it's a bit silly. But I believe it may be legitimate to think of it that way, and would preserve the notion of equality. (I am eliding proper treatment of negative signs here, which may be important.)
a. Modify the above as appropriate for $O$ instead of $\Theta$


Precedence in regular expressions I'm having trouble finding the language represented by the following:

(AA|BB)*

Should the expression be read as... ( A (A|B) B ) *
or... ( (AA) | (BB) )*

If that isn't clear, should this produce something like... ABABAB or should it produce AABBAABBBBAA

My guess is that AABBAA is part of the represented language, while AB is not.

This depends entirely on convention; with respect to a (proper) formal definition, the expression is invalid as it not properly parenthesised. I'd say that typically, the order is (from stronger to weaker binding)

Kleene Star/Plus (also finite versions),
concatenation,
alternative.

Note that this corresponds (visually) to exponentiation over multiplication over addition in basic arithmetics, so it's probably the natural way.

That is,

$10^*1$ is read as $1(0)^*1$ and
$10|01|11$ as $(10)|(01)|(11)$.

Note that I still drop parentheses due to associativity of concatenation and alternative.

This Regular expression $(AA|BB)*$ can accept any string having two consecutive A's or B's i.e. even number of consecutive A's and even number of consecutive B's. so AABBAA is in it but AB is not in it.


Difference between Normative annexes and Informative annexes in ADA 95 I was reading the ADA 95 reference manual. I came across these  two words in annexes
 Normative and informative . I couldnt find the difference between those. Your help will  be much appreciated.

"Normative" means something that has to be followed, part of the standard. "Informative" is explanations meant to be understood by mere human beings, and that might be ambiguous or inaccurate. It is not to be relied on. Read it to understand, refer to the normative parts where it matters.

Normative is it is and informative is it could be.  One is certainly settled while the other is yet settled.


Find Minimum number of platforms The questions is as follows with the answer:

  Q) Given the arrival and departure time of various trains in a station. Calculate the minimum number of platforms required such that no train has to wait for another train to vacate the platform. The question basically means calculate the maximum number of trains that would be present in the platform at any given time.

  Answer

  Sort the arrival time and sort the departure time, keep a count initialized to 0. compare the first element of the arrival time with the first of departure, increase the value of count if the value at current Index at arrival is less than the value index at departure and increment the arrival index, and vice versa. Keep the maximum count that you see.

MY PROBLEM: I have tried hard but I am not able to get why to sort both arrival and departure timings? As a train is single entity and you sort arrival and departure separately how can we know which train arrival matches with its departure? I am facing the same problem in closest pair problem as why to sort x points and y points separately.

The answer is very simple: try to construct an algorithm which doesn't sort both arrival and departure times, and see if that's possible. If so, then there is an alternative algorithm which indeed doesn't requiring both times. Otherwise, you will understand why this is necessary.

The intuitive explanation of why we sort both arrival and departure times is that we are actually sorting all events. There are two types of events, arrival and departure, and we want to process them as they happen. We don't care about matching departure times with arrival times – that is, for our algorithm to work, we don't need to know which train is involved, only that a train has arrived or has left the station.

This actually suggests a way to restate the algorithm you describe. Sort all events according to time. Now go over them in order of increasing time (we assume for simplicity that all times are distinct). Keep a counter of the number of trains in station. When processing an arrival event, increase the counter; when processing a departure event, decrease the counter. Keep track of the maximal value of the counter.

The algorithm you describe instead sorts the arrival and departure times separately, and then performs an online merge (same algorithm as in merge sort for merging two sorted lists). I don't know why they described the algorithm this way rather than the way I described it.

Create a single timeline in which an arrival is a +1 and a departure
is a -1 (train)
Then sort on that single time
Your don't really care which train is at the station but
rather a train
When a train arrives +1
When a train depart -1
Keep a running total of the trains at the platform / station

If have

arrival depart
1       3
2       4

Then at time 2 there will 2 trains at the station
And at time 3 then will be 1 train at the station
Must sort on arrival/depart to sync on the two events

I am not good with pseudocode

foreach (stop in schedule)
{
    timeline.add(stop.station, +1, stop.arrivalTime)
    timeline.add(stop.station, -1, stop.Departure time)
}

int maxTrains = 0
int trains = 0
foreach (tlStop in in timeline.where(tlStop.station = x).orderby(tlStop.time))
{
    trains += tlStop.arriveDepart
    if(maxTrains < trains)
       maxTrains = trains
}


What is a problem, a task, and a solution? I am attending algorithms and data structures course in my University and my professor gave me an interesting question the other day. He told me to think about it.

What is a problem, a task, and a solution?

It seems to me like it's more of a philosophical question. All of those 3 things correlate to one another.

To me, it seems like if we have a problem, we then have a task to solve it, which we might be able to do with an algorithm, which is a solution.

What do you guys think would be the answer to this question? Does it have some kind of deeper meaning about algorithms, or am I just overthinking it?

philosophically, a problem isn't a problem until there is unrest, and a way to explain it as such. i.e. an understanding leads to determining if it really is a problem, or just misunderstood.  Correctly specifying the problem then leads to its identification.

A bit morbid, but for ex, people dying from arsenic poisoning seems like a problem. Arsenic is poisonous, it will cause death. Is this the problem? No, the problem is exposure. (stated generally for brevity.) The task becomes solving exposure. And of course there may be multiple solutions. Detection, protective gear, isolation, etc.


Interactive Proofs for coNP I am trying to understand interactive proof systems and tried the following problem as an exercise. We know that $PH \subseteq PSPACE$ and $IP=PSPACE$, so come up with (easy to understand) interactive proof systems for $PH$?

An interactive proof system for $NP$ is trivial, but I failed to get an interactive proof system even for $coNP$. Do you know of an explicit interactive proof system (by explicit I mean without going through the $IP=PSPACE$ route) for $coNP$?

Wikipedia outlines such an example. Consider the coNP-complete problem UNSAT: given a CNF $\varphi$ on $n$ variables, we want to convince the verifier that $\varphi$ is not satisfiable. We arithmetize $\varphi$ to a polynomial $p$ and choose some large prime $q$. Let
$$p(x_1,\ldots,x_k) = \sum_{x_{k+1}=0}^1 \cdots \sum_{x_n=0}^1 p(x_1,\ldots,x_n).$$
The protocol proceeds as follows:

Prover sends verifier a prime $q \in (2^n,2^{n+1})$, and the latter verifies that $q$ is prime.
Prover sends verifier $p(z) \in \mathbb{Z}_q[z]$. Verifier verifies that $p(0) + p(1) = 0$, and sends prover a random $r_1$.
Prover sends verifier $p(r_1,z) \in \mathbb{Z}_q[z]$. Verifier verifies that $p(r_1,0) + p(r_1,1) = p(r_1)$, and sends prover a random $r_2$.
Eventually, verifier gets $p(r_1,\ldots,r_n) \in \mathbb{Z}_q$, and verifies that it has the correct value by evaluating $p$ directly.

Because the degree of $p$ is small compared to $q$, if the prover is cheating then the verifier will probably catch her (see Wikipedia for the proof, or work it out yourself using the Schwartz-Zippel lemma).

Graph non-isomorphism at Proofs that Yield Nothing But their Validity or All Languages in NP have Zero-Knowledge Proofs, Goldreich, Micali and Wigderson, JACM, 1991.

Common input is a pair of graphs: $G_1, G_2$.
At the start of each round, verifying party chooses an index $i \in \{1,2\}$ at random and sends a random permutation of graph $G_i$. Proving party responds with an index $b \in \{1,2\}$.

Completeness property: for non-isomorphic graphs, prover always give correct response $b=i$.

Soundness: for isomorphic graphs, prover give correct response with probability $\frac{1}{2}$.


Scheduling a sequence of queue operations that push and pop items at specified times What is the time complexity of the following problem?

Definitions

A FIFO is a queue functional unit supporting four commands: PUSH (data to back of queue), POP (the head of the queue), PNP (POP the head of queue and PUSH it to the back), NOP (do nothing). Each command takes one unit of time to execute.

FIFO code (or a schedule of commands) is a sequence of commands to execute.

Problem Description

We are given $n$ items of data $T_1,\dots,T_n$, and $n$ triplets $(T_1,t^{in}_1,t^{out}_1),\dots,(T_n,t^{in}_n,t^{out}_n)$. $t^{in}_i$ and $t^{out}_i$ identify the time when $T_i$ is PUSHed and POPed respectively.  We're guaranteed that $t^{in}_i<t^{out}_i$ for every $i$ and $t^{in}_i,t^{out}_i$ are all unique.

The goal is to produce FIFO code (a schedule of commands) that push each $T_i$ at time $t^{in}_i$ and pop it at time $t^{out}_i$, by adding NOP and PNP commands between the PUSH and POP commands given.  No extra PUSH or POP commands can be added: the resulting code must contain exactly $n$ PUSHes and $n$ POPs.

Example

Input:
$(T_1,2,4)$,
$(T_2,1,5)$

Solution:

PUSH $T_2$
PUSH $T_1$
PNP
POP // T_1
POP // T_2

Initial Direction

Solving this problem is equivalent to solving a set of equations with constraints.

Denote the number of time units in an interval between consecutive input $t^{in}_i$/$t^{out}_i$ by $K_i$.

In the above example in the question there are three intervals:

|PUSH($T_2$) | PUSH($T_1$)|---------------|POP($T_1$)  |POP($T_2$)|

|---------------|---------------|---------------|---------------|---------------|

$K_1=0$.
$K_2=1$.
$K_3=0$.

The depth of the FIFO at the beginning and end of each such interval is the number of PUSHs minus POPs made before it, denote it by $d_i$.

In the above example:

$d_0=0$.
$d_1=1$.
$d_2=2$.
$d_3=1$.

Denote by $x_i\in \mathbb{N}\cup\{0\}$ the number of PNP assigned in interval $K_i$, then $x_i\leq K_i$.

In the above example:

$x_1\leq 0$.
$x_2\leq 1$.
$x_3\leq 0$.

Per data unit $T_i$ add an equation asserting it is available at the head of the FIFO at time $t^{out}_i$ by adding $d_i+x_{i+1}$ modulo the depth, $d_{i+1}$ of the FIFO per interval. In the above example:

For $T_1$: $(1+x_2)\bmod 2=0$.
For $T_2$: $((( (0+x_1)\bmod 1+x_2 ) \bmod 2)+x_3) \bmod 1 =0$.

And the solution is $x_1=0, x_2=1, x_3=0$ corresponding with the solution above.

But I'm not sure how to use this information to understand the complexity of the problem.

In the worst case,

The element at the tail of the queue need to be popped i.e.,

  Given n units of data and n triplets

If n = 4 (number of element in the queue and number of triplets are four)

Input: (T1, 1, 14), (T2, 2, 13), (T3, 3, 11), (T4, 4 ,8)

At time 4 the state of the queue:

╔══════════════════════════════╗
║            QUEUE             ║
╠══════╤══════╤════╤════╤══════╣
║      │ Head │    │    │ Tail ║
╟──────┼──────┼────┼────┼──────╢
║ DATA │  T1  │ T2 │ T3 │  T4  ║
╚══════╧══════╧════╧════╧══════╝

At time 5,  T4  should be popped and to do that all the element left to T4 should be PNP (here, three PNP).

  PNP (POP the head of queue and PUSH it to the back)

That is, (n-1) elements of the queue should be PNP to pop nth element from the queue.

At time 7 the state of the queue:

╔══════════════════════════════╗
║            QUEUE             ║
╠══════╤══════╤════╤════╤══════╣
║      │ Head │    │    │ Tail ║
╟──────┼──────┼────┼────┼──────╢
║ DATA │  T4  │ T1 │ T2 │  T3  ║
╚══════╧══════╧════╧════╧══════╝

At time 8 the state of the queue (pop T4):

╔═════════════════════════════╗
║            QUEUE            ║
╠══════╤═══╤══════╤════╤══════╣
║      │   │ Head │    │ Tail ║
╟──────┼───┼──────┼────┼──────╢
║ DATA │ - │  T1  │ T2 │  T3  ║
╚══════╧═══╧══════╧════╧══════╝

As we go on, we can see for popping one element at the tail requires to PNP all the element right of it.

Gives,

╔══════════════════════╤════════════════════════╗
║ Element to be popped │ Number of NPN required ║
╠══════════════════════╪════════════════════════╣
║          n           │          n-1           ║
╟──────────────────────┼────────────────────────╢
║         n-1          │          n-2           ║
╟──────────────────────┼────────────────────────╢
║          .           │           .            ║
╟──────────────────────┼────────────────────────╢
║          .           │           .            ║
╟──────────────────────┼────────────────────────╢
║          2           │           1            ║
╟──────────────────────┼────────────────────────╢
║          1           │           0            ║
╚══════════════════════╧════════════════════════╝

Thus, in worst case we have a total

= n-1 + n-2 + n-3 + ... + 2 + 1

= [ n ( n + 1 ) ] / 2 - n

= n2 + n

= O( n2 )

Answer :

Worst case time complexity of the problem = O( n2 )

Best case time complexity of the problem = O( 1 ) // when an element is requested to pop, it is found at the head of the queue.


Why is the CPU Involved During Keyboard Echo? I'm currently studying for a computer science exam, and I've come across a concept that has me somewhat stumped.

  When one types a key on the keyboard, an ASCII character is transmitted to the CPU. Upon reception of this character, the CPU outputs the same character to the screen. This process is called echoing. Instead of having the CPU involved, why don’t we simply have this echoing process done within the keyboard/screen unit so that the CPU is free to do other useful work?

Now, intuitively, I feel like this is because there is no defined keyboard/screen unit, and the CPU is the device which is responsible for communicating between the screen and the keyboard, through the interconnection network. However, I feel like the fact that a keyboard/screen unit is mentioned may mean I'm missing an important concept. Is this the case? Why do we involve the CPU in the echo process?

Letting the computer see each character as it is typed allows programmers to make the user interface more dynamic.

Back when a serious computer was the size of several upright refrigerators and computers operated on user input a line at a time, terminal input was handled as you described.  You typed a line of text on a terminal which displayed it locally (often on paper).  Only when you pressed the ENTER or RETURN key was the text sent to the mainframe or minicomputer to be processed.

But even back then, the advantage of letting the computer see the user input early was realized by the engineers of the time.  Command completion, where you type the first few letters of a command and the computer fills in the rest, was invented in the mid 1960's.  This feature was copied and improved through the years to where it stands today, available in all modern UNIX shells and under Windows as well.

Allowing the CPU to see each character as it is typed also allows shells to offer command line editing and history features well beyond what a dumb terminal could provide.  A key can allow you to step back through a list of commands you've previously typed, choose one, and then edit it slightly before pressing RETURN to have it executed.  Text can be cut and pasted between command lines, possible because the CPU has access to previous commands while the terminal does not.  Filenames as well as commands can be completed based on partial input, again possible because the CPU has access to the names of files in the filesystem and the terminal does not.

How could the CPU not be involved? How would the computer know whether to print anything at all to the screen without the CPU being involved? How would it know where to print the character? How would it know what font to use? How would it know how to render that font?


Do any decision problems exist outside NP and NP-Hard? This question asks about NP-hard problems that are not NP-complete. I'm wondering if there exist any decision problems that are neither NP nor NP-hard.

In order to be in NP, problems have to have a verifier that runs in polynomial time on a deterministic Turing machine. Obviously, all problems in P meet that criteria, but what about the problems with sub-exponential complexity? They do not belong to P and it's not obvious to me that they all have efficient deciders. And they certainly don't qualify for NP-complete.

I'm willing to believe that all decision problems are either NP or NP-hard or both, but nobody has actually said that (that I can find). I'm also willing to believe that such problems do exist, even if they are very contrived. Maybe someone more knowledgeable can put this issue to rest for me. Thanks.

Edit

I abused the term 'subexponential' in my question. In my mind it meant some problem with a complexity between exponential and polynomial like L-notation in this table. See the links in Raphael's answer for more details.

If $P = NP$, then any non-trivial language is NP-hard, and any trivial language belongs to NP. Hence, we do not get anything which is neither NP or NP-hard in this case.

If, however, $P \neq NP$, then there are languages which are neither in NP nor NP-hard.

For example, we can consider the language $\{1^n \mid \text{the } n\text{-th TM halts}\}$. As this language is not computable, it is clearly outside of $NP$. As this language is sparse, $P \neq NP$ together with Mahaney's theorem implies that it is not NP-hard.

If we want a computable counterexample, we can take a language $L$ that is not in EXPSPACE. We number all finite words in increasing order as $(w_n)_{n \in \mathbb{N}}$, and now consider the language $L' = \{1^n \mid w_n \in L\}$. Again, Mahaney's theorem ensures that $L'$ is not NP-hard. If $L'$ were in NP (or even PSPACE), then an EXPSPACE algorithm for $L$ would be available in "Given w_n, compute 1^n and run the PSPACE-algorithm for $L'$ on it."

See here https://math.stackexchange.com/questions/235162/if-an-unary-language-exists-in-npc-then-p-np for a proof of Mahaney's theorem. Note that Yuval speaks about starting with an NP-complete unary language, that assumption is not used - the argument only needs an NP-hard unary language.

The answer is (trivially) yes. Any non-decidable language provides a decision problem that is harder than anything in NP.


Implementing the Schur decomposition of a matrix I'm trying do implement the Schur decomposition of a matrix, but I can't find any good articles for the theory. Could someone share one?

It's italian but it's very clear... Read this:

Shur decomposition

Proposition 6.13


Algorithm to explore every node in a graph I need an algorithm to explore every node in a graph (starting at any given node). Each node can have multiple parent nodes and multiple child nodes.

The following algorithm (in psuedocode) appears to gather every node but results in duplicate nodes (I think because the recursive 'paths' crossover at some points):

rFindAll(Node ID, Array currentpath) //current path passed by value
{
  Array connectedNodes = getConnectedNodes(ID);

  for_each_node (Node n : connectedNodes)
  {
     if(find(currentpath, n) == NOT_FOUND) // check to ensure id not in current recursive path
     {
        // every n is a node which is within the same graph as the original node
        currentpath.add(n);
        rFindAll(n, currentpath);
     }
  }

}

I was just wondering whether anyone has a better suggestion to do this. I've looked on google/wikipedia and there was nothing which would obviously help.

Thanks

The standard way to solve this is called whatever-first search. (Because depth-first and breadth-first and best-first and others are all special cases of it.)

The algorithm goes like this:

Pick a starting node
Add the starting node to a "bag" (arbitrary data structure)
While the bag isn't empty:
    Take a node out of the bag
    Mark this node as "explored"
    [Do whatever you like with this node]
    Add all this node's unexplored neighbors to the bag

The choice of "bag" is up to you. A stack makes depth-first search, a queue makes breadth-first search, a priqueue makes best-first search, and so on, but you can use anything you like, as long as you can put things into it and take things out of it.

Not sure whether "rFindAll" is first called in your program. If you just pass the initial node with empty "currentpath", obviously, the initial node is not added into the path and will be visited again and introduce duplication. You can update your function by moving the line
currentpath.add(n);
to the first position of the function:
rFindAll(...)
{
currentpath.add(n);
...
}

Another potential issue might be related to your programming language. If you are using c/c++, your code does have problem on function argument:
rFindAll(Node ID, Array currentpath)
Here "Array currentpath" is defined by val, so the update on this variable will not be propagated to the upper level. This may also lead to duplication.

In addition, please you'd set to store visited node instead of array, for better performance.


Fastest way to compute a path from a known cycle with unordered edges and vertices I have an (undirected) graph isomorphic to $C_n$ with unordered edges/vertices in some data structure (in particular, a list of tuples representing the edges), etc. I was wondering what is the fastest algorithm to compute a path which begins and ends at some given node in the cycle, given this set of nodes? The simplest thing seems to be to just use DFS, but that seems like overkill for what I'm sure is a relatively simple algorithm.

I understand your question this way:

There is given a graph with nodes and edges. There might or might not be one or more circles in that graph. And there is given a certain start-node within the set of nodes.

You ask, if this start-node is part of at least one circle, and you ask, which nodes (of which one is the given start-node) and edges form the smallest circle.

If this was your question, then I have an answer:

DFS is not the best choice. BFS is. BFS = Breadth-first-search. There is an wikipedia-article that describes this algorithm.

The idea of this algorithm is to begin to test all nodes at the end of the edges that are directly connected with the given node. This gives you a list of all direct neighboring nodes of the start-node. I call them the level-1-neighbors.

In the next step you repeat this search for each level-1-neighbors, but now you ignore all edges that directly lead back to where you did come from. The result are the level-2-neighbors. And then you repeat this for the level-n-neighbors to get the level-(n+1)-neighbors.

This transforms your graph into a new graph, which is a tree. The start-node is the root of this tree, the level-1-neighbors are the roots children, level2-neighbors are children of those children.

If your original graph contains a circle, then nodes will appear twice (or more often) in the resulting tree, because there are (at least) two different ways, that you can move through the circle to reach nodes in the circle (clockwise and counter-clockwise).

So, if a certain node appears a second time in the graph, then you have found a circle. The circle is the path starting at one representation of that node, going up till you reach the first common ancestor of both representations and then go down to the second representation.

If the common ancestor is the root node, you found the circle with the least number of nodes that goes through the given node. If the common ancestor is not the root, then you just have found a circle, that is connected with the given node by a side-arm. In this case you must go on searching.

There is an easier (but longer) algorithm for the case that there are directed edges: Use BFS until you hit the start-node for a second time. Then the path from the root to the second representation of the start-node is the shortest circle. This is simpler (you need not compare every new node with any node you already passed, but only with the root), but probably needs more resources because the tree you have to build will be deeper.

In both versions of the algorithm you must pay attention not to get lost in loops (again and again walking through circles that are not the needed circle)


Could min cut be easier than network flow? Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut.  Therefore, the complexity of computing a minimum $(s,t)$-cut is no more than the complexity of computing a maximum $(s,t)$-flow.

Could it be less?  Could there be an algorithm for computing a minimum $(s,t)$-cut that is faster than any max-flow algorithm?

I tried finding a reduction to reduce the $(s,t$)-max-flow problem to the $(s,t)$-min-cut problem, but I wasn't able to find one.  My first thought was to use a divide-and-conquer algorithm: first find a min-cut, which separates the graph into two parts; now recursively find a max-flow for the left part and a max-flow for the right part, and combine them together with all of the edges crossing the cut.  This would indeed work to produce a maximum flow, but its worst-case running time might be as much as $O(|V|)$ times as large as the running time of the min-cut algorithm.  Is there a better reduction?

I realize the max-flow min-cut theorem shows that the complexity of computing the value of a max-flow is the same as the complexity of computing the capacity of a min-cut, but that's not what I'm asking about.  I'm asking about the problem of finding a max-flow and finding a min-cut (explicitly).

This is very closely related to Compute a max-flow from a min-cut, except: (1) I'm willing to allow Cook reductions (Turing reductions), not just Karp reductions (many-one reductions), and (2) perhaps given $G$ we can find some graph $G'$ such that the min-cut of $G'$ makes it easy to compute the max-flow of $G$, which is something that's out of scope for that other question.

Here is a possible approach:

Suppose you know the cut S, then finding the flow from $S$ to $t$ is a min cost network flow problem with zero cost, since you know exactly the outflow at each vertex in $V\setminus S$ and in the inflow at $t$. Suppose $f$ denotes an $S-t$ flow and $A$ the node-arc matrix (i.e. row $i$, col $j$ has 1 if $i$ is the tail of $j$, -1 if its the head, zero otherwise), and let $b$ be such that $Af = b$ if $f$ satistfies the supply/demand, and the flow conservation. Then with gaussian elimination we can find a feasible solution in $|V|^3$ operations.

To find a cut from a flow we need to construct the residual graph which takes at most $|E|$ time, and then potentially traverse $|V|$ vertices.

So for complete graphs and the minimum cut being just the source or just the sink, the reduction takes equal time in both directions worst case. However, I would think that finding a feasible solution to $Af =b$ can be done faster than $|V|^3$ given the special structure. I am not sure how to prove that though.