Formal Verification of Functional Programs

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

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

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

x :: a -> b
x = x

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

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

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

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

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


Büchi automata: accepting run vs. runs with arbitrarily many final states

Consider $\Sigma = \{0,1\}$ and $w = 1101001000100001\ldots$, i.e., there is an increasing number of zeros between two ones. Now consider the automaton with states $q_0, q_1$, and $q_A$ where $q_A$ is the only accepting state. On input $0$, always stay in the current state. On input $1$ allow the following transitions: In state $q_0$, either stay in $q_0$ or go to state $q_A$; in state $q_A$, go to $q_1$; in state $q_1$, stay in $q_1$.

If the transition $q_0 \to q_A$ happens at a position in $w$ that is followed by $n$ zeros, $q_A$ will occur exactly $n+1$ times in that run. Since $w$ contains $n$ consecutive zeros for all $n$ but no infinite sequence of zeros, this is a counterexample to your statement.


Here is a provisional answer. The de Bruijn index and level of a bound variable sum up to the number of enclosing lambdas: $i+l=n_\lambda$. Since the index can be recovered from the level by subtraction, levels can be implemented as 'predecessor' indices p:

z :: (a, b) -> a
z (x, _) = x

s :: (a -> b) -> (c, a) -> b
s v (_, h) = v h

-- ^^^ as above

p :: (((), a) -> b) -> a -> b
p v h = v ((), h)

-- (p . s) v == v

app :: (a -> b -> c -> d) -> (a -> b -> c) -> a -> b -> d
app e1 e2 v h = e1 v h (e2 v h)

-- app manages an extra bit of context: the number of enclosing lambdas

lam :: (((a, b) -> c) -> (d, e) -> f) ->
       (b -> c) -> e -> d -> f
lam e v h x = e (s v) (x, h)

-- lam increments that context

eval :: (((a, env) -> a) -> () -> b) -> b
eval t = t z ()

-- evaluating closed terms...the starting context is z

This seems reasonable, and terms with just one variable (and arbitrary numbers of lambdas) behave as expected. But the type-checker chokes on terms with distinct variables -- e.g., app (p . p) p, our representation of the open term $21$, gives an 'infinite type' error.

To see why, let's consider a concrete evaluated closed term, eval $ lam (lam (app (p . p) p)). If you churn through the reductions by hand, eventually you end up with the following:

\x f -> s (s z) ((), ((), (f, (x, ())))) (s (s z) ((), (f, (x, ()))))

If both occurrences of s (s z) are polymorphic, this appears well-typed, and can be further simplified, to \x f -> f x, as desired (well, our de Bruijn level representation of this term is $\lambda\lambda 21$... close enough!). The problem, it seems, is that the Haskell type-checker insists that the two occurrences of s (s z) have the same monomorphic type, and therefore seems related to the absence of 'first-class polymorphism' in Haskell.

It is not obvious to me how 'deep' the problem here goes -- whether it can be massaged in Haskell; and if not, whether the implementation here can be coherently stated in, e.g., System F (Hindley-Milner seems out due to the need for first-class polymorphism).


I couldn't understand your approach exactly (Seems it's correct), but there is a simple rule for impossible orders: The order is impossible $iff$ there is $a_i,a_j,a_k$ such that $a_i > a_k > a_j$ and $i<j<k$. To such a $a_i,a_j,a_k$ we say bad triple.

Why? First you should prove that if there is bad triple then the sequence is impossible, but this is simple and I'll leave it as exercise (middle number couldn't pop sooner than bigger except smaller poped before all of them).

Second you should prove all impossible orders have at least one bad triple, Assume you have a sequence without any bad triple, you could find the order of push and pop so it's not impossible sequence. For reconstructing the push and pop orders just use naive approach (operation is pop while you iterating over consecutive numbers), but for formal proof (for simplicity) you could use induction, assume for all sequences of length $m$ if there isn't bad triple they aren't impossible. For sequence of length $n$, you can set operations as pop (start from end of sequence), while encountering with increasing consecutive numbers, now you have a sequence of length $m$, with $m < n$, without bad triple, so you can reconstruct push and pop for this sequence, so original one wasn't impossible. start of induction is sequence of length 3.


Create automata from non regular grammar

Your first language isn't regular. Here is a simple way of showing this. Consider all words in your language of the form $a^*c^*$; if your language were regular, then so would be that language. However, the new language is generated by the grammar $L \to \epsilon \mid aLcc$ (this requires an argument), and so is $\{a^n (cc)^n : n \geq 0\}$, which is classically known to be irregular.

With more effort, you can show that your language consists of all words $w$ in which every proper prefix $x$ satisfies $\#_a(x) > 2\#_c(x)$, and furthermore $\#_a(w) = 2\#_c(w)$.

An identical argument works for your second language. With more effort, you can show that the language consists of all words $w$ in which every prefix $x$ satisfies $\#_a(x) \geq 2\#_c(x)$, and furthermore $\#_a(w) = 2\#_c(w)$.

Summarizing, both of your languages are irregular, and this can be shown by intersecting them with $a^*c^*$.


Is it possible to generate a better random number generator algorithm from an algorithm that use N computers with one that uses N+1 computers?

The fastest random number algorithm that we know is
0

It is not very random, but it is very fast and therefore the best according to your definition. Maybe you need to rethink your definition. Maybe you should rethink the idea that there might be a “best” algorithm.


Cook–Levin theorem and reduction as injective function

Your question is a bit unclear, but let me hazard a guess. Let $L$ be an NP language. According to the Cook–Levin theorem, there is a polynomial time reduction $\phi_L$ from $L$ to SAT, that is, $\phi_L$ is a polynomial time function that satisfies $x \in L$ iff $\phi_L(x) \in \mathrm{SAT}$. You are asking why $\phi_L$ is injective.
Roughly speaking, $\phi_L(x)$ constructs a formula which describes the operation of a nondeterministic Turing machine for $L$ executing on $x$. The input $x$ is hardcoded in this description, and in particular, we can extract $x$ from $\phi_L(x)$. This implies that $\phi_L$ is injective.


In a DFA, does every state have a transition on every symbol of the alphabet?

You seem to have stumbled on a contentious issue.  Apparently computer scientists like to argue.  I certainly like to argue, so here goes!

My answer is an unequivocal: No.  A deterministic finite automata does not need a transition from every state for every symbol.  The meaning when $\delta(q,a)$ does not exist is simply that the DFA does not accept the input string.

While you can create a definition of DFA that requires that $\delta(q,a)$ does exist, it is simply not the case that a missing transition makes the resulting structure (whatever you call it) in any way nondeterministic as many of the commenters are claiming.  If you are taking a course on automata theory then the next topic will be context-free languages and push-down automata where the distinction between nondeterministic and deterministic automata is crtical, and you need to use the correct definition of non-determinism.

Non-determinism is associated with having more than one legal transition.

I think we all agree with the following Wikipedia definition (which I'll show in just a second is slightly ambiguous):

A deterministic finite automaton $M$ is a 5-tuple, ($Q$, $\Sigma$, $\delta$, $q_0$, $F$), consisting of

a finite set of states ($Q$)
a finite set of input symbols called the alphabet ($\Sigma$)
a transition function ($\delta : Q \times \Sigma \rightarrow Q$)
a start state ($q_0 \in Q)$
a set of accept states ($F \subseteq Q$).

Let $w = a_1 a_2 \cdots a_n$ be a string over the alphabet $\Sigma$. The automaton $M$ accepts the string $w$ if a sequence of states, $r_0, r_1, \ldots, r_n$, exists in $Q$ with the following conditions:

$r_0 = q_0$
$r_{i+1} = \delta(r_i, a_{i+1})$, for $i = 0, \ldots, n−1$
$r_n \in F$.

The ambiguity, and the controversy is over the defintion of the transition function, $\delta$ (number "3" in the first bulleted list.)  We all agree that what differentiates a DFA from an NFA is that $\delta$ is a function rather than a relation.  But is $\delta$ a partial function or a total function?

The definition of the DFA works just fine if $\delta$ is a partial function.  Given an input string, if you reach a state $q_i$ with an input symbol $a_j$ where there is no next state then the automata simply does not accept.

Moreover when you extend this definition to create the definition of push-down automata it will be the case that you must make the distinction that push-down automata with transition functions that are partial functions are classified as deterministic, not nondeterministic.

If the partial function bothers you then here is a trivial transformation that makes $\delta$ a total function.  (This transformation is not like the subset construction algorithm, it adds at most O(1) states, is linear in the original number of states, and can be extended to work with PDAs.  None of those facts is true of the subset construction algorithm.)

add a state $q_{\mathrm{error}}$
for every pair $(q_i, s_j)$ where $\delta$ is undefined, define $\delta(q_i, s_j) = q_{\mathrm{error}}$.

This automata has a $\delta$ that is a total function and accepts and rejects exactly the same set of states that your original automata accepted and rejected.

Edit, January 2019

Commenter @Alex Smart rightly critiques me for neither giving references, nor for explaining why we should care.  So here goes:

The reason we care about the exact definition of determinism vs non-determinism, is that some classes of non-deterministic automata are more powerful than their deterministic cousins, and some classes of non-deterministic automata are not more powerful than their deterministic cousins.  For finite automata and Turing machines the deterministic and non-deterministic variants are of equivalent power.  For pushdown automata there are languages where the distinction is important: There are NPDA that accept the language, and no DPDA accepts the language.  For the linear bounded automata the question is (or was last time I checked) open.  The increase of power of NPDA over DPDA comes from allowing multiple transitions, not from turning the transition function from a total function to a partial function.

Books from the compiler community:

Aho and Ullman, Principles of Compiler Design, 1977: First defines NFA (page 88) with a transition relation, then (p. 90-91):

  We say a finite automaton is deterministic if
  1. It has no transitions on input $\epsilon$.
  2. For each state $s$ and input symbol $a$, there is at most one edge labeled $a$ leaving $s$.

Aho, Sethi, and Ullman, Compilers, principles, tecniques, and tools, 1988 reprint, is similar, it first defines NFA with a transition relation, then (p. 115-116):

  A deterministic finite automata (DFA, for short) is a special case of a non-deterministic finitie automaton in which ... there is at most one edge labeled $a$ leaving $s$.

(Note that in the comments @Alex Smart says, "the dragon specifically mentions that the function is total."  I assume he is talking about the later edition with co-author Lam, which I don't have access to at the moment.)

Appel, Modern Compiler Implementation in Java, 1988 (p. 22):

  In a deterministic finite automaton (DFA), no two edges leaving from the same state are labeled with the same symbol.

Appel then goes on to explain that when using DFA to recognize longest matches we explicitly make use of the missing transitions to decide when to stop (p. 23):

  when a dead state (a nonfinal state with no output transitions) is reached, the variables [which record the longest match we've seen so far] tell what token was matched, and where it ended.

Books from the switching-theory community:

Kohavi, Switching and Finite Automata Theory, 2/e, 1978, p. 611 says:

  Because a state diagram describes a deterministic machine, the next state transition must be determined uniquely by the present state and the presently scanned input symbol.

I would typically interpret uniquely to mean "exactly one", not "no more than one".  (I.e., Kohavi seems to be saying that determinism requires a total function)

Books from the theory-of-computation community:

Here it seems to be more common to define DFAs before NFAs, and require DFAs to have a total transition function, but then define NPDAs before DPDAs, and define "determinism" as being a restriction of the transition relation to having no-more-than-one entry for each state/symbol pair.

This is true of Hopcroft and Ullman, 1979, Lewis and Papadimitriou, 1981, and, especially of Sipser, 2006, who uses the definition of DFA pedagogically to introduce precise formal definitions, and explain their importance and explicitly says (p.36):

  the transition function, $\delta$, specifies exactly one next state for each possible combination of a state and an input symbol.

This seems to follow the historical development.  Deterministic finite automata were introduced in the 40s and 50s.  Non-determinisitc finite automata were introduced in the paper by Rabin and Scott, "Finite automata and their decision problems, IBM J. Rsrch and Dvpt, 3(2):114-125, 1959.  Following earlier authors, Rabin and Scott define deterministic finite automata (which they call ordinary automata) as having a transition function "defined on the Cartesian product $s\times\Sigma$ of all pairs of states and symbols."  (Which I would interpret as meaning a total function).

Interestingly Rabin and Scott, also define non-deterministic finite automata in terms of a total function!  Page 120, Definition 9:

  A nondeterministic (finite) automaton ... is a system where ... $M$ is a function[!] of $S\times\Sigma$ with values in the set of all subsets of $S$.

That is: the transition function being total does not make the system deterministic!

Sipser 2006 follows Rabin and Scott and uses a total transition function from states/symbols to the power set of states for his definitions of non-deterministic finite automata, non-deterministic PDA, and non-deterministic Turing Machines, but skips the topic of deterministic PDA.

Both Hopcroft and Ullman, 1979, and Lewis and Papadimitriou, 1981 use partial functions in their definitions of deterministic PDAs.  They first define NPDAs with a transition relation, and then when they get to PDAs, Lewis and Papadimitriou say (p. 135),

  A pushdown automaton is deterministic, intuitively speaking, if there is at most one transition applicable to each configuration.

While Hopcroft and Ullman say (p. 112):

  The PDA ... is deterministic in the sense that at most one move is possible from any ID.


Number of spanning trees in undirected simple graph

You cannot show this since it isn't true. I encourage you to try out some actual numbers (e.g. $n=2$) and see for yourself that the numbers don't match. The problem is that what you should be subtracting is not the number of cycles of length $n-1$, but rather the number of collections of $n-1$ edges which contains at least one cycle. Such a collection need not be a cycle of length $n-1$.

In addition, the formula for the number of cycles of length $n-1$ is wrong. The number is $n(n-2)!$ rather than your $n(n-1)!$, and even this formula is only valid for $n \geq 4$ (for smaller $n$ there are no such cycles). However, even after replacing $n(n-1)!$ by $n(n-2)!$, the numbers don't match.


Pumping Lemma for $L=\{a^{2k} b^n b^k \mid k\ge0, n\ge0\}$

Choose for example the word $x=a^{2k}b^{k}\in L$ ( with $|x|=3k\ge k$)
Possible partitions of $x=uvw$ are $u=a^l,\;v=a^s,\;w=a^mb^{k}$ with $s\ge 1,\; l+s\le k$ and $l+s+m=2k$
Now lets look at $uv^2w=a^{2k+s}b^k$ which is clearly not in $L$. If $s$ is odd, than the number of $a$'s is odd and therefore $uv^2w\notin L$. If otherwise $s$ is even, then the number of $b$'s would have to be larger than $(2k+s)/2$, which it is not ($k<(2k+s)/2)$. Therefore $uv^2w\notin L$ holds for each $s\ge 1$.

$\rightarrow$ $L$ is not regular.


For every $\mathrm{NP}$ language $L$, is there a verifier such that, for all the certificates $u$ of other verifiers of $L$, it accepts $(x, u)$?

Fix $x \in L$ of length $|x|=n$. Suppose that $\mathcal{V}_q \neq \emptyset$, and let $m = q(n)$. Choose some $V^0 \in \mathcal{V}_q$. For any $s \in \{0,1\}^m$, let $V^s(y,u) = V^0(y,u \oplus s)$ for inputs of length $n$ and witnesses of length $m$, $V^s(y,u) = 0$ for inputs of length $n$ and witnesses lengths different from $m$, and $V^s(y,u) = V^0(y,u)$ otherwise. Then $V^s$ is a verifier for $L$ for all $s$, and so $\bigcup_{V \in \mathcal{V}_q} V_x = \{0,1\}^m$.
This means that if a verifier $\bar{V}$ exists, then $\bar{V}_x$ is the set of all strings of length $q(|x|)$. This means that $\bar{V}$ need not consult its witness, showing that $L \in \mathsf{P}$.


Rewritten to match the new edited version of the question

What you want to think about is the size of the state for a DFA corresponding to a regular expression to match the number in question.

(I don't know how to draw DFAs here so work with my hand waving if you can.)

Since the thing you are looking for is a constant string the regular expression is just that string, say for example 6041234567. As a DFA this is a start node connected 10 intermediate nodes and a final accepting node. Then each of these nodes connect to the next node if the next character is the right one in the stream or back to the start if it is an incorrect input.  If you ever reach the final accepting node you have found the phone number and can do a happy dance.

That is all a setup for the fact that the only thing that matters state-wise is the current node you are matching on.  In my simple example here there are 12 nodes total, so you really only need 4 bits of data.

So you could have one upped the interviewer and said that in reality all you needed is a single nybble, instead of a whole byte.

A note about loop unrolling and state hiding

You can also achieve this by just writing a long list of checks for each individual digit as David commented above with what appears to be zero state.  But what that long list of checks is really doing is just moving the state into the program counter. You can do that with any fixed length matching problem, it is technically true but not really interesting.

One can also argue that I am moving state into the DFA, how is that represented? That is a fair cop, if one is being super pedantic, we would have to specify things like "A DFA is a 5-tuple consisting of yada yada yada" when we really need that precision.  Unless you were interviewing for a position in CS theory or compiler design no interviewer would be going there.

The reason that I am pretty certain that my answer is the right one in this case is that this question sounds like one that is asked all the time.  About half-way through a Theory of Computation course right after you learn about using DFAs to match REGEXPs you will look into the number of states and how to represent them.  This gives a nice intuition about the complexity and "size" of the various languages they match.  It also nicely segues into the way that removing determinism can greatly shrink the resulting transition graph and going the other way can result in an explosion in the number of states.


We define the alphabet as the set of natural numbers.

No you don't. The alphabet must be finite.

  Am I correct in saying that, we do not know whether this Turing machine will halt for any given input?

If all you know is that the TM recognizes the language then you're correct: it could loop forever on some inputs.

  Since this is a decision problem, the language realised from it, will always b finite?

That doesn't follow from being a decision problem. This language is finite because there are only finitely many natural numbers less than 400. But, for example, the language of even numbers is infinite, but it's still a decision problem.

  Am I correct in saying that we have defined this Turing machine to accept one word at a time, where the words are numbers. We could have made it accept two words, if the algorithm was modified to accept two inputs.

Yes, you could produce a Turing machine that decides the language $\{x,y\mid x,y\leq 400\}$.

  How would the Language be for the problem: "Is X <= Y?"

It would be the set of all strings with that property.

  For a decision problem, the elements in the Language realised are the solutions?

I'm not sure what you mean by "realised". (You wrote it before but the exact meaning wasn't so important, then.) A decision problem is any problem of the form "Does the input string have property X?" and it's naturally associated with the language of strings that do have that property.


Are modern programming languages context-free?

Practically no programming language, modern or ancient, is truly context-free, regardless of what people will tell you. But it hardly matters. Every programming language can be parsed; otherwise, it wouldn't be very useful. So all the deviations from context freeness have been dealt with.
What people usually mean when they tell you that programming languages are context-free because somewhere in the documentation there's a context-free grammar, is that the set of well-formed programs (that is, the "language" in the sense of formal language theory) is a subset of a context-free grammar, conditioned by a set of constraints written in the rest of the language documentation. That's mostly how programs are parsed: a context-free grammar is used, which recognises all valid and some invalid programs, and then the resulting parse tree is traversed to apply the constraints.
To justify describing the language as "context-free", there's a tendency to say that these constraints are "semantic" (and therefore not part of the language syntax). [Note 1] But that's not a very meaningful use of the word "semantic", since rules like "every variable must be declared" (which is common, if by no means universal) is certainly syntactic in the sense that you can easily apply it without knowing anything about the meaning of the various language constructs. All it requires is verifying that a symbol used in some scope also appears in a declaration in an enclosing scope. However, the "also appears" part makes this rule context-sensitive.
That rule is somewhat similar to the constraints mentioned in this post about Javascript (linked to from one of your comments to your question): that neither a Javascript object definition nor a function parameter list can define the same identifier twice, another rule which is both clearly context-sensitive and clearly syntactic.
In addition, many languages require non-context-free transformations prior to the parse; these transformations are as much part of the grammar of the language as anything else. For example:

Layout sensitive block syntax, as in Python, Haskell and many data description languages. (Context-sensitive because parsing requires that all whitespace prefixes in a block be the same length.)

Macros, as in Rust, C-family languages, Scheme and Lisp, and a vast number of others. Also, template expansion, at least in the way that it is done in C++.

User-definable operators with user-definable precedences, as in Haskell, Swift and Scala. (Scala doesn't really have user-definable precedence, but I think it is still context-sensitive. I might be wrong, though.)

None of this in any way diminishes the value of context-free parsing, neither in practical nor theoretical terms. Most parsers are and will continue to be fundamentally based on some context-free algorithm. Despite a lot of trying, no-one yet has come up with a grammar formalism which is both more powerful than context-free grammars and associated with an algorithm for transforming a grammar into a parser without adding hand-written code. (To be clear: the goal I refer to is a formalism which is more powerful than context-free grammars, so that it can handle constraints like "variables must be declared before they are used" and the other features mentioned above, but without being so powerful that it is Turing complete and therefore undecidable.)
Notes

Excluding rules which cannot be implemented in a context-free grammar in order to say that the language is context-free strikes me as a most peculiar way to define context-freeness. Of course, if you remove all context-sensitive aspects of a language, you end up with a context-free superset, but it's no longer the same language.


Can big-step semantics express evaluation order?

No, you cannot express evaluation order using big-step semantics.

Borrowing from Benjamin Pierce: big-step semantics is a multi-step evaluation relation that directly formulates the notion of "this term evaluates to that final value". So it cannot impose the kind of evaluation order you describe.

Also keep in mind what the horizontal bar represents. Again borrowing from Pierce: If we have established the statements in the premise(s) listed above the line, then we may derive the conclusion below the line. It would not make sense to impose an ordering on the premises to draw the conclusion.


Closure of a CFL under specific operation

You are right, regular languages are closed under inversion $\mathrm{inv}$, using some proper guesses, or see my answer to a relevant question here.

Context-free languages are not closed under $\mathrm{inv}$. Your intuition does not work. We cannot push $y$ on the stack because it will make the 'real' stack below it inaccessible for the simulation.

Here is a possible counter example. Consider $L = \{ a^nb^nc^md^m \mid m,n\ge 1 \}$. Then try $\mathrm{inv}(L) \cap a^*c^*b^*d^* $.


Why are there more non-computable functions than computable ones?

The are countably many computable functions:

Each computable function has at least one algorithm.
Each algorithm has a finite description using symbols from a finite set, e.g. finite binary strings using symbols $\{0,1\}$.
The number of finite binary strings denoted by $\{0,1\}^*$ is countable (i.e. the same as the number of natural numbers $\mathsf{N}$).

Therefore there can be at most countably many computable functions.
There are at least countable many computable function since for each $c\in \{0,1\}^*$, the constant function $f(x)=c$ is computable.

In other words, there is a correspondence between:

the set of computable functions,
the set of algorithms,
$\{0,1\}^*$, the set of finite strings from $\{0,1\}$, and
$\mathbb{N}$, the set of natural numbers.

On the other hand, there are uncountably many functions over strings (or natural numbers). A function $f:\mathbb{N} \to \mathbb{N}$ (or $f:\{0,1\}^* \to \{0,1\}^*$) assigns a value for each input. Each of these values can be chosen independently from others. So there are $\mathbb{N}^\mathbb{N}=2^\mathbb{N}$ possible function. The number of functions over natural numbers is equal to the number of real numbers.

Since only countably many of functions are computable, most of them are not. In fact the number of uncomputable functions is also $2^{\mathbb{N}}$.

If you want to picture this intuitively, think about natural numbers and real numbers, or about finite binary strings and infinite binary strings. There are way more real numbers and infinite binary strings than natural numbers and finite strings. In other words $\mathbb{N} < 2^\mathbb{N}$ (for a proof of this fact see Cantor's diagonal argument and Cardinal arithmetic).


how does Kleene-Post show two languages that are not Turing reducible to each other?

Unfortunately, I don't possess a copy of Sipser, so I will just define all my notation. Let $T_0,T_1,\ldots$ an enumeration of all oracle Turing machines whose input is a word over some alphabet $\Sigma$. I will denote by $T_i^O(x)$ the output of the execution of $T_i$ on input $x$ with oracle $O$, or $\bot$ if the machine doesn't halt. We say that $T_i$ (Turing-)reduces $A$ to $B$ if $T_i^B(x)$ halts for all $x$, and returns the truth value of "$x \in A$". We assume for simplicity that the output of $T_i^B(x)$ can always be interpreted as a truth value.
We will construct two sequences $A_0,A_1,\ldots$ and $B_0,B_1,\ldots$ of "partial sets", that is, mappings from $\Sigma^*$ to $\{0,1,\bot\}$. Initially, $A_0$ and $B_0$ map all strings in $\Sigma^*$ to $\bot$. Moreover, $A_{i+1}$ is an extension of $A_i$, that is, if $A_i(x)\neq \bot$ then $A_{i+1}(x) = A_i(x)$. Furthermore, each $A_i$ or $B_i$ is defined (not equal to $\bot$) for only finitely many words in $\Sigma^*$.
We will eventually take $A$ to be a set extending all $A_i$, that is, if $A_i(x) = 0$ for some $i$ then $i \notin A$; if $A_i(x) = 1$ for some $i$ then $i \in A$; and otherwise the status of $i$ doesn't matter (for definiteness, let $i \notin A$). The extension property guarantees that $A$ is well-defined. We define $B$ similarly.
We construct $A_{2i+1},B_{2i+1}$ from $A_{2i},B_{2i}$ in a way which rules out $T_i$ being a reduction from $A$ to $B$. By assumption, there exists $x \in \Sigma^*$ such that $A_{2i}(x) = \bot$. Consider what happens when we try to run $T_i$ on input $x$ with oracle $B_{2i}$. If $T_i$ tries to apply the oracle on a word $y$ on which $B_{2i}$ is defined, then it gets $B_{2i}(y)$. If $B_{2i}(y) = \bot$, then we simulate both branches in parallel (each of them could further split down the road). One of the following must happen:

There is a branch on which computation halts.
All branches result in non-halting computations.

The second case is easy – $T_i$ cannot be a reduction from $A$ to $B$, since it doesn't halt on input $x$, whatever happens in later stages of the construction. So we take $A_{2i+1} = A_{2i}$ and $B_{2i+1} = B_{2i}$.
In the first case, we actually have to do something. Pick a halting branch. The branch corresponds to a choice of definite values for some strings in $\Sigma^*$ on which $B_{2i}$ is undefined. We form $B_{2i+1}$ from $B_{2i}$ by keeping all values already defined in $B_{2i}$, and defining the additional strings occurring in the halting branch according to the branch. We form $A_{2i+1}$ from $A_{2i}$ by keeping all values already defined in $A_{2i}$, and defining $A_{2i+1}$ on $x$ in the opposite way to what $T_i$ answers in the halting branch: if $T_i$ outputs Yes then $A_{2i+1}(x) = 0$, and if $T_i$ outputs No then $A_{2i+1}(x) = 1$. This ensures that $T_i$ does not reduce $A$ to $B$, since it outputs the wrong value on $x$.
We construct $A_{2i+2},B_{2i+2}$ from $A_{2i+1},B_{2i+1}$ in a similar way, switching the roles of $A$ and $B$, ruling out $T_i$ being a reduction from $B$ to $A$.
Since the final $A$ and $B$ "encompass" all $A_i,B_i$, by construction no $T_i$ reduces $A$ to $B$ or $B$ to $A$, and so there is no Turing reduction from $A$ to $B$ or from $B$ to $A$.

The dichotomy above (some branch halts / all branches never halt) is not computable, in the sense that given $A_{2i},B_{2i},T_i$ we cannot determine which of the two options occurs. But it is possible using an oracle to the halting problem, since we can construct a Turing machine which tries out all branches in parallel, and immediately halts if one of them halts. Furthermore, by "going down the tree" we can find a halting branch if such exists. This shows that we can compute the sequences $A_i,B_i$ using an oracle to the halting problem.
Now suppose that when choosing a string $x$, then we always choose the first such string on which $A_{2i}$ (or $B_{2i+1}$) is undefined, according to some fixed ordering. This guarantees that any string will be eventually defined by some $A_i$ and by some $B_j$. Since the sequences $A_i,B_j$ are computable using an oracle to the halting problem, this shows that the sets $A,B$ are computable using an oracle to the halting problem.

Here is an alternative proof. Let $\mu$ be an arbitrary measure on languages such that $\mu(L) = 0$ for any specific language $L$ (we say that $\mu$ has no atoms). For example, $\mu$ could correspond to the experiment in which each word is put in the language with probability $1/2$ independently.
Let $\mathbf{A},\mathbf{B} \sim \mu$. The probability that $T_i$ reduces $\mathbf{A}$ to $\mathbf{B}$ is 0, since fixing the outcome of $\mathbf{B}$ to be $B$, there is at most one language $L$ which $T_i$ reduces to $B$, and by assumption $\mu(L) = 0$. Since there are only countably many machines $T_i$, it follows that the probability that $\mathbf{A}$ reduces to $\mathbf{B}$ is zero. Similarly, the probability that $\mathbf{B}$ reduces to $\mathbf{A}$ is 0. We conclude that almost surely (that is, with probability 1), $\mathbf{A}$ doesn't reduce to $\mathbf{B}$ and $\mathbf{B}$ doesn't reduce to $\mathbf{A}$. In particular, there exist realizations $A,B$ such that $A$ doesn't reduce to $B$ and $B$ doesn't reduce to $A$.


What is the "shortest path heuristic" for the Steiner problem in graphs?

Let G = (V, E) be our graph, and S be the set of vertices that must be in the Steiner tree. Let t be the number of leaves in the optimal Steiner tree.
It seems that Takahashi and Matsuyama's algorithm (1980) is indeed the "shortest path heuristic" since it actually uses shortest-path searches. Starting from a single vertex, it simply grows the tree T by finding the closest vertex v in S \ T that hasn't been added yet, and adding the shortest path from T to v until all vertices have been added, similar to Prim's algorithm for the minimum spanning tree.
The algorithm I cited from Wikipedia, based on the metric closure, is due to Kou, Markowsky and Berman (1981), and boils down to: compute the metric closure, find the minimum spanning tree of the metric closure, turn this back into a subgraph (not necessarily a tree) of the original graph, find the minimum spanning tree of that subgraph, then repeatedly remove leaves that are not in S.
I didn't read Gilbert and Pollak (1968) fully (it's mostly about the geometry of Steiner trees in the plane). I presume they did something similar to Kou et al., but without the final pruning step, which might explain why they only got within a factor 2 from the optimal cost, rather than the 2 - 2/t by Kou et al..
I made some edits to Wikipedia to record all this, and added a summary of an algorithm by Wu, Widmayer and Wong (1986), which is more efficient and also easier to implement than both of the above, while retaining the same optimality bound.


First note that $\text{increase-key}$ must be $O(\log n)$ if we wish for $\text{insert}$ and $\text{find-min}$ to stay $O(1)$ as they are in a Fibonacci heap.

If it weren't you'd be able to sort in $O(n)$ time by doing $n$ $\text{insert}$s, followed by repeatedly using $\text{find-min}$ to get the minimum and then $\text{increase-key}$ on the head by $\omega$ with $\forall x:\omega > x$ to push the head to the end.

Now, knowing that $\text{increase-key}$ must be $O(\log n)$ we can provide a very simple asymptotically optimal implementation for it. To increase a node $n$ to value $x$, first you $\text{decrease-key}(n, -\infty)$, then $\text{delete-min()}$ followed by $\text{insert}(n, x)$.


Why isn't plus_assoc rewriting correctly?

It is rewriting correctly. Coq doesn't print redundant parentheses. The + operator is left-associative, so n + m + p is a valid way of writing the term (n + m) + p, and Coq prints it without the parentheses.
Coq < Check (n + m) + p.
n + m + p
     : nat

Just to be clear, n + m +p and (n + m) + p are exactly the same term, not just terms that are equal. They're different ways to use notations to write Nat.add (Nat.add n m).
Theorem plus_swap : forall n m p : nat,
  n + (m + p) = m + (n + p).
Proof.
  intros n m p.
  Unset Printing Notations.
  Show. (* Now the goal is shown as: eq (Nat.add n (Nat.add m p)) (Nat.add m (Nat.add n p)) *)
  rewrite -> plus_assoc. (* Now the goal is: eq (Nat.add (Nat.add n m) p) (Nat.add m (Nat.add n p)) *)


Equivalence of Büchi automata and linear $\mu$-calculus

The constructive equivalence of linear-time fixed point formulae (the logic is called $\nu$TL by some) and Buechi automata is given in a paper by Mads Dam from 1992.

Fixed Points of Buchi Automata, FST&TCS 1992.

See page 4 for the construction of a $\nu$TL formula from a Buechi automaton. The construction of a Buechi automaton from a $\nu$TL formula is more complicated and takes the rest of the paper.
The rest of this reply is a brief argument that this result existed in the literature in far less direct form. Pierre Wolper showed that there were omega-regular properties that were not LTL-definable and gave an extension of LTL (called ETL) that could express omega-regular properties.

Temporal Logic can be more expressive, Pierre Wolper, Information and Computation, 1983.

It is also known that one can translate ETL formulae into $\nu$TL formulae, so by combining these results you can read off a translation of Buechi automata into $\nu$TL. In the other direction, it follows from the work of Buechi that S1S (the second order theory of one successor) formulae can be compiled into Buechi automata and by translating $\nu$TL formulae into S1S, we obtain a translation of $\nu$TL to Buechi automata.
If you want a more in-depth introduction to these topics, I suggest Mads Dam's lecture notes, or the work of Roope Kaivola (sadly not as widely known as much related work).

Temporal Logics, Automata, and Classical Theories - An Introduction, Mads Dam, ESSLLI 1994.
Using Automata to Characterise Fixed Point Temporal Logics, Roope Kaivola


Processor pipelining question: number of instructions per second

The book quite rightfully ignores the three startup cycles. Nobody cares whether it performs $10^9$ or $10^9-3$ instructions. In reality, "1 ns" is never exactly one nanoseconds, so the deviation from the clock rate not being exactly one per nanosecond makes much more difference.


How do stack-based cache algorithms avoid Belady's anomaly?

Stack based algorithms implies that a set of n pages will be a subset of n+1 pages. Why?

In LRU every time a page is referenced it is moved at the top of the stack, therefore the top n pages of the stack are the n most recently used pages. Furthermore, since in LRU the near future is an approximation of recent past, we effectively will reduce the page faults if we increase n.

That is, if number of frames are now made n + 1, top of the stack will have n+1 most recently used pages. Hence, set of n pages are a subset of n+1 pages and as page faults are directly proportional to n (due to the LRU assumption) increasing n will never increase page faults.

An intuitive case(special case) is to think that the LRU stack uses n = number of total pages required by the process. There will be no page faults. And if n=1, there will be page faults equal to total pages required by the process.


Prove that $I(A;B|C)=0$ given $I(A;B)=0$

Your claim is false. Let $A,B,C$ range uniformly over the set
$$
\{(x,y,z) \in \{0,1\}^3 : x \oplus y \oplus z = 0 \}.
$$
On the one hand, $I(A;B) = 0$. On the other hand, $I(A;B|C) = 1$.


How to convert a decimal number to ASCII representation

The ASCII encodings for digits 0 to 9 are 48 to 57 in decimal, or 30 to 39 in hexadecimal.


Mankind formalized computation and developed two system for it in 1936 with the seminal papers of Alonzo Church on $\lambda$-calculus and Alan Turing (who today, June 23rd 2012, would turn 100 years old if not for despicable circumstances leading to his early passing) on what became known as Turing-machines. Both mathematicians were solving the Entscheidungsproblem.

Although Church's paper was published slightly earlier, Turing was unaware of it when he developed his ideas, and Turing's approach proved to be more useful for the design of real-world machines. This was because he showed how to design a Universal Turing Machine that could be programmed to run any computation. This universal machine, with a concrete architecture based on the work of John von Neumann is the basic idea behind the machine on which you are reading my answer.

As you noted, computable is defined as "computable on a Turing machine" and all other reasonable models of computation have proven to be equivalent in their power. The belief that all reasonable models of computation are equivalent in what decision problems they can solve is known as the Church-Turing thesis. In its original form, it is almost completely believed by the learned community. In fact it is not completely clear what it would mean to prove/disprove the Church-Turing thesis; in a lot of ways it becomes an empirical question.

However, there is still the extended Church-Turing thesis which asks the slightly more subtle question of: what can be computed efficiently?. Many classical models, such as $\lambda$-calculus, Turing Machines, tag-based systems, cellular automata, etc are equivalent under the extended thesis as well. However, the recent development of quantum computing casts doubt on the extended thesis. Although most people who work on quantum computers (including me) believe they are more efficient that classical ones, the matter is subject to scholarly debate. Note that in terms of the coarse notion of what is computable (as opposed to efficiently computable) quantum computing is still equivalent to Turing's model.


Does it make sense to say Big Theta of 1? Or should we just use Big O?

Remember your definitions! As $n \to \infty$ (the use in CS, almost always) $O(\cdot)$ is an upper bound (within a constant multiple, for large $n$), $\Omega(\cdot)$ is a lower bound (within a constant multiple, for large $n$), and $\Theta(\cdot)$ both of the previous. To see the difference, as $n \to \infty$ you have:

$\begin{align*}
  1 + \lvert \sin n \rvert
    &= O(1) \\
  1 + \lvert \sin n \rvert
    &= \Omega(1) \\
  1 + \lvert \sin n \rvert
    &= \Theta(1) \\
  e^{-n}
    &= O(1) \\
  e^{-n}
    &\ne \Omega(1) \\
  e^{-n}
    &\ne \Theta(1)
\end{align*}$

For the first three, as $\sin x$ moves between -1 and 1, the expression fluctuates between 1 and 2.

To see why $e^{-n} \ne \Omega(1)$ (and so $e^{-n} \ne \Theta(1)$), note that we are looking for a constant $c > 0$ and an $N_0$ so that for all $n \ge N_0$ we have $e^{-n} \ge c \cdot 1$. For any $c$ you pick, you'll find that taking $n > \ln 1 / c$ makes this false. So no $c$ works.


Prove the language $\{x \in \Sigma^* : \exists w \in \Sigma^* \ xww \in L \}$ for regular language $L$ is regular

Let $A = (Q, \delta, q_0, F)$ a DFA that accepts $L$. For $q, q' \in Q$, define:

$L_{q,q'} = \{u\in \Sigma^*, \delta^*(q, u) = q'\}$;
$L_{q',F} = \{u\in \Sigma^*, \delta^*(q', u) \in F\}$.

It is quite easy (can you prove it?) to see that those languages are regular.
Now the language $\{x\in \Sigma^*\mid \exists w\in\Sigma^*, xww\in L\}$ can be written as:
$$\bigcup\limits_{q\in Q}L_{q_0,q}\cdot M(q)$$
Where $M(q) = \left\{\begin{array}{rl}\emptyset&\text{if }\bigcup\limits_{q'\in Q}L_{q,q'}\cap L_{q',F}=\emptyset\\\{\varepsilon\}&\text{otherwise}\end{array}\right.$
$M(q)$ is regular since it is either $\emptyset$ or $\{\varepsilon\}$, so that means that $Z(L)$ is regular.


What are the treatises on how to build mechanical computers?

This is a very broad question, with a different answer for each kind of device.
The computers before modern times did NOT use logic gates.

For example the January 2004 Scientific American article "The Curious History of the First Pocket Calculator" covers how Curta calculators work, in addition to the history.

The Antikythera mechanism used gear reductions (gears with differing teeth counts) to implement the ratios of times of various periodic events to predict positions. Given the [known even then] frequencies, it is straightforward to compute the required gear ratios. http://www.cs.virginia.edu/~robins/Decoding_an_Ancient_Computer.pdf

In addition (as mentioned in a comment above) there were many many different flavors of analog computers, that a quick google search should be able to find explanations for many of them.


Generate a uniform random numbers in $O(1)$

Since $r < m \leq n$, necessarily $k \geq 1$ and so $n - r = km \geq m > r$. In particular, $r < n/2$ and so $n-r > n/2$. In total, we conclude that $n/(n-r) < 2$.


Is the clique problem NP-complete also on bipartite or planar graphs?

In a bipartite graph there can be no clique of size three. Not much of a problem that is left I guess?

(edit) Sorry, that was too fast, I realize thanks to comment by Nicholas below. To make up for it I googled a reference.

The maximum edge biclique problem is NP-complete by Ren*e Peeters. Discrete Applied Mathematics 131 (2003) 651 – 654

(ps) So I understand that my answer relates to a question that changes the types of graphs we are looking for, kind of bipartite cliques, whereas the other answer restricts the set of graphs we are looking in to planar. In planar graphs cliques can have size at most four, thanks to Kuratowski.


What is the difference between a Top type and a Unit type

Let me first give the mathematical counterparts of the unit and the top type:

the unit type is the type $U$ such that for every type $X$ there is a unique map $X \to U$
the top type is the type $T$ such that every type $X$ is a subtype of $T$, written $X \leq T$

Thus we cannot speak of the top type unless we have subtyping. Not all type systems have subtyping, and in those there is no top type to speak of.

The unit type $U$ must be very small: since there is only one map $U \to U$, if we have $a, b: U$ then the two maps $x \mapsto a$ and $x \mapsto b$ must be equal, whence $a = b$. We should be more precise about what "equal" means, and we should discuss non-terminating computations, but let's keep things simple. On the other hand, there must be at least one element of $U$, or else there can be no map $\mathtt{int} \to U$. (NB: We can only have a map $S \to \emptyset$ when $S$ itself is the empty set.)

The type called $\mathtt{void}$ isn C/C++ has the property of the unit type. It is a mistake to think that a function returning $\mathtt{void}$ "returns nothing". It actually returns precisely one thing, but because the unique thing that it returns is unique and does not carry any information beyond the fact that the function actually returned, we never make the thing explicit. Thus programmers never see it, and so they end up thinking it isn't there. There are programming languages in which the unique element of the unit type can be made explicit. Can there be a function that returns nothing? Yes, it's a function that does not return at all (if it did, it would have to return something) – it is a function which raises an exception! Raising an exception is not "returning".

The top type $T$ must be in some sense very large because every other type is a subtype of $T$. Note that $X \leq T$ does not necessarily mean that there is an injective map $X \to T$, nor does the fact that there is a map $X \to T$ imply $X \leq T$. There are many kinds of subtyping and it is really quite impossible to tell  more precisely what "large" means without knowing what sort of subtyping we are talking about.

For example, in some languages there is subtyping between numerical types, so that for instance $\mathtt{byte} \leq \mathtt{int} \leq \mathtt{float}$. Here $\mathtt{float}$ could be the top type, and it is the "largest" numerical type.

On the other hand, structural record subtyping says that the record type $R = \{\ell_1 : X_1, \ldots, \ell_m : X_m\}$ is a subtype of $Q = \{k_1 : Y_1, \ldots, k_n : Y_n\}$ when every field $k_j : Y_i$ has a corresponding field $\ell_i : X_i$ such that $k_j = \ell_i$ and $X_i \leq Y_j$. In words, $R \leq Q$ means that an $R$-record may be seen as a $Q$-record because it has all the fields that a $Q$-record should have, and possibly more. Under this view the top type is the empty record $\{\}$, which is isomorphic to the unit type!

You asked concretely about subtyping of functions. The basic rule there is: if $X_2 \leq X_1$ and $Y_1 \leq Y_2$ then $(X_1 \to Y_1) \leq (X_2 \to Y_2)$ (notice the reversal of inequality for $X_1$ and $X_2$). In your particular case we have $X_1 = X_2 = T_1 \times T_2 \times T_3$, $Y_1 = \mathtt{SomeType}$ and $Y_2 = \mathtt{unit}$ (I refuse to write "void" for something that is not the empty type and C/C++ can go sulk in the corner). So the question comes down to $\mathtt{SomeType} \leq \mathtt{unit}$, i.e., should the unit type be the top type? Well, this depends on what "subtype" means, as I tried to explain above. In C and C++ subtyping is expressed through a system of implicit coercions, so you'd have to open a book on C and find out whether there is supposed to be an implicit coercion from an arbitrary type to the unit type. It's a matter of language definition.


Given a 3CNF with clauses $\phi_1,\ldots,\phi_k$ on variables $x_1,\ldots,x_n$. Suppose both $x_i$ and $\overline{x_i}$ appear in the formula for at most $k_i$ times respectively.

We design a colored DAG $G$ whose vertices consists of three parts:

"Assignment" vertices $v_i(j)$ and $\bar{v}_i(j)$, $1\leq i\leq n$, $1\leq j\leq k_i$. Color $v_i(j)$ with the "color" $x_i(j)$, and $\bar{v}_i(j)$ with $\overline{x_i}(j)$.
"Clause" vertices $w_{i'}(j')$, $1\leq i'\leq k$, $j'=1,2,3$. Color $w_{i'}(j')$ with the color $x_i(j)$ (or $\overline{x_i}(j)$) if $\overline{x_i}$ (or $x_i$, resp.) is the $j'$-th literal of clause $\phi_{i'}$, and it's the $j$-th clause containing this literal.
"Cut" vertices $s=s_0,s_1,\ldots,s_n, s_{n+1},\ldots s_{n+k}=t$. Color them with distinct colors different from above.

The edges include:

$s_{i-1}v_i(1)$, $v_i(j)v_i(j+1)$, $v_i(k_i)s_i$;
$s_{i-1}\bar{v}_i(1)$, $\bar{v}_i(j)\bar{v}_i(j+1)$, $\bar{v}_i(k_i)s_i$;
and $s_{n+i'-1}w_{i'}(j')$, $w_{i'}(j')s_{n+i'}$.

For instance, from the 3CNF
$(x_1 \vee x_2 \vee \overline{x_3})\wedge(x_1 \vee \overline{x_2}\vee x_3)$
the following graph is constructed (The edge directions are from left to right).

Now it is not hard to see that the original 3CNF is satisfiable if and only if there is a $s$-$t$ path with different vertex colors in $G$.

(By the way, it is a by-product that the existsence of $s$-$t$ path with different vertex colors in colored DAG is $\textsf{NP-hard}$. I didn't find many literatures about this problem in computational perspective. If you know, please comment!)

So what is the relation between $G$ and OP's problem? Intuitively what we are going to do is to design a matrix $h$, so that each color is mapped to a row (which is a person), and the edges are mapped to consecutive columns (time slots). Therefore a maximum scheduling, which is basically going from left to right in the matrix, corresponds to an $s$-$t$ path.

Our matrix $h$ have $2n+1+\sum_i 2k_i+k$ columns, with indices starting from $0$. In the following constrcution $X$ an $Y$ are two values satisfy $1\ll X\ll Y$. The ratios $X/1, Y/X$ can be large powers of $k$ and $n$. Let $K_i=2i+2\sum_{j=1}^i k_i$.

For each $s_i$, $0\leq i\leq n$, let $h(s_i,K_i)=h(s_i,K_i-k_i-1)=h(s_i,K_i+k_{i+1}+1)=Y$ (if the coordinate exists, same below).
For each $x_i(j)$, let $h(x_i(j),K_{i-1}+j)=X$; For each $\overline{x_i}(j)$, let $h(\overline{x_i}(j),K_{i-1}+k_i+1+j)=X$.
For each $\phi_{i'}$, $1\leq i'\leq k$ and a literal $x$ in the clause $\phi_{i'}$, let $h(x,K_n+i')=1$.
All the other entries are 0.

For example, for the above example graph the corresponding matrix is

Now we claim: the original 3CNF is satisfiable if and only if the maximum value is $(2n+1)Y+\sum_i k_iX+k$.

Consider the scheduling achieving the maximum value. Since there are exactly $(2n+1)$ columns in $h$ containing $Y$, they should all be covered.
For the column $K_i+k_i+1$ which has two choices of $Y$, suppose the scheduling assigns it to $s_i$. Since column $K_i$ must be assigned to $s_i$, by the consecutiveness we have to lose the columns $K_i+1$ to $K_i+k_i$. Same things happen if the scheduling assign the column $K_i+k_i+1$ to $s_{i+1}$.

Therefore, in order to have the value $\sum_i k_iX$, we must select all the rest available $X$'s in the matrix, which corresponds to an assignment on variables. So the rest value of $k$ is achievable if and only if the assignment satisfy every clause.

As a conclusion, deciding the maximum value of a legal scheduling is in $\textsf{NP-hard}$. Maybe that's why all our previous attempts to find an algorithm failed.


Since we are checking edges in different order each time, the time taken will depend on the order of the edges being checked in Bellman-Ford algorithm.

We will get the final result in 2 steps if our order is $v_1v_2, v_2v_3, v_3v_4, ... v_{99}v_{100}$.

However we  will get the final result in 100 steps if our order is $v_{99}v_{100}, v_{98}v_{99}, ..., v_3v_2, v_2v_1$. We can prove that this is worst possible by noting that in Bellman-Ford algorithm with positive weights, in every iteration at least one shortest distance is calculated correctly. So in first iteration we will only determine the shortest distance to $v_2$, others will remain $\infty$, in second iteration we will determine the shortest distance to $v_2$ and $v_3$ while others still remain $\infty$, and so on so forth.


Examples of context sensitive syntactic constructs (statements)

Here are three context-sensitive syntaxes actually found in programming languages. I don't believe I've ever seen a language which has types, names and values distributed as per your example, but it could certainly exist, and I'm sure there are even less readable syntaxes which are possible. The following are at least somewhat readable:

Syntactic whitespace, as per Python or Haskell. This is usually handled with a context-sensitive lexical scanner rather than a context-sensitive grammar, but it is certainly context-sensitive, and it could be handled with a context-sensitive grammar if you had the machinery available. (In fact, it could be cleaner to handle it in the parser, especially for languages like Haskell in which layout-sensitive parsing is optional. [Note 1])
Multi-dimensional array literals. Here, I'm not talking about languages which implement heterogeneous one-dimensional arrays as first-class types, so that an array can be an element of another array; in that case, there is no requirement that a multi-dimensional array be regular. Rather, I'm talking about languages in which multi-dimensional arrays must be regular, and so an irregular literal is a syntax error:

julia> [2 3 4;5 6 8]
2x3 Array{Int64,2}:
 2  3  4
 5  6  8

julia> [2 3 4;5 6]
ERROR: hvcat: row 2 has mismatched number of columns
 in hvcat at abstractarray.jl:993

That's a bit of a cheat, because the Julia syntax above is really syntactic sugar for a call to hvcat, as indicated in the error message. But it could have been syntactic. Fortress -- the syntactic collector's favourite vapourware language -- proposed syntactic array literals:

  The parts of higher-dimensional matrices are separated by repeated-semicolons, where the dimensionality of the result is equal to one plus the number of repeated semicolons. Here is a 3 x 3 x 3 x 2 matrix:

[ 1 0 0
  0 1 0
  0 0 1   ;;   0 1 0
               1 0 1
               0 1 0   ;;   1 0 1
                            0 1 0
                            1 0 1
  ;;;
   1 0 0
   0 1 0
   0 0 1   ;;   0 1 0
                1 0 1
                0 1 0   ;;   1 0 1
                             0 1 0
                             1 0 1 ]

  The elements in a matrix expression may be either scalars or matrices themselves. If they are matrices, then the elements along a row (or column) must have the same number of columns (or rows), though two elements in different rows (columns) need not have the same number of columns (rows). A scalar is treated as a one by one matrix. (Quoted from The Fortress Language Specification by Guy L. Steele et al, §2.3.19, p. 21)

Agreement between parameter count in function prototypes and number of arguments in function calls. Perhaps this fits in your concept of "type checking", and I don't think it adds anything interesting to your problem set. But it is certainly context-sensitive.

Notes

I stumbled upon Layout-sensitive Generalized Parsing by Sebastian Erdweg, Tillmann Rendel, Christian Kästner, and Klaus Ostermann. while writing this answer, but I haven't read it. It seems to propose a usable formalism for layout-aware parsing.


Separating numbers with a minimal difference

As shown in the previous answer, this problem can be modeled as a scheduling problem with release and due dates. However, Schrage's heuristic works only for the case $p_j=1$ (all processing times are $1$) or when release and due dates agree (i.e. there is an order such that $r_1\leq\cdots\leq r_n$ and $d_1\leq\cdots\leq d_n$).

For the case $p_j=p$ polynomial algorithms have been found by Simons (1978), Carlier (1981), and Garey et al. (1981), running in time $O(n^2\log n)$, $O(n^2\log n)$, and $O(n\log n)$, respectively.

The algorithm of Garey et al. schedules unit-time tasks, but allows arbitrary release and due dates. The above problem can be reduced to this setting by dividing all dates and processing times by $p$. The main idea of the algorithm is to find a set of forbidden regions where no task is allowed to start. They show that Schrage's heuristic when respecting forbidden regions finds a feasible schedule of minimal makespan. When constructing the forbidden regions their algorithm may also detect infeasibility.

To see how the algorithm works, first look at a simpler problem: schedule $n$ unit-time tasks between a release date $r$ and a deadline $d$ respecting forbidden regions $F=\bigcup_i (a_i,b_i)$, where each region $(a_i,b_i)$ is  an open interval. (Note here we're not concerned with release and due dates of individual tasks.)

This problem can be solved by Backscheduling: define a sentinel starting time $s_{n+1}=d$, and for $i=n,n-1,\ldots,1$ set starting time $s_i$ to the latest time not later than $s_{i+1}-1$ that is not forbidden.

Write $B(r,d,n,F)$ for an application of Backscheduling for the above inputs, and define the return value as $s_1$, the latest possible starting date for scheduling the $n$ tasks. Now, if $B(r,d,n,F)<r$ there is no feasible schedule for the $n$ tasks. Further, if $r\leq B(r,d,n,F)<r+1$ no other task can start in $(B(r,d,n,F)-1,r)$ since otherwise there is again no feasible schedule for the $n$ tasks, and thus $(B(r,d,n,F)-1,r)$ can be declared a forbidden region.

It turns out that this logic is sufficient to find all forbidden regions that are required to make Schrage's heuristic work. Assume that tasks are ordered such that $r_1\leq r_2\leq\cdots\leq r_n$ and write $n(r,d)$ for the number of tasks which are released and due in the closed interval $[r,d]$.

set $F=\emptyset$
for tasks $i=n,n-1,\ldots,1$:
  $c=\min \{ B(r_i,d_j,n(r_i,d_j),F) \mid \forall j: d_j\geq d_i\}$
  if $c<r_i$: return "no feasible schedule"
  else if $r_i\leq c<r_i+1$: set $F=F\cup\{(c-1,r_i)\}$

A straightforward implementation as above would take time $O(n^4)$. Garey et al. show (besides correctness) that by updating the times obtained by Backscheduling, joining overlapping forbidden regions, and making "forbidden" queries $O(1)$ time can be brought down to $O(n^2)$, and by using even better datastructures to $O(n\log n)$.


As I understand your question, your problem statement is:

  Given a set of ordered lists $\{L_1,L_2,\ldots,L_n\}$, learn the relation $r(a,b)$ for the partial order of each $L_1,L_2,\ldots,L_n$. Then use this learned relation to sort a new list.

So, in your example, the relation would be the lexicographical order. But your data set has some noise because the last list breaks the order in several places.

This seems to be a case of preferrence learning, and more specifically, object ranking.


Finding the lowest-weight negative cycle in a weighted digraph

Finding the least weight simple negative cycle is NP-hard even in the undirected case, as shown in this answer by reduction from Hamiltonicity. The reduction is very simple: make each edge have weight $-1$. There is a cycle of least weight at most $-n$ iff the graph is Hamiltonian.


Algorithmic problem of regular, context-free, and recursively enumerable languages

Both questions are undecidable.
Notice that the empty language is both regular and context-free.
Thus we can state that the problem of determining if $L_1 \cap L_2$ is context-free is at least as hard as determining if $L_1$ is context-free (and similarly determining if $L_1 \cap L_3$ is a regular language is at least as hard as determining if $L_1$ is a regular language). By Rice's Theorem any non-trivial property about a Turing-Machine is undecidable and thus your two questions are undecidable.
For a detailed proof/answer to your second question look at this post.
IT shows how you would apply Rice's Theorem in your cases.


I have not heard of any computational problem that cannot be solved by an Universal Turing Machine, and UTM itself fits on a single page:

https://rosettacode.org/wiki/Universal_Turing_machine

In accordance with your plan, it totally disregards human and hardware limitations, by using up both time and space extravagantly. If you disregard some limitations, the quality of an answer quickly degrades to the point of being irrelevant.

IMHO the art of computing is in seeing the equivalence classes and transforming some initial solution to re-balance resources for the specific prioritized objectives. In the absence of priorities and limitations, there is no art. This quest is provably inexhaustible and will never be possible to automate.

BTW, I am also working on a new computing platform (a CPU and a programming language) that is an order-of-magnitude better in one aspect (speed, low transistor count, low energy consumption, easy comprehensibility, short programs), while matching existing solutions on the other aspects. It is a synergy based on closer matching the actual problem and balancing the workload among transistors, microcode and high-level-code. I see a big unused slack in the current technologies, and the gains can be spent on the mentioned objectives.


Is the set of all valid C programs countable?

Infinite. Countable. Given a length $l$, and a finite number of characters, $c$, we know that each length has only finitely many possible valid c codes $c^L$. We can easily make a bijection from the natural numbers to the lengths, and at each length we add only finite number of other valid code, thus countable.


If space is greater than time, as it must surf the space (in the related Turing machine), it will be contradicted by time is less than space. Hence, we can find that all problems which are in $DTIME(f(n))$ are in $DSPACE(f(n))$. and the proof is completed.

On the other hand, the size of input is important. Hence, if we set $m = n^2$ we reach to the first relation. Hence, it is true again.


Applying information theory to processor clocks

Technically, clock skew does this already. Specifically the technique known as "useful skew". When a data signal is going to travel from one storage element to another (both updating based on the clock), the clock that the source and destination elements receive are not quite the same.

In "useful skew", the clock at the destination is delayed such that the data has more time to travel before the capture clock edge arrives at the destination storage element. This allowed more distance of travel as well as more computation.


Compare Hidden Markov Model's sample with ground truth data

Compute the likelihood of the observed data, for each model.  Then higher the likelihood, the better the fit.  The likelihood is just the probability that the model assigns to the observed data, which for HMMs can be computed using dynamic programming.
Be prepared that the more complex the model, the higher the likelihood will be, but that doesn't necessarily mean the model is "better" -- you run the risk of overfitting.  Larger HMMs may fit the training data better, but if the HMM is too large, it might perform poorly on new data because of overfitting.


If you count a CPU (as you imply in your text) as an unbounded memory and the processor, then no you can't model it as a PDA. A push down automaton (with one stack) can only recognize context-free languages, for example $\{a^n b^n c^n | n \geq 0\}$ cannot be recognized by a PDA, but presumably could be recognized by your blue computer with massive graphics card and DVD.

Typically, we think of your blue computer with massive graphics cards and DVD as a Turing Machine, because that often proves to be the best way to model it.

On the other hand, if you model your CPU without unbounded memory, then PDA is still not the right model. If your CPU has no memory or only a small (i.e. bounded) amount of on-chip memory, then it can only be in a finite number of states, and is better modeled as a DFA.


Are parser combinators equivalent to scannerless parsing?

It may be that both are commonly used together (that's the kind of estimation which is very sensible to perspective effects), but they are in principle different.

Scannerless means that the parser is directly fed the stream of characters instead of getting tokens recognized by a scanner with white spaces and comments removed.  You can use whatever kind of parsers you want to parse the characters.

Parser combinators is a way to build a parser for a complex language from parsers for simpler one.  The stream of symbols on which the bottom parsers are working may be a stream of tokens recognized by a scanner or a stream of characters.

That said, it is possible to hold the point of view that a scanner is a parser combinators (combining regular expressions) and thus that parser combinators are always scannerless parsers (if you are using different tools for both, that seems a quite abstract point of view). But even then, it is possible to have scannerless parsers which are using other parsing techniques.


How can I find spans where the distance between two poly-lines is more or less than some threshold?

Given a point $P$ and a polyline $L$, you can compute the distance from $P$ to $L$ (i.e., the distance from $P$ to the nearest point on $L$).

Now take the union of all of the following points:

The endpoints of the line segments in the blue polyline
For each endpoint of each line segment in the red polyline, the closest point on the blue polyline
All intersection points where the blue polyline intersects the red polyline

This set can be computed efficiently, and its size is linear in the size of the input.  Let $P_1,P_2,\dots,P_n$ denote these points, in the order they appear on the blue polyline.  Let $Q_i$ be the point on the red polyline that is closest to $P_i$.

Now consider any pair of consecutive points $P_i,P_{i+1}$.  As we move along the blue polyline from $P_i$ to $P_{i+1}$, the distance to the red polyline will either increase monotonically or decrease monotonically.  Thus, if it crosses the threshold (e.g., starts below the threshold and increases to something larger than the threshold), you can use binary search to find the point where it crosses the threshold.

In fact, we can say more.  Consider a point $P = \alpha P_1 + (1-\alpha) P_{i+1}$, as $\alpha$ increases from $0$ to $1$,  and let $Q$ be the nearest point on the red polyline to $P$.  As $\alpha$ increases from $0$ to $1$, $P$ be moving along a straight-line path, i.e., along a single line segment of the blue polyline.  Similarly, $Q$ will also e moving along a straight-line path, i.e., along a single line segment of the red polyline.  Consequently, there's a simple formula for the distance between the two as a function of $\alpha$, and we can solve for the $\alpha$ that makes this distance equal to the threshold.  Thus, this will let us precisely identify the point where the minimum distance between the two polylines is exactly equal to the threshold.

Now doing a linear scan over all consecutive pairs $P_i,P_{i+1}$ will enable you to find all places where the minimum distance is higher than some threshold, exactly.


Kolmogorov Complexity: Why would you need more bytes than the string itself?

The exact value of the Kolmogorov complexity depends on the language chosen to represent strings. This language has to be Turing complete, so representing all strings as themselves isn't an option.

By the pigeonhole principle, if there is at least one string of length at most $n$ whose representation is shorter than itself, then there is also at least one string of length at most $n$ whose representation is longer than itself. (The representation is a compression algorithm.)

You can have a description language where each string has a representation that's at most one bit longer than itself: start each representation with a bit that indicates either “print literally” or “interpret”. Not all description languages are that simple though.

A more formal statement is given further down in the Wikipedia article, in the invariance theorem section. There are optimal description languages, such that for any given language, there is a constant $C$ such that the description of any string in the optimal language (no matter what its length is) is at most $C$ bits longer than in that other language. Intuitively, write an interpreter for the other language in the optimal language.


tries all possible combinations and because of this, is in fact the same as a brute force approach

You don't share the specific algorithm you have in mind, but I think you are wrong. Trying all splittings at every level of the recursion is not the same as trying all solutions.

  since subset sum can be solved by dynamic programming, I was not completely convinced that it is NP-Complete

Again, you don't share the specific algorithm, but it probably has pseudo-polynomial running time. So no, there is no contradiction; "dynamic programming" does not equal "polynomial time" let alone "fast".


There are several possible ways to solve this problem. One way is to assume some measurement model (usually Gaussian noise) and then find the maximum likelihood solution.

That is, we start with some distribution of the measured distance given the actual distance  and the noise level, for example if the actual distance is $d$ and the noise level is $\sigma$, then perhaps the measured distance is distributed $N(d,\sigma)$.

Given a sequence of measurements, for each potential list of positions (say with $a=0$ to break the symmetry), we can calculate the likelihood that we would get the actual measurements. In your case, we would get
$$ L(a,b,c,d,e) = \frac{1}{\sqrt{2\pi} 0.4} e^{-(5-(b-a))^2/(2\cdot 0.4)} \cdot \frac{1}{\sqrt{2\pi} 0.7} e^{-(9-(c-a))^2/(2\cdot 0.7)} \cdots. $$
The idea is to find the setting of $a,b,c,d,e$ that maximizes $L(a,b,c,d,e)$. To that end, we can calculate
$$ -\log L(a,b,c,d,e) = C + \frac{(5-(b-a))^2}{2\cdot 0.4} + \frac{(9-(c-a))^2}{2\cdot 0.7} + \cdots.$$
We want to minimize the latter. We can substitute $a = 0$, and then differentiate with respect to each of the other variables, and equate to zero. For example, differentiating with respect to $b$, we obtain
$$ 0 = -\frac{\partial \log L}{\partial b} = \frac{b-5}{0.4} + \frac{b-c+6}{0.8} + \frac{b-d-10}{0.7} + \frac{b-e-2}{1.0}. $$
In this way, we get linear equations which we can solve for $b,c,d,e$. (This is the method of least squares.)

For other models of noise, we might have to use numerical optimization instead. You can find more examples in any machine learning textbook.


Finding suitable NP-complete problem to reduce to my problem

This problem is essentially just a rephrasing of the classic NP-complete problem PARTITION. If you can partition a set $S$ of natural numbers into two partitions $S_1$ and $S_2$ with equal sum, then $\sum_{s \in S_1} s + \sum_{s \in S_2} -s = 0$ and vice versa.


Detecting approximate sum collisions in two lists.

I believe there is no known algorithm with running time faster than $O(N^2)$, even if you work with integers and ask for a tuple such that $A_a + A_b - (B_c + B_d) = 0$ (i.e., is exactly zero).

There are algorithms with running time $O(N^2)$ and space $O(N)$.  Basically, they iterate through the sum sets $S_A$ and $S_B$ in order, without ever storing the entire sets in memory, by using a priority queue.

There are also algorithms that with running time $O(N^{4/3})$, if the numbers are chosen uniformly at random over some range and if you can choose $N$ appropriately (i.e., if the relationship between $N$ and the size of that range can be chosen appropriately) and if you only care about finding one such 4-tuple (even though many might exist).  I suspect this probably isn't of use to you.


How is this reduction of 3-SAT to Half-SAT not valid?

As mentioned in the comments, this reduction is incorrect because it is necessary to have equivalence. While we may have 3-SAT => Half-SAT we do not have !3-SAT => !Half-SAT or Half-SAT => 3-SAT (the contrapositive). A proper reduction would need to do something like so:
Add m + 1 clauses (y or y or y)
Add a contradictory clause (y or not y)
Now exactly half of the clauses are True iff there is a solution to 3-SAT.


Let $n_0 = n$ and $n_{i+1} = n_i - \log n_i$. Then $T(n)$ is one plust the minimal $t$ such that $n_t \leq 1$.
Clearly $n_{i+1} \geq n_i - \log n$, hence $n_t \geq n - t\log n$, implying that $T(n) \gtrsim n/\log n$.
In the other direction, as long as $n_i \geq \sqrt{n}$, the sequence decreases by at least $\tfrac{1}{2} \log n$, hence it takes at most $2n/\log n$ steps to get down from $n$ to $\sqrt{n}$. After at most $4\sqrt{n}\log n$ steps, we get down to $\sqrt[4]{n}$; and so on. If we carefully count the steps, we see that $T(n) = O(n/\log n)$. Hence $T(n) = \Theta(n/\log n)$.


Regular expression for words in a language where each letter appears at least once

A DFA for your language is:

The name of the states are self descriptive.

Following comments from D.W., here is a way to compute such an automaton. It is a bit tedious and error prone by hand, but easy to do by computer with the proper algorithms. These ideas are to be found in this reference question.

You define 3 languages on the alphabet $\Sigma^*=\{a,b,c\}$, $L_a$, $L_b$, and $L_c$, such that each contains all string that have at least one occurrence of the subscript symbol.

For example $L_a=\{w\mid |w|_a\geq 1\}$

The language you want is $L_a\cap L_b \cap L_c$.

The corresponding finite automata are much easier to define. Then you only have to apply twice the standard crossproduct construction to get the automaton for the intersection.

The advantage of using standard construction is that it spares you the need to prove your result correct (if done by a computer ... I would not trust a human being).

A regular expression is:

$$\begin{align}   (\;\;\;
    (aa^*b & +bb^*a)(a+b)^*c \\
   +(bb^*c & +cc^*b)(b+c)^*a \\
   +(cc^*a & +aa^*c)(c+a)^*b\;\;\;) \;\;  (a+b+c)^*
\end{align}$$

You can more or less read it from the DFA. Otherwise, just use the standard algorithms, and good luck.


Why does Radix sort require stable digit sorts?

Integers that are equal in some digit aren't always equal (e.g., 12 and 13).

Let's sort [13, 12] using a LSD-first radix sort (base 10). But we'll use an unstable sort for each digit.

First we sort by the 1's place, so the array becomes [12, 13].

Now we sort by the 10's places, but 12 and 13 have the same digit. Since the sort is unstable, the resulting array could be [12, 13] or [13, 12]. We don't know.

If the sort were stable we would be guaranteed to get a correctly sorted array.


Can input to a Turing machine be of infinite length?

There is no problem in running a Turing machine on a tape initialized with an infinite string, although this is not usually considered. We still need the machine to terminate in finite time, though. There are also notions of infinite-time computation, which may be appropriate here.


Recall that Turing Machines are often defined to output only a yes/no answer. Transducers are used to extend this to a general output, which is sometimes more appropriate for a certain task (e.g. defining mapping-reductions).

When we use transducers, we can also analyze their runtime, and in this case they compute functions, so we are interested in which functions can be computed using a transducer that runs in polynomial time.

In this context, running in polynomial time means that, as you state, the transducer is allowed to run for $p(|x|)$, where $p$ is a fixed polynomial, and $x$ is the input to the transducer. Finally, the transducer outputs the binary representation of the function that it computes.

Let's consider the first example: $f(x)=x^2$. A transducer that computes it takes as input a binary number, for example $11$ (3 in binary). It then needs to output $1001$. To actually compute this value, we can use the long-multiplication algorithm from preschool. What we need to notice is that this algorithm is indeed polynomial in $|x|$ - the length of the binary representation of $x$. It is not hard to verify that the algorithm runs in  quadratic time of this length.

So we have a polynomial-time transducer for $f(x)=x^2$, so it is in FP.

Now let's consider example 3: $f(x)=2^x$. Consider an input $x$. What is the size of the binary representation of $f(x)$? Well, it's $\log f(x)$. But
$$\log f(x)=\log 2^x=x$$
and $x$ is exponential in $|x|$ - indeed, the size of the representation of $x$ is $\log x$.

So we have that $\log(f(x))$ is exponential in $|x|$, or in other words, $|f(x)|$ is exponential in $|x|$, and in particular, $|f(x)|>|p(x)|$ for every polynomial $p$ and for large enough $x$ (because $2^n\in \omega(p(n))$ for every polynomial $p$).

So it is no possible to even write down $f(x)$ in polynomial time, let alone compute it. This is why $2^x\notin FP$.

Finally, the second example is just an emphasis on the relation between FP and P: Given $G,s$ in some representation (e.g. a "text file" encoded in binary) it is easy to compute the shortest path from $s$ to all the vertices using BFS, which runs in polynomial time. So essentially, once you run BFS on the graph and mark all the shortest paths, you get some binary string which represents it. You then output this binary string.

The important thing to take from the second example is the concept that if you are looking for a solution which is not a yes/no answer (e.g. shortest path, result of an arithmetic expression, etc.) and you can solve a related decision problem using TMs in polynomial time (e.g. "is there a path shorter than $k$?", "is the result of this expression smaller than $v$?"), then in many cases you can use the TM that solves the decision problems to actually obtain a transducer that runs in polynomial time, so the problem will be in FP.


How do you find set of keywords present in set of words in linear time or log time?

I'm interpreting your question as wanting to quickly ensure that every word from the keys list is included in the sentence list.

Assuming you're using a sane version of python, the running time for the initial construction of the counter object is linear in the length of the sentence's description. At least as long as no word appears so many times that the integer stored in the counter exceeds INT_MAX.

So the overall running time, for sane inputs, is linear in the input, which is the best you can possibly expect (since Python has to read the entire input anyway, which takes linear time already).

That said, there's no compelling reason to use a counter here. You could just as easily have used a Set object and achieved the same running time without the assumption on word counts not exceeding a certain value. It might also be easier to read.

For example

def cover_test(keys, sentence):
    sentence_word_set = set(sentence)
    for key in keys:
        if key not in sentence_word_set:
            return False
    return True

or even

def cover_test(keys, sentence):
    sentence_word_set = set(sentence)
    return all(i in sentence_word_set for i in keys)

Set construction is promised to be expected linear-time in the size of sentence, with expected constant-time lookups. And the for loop goes through each key once (totalling to something linear in the size of keys) so the running time is expected linear in the whole input. Which again is the best you can do.


What will happen to NP-Hard problems if P=NP

No. A problem is Np-Hard if all NP problems are reducible to an instance of that problem in polynomial time. Some NP-Hard problems cannot be solved in nondeterministic polynomial time, and are not in NP. Then these problems will not be polynomial time solvable regardless of whether or not P=NP.


Find the element $x$ that maximizes $f(x)$ for $x \in \sum A_i$

Unless you have some further structure to the problem (i.e., the function) you can't do better than  checking all.


The graphs you want are printed in the book “CMOS VLSI Design” Weste/Harris (2005), on page 5 of the freely available introduction.


Construct an undirected graph with $k$ vertices, where each vertex represents a set $A_i$, and you draw an edge between two vertices if their sets share an element.  Now you have an instance of subgraph isomorphism: you have a graph $H$ on five vertices (of the shape shown in your question), and you want to enumerate all subgraphs of $G$ that are isomorphic to $G$.  You do have an additional distinctness condition, but if you can enumerate all isomorphic subgraphs, you can check whether they satisfy that additional condition in post-processing (and in most cases I expect they typically will).
This subgraph isomorphism problem looks challenging.  A naive approach has $O(k^5)$ running time: enumerate all 5-tuples of vertices.  You can improve this slightly, to $O(k^2m^{1.5})$ time, where $m$ counts the number of edges in the graph (note that $m\le k^2$, and might be much smaller, so this might be better).  First, enumerate all 3-cliques (triangles).  This can be done in $O(m^{1.5})$ time (see http://complexnetworks.fr/wp-content/uploads/2011/01/triangles.pdf and https://users.soe.ucsc.edu/~sesh/pubs/conf-triangle-enum.pdf).  These will be your candidates for $A_1,A_2,A_3$.  Next, enumerate all possible candidates for $A_4,A_5$ and check to see if they meet the requirements.  This might not be much faster, but maybe it would help a little bit.


Why AKS primality test is called polynomial?

The time complexity of the AKS primality test is $O(n^6)$, where $n$ is the length of the input. The length of an integer $N$ is roughly $\log N$, so the time complexity of the AKS primality test applied to the integer $N$ is $O(\log^6 N)$.

Finally, I'm not sure what you mean by a problem being strictly contained in P. Every problem in P is contained in some smaller class $\mathsf{TIME}(O(n^k))$ for some $k$.


Why is this $f(n) \leq 6n^3 + n^2 \log n \in O(n^3)$ for all $n \geq 1$?

First of all, it is not a "question equation" but the definition of $f$.

The task at hand is to show that $f(n) \in O(n^3)$. By the definition of $O(n^3)$ this means that we need to find $n_0$ and $C$ such that $f(n) \leq C n^3$ for all $n \geq n_0$. There may be many $n_0$ and $C$ that work, we just need to find one.

I pull out of my hat $n_0$ and $C$ that work (because I am a professional mathematician), namely $n_0 = 1$ and $C = 7$. Now we have to verify: for all $n \geq 1$ we have $f(n) \leq 7
n^3$.

Because $\log n \leq n$ whenever $n \geq 1$ (draw a graph of $y = \log x$ and $y = x$, and stare at it for a while) we may replace $\log n$ in the definition of $f$ with $n$, and we will get something bigger. So we have for all $n \geq 1$:
$$f(n) = 6 n^3 + n^2 \log n \leq 6 n^3 + n^2 \cdot n = 6 n^3 + n^3 = 7 n^3$$
We have established that $f(n) \leq 7 n^3$ for all $n \geq 1$, as required. We get an A on the midterm.

The question remains how I pulled out of my hat $n_0 = 1$ and $C = 7$, since this is what you will have to do on your mid-term. You start with $f(n)$ and "massage" it into something that is larger and has the form $C n^3$. On the way you observe that your massaging only works for $n$ large enough, and that gives you $n_0$.

Let us have another example: show that $g(n) = 23 n^2 + 17 + \log n$ is in $O(n^2)$. The massaging process goes as follows: turn every term which grows more slowly than $n^2$ into something of the form $C n^2$, and think about which $C$ to use and for which $n$ it is going to work. We have three terms to worry about, and notice how each has several possible ways of massaging:

the term $23 n^2$ is already in the correct form.
the term $17$, we give three possibilities just for fun:

$17 \leq 17 n^2$ for $n \geq 1$
$17 \leq 17 n^2$ for $n \geq 100$
$17 \leq n^2$ for $n \geq 5$

the term $\log n$:

$\log n \leq 42 n^2$ for all $n \geq 3$

I have purposely chosen weird and suboptmal values for $C$ and $n_0$ for each of the terms to show you that there is a lot of choice. For example, it would have been more "optimal" to say that $\log n \leq n^2$ for $n \geq 1$. For the term $17$ I gave three possible massages, let us work with the second one. We compose our observations together by replacing each term with its upper bound:
$$g(n) = 23n^2 + 17 + \log n \leq 23 n^2 + 17 n^2 + 42 n^2 \leq 1000 n^2.$$
I was too lazy to compute $23 + 17 + 42$ so I just approximated it with something larger, namely $1000$. Thus our $C = 1000$. We still have to figure out $n_0$. As far as the term $23 n^2$ is concerned any $n_0$ is ok. The term 17 wants $n_0 = 100$ and the term $\log n$ wants $n_0 = 3$. So we may take any $n_0$ that is larger than or equal 100 and 3, for example let us take $n_0 = 4127$.

We have now successfull pulled $C$ and $n_0$ from a hat. It is time to write the official solution so that we appear to be very smart, and to confuse students who start studying only two days before the midterm:

  The function $g(n) = 23n^2 + 17 + \log n$ is in $O(n^2)$ because for every $n \geq 4127$ we obviously have $g(n) \leq 23 n^2 + 17 n^2 + 42 n^2 \leq 1000 n^2$. We used here the easy observations that $17 \leq 17 n^2$ and $\log n \leq 42 n^2$ for every $n \geq 4127$.


Shortest Path problem(Single Source&Destination)

Your goals are not achievable.

You want the running time to be $O(K)$, where $K$ is the number of layers (or the distance from the source to the destination, I'm not sure which).  However, this running time is not achievable.  Suppose we have only a handful of layers, but millions of vertices in each layer: say, $K$ layers, but $N/K$ vertices per layer, where $K$ is small and $N$ is large).  Then there is no way to get a running time of $O(K)$, because any solution will have to look at every vertex in each of those layers.  Therefore, the best you can hope for is a worst-case running time of $O(N)$; $O(K)$ isn't achievable.

So, there is no algorithm that will meet your constraints.

That's the bad news.  The good news is that there is an algorithm that is efficient and has a running time that is asymptotically optimal.  This is the standard algorithm for computing shortest paths in a DAG: you topologically sort the DAG, then visit the vertices in topologically sorted order, calling "Relax" on each edge.  Any good algorithms textbook is likely to describe this algorithm.

The running time of this algorithm is linear, i.e., $O(V+E)$.  One can also prove that this is the best worst-case running time one can hope for: it's not possible to do any better, in terms of asymptotic worst-case running time.  So, from a theoretical perspective, the standard algorithm is excellent.

Now this doesn't rule out the possibility that clever implementation can improve the constant factors.  Indeed, it is likely that careful consideration of things like the structure of your graphs and the memory hierarchy might yield speedups that are measurable in practice.  But you shouldn't expect an improvement in the asymptotic running time.


adder in logisim using only 2-input-NAND gates

If I understand your question right, you want to build an incrementor.

First you need to build a halfadder. If you do not can or want to design it, you can ask logisim to do it.

choose project/analyse circuit. add two inputs (a,b) and two outputs (o,c).

then fill in the logic table for the half adder.

a b | o c
...............
0 0 | 0 0
0 1 | 1 0
1 0 | 1 0
1 1 | 0 1

then push build circuit and check both options (2 input gates only and nand only)

logisim wil build the circuit:

then you can connect 8 halfadders to build a 8 bits incrementor.


Is this a well founded inductive type? Can I express this in Coq?

You have misunderstood why A stands there in the definition of list.

Let us first look at how we might define lists of booleans:

Inductive ListBool : Set :=
  | nilBool : ListBool
  | consBool : bool -> ListBool -> ListBool.

And here is how we might define lists of natural numbers:

Inductive ListNat : Set :=
  | nilNat : ListNat
  | consNat : nat -> ListNat -> ListNat.

As you can see the nilBool and nilNat are constants that do not depend on any parameters. It is boring to define lists of booleans, lists of natural numbers, lists of lists of booleans, etc. Coq allows a parametrized definition of lists in which the List type itself takes a parameter A as input, to give lists of elements of type A. This is defined as you wrote:

Inductive List (A : Set) : Set :=
  | nil : List A
  | cons : A -> List A -> List A.

In the nil clause we have List A. Here A is the argument to List, it is not an argument to nil. If we wrote just List then Coq would ask "list of what"? For a similar reason the cons constructor has two occurences of List A.

Let me put it another way. The type of ListNat is Set. The type of List is Set -> Set. So we have to apply List to a set before we get a list.


What is the difference between centralised, decentralised, distributed, fully-distributed?

You need to differentiate between centralization/decentralization on the one hand and distributed/non-distributed on the other hand.

Centralization
Centralization tells you where the processing gets done.
Fully centralized systems do all their processing in one place.

Distribution
Distribution has nothing to do with processing. It just relates to systems that communicate via messages.
A non-distributed system is a stand-alone PC with no clients, or a server with dumb clients.

A fully distributed system does not have a single source of truth, however that does not mean that all nodes have to be equal. You can have 'supernodes' mixed with lesser nodes and still be fully distributed.

Distribution = network
The current incarnation of distributed systems are networked systems, but of course it's perfectly possible to pass messages using a serial cable, sneakernet or carrier pigeon. Is that a distributed system?
Yes if both systems do actual work, No if one system is simply a recipient of data (printer/terminal etc).

Peripherals do not count
The passing of screen and keyboard data between the terminal and the server is not deemed substantial enough to qualify as message passing.

Caveat
The definition of distributed computing is best narrowed down in the context of a specific protocol or algorithm (e.g. bittorrent or mapreduce)
Outside that context it becomes exceedingly vague to the point of being meaningless.

The mysterious diagram
The diagram in the question seems to hint at some sort of hierarchy and thus centralisation.
Obviously the systems A,B,C and D cannot be peripherals (because they are not leaf nodes) and thus some message passing (aka network activity) ought to take place.
What the nature of the leaf nodes (A123 et al) is is unclear, but these leafs do seem subservient to A,B and C proper.


You are right about $1$.
For $2$, $L_1$ reduces to $L_2$, means $L_1$ as least as hard as $L_2$. But not vice versa as adding numbers is in $P$ and tower of Hanoi is in $EXP$, so the later is hard but addition does not reduce to tower of Hanoi. Just knowing the hardness does not say much. Hence the statement is false. If it were not the case, then statement $2$ would have been true.
For $L_1, L_2\in NP\;Complete$, as $L_1,L_2\in NP$, $L_1$ reduces to $L_2$ and $L_2$ reduces to $L_1$, according to NP-Complete definition. So, their hardness is same. So, they both belong to the same class. Hence, $L_1\in P\Rightarrow L_2\in P$ and vice versa. So, $3$ is correct.


Priority queue with unique elements and sublinear time merge?

Keep your elements in linked lists of buckets. Buckets will have size $O(\lg^2 n)$ when stored in a list with $n$ total elements. Buckets are stored as balanced search trees with $O(\lg n)$ insert (and, since each bucket has size $O(\lg^2 n)$, this is actually $O(\lg \lg n)$), $O(1)$ extractMin, $O(n+m)$ merge, $O(\lg n)$ split, and no duplicates. The liked list should be sorted by the size of the buckets, though not their key values.

To maintain the bucket invariant, we need to occasionally combine or split buckets. To pay for this, we assign each priority queue a potential. This lets us use the physicist's amortization.

Each bucket will be assigned a potential of $0$ if it has size within $1$ of $\lg^2 n$ and a potential of $c \lg^2 n$ if it is size $\lg^2 n/d$ or $d \lg^2 n$ (for constants $c$ and $d$ to be determined later), varying bitonicly and linearly in the size of the bucket.

The tricky method is merge. Assume we are merging two lists of size $n$ and $an$, for $a>1$. We split into two cases depending on whether $a < \lg^2 n$.

If $a < \lg^2 n$, then we join the lists by merging them like in merge sort, so that the buckets stay sorted by size. Since the buckets have size $O(\lg^2 n)$, the linked lists have length $O(n/\lg^2 n)$ and $O(an/\lg^2 an)$, so merging them takes time $O(an/\lg^2 an)$ which is $o(an)$, and so is sublinear.

It also may increase the potential. Each bucket gets at most $O(\lg^2 (1+a)n - \lg^2 n) = O(\lg^2 (1+a) + \lg n \lg (1+a))$ closer to criticality. This is $O(\lg n \lg \lg n)$, and there are $O(an/\lg^2 an)$ buckets, so the increase in potential is at most $O(an \lg n \lg \lg n/\lg^2 an)$, which is $o(an)$ and thus sublinear.

Finally, we traverse the head and tail of the list, splitting and joining supercritical buckets until no supercritical buckets are left. This is "free", paid for by the potential we release. (To place them properly, we need to maintain a finger to the point in the list where buckets are exactly the right size. This is $O(1)$ extra work on each operation.)

If $a > \lg^2 n$, we destroy the smaller priority queue and insert its items one-by-one into the larger queue. As long as insert is $o(\lg^2 n)$ amortized, this is sublinear.

Insert adds an element to the smallest bucket. This increases its potential by at most $O(1)$ and increases the potential of the rest of the buckets by at most $O(\lg^2 (n+1) - \lg^2 n) = O(\lg n/n)$. Since there are $O(n/\lg^2 n)$ buckets, the total increase in potential is $O(1/\lg n)$. If the smallest bucket is large, some splitting may be required, but this is amortized free (paid for by the potential we get back). The total amortized cost of insert is thus the cost to insert it into a bucket, which is $O(\lg \lg n)$.

extractMin traverses the bucket list and identifies the buckets with minimum key. It removes the minimum key from each of these buckets, rearranging the bucket list as necessary to maintain order. The total structure size may change by $O(n/\lg^2 n)$ if we remove a key from each bucket. This induces a potential change of at most $O(\lg n)$ in each bucket, for a total potential change of $O(n/\lg n)$. The traversal and removal take time linear in the number of buckets, which is $o(n)$.

Note that these operations, including an extractMin that extracts every copy of the minimum, are sublinear in the number of elements, not the number of unique elements. The number of unique elements in a priority queue of size $n$ may be as low as $\Theta(\lg^2 n)$.


Recognizer to check if the language of a Turing machine contains a finite subset

Yes, it is sufficient.

$\langle M \rangle \in L \Longleftrightarrow B\subseteq L(M) \Longleftrightarrow M\text{ accepts all strings in }B \Longleftrightarrow M\text{ accepts }123$.