What is the definition of P, NP, NP-complete and NP-hard?

I think the Wikipedia articles
$\mathsf{P}$, $\mathsf{NP}$, and $\mathsf{P}$ vs. $\mathsf{NP}$ are quite good.
Still here is what I would say: Part I, Part II

[I will use remarks inside brackets to discuss some technical details which
you can skip if you want.]

Part I

Decision Problems

There are various kinds of computational problems.
However in an introduction to computational complexity theory course
it is easier to focus on decision problem,
i.e. problems where the answer is either YES or NO.
There are other kinds of computational problems but
most of the time questions about them can be reduced to
similar questions about decision problems.
Moreover decision problems are very simple.
Therefore in an introduction to computational complexity theory course
we focus our attention to the study of decision problems.

We can identify a decision problem with the subset of inputs that
have answer YES.
This simplifies notation and allows us to write
$x\in Q$ in place of $Q(x)=YES$ and
$x \notin Q$ in place of $Q(x)=NO$.

Another perspective is that
we are talking about membership queries in a set.
Here is an example:

Decision Problem:

  Input: A natural number $x$,
  Question: Is $x$ an even number?

Membership Problem:

  Input: A natural number $x$,
  Question: Is $x$ in $Even = \{0,2,4,6,\cdots\}$?

We refer to the YES answer on an input as accepting the input and
to the NO answer on an input as rejecting the input.

We will look at algorithms for decision problems and
discuss how efficient those algorithms are in their usage of computable resources.
I will rely on your intuition from programming in a language like C
in place of formally defining what we mean by an algorithm and computational resources.

[Remarks:
1. If we wanted to do everything formally and precisely
we would need to fix a model of computation like the standard Turing machine model
to precisely define what we mean by an algorithm and
its usage of computational resources.
2. If we want to talk about computation over objects that
the model cannot directly handle,
we would need to encode them as objects that the machine model can handle,
e.g. if we are using Turing machines
we need to encode objects like natural numbers and graphs
as binary strings.]

$\mathsf{P}$ = Problems with Efficient Algorithms for Finding Solutions

Assume that efficient algorithms means algorithms that
use at most polynomial amount of computational resources.
The main resource we care about is
the worst-case running time of algorithms with respect to the input size,
i.e. the number of basic steps an algorithm takes on an input of size $n$.
The size of an input $x$ is $n$ if it takes $n$-bits of computer memory to store $x$,
in which case we write $|x| = n$.
So by efficient algorithms we mean algorithms that
have polynomial worst-case running time.

The assumption that polynomial-time algorithms capture
the intuitive notion of efficient algorithms is known as Cobham's thesis.
I will not discuss at this point
whether $\mathsf{P}$ is the right model for efficiently solvable problems and
whether $\mathsf{P}$ does or does not capture
what can be computed efficiently in practice and related issues.
For now there are good reasons to make this assumption
so for our purpose we assume this is the case.
If you do not accept Cobham's thesis
it does not make what I write below incorrect,
the only thing we will lose is
the intuition about efficient computation in practice.
I think it is a helpful assumption for someone
who is starting to learn about complexity theory.

  $\mathsf{P}$ is the class of decision problems that can be solved efficiently,
  i.e. decision problems which have polynomial-time algorithms.

More formally, we say a decision problem $Q$ is in $\mathsf{P}$ iff

  there is an efficient algorithm $A$ such that
  for all inputs $x$,

  if $Q(x)=YES$ then $A(x)=YES$,
  if $Q(x)=NO$ then $A(x)=NO$.

I can simply write $A(x)=Q(x)$ but
I write it this way so we can compare it to the definition of $\mathsf{NP}$.

$\mathsf{NP}$ = Problems with Efficient Algorithms for Verifying Proofs/Certificates/Witnesses

Sometimes we do not know any efficient way of finding the answer to a decision problem,
however if someone tells us the answer and gives us a proof
we can efficiently verify that the answer is correct
by checking the proof to see if it is a valid proof.
This is the idea behind the complexity class $\mathsf{NP}$.

If the proof is too long it is not really useful,
it can take too long to just read the proof
let alone check if it is valid.
We want the time required for verification to be reasonable
in the size of the original input,
not the size of the given proof!
This means what we really want is not arbitrary long proofs but short proofs.
Note that if the verifier's running time is polynomial
in the size of the original input
then it can only read a polynomial part of the proof.
So by short we mean of polynomial size.

Form this point on whenever I use the word "proof" I mean "short proof".

Here is an example of a problem which
we do not know how to solve efficiently but
we can efficiently verify proofs:

  Partition
  Input: a finite set of natural numbers $S$,
  Question: is it possible to partition $S$ into two sets $A$ and $B$
  ($A \cup B = S$ and $A \cap B = \emptyset$)
  such that the sum of the numbers in $A$ is equal to the sum of number in $B$ ($\sum_{x\in A}x=\sum_{x\in B}x$)?

If I give you $S$ and
ask you if we can partition it into two sets such that
their sums are equal,
you do not know any efficient algorithm to solve it.
You will probably try all possible ways of
partitioning the numbers into two sets
until you find a partition where the sums are equal or
until you have tried all possible partitions and none has worked.
If any of them worked you would say YES, otherwise you would say NO.

But there are exponentially many possible partitions so
it will take a lot of time.
However if I give you two sets $A$ and $B$,
you can easily check if the sums are equal and
if $A$ and $B$ is a partition of $S$.
Note that we can compute sums efficiently.

Here the pair of $A$ and $B$ that I give you is a proof for a YES answer.
You can efficiently verify my claim by looking at my proof and
checking if it is a valid proof.
If the answer is YES then there is a valid proof, and
I can give it to you and you can verify it efficiently.
If the answer is NO then there is no valid proof.
So whatever I give you you can check and see it is not a valid proof.
I cannot trick you by an invalid proof that the answer is YES.
Recall that if the proof is too big
it will take a lot of time to verify it,
we do not want this to happen,
so we only care about efficient proofs,
i.e. proofs which have polynomial size.

Sometimes people use "certificate" or "witness" in place of "proof".

Note I am giving you enough information about the answer for a given input $x$
so that you can find and verify the answer efficiently.
For example, in our partition example
I do not tell you the answer,
I just give you a partition,
and you can check if it is valid or not.
Note that you have to verify the answer yourself,
you cannot trust me about what I say.
Moreover you can only check the correctness of my proof.
If my proof is valid it means the answer is YES.
But if my proof is invalid it does not mean the answer is NO.
You have seen that one proof was invalid,
not that there are no valid proofs.
We are talking about proofs for YES.
We are not talking about proofs for NO.

Let us look at an example:
$A=\{2,4\}$ and $B=\{1,5\}$ is a proof that
$S=\{1,2,4,5\}$ can be partitioned into two sets with equal sums.
We just need to sum up the numbers in $A$ and the numbers in $B$ and
see if the results are equal, and check if $A$, $B$ is partition of $S$.

If I gave you $A=\{2,5\}$ and $B=\{1,4\}$,
you will check and see that my proof is invalid.
It does not mean the answer is NO,
it just means that this particular proof was invalid.
Your task here is not to find the answer,
but only to check if the proof you are given is valid.

It is like a student solving a question in an exam and
a professor checking if the answer is correct. :)
(unfortunately often students do not give enough information
to verify the correctness of their answer and
the professors have to guess the rest of their partial answer and
decide how much mark they should give to the students for their partial answers,
indeed a quite difficult task).

The amazing thing is that
the same situation applies to many other natural problems that we want to solve:
we can efficiently verify if a given short proof is valid,
but we do not know any efficient way of finding the answer.
This is the motivation why
the complexity class $\mathsf{NP}$ is extremely interesting
(though this was not the original motivation for defining it).
Whatever you do
(not just in CS, but also in
math, biology, physics, chemistry, economics, management, sociology, business,
 ...)
you will face computational problems that fall in this class.
To get an idea of how many problems turn out to be in $\mathsf{NP}$ check out
a compendium of NP optimization problems.
Indeed you will have hard time finding natural problems
which are not in $\mathsf{NP}$.
It is simply amazing.

  $\mathsf{NP}$ is the class of problems which have efficient verifiers,
  i.e.
  there is a polynomial time algorithm that can verify
  if a given solution is correct.

More formally, we say a decision problem $Q$ is in $\mathsf{NP}$ iff

  there is an efficient algorithm $V$ called verifier such that
  for all inputs $x$,

  if $Q(x)=YES$ then there is a proof $y$ such that $V(x,y)=YES$,
  if $Q(x)=NO$ then for all proofs $y$, $V(x,y)=NO$.

We say a verifier is sound
if it does not accept any proof when the answer is NO.
In other words, a sound verifier cannot be tricked
to accept a proof if the answer is really NO.
No false positives.

Similarly, we say a verifier is complete
if it accepts at least one proof when the answer is YES.
In other words, a complete verifier can be convinced of the answer being YES.

The terminology comes from logic and proof systems.
We cannot use a sound proof system to prove any false statements.
We can use a complete proof system to prove all true statements.

The verifier $V$ gets two inputs,

$x$ : the original input for $Q$, and
$y$ : a suggested proof for $Q(x)=YES$.

Note that we want $V$ to be efficient in the size of $x$.
If $y$ is a big proof
the verifier will be able to read only a polynomial part of $y$.
That is why we require the proofs to be short.
If $y$ is short saying that $V$ is efficient in $x$
is the same as saying that $V$ is efficient in $x$ and $y$
(because the size of $y$ is bounded by a fixed polynomial in the size of $x$).

In summary, to show that a decision problem $Q$ is in $\mathsf{NP}$
we have to give an efficient verifier algorithm
which is sound and complete.

Historical Note:
historically this is not the original definition of $\mathsf{NP}$.
The original definition uses what is called non-deterministic Turing machines.
These machines do not correspond to any actual machine model and
are difficult to get used to
(at least when you are starting to learn about complexity theory).
I have read that many experts think that
they would have used the verifier definition as the main definition and
even would have named the class $\mathsf{VP}$
(for verifiable in polynomial-time) in place of $\mathsf{NP}$
if they go back to the dawn of the computational complexity theory.
The verifier definition is more natural,
easier to understand conceptually, and
easier to use to show problems are in $\mathsf{NP}$.

$\mathsf{P}\subseteq \mathsf{NP}$

Therefore we have
$\mathsf{P}$=efficient solvable and $\mathsf{NP}$=efficiently verifiable.
So $\mathsf{P}=\mathsf{NP}$ iff
the problems that can be efficiently verified are
the same as the problems that can be efficiently solved.

Note that any problem in $\mathsf{P}$ is also in $\mathsf{NP}$,
i.e. if you can solve the problem
you can also verify if a given proof is correct:
the verifier will just ignore the proof!

That is because we do not need it,
the verifier can compute the answer by itself,
it can decide if the answer is YES or NO without any help.
If the answer is NO we know there should be no proofs and
our verifier will just reject every suggested proof.
If the answer is YES, there should be a proof, and
in fact we will just accept anything as a proof.

[We could have made our verifier accept only some of them,
that is also fine,
as long as our verifier accept at least one proof
the verifier works correctly for the problem.]

Here is an example:

  Sum
  Input: a list of $n+1$ natural numbers $a_1,\cdots,a_n$, and $s$,
  Question: is $\Sigma_{i=1}^n a_i = s$?

The problem is in $\mathsf{P}$ because
we can sum up the numbers and then compare it with $s$,
we return YES if they are equal, and NO if they are not.

The problem is also in $\mathsf{NP}$.
Consider a verifier $V$ that gets a proof plus the input for Sum.
It acts the same way as the algorithm in $\mathsf{P}$ that we described above.
This is an efficient verifier for Sum.

Note that there are other efficient verifiers for Sum, and
some of them might use the proof given to them.
However the one we designed does not and that is also fine.
Since we gave an efficient verifier for Sum the problem is in $\mathsf{NP}$.
The same trick works for all other problems in $\mathsf{P}$ so
$\mathsf{P} \subseteq \mathsf{NP}$.

Brute-Force/Exhaustive-Search Algorithms for $\mathsf{NP}$ and $\mathsf{NP}\subseteq \mathsf{ExpTime}$

The best algorithms we know of for solving an arbitrary problem in $\mathsf{NP}$ are
brute-force/exhaustive-search algorithms.
Pick an efficient verifier for the problem
(it has an efficient verifier by our assumption that it is in $\mathsf{NP}$) and
check all possible proofs one by one.
If the verifier accepts one of them then the answer is YES.
Otherwise the answer is NO.

In our partition example,
we try all possible partitions and
check if the sums are equal in any of them.

Note that the brute-force algorithm runs in worst-case exponential time.
The size of the proofs is polynomial in the size of input.
If the size of the proofs is $m$ then there are $2^m$ possible proofs.
Checking each of them will take polynomial time by the verifier.
So in total the brute-force algorithm takes exponential time.

This shows that any $\mathsf{NP}$ problem
can be solved in exponential time, i.e.
$\mathsf{NP}\subseteq \mathsf{ExpTime}$.
(Moreover the brute-force algorithm will use
only a polynomial amount of space, i.e.
$\mathsf{NP}\subseteq \mathsf{PSpace}$
but that is a story for another day).

A problem in $\mathsf{NP}$ can have much faster algorithms,
for example any problem in $\mathsf{P}$ has a polynomial-time algorithm.
However for an arbitrary problem in $\mathsf{NP}$
we do not know algorithms that can do much better.
In other words, if you just tell me that
your problem is in $\mathsf{NP}$
(and nothing else about the problem)
then the fastest algorithm that
we know of for solving it takes exponential time.

However it does not mean that there are not any better algorithms,
we do not know that.
As far as we know it is still possible
(though thought to be very unlikely by almost all complexity theorists) that
$\mathsf{NP}=\mathsf{P}$ and
all $\mathsf{NP}$ problems can be solved in polynomial time.

Furthermore, some experts conjecture that
we cannot do much better, i.e.
there are problems in $\mathsf{NP}$ that
cannot be solved much more efficiently than brute-force search algorithms
which take exponential amount of time.
See the Exponential Time Hypothesis
for more information.
But this is not proven, it is only a conjecture.
It just shows how far we are from
finding polynomial time algorithms for arbitrary $\mathsf{NP}$ problems.

This association with exponential time confuses some people:
they think incorrectly that
$\mathsf{NP}$ problems require exponential-time to solve
(or even worse there are no algorithm for them at all).
Stating that a problem is in $\mathsf{NP}$
does not mean a problem is difficult to solve,
it just means that it is easy to verify,
it is an upper bound on the difficulty of solving the problem, and
many $\mathsf{NP}$ problems are easy to solve since $\mathsf{P}\subseteq\mathsf{NP}$.

Nevertheless, there are $\mathsf{NP}$ problems which seem to be
hard to solve.
I will return to this in when we discuss $\mathsf{NP}$-hardness.

Lower Bounds Seem Difficult to Prove

OK, so we now know that there are
many natural problems that are in $\mathsf{NP}$ and
we do not know any efficient way of solving them and
we suspect that they really require exponential time to solve.
Can we prove this?

Unfortunately the task of proving lower bounds is very difficult.
We cannot even prove that these problems require more than linear time!
Let alone requiring exponential time.

Proving linear-time lower bounds is rather easy:
the algorithm needs to read the input after all.
Proving super-linear lower bounds is a completely different story.
We can prove super-linear lower bounds
with more restrictions about the kind of algorithms we are considering,
e.g. sorting algorithms using comparison,
but we do not know lower-bounds without those restrictions.

To prove an upper bound for a problem
we just need to design a good enough algorithm.
It often needs knowledge, creative thinking, and
even ingenuity to come up with such an algorithm.

However the task is considerably simpler compared to proving a lower bound.
We have to show that there are no good algorithms.
Not that we do not know of any good enough algorithms right now, but
that there does not exist any good algorithms,
that no one will ever come up with a good algorithm.
Think about it for a minute if you have not before,
how can we show such an impossibility result?

This is another place where people get confused.
Here "impossibility" is a mathematical impossibility, i.e.
it is not a short coming on our part that
some genius can fix in future.
When we say impossible
we mean it is absolutely impossible,
as impossible as $1=0$.
No scientific advance can make it possible.
That is what we are doing when we are proving lower bounds.

To prove a lower bound, i.e.
to show that a problem requires some amount of time to solve,
means that we have to prove that any algorithm,
even very ingenuous ones that do not know yet,
cannot solve the problem faster.
There are many intelligent ideas that we know of
(greedy, matching, dynamic programming, linear programming, semidefinite programming, sum-of-squares programming, and
many other intelligent ideas) and
there are many many more that we do not know of yet.
Ruling out one algorithm or one particular idea of designing algorithms
is not sufficient,
we need to rule out all of them,
even those we do not know about yet,
even those may not ever know about!
And one can combine all of these in an algorithm,
so we need to rule out their combinations also.
There has been some progress towards showing that
some ideas cannot solve difficult $\mathsf{NP}$ problems,
e.g. greedy and its extensions cannot work,
and there are some work related to dynamic programming algorithms,
and there are some work on particular ways of using linear programming.
But these are not even close to ruling out the intelligent ideas that
we know of
(search for lower-bounds in restricted models of computation
if you are interested).

Barriers: Lower Bounds Are Difficult to Prove

On the other hand we have mathematical results called
barriers
that say that a lower-bound proof cannot be such and such,
and such and such almost covers all techniques that
we have used to prove lower bounds!
In fact many researchers gave up working on proving lower bounds after
Alexander Razbarov and Steven Rudich's
natural proofs barrier result.
It turns out that the existence of particular kind of lower-bound proofs
would imply the insecurity of cryptographic pseudorandom number generators and
many other cryptographic tools.

I say almost because
in recent years there has been some progress mainly by Ryan Williams
that has been able to intelligently circumvent the barrier results,
still the results so far are for very weak models of computation and
quite far from ruling out general polynomial-time algorithms.

But I am diverging.
The main point I wanted to make was that
proving lower bounds is difficult and
we do not have strong lower bounds for general algorithms
solving $\mathsf{NP}$ problems.

[On the other hand,
Ryan Williams' work shows that
there are close connections between proving lower bounds and proving upper bounds.
See his talk at ICM 2014 if you are interested.]

Reductions: Solving a Problem Using Another Problem as a Subroutine/Oracle/Black Box

The idea of a reduction is very simple:
to solve a problem, use an algorithm for another problem.

Here is simple example:
assume we want to compute the sum of a list of $n$ natural numbers and
we have an algorithm $Sum$ that returns the sum of two given numbers.
Can we use $Sum$ to add up the numbers in the list?
Of course!

Problem:

  Input: a list of $n$ natural numbers $x_1,\ldots,x_n$,
  Output: return $\sum_{i=1}^{n} x_i$.

Reduction Algorithm:

  $s = 0$
  for $i$ from $1$ to $n$
  2.1.  $s = Sum(s,x_i)$
  return $s$

Here we are using $Sum$ in our algorithm as a subroutine.
Note that we do not care about how $Sum$ works,
it acts like black box for us,
we do not care what is going on inside $Sum$.
We often refer to the subroutine $Sum$ as oracle.
It is like the oracle of Delphi in Greek mythology,
we ask questions and the oracle answers them and
we use the answers.

This is essentially what a reduction is:
assume that we have algorithm for a problem and
use it as an oracle to solve another problem.
Here efficient means efficient assuming that
the oracle answers in a unit of time, i.e.
we count each execution of the oracle a single step.

If the oracle returns a large answer
we need to read it and
that can take some time,
so we should count the time it takes us to read the answer that
oracle has given to us.
Similarly for writing/asking the question from the oracle.
But oracle works instantly, i.e.
as soon as we ask the question from the oracle
the oracle writes the answer for us in a single unit of time.
All the work that oracle does is counted a single step,
but this excludes the time it takes us to
write the question and read the answer.

Because we do not care how oracle works but only about the answers it returns
we can make a simplification and consider the oracle to be
the problem itself in place of an algorithm for it.
In other words,
we do not care if the oracle is not an algorithm,
we do not care how oracles comes up with its replies.

For example,
$Sum$ in the question above is the addition function itself
(not an algorithm for computing addition).

We can ask multiple questions from an oracle, and
the questions does not need to be predetermined:
we can ask a question and
based on the answer that oracle returns
we perform some computations by ourselves and then
ask another question based on the answer we got for the previous question.

Another way of looking at this is
thinking about it as an interactive computation.
Interactive computation in itself is large topic so
I will not get into it here, but
I think mentioning this perspective of reductions can be helpful.

An algorithm $A$ that uses a oracle/black box $O$ is usually denoted as $A^O$.

The reduction we discussed above is the most general form of a reduction and
is known as black-box reduction
(a.k.a. oracle reduction, Turing reduction).

More formally:

  We say that problem $Q$ is black-box reducible to problem $O$ and
  write $Q \leq_T O$ iff
  there is an algorithm $A$ such that for all inputs $x$,
  $Q(x) = A^O(x)$.

In other words if there is an algorithm $A$ which
uses the oracle $O$ as a subroutine and solves problem $Q$.

If our reduction algorithm $A$ runs in polynomial time
we call it a polynomial-time black-box reduction or
simply a Cook reduction
(in honor of
Stephen A. Cook) and
write $Q\leq^\mathsf{P}_T O$.
(The subscript $T$ stands for "Turing" in the honor of
Alan Turing).

However we may want to put some restrictions
on the way the reduction algorithm interacts with the oracle.
There are several restrictions that are studied but
the most useful restriction is the one called many-one reductions
(a.k.a. mapping reductions).

The idea here is that on a given input $x$,
we perform some polynomial-time computation and generate a $y$
that is an instance of the problem the oracle solves.
We then ask the oracle and return the answer it returns to us.
We are allowed to ask a single question from the oracle and
the oracle's answers is what will be returned.

More formally,

  We say that problem $Q$ is many-one reducible to problem $O$ and
  write $Q \leq_m O$ iff
  there is an algorithm $A$ such that for all inputs $x$,
  $Q(x) = O(A(x))$.

When the reduction algorithm is polynomial time we call it
polynomial-time many-one reduction or
simply Karp reduction (in honor of
Richard M. Karp) and
denote it by $Q \leq_m^\mathsf{P} O$.

The main reason for the interest in
this particular non-interactive reduction is that
it preserves $\mathsf{NP}$ problems:
if there is a polynomial-time many-one reduction from
a problem $A$ to an $\mathsf{NP}$ problem $B$,
then $A$ is also in $\mathsf{NP}$.

The simple notion of reduction is
one of the most fundamental notions in complexity theory
along with $\mathsf{P}$, $\mathsf{NP}$, and $\mathsf{NP}$-complete
(which we will discuss below).

The post has become too long and exceeds the limit of an answer (30000 characters).
I will continue the answer in Part II.


Why does Dijkstra's algorithm fail on a negative weighted graphs?

Dijkstra relies on one "simple" fact: if all weights are non-negative, adding an edge can never make a path shorter. That's why picking the shortest candidate edge (local optimality) always ends up being correct (global optimality).

If that is not the case, the "frontier" of candidate edges does not send the right signals; a cheap edge might lure you down a path with positive weights while an expensive one hides a path with negative weights.

For details, I recommend you check out a correctness proof and try to do it with negative weights; observe where it breaks.


Question about the CLRS Linear Programming chapter

Lemma 29.4 mentions an LP, because that is what they need it for, but it is really a statement in linear algebra about the system of equations $Ax=b$ and a linear form $\phi(x)=c\cdot x$, which in the LP is the objective function.

Lemma 29.4:
If the variables $x_i,i\in B$ are basic variables, i.e. if the corresponding columns of $A$ are a maximal set of linearly independent columns, then you can solve for those variables in terms of the rest of the variables $x_i,i\in N$ and the polynomials obtained are unique. In addition, if you write $\phi(x)=\psi(x_i,i\in N)$, the polynomial $\psi$ is also unique.

(Well, this version of the lemma includes the assertion that one can solve for those variables. This is due to Gaussian elimination.)
Now, for the uniqueness, as they did, you assume that you have two expressions of the basic variables in terms of the non-basic ones
$(x_i)_{i\in B}=(b_i)_{i\in B}+S(x_j)_{j\in N}$ for some matrix $S$ and $(x_i)_{i\in B}=(b_i')_{i\in B}+S'(x_j)_{j\in N}$.
So the polynomials $(b_i)_{i\in B}+S(x_j)_{j\in N}$ and $(b_i')_{i\in B}+S'(x_j)_{j\in N}$ are the same.
By definition $(b_i)_{i\in B}=(b_i')_{i\in B}$ and $S=S'$.
There is no real need to talk about values of the variables, since all the statements are purely algebraic, in the ring of polynomials in the variables $x_i$. So, there is no need for Lemma 29.3. Of course, the equations written have to be thought as equations between polynomials and not as equations between values of functions that are satisfied for all values of the variables. Ignore this paragraph if it causes confusion.


Produce all unordered unique combinations of N-sized subsets of an m·N-sized set

Knuth wrote a chapter on this, as part of the new volume 4 of his Art of Computer Programming.
The simplest algorithm uses the following recursion to generate all combinations of length $m$ of a set $x_1,\ldots,x_n$:

If $m = 0$ then output the empty set.
Otherwise, for each $m \leq i \leq n$, generate all combinations of length $m-1$ of $x_1,\ldots,x_{i-1}$, and add $x_i$ to all of them.


This can be proved by contradiction. You can use the fact that $PSPACE$ language remains $PSPACE$ if we remove polynomial length padding, where as $DTIME$ does not.


How to represent text for a program to add punctuation to a block of text?

I am making two assumptions here about things that, to me, are not quite clear from your question

When you say you removed punctuation, you actually meant whitespaces as well.
You tried neural networks, but not in a sequence-to-sequence fashion.

What's nice about your problem is that you can generate training data as much as you want just by taking a proper piece of text and removing all the punctuation.

This being said, I suggest you engage your problem as a machine translation task where you want to predict the proper text given the one without punctuation.

Today, the best way to do this is by sequence-to-sequence learning with deep neural network (just pick a few machine translation papers from last ACL (= Annual Meeting of the Association for Computational Linguistics) conference to learn more about that.

Concerning you actual question, how to represent the input, I'm not quite sure if you have to limit the size of your input beforehand or not. In any way, you could choose the size of your input window so that any block of text that you possibly want to put in would fit (if you know beforehand how long your paragraphs will be). Or it might be that you can just cut your input sequence at an arbitrary letter and your model will learn to make sense of it anyway (I am not an expert in neural machine translation).

So, as you can see, my answer is maybe not completely on the spot but I hope it is helpful to you anyway.


What is the largest possible minimal 3CNF formula as function of the number of variables?

Chungboom Lee, On the size of minimal unsatisfiable formulas shows that when $k=2$, the answer is $\Theta(n)$, and when $k \geq 3$, the answer is $\Theta(n^k)$. Here $k$ is width of the clauses.


Reduction to longest path from longest chain of tiles

But I wonder, I have shown that in general you have to solve the longest path problem to find the longest chain of such tiles

Not exactly, you have given a way of finding the longest chain of tiles (transform the tiles into a graph and solve longest path). There are many other possible approaches (you can try to transform it into a boolean formula and solve a SAT instance).... how do you know that none of them is easier? You could also use undecidable problems to solve your tile question (build a turing machine that halts iff the tiles have a solution of some size), it doesn't mean that your problem is undecidable.

Reductions work the other way around. I like to see an NP-hard problem as "a tool that may be used to solve any other NP problem". So  you need to show that your tile problem is one possible tool for solving longest path. That is, you are given a graph, and you need to describe a set of tiles with the good property (the tiles have a length-k solution iff the graph has a length-k path). This way, you know that your tile problem is a new possible tool for solving longest path, and, in turn, every other NP problem.

PS: there are also errors in the reduction you describe, beside the method problem discussed here: if the same integer appears in three different tiles (say, 4-2,4-7,4-9), then theses three nodes would form a valid path in the graph, but not a valid sequence of tiles. You'll find it easier to see a tile as an edge rather than a vertex


Constructing Turing Machine for division with 8

A number (in binary) is divisible by 8 if it ends at least by 3 0's. Remember that an integer is divisible by 2 (without remainder) if it ends with 0 and since $8=2^3$ its binary representation must end with at least 3 zeros.

In fact a finite automaton is enough to recognize numbers divisible by 8. The following transitions are for a DFA which can be easily rewritten as TM instructions.

$q_1$ - start state, $q_4$ - accept state.
$\delta(q_1, 0) = q_2, \delta(q_1, 1) = q_1$
$\delta(q_2, 0) = q_3, \delta(q_2, 1) = q_1$
$\delta(q_3, 0) = q_4, \delta(q_3, 1) = q_1$
$\delta(q_4, 0) = q_4, \delta(q_4, 1) = q_1$


Suppose an array $A$ is a maxheap.  Inserting a large element in the first position of $A$ does not necessarily preserve the maxheap property.  The maxheap property requires a node's value to be larger than both its children's values, for each node in the tree.  If the value inserted in the first position is larger than all values in the array, then the maxheap property is preserved at the root node, but might not be preserved at some of the other (lower level) nodes.

We can construct an initial array $A$ such that the nodes in the subtree rooted at the right child of the root have much larger values than the nodes in the subtree rooted at the left child of the root. When a new value is inserted in the first position of the array, the tree changes so that the smaller values in the left subtree become parents of the larger values in the right subtree, causing the maxheap property to be violated. For example, take $A=[6,3,5,2,1,4]$, which is a maxheap.  Inserting a $7$ in the beginning modifies $A$ to $A=[7,6,3,5,2,1,4]$, which is not a maxheap because the node with value $3$ is a parent of the node with value $4$.


Can I use infinite numbers in a reduction?

A language cannot contain infinite numbers, since by definitions it is a set of finite numbers. The language itself could be infinite, though: it could contain infinitely many numbers.

In your solution, in the first case, you first enter an infinite loop and then "start accepting infinite numbers", but once you've entered an infinite loop, you're not accepting anything.

Your reduction $f$ has to satisfy the following two properties:

If $e \in L_{\mathrm{empty}}$ then $f(e) \in L_{\mathrm{inf}}$.
If $e \notin L_{\mathrm{empty}}$ then $f(e) \notin L_{\mathrm{inf}}$.

In plain English:

If $L_e$ accepts no inputs then $L_{f(e)}$ should accept infinitely many inputs.
If $L_e$ accepts at least one input then $L_{f(e)}$ should accept finitely many inputs.

Try to see if you can come up with such a function $f$. The basic idea is similar to yours - on input $n$, $f(e)$ should check whether $L_e \cap \{1,\ldots,n\} \neq \emptyset$. You should just be more careful in what happens next.


Prove finding k disjoint paths from n given paths in a directed graph is NP-complete

Membership of your problem in $\mathsf{NP}$ is trivial. To prove that it is also $\mathsf{NP}$-hard consider an instance of (the decision version of) independent set consisting of a graph $G=(V, E)$ with $|V|=n$ and of an integer $k$.

Construct the graph $H = (V', E')$ where $V' = V \cup \{ x_{u,v} \, : \, (u,v) \in E \}$ and $E' = V' \times V'$.

For each $u \in V$ let $v_1, v_2, \dots, v_h$ be the neighbors of $u$ in $G$ and define the path $P_u = \langle u, x_{u,v_1}, x_{u,v_2}, \dots, x_{u,v_h} \rangle$ in $H$.
Let $\mathcal{P} = \{P_u \, : \, u \in V\}$.

There is an independent set of size at most $k$ in $G$, if and only if there is a subset $\mathcal{P}'$ with $|\mathcal{P}'| \le k$ such that the paths in $\mathcal{P}'$ are pairwise vertex-disjoint.

More precisely, if $S$ is an independent set of $G$, then $\{ P_u \, : \, u \in S \}$ is a collection of pairwise vertex-disjoint paths in $H$ and, if $\mathcal{P}'$ is a collection of pairwise vertex-disjoint paths in $H$, then $\{u \, : \, P_u \in \mathcal{P}' \}$  is an independent set of $G$.


Why has Windows used NTFS for 20+ years, while many different systems have trendend in the linux community over the same time?

NTFS is pretty good. From the start it had journaling (unlike ext2), size limits large enough that they would never be an issue (unlike ext2/3), and a flexible design that allowed arbitrary attributes to be defined and attached to files.

Developing filesystems for Windows is difficult. The necessary headers and documentation were for years not included in the Windows driver development kit; instead you had to, I think, sign an NDA and pay thousands of dollars for the IFS kit and support. The number of features you'd have to implement to be able to replace NTFS is large. Filesystem design is a black art under the best of circumstances. And Microsoft probably wouldn't want to support a filesystem designed by a third party in the default Windows install no matter how good it was.

Your list of popular Linux filesystems isn't all that long. ext2-4 are all pretty similar to each other, and btrfs is similar to ReFS.


How is a nondeterminisitic automaton running on an input?

A non-deterministic automaton runs in all possible sequence of states on a given input. It is not a random run.

An input symbol is accepted only if in at least one of the runs it has reached an accepting state after reading the given input.

Hope this helps :D


Essential bit content - prove that we can't use less bits than that

The function wouldn't be one-to-one otherwise.
The size of the set in the left is $|A|$, and its image would be of size at most $2^l<2^{H_0}=|A|$, therefore, the function wouldn't be injective and thus you wont be able to de-compress some of the data.
Therefore it will be a lossy-compression for any $l<H_0$.


Link-cut trees: using access() and link()

I think you might be mixing up the represented tree, $R$, and the auxiliary tree representation of the represented tree, $T$.

Recall the definition of $LINK(v, w)$:

  $link(v, w)$ - Makes vertex $v$ a new child of vertex $w$.

This happens in the represented tree. Then to keep the auxiliary representation consistent we make $w$ the left child of $v$ because they are keyed by their depth in the represented tree (i.e. left children are higher, right children are lower in the represented tree). So your proposed linking should happen like so:

$link(A, B)$ - Make $A$ the child of $B$ in $R$. Make $B$ the left child of $A$ in $T$ (assumptions are omitted).

$link(B, C)$ - Make $B$ the child of $C$ in $R$. Rebalance the splay tree in $T$ and make $C$ left child of $B$.

$link(C, D)$ - Similar to step 2.

Then we have the preferred path in the represented tree is simply $D \rightarrow C \rightarrow B \rightarrow A$.


What happens to the cache contents on a context switch?

That depends both on the processor (not just the processor series, it can vary from model to model) and the operating systems, but there are general principles. Whether a processor is multicore has no direct impact on this aspect; the same process could be executing on multiple cores simultaneously (if it's multithreaded), and memory can be shared between processes, so cache synchronization is unavoidable regardless of what happens on a context switch.

When a processor looks up a memory location in the cache, if there is an MMU, it can use either the physical or the virtual address of that location (sometimes even a combination of both, but that's not really relevant here).

With physical addresses, it doesn't matter which process is accessing the address, the contents can be shared. So there is no need to invalidate the cache content during a context switch. If the two processes map the same physical page with different attributes, this is handled by the MMU (acting as a MPU (memory protection unit)). The downside of a physically addressed cache is that the MMU has to sit between the processor and the cache, so the cache lookup is slow. L1 caches are almost never physically addresses; higher-level caches may be.

The same virtual address can denote different memory locations in different processes. Hence, with a virtually addressed cache, the processor and the operating system must cooperate to ensure that a process will find the right memory. There are several common techniques. The context-switching code provided by the operating system can invalidate the whole cache; this is correct but very costly. Some CPU architectures have room in their cache line for an ASID (address space identifier) the hardware version of a process ID, also used by the MMU. This effectively separates cache entries from different processes, and means that two processes that map the same page will have incoherent views of the same physical page (there is usually a special ASID value indicating a shared page, but these need to be flushed if they are not mapped to the same address in all processes where they are mapped). If the operating system takes care that different processes use non-overlapping address spaces (which defeats some of the purpose of using virtual memory, but can be done sometimes), then cache lines remain valid.

Most processors that have an MMU also have a TLB. The TLB is a cache of mappings from virtual addresses to physical addresses. The TLB is consulted before lookups in physically-addressed caches, to determine the physical address quickly when possible; the processor may start the cache lookup before the TLB lookup is complete, as often candidate cache lines can be identified from the middle bits of the address, between the bits that determine the offset in a cache line and the bits that determine the page. Virtually-addressed caches bypass the TLB if there is a cache hit, although the processor may initiate the TLB lookup while it is querying the cache, in case of a miss.

The TLB itself must be managed during a context switch. If the TLB entries contain an ASID, they can remain in place; the operating system only needs to flush TLB entries if their ASID has changed meaning (e.g. because a process has exited). If the TLB entries are global, they must be invalidated when switching to a different context.


algorithm to find all values that occur more than n/10 times

Perhaps the hint was aiming at the following approach. Suppose that the array were sorted. If a value appears $m$ times and we divide the array into intervals of length $m$, then the value must appear at the end of one of the intervals. This suggests the following algorithm for finding all values that appear $n/C$ times: compute the $i \cdot n/C$-largest elements for $1 \leq i \leq C$, and for each of them, check whether the value appears at least $n/C$ times. Each iteration takes $O(n)$ time using Quickselect, for a total of $O(Cn)$ time.


This problem does generalize the clique problem.

One example of a metric is the shortest path distance in a connected, unweighted graph $G$, where the distance between vertices $u$ and $v$, $d(u,v)$, is the length of the shortest path between them. There exists a clique of size $K$ in this graph if and only if we can find $K$ points whose distances sum to ${K \choose 2}$.

For finding cliques of size $5$ you can do slightly better than brute force: see this answer. However without more structure on the metric you are interested in it is an open problem to do significantly better.


Interesting question. For a better theoretical understanding of the whole theory I would suggest you to re-read "Introduction to Algorithms, Third Edition, Cormen" Chapter 12 (Trees) and Chapter 13 (Red-Black Trees). Since it is stated there that (page 311):

As an immediate consequence of this lemma, we can implement the
dynamic-set operations SEARCH , MINIMUM , MAXIMUM , SUCCESSOR ,
and PREDECESSOR in $O(\log n)$ time on red-black trees, since each can
run in $O(h)$ time on a binary search tree of height $h$ (as shown in
Chapter 12) and any red-black tree on n nodes is a binary search tree
with height $O(\log n)$.

Red-Black trees do not differ from AVL-trees from a strict computational point of view: https://www.geeksforgeeks.org/red-black-tree-vs-avl-tree/. An AVL tree is a subset of a Red-Black tree: http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=22948. So from a theoretical point of view, you can map them together (computational-complexity wise).
Regarding a pure understanding of why the INSERTION is $O(\log n)$, check this implementation example. There you can clearly see that what makes an AVL differ from a standard BST are the rotations, that can be performed in constant time. With those you get a balanced tree, and with a balanced tree you get $O(\log n)$ INSERTION.


Language is recursive, hence recursively enumerable

Depending on what definitions you use, the proof can be trivial.  We can all agree that a set $S$ is recursive if there is a Turing machine that halts on every input, accepts the members of $S$ and rejects the non-members of $S$. Such a Turing machine is called a decider of the set.

One definition of the recursively enumerable sets is that $S$ is RE if there is a Turing machine that accepts every member of $S$ and does not accept any non-member.  That is, if $x\notin S$, the machine either rejects it or loops forever.  By this definition, it is trivial that every recursive language is RE: the machine that decides the language has the property that it accepts everything in the set and nothing outside it.

The other definition is that a set $S$ is RE if there is a Turing machine that accepts every member of the set and loops forever for every non-member.  This appears to be the definition your book is using.  Now, suppose you have a machine that decides a set $S$.  Modify it so that, instead of rejecting non-members of the set, it loops forever.  This gives a machine that accepts every member of $S$ and loops forever for every non-member.  This is exactly what you need to conclude that $S$ is RE.

The same idea proves that the two definitions of RE are the same.  Any machine that obeys the second definition also obeys the first one (the first says it can either loop or reject for non-members: it happens to loop for all of them but that's a valid choice).  Any machine that obeys the first definition can be converted to obey the second by the same trick: replace rejection with looping.


Regular expression for a finite automaton appears to be wrong

Yes, you are right.

As given FA is DFA. It is accepting string only $\{\epsilon \}$.

And, complement of given  DFA accepting :
$\implies (1+0+1(0+1))(0+1)^*= (1+0+(10+11))(0+1)^*$

$\implies 1(0+1)^*+0(0+1)^*+(10+11)(0+1)^* = (0+1)^+ =$ { accepting everything other than $\{\epsilon \}$ string over alphabet $\{0,1\}$}.


After implementing a novel encryption algorithm, how would one go about analyzing its security or get help from others in doing so?

Typically, there are a variety of steps in evaluating a new algorithm.  They start with the quick review

is it already known?
does it vary only in nonrelevant ways from what is known?

which is commonly enough to show vulnerabilities in many amateur attempts at encryption.  The point is that there are a number of well known ways to translate strings of symbols into other strings of symbols, and many of those have been evaluated in common cryptographic studies.  Good books on cryptography cover these.

Then, the more intensive analyses begin.  These include:

functional inversion
analysis of the symbol statistics
differential cryptanalysis

and a variety of other mathematical techniques for extracting information of the keys from the intercept stream.

Also, if the technique involves nontraditional information stores (if it doesn't have keys, if it has strange communication channels and protocols, etc.), then you have to also analyse the various impersonation and interception scenarios on each channel.

For the description given, it would appear that the first cryptographic algorithm would fail the first quick view.  Substitution ciphers are well known.  It doesn't really matter how many times you compose substitution ciphers, their properties are the same.  If you had 10 keys and did substitution 10 times before final send, it would be equivalent to a single key substitution cipher and have no better security.  Unless there is some other tweak to the algorithm, that would quickly be dismissed as already known.


Derive Turing Machine with high level description

Its easy to check that $C$ is given in Chomsky Normal Form, because you just have to iterate through the production rules and make sure each one of them satisfies the definitions for being a CNF production.
Then, the harder part is deciding whether $C$ can produce $s$ or not.
Notice, that a CNF will derive a word with length $n$, in exactly $2n-1$ steps. (every production will either transform a variable to the letter corresponding to it, or will create one new variable)
Keeping this in mind, we can just iterate through all production chains that contain $2n-1$ steps (for $n=|s|$), and check whether we saw $s$ or not. If $s\in L(C)$, then we will see it, since $s$ can be derived with $2n-1$ steps. And if $s\notin L(C)$ we won't see it, therefore the algorithm is correct.


Find the kth smallest element in an unsorted array of non-negative integers

There is a simple randomized algorithm running in expected $O(n\log n)$ time. The algorithm is a variant of the better known algorithm QuickSelect.

The algorithm maintains a pair of values $a \leq b$, initially $-\infty$ and $+\infty$ (or, the minimum and maximum values of the array). At each round, it chooses a uniformly random element $c$ in the range $[a,b]$ from the array, and computes its order statistics, i.e., the value $\ell$ such that $c$ is the $\ell$th smallest element in the array.

If $\ell = k$, then we return $c$.
If $\ell > k$, we replace $b$ with $c$.
If $\ell < k$, we replace $a$ with $c$.

If $a = b$ then we return $a$. Otherwise, we continue for one more iteration.

Each iteration takes time $O(n)$, so in order to estimate the running time of the algorithm, we need to estimate the number of rounds. We will keep track of the number of "live" elements, initially $n$. The algorithm ends when the number of live elements gets down to 1 (or even sooner, if there are repeated elements).

Let us denote by $n_t$ the number of elements after $t$ rounds, so that $n_0 = n$. The exact distribution of $n_{t+1}$ given $n_t$ depends on the location of the $k$th order statistics among the live elements. Let us suppose that the $k$th order statistics is the $\ell$th live element. Without loss of generality, $\ell \leq (n_t+1)/2$. Suppose that we choose the $r$th order statistic, so $r$ is uniform over $1,\ldots,n_t$. Then:

If $r = 1,\ldots,\ell-1$ then $n_{t+1} = n_t - (r-1)$.
If $r = \ell$ then $n_{t+1} = 0$.
If $r = \ell+1,\ldots,n_t$ then $n_{t+1} = r$.

In total, the expected value of $n_{t+1}$ is
$$
\frac{1}{n_t} [(n_t + \cdots + n_t-\ell+2) + (\ell+1 + \cdots + n_t)].
$$
The number of summands is constant, and the worst case is when $\ell = (n_t+1)/2$, in which case the expected value of $n_{t+1}$ is
$$
\frac{(\frac{n_t+1}{2}+n_t)\frac{n_t-1}{2}}{n_t} \leq \frac{3}{4}n_t.
$$
Induction shows that $\mathbb{E}[n_t] \leq (3/4)^t n$, and so the expectation drops below 1 for $t = O(\log n)$.

While this doesn't quite show that the expected number of iterations is $O(\log n)$, more refined arguments do, and they moreover show that the number of iterations is $O(\log n)$ with high probability.

Here are some hints on how to implement the algorithm. The crucial step is to choose a uniformly random element $c$ in the range $[a,b]$ from the array. There are at least two ways to go about it, both taking $O(n)$:

Reservoir sampling

Initialize $N = 0$ and $X = \bot$.
Go over all elements of the array. For each element $x$, if $a \leq x \leq b$:

Increment $N$.
Replace $X$ with $x$ with probability $1/N$.

Return $X$.

Linear scan

Count the number of elements in the array between $a$ and $b$ — say the answer is $N$.
Draw a random integer $i$ between 1 and $N$.
Go over the array again, and return the $i$th element between $a$ and $b$.


Does O(1) communication complexity imply that a language is regular?

No.  Let $L_0$ be a context-free language, say the language of matched parentheses, $L_1 = \Sigma^* \setminus L_0$, and
$$L = \{ij \mid b \in \{0,1\}, i \in L_b, j \in L_b, |i|=|j|\}.$$
Then $L$ is not regular, but it has communication complexity $O(1)$.


No, this is not true. For example, let $f$ be the constant $1$ function, and define $g$ by $g(2n) = 1/n$ and $g(2n+1) = 1$.


The sorting problem for partially ordered sets

Take a worst case scenario.

The set is built out of pairs of objects $a_i, b_i$ where $a_i < b_i$ and there exists no order between $a_i < b_j$ when $i\neq j$.

This means that to know whether you can delete an element you need to check it against every other element resulting in a quadratic general case.

The best data structure to avoid that is where each node has a direct reference to which nodes it is greater or equal to. But to build that you need a quadratic algorithm.


Decidability of the language that accepts a universal turing machine

If $L_{u}$ would be decidable,  $L_u^\complement$ would be decidable too (the complement of a recursive language is recursive too) , but if you can build a TM that accepts $L_u^\complement$ you can build a TM that accepts $L_d=\{w \mid w_i \notin L(M_i)\} $ that is not RE.

In fact if $w \in L_d  \implies (w,w)\notin L_u \implies (w,w) \in L_u^\complement$.

So with a reduction from $L_d$ to $L_u$ it can be shown that $L_u$ is not decidable.


Can someone pelase give a counter example of it? If a problem is in NP then there is no known polynomial time algorithm to solve it

NP is the class of decision problems where any instance with an answer "YES" has a proof that the answer is YES which can be checked in polynomial time. NP contains all problems that are solvable in polynomial time. Therefore there are many problems in NP with known polynomial time algorithms.

If you are talking about NP-complete problems, that's a whole different matter. There is (at this point in time) no NP-complete problem with a known polynomial time algorithm to solve it.

Someone might find a proof that for an NP-complete problem there is no NP-complete problem with a polynomial time algorithm to solve it - not just no known algorithm, but no algoritm at all.

On the other hand someone might actually find an NP-complete that can be solved in polynomial time. It is unlikely though.


To answer the title question, yes, computation is independent of hardware. Computation is defined by the transformation of information, not by how it's embedded in the real world. This is easy to see: all the computation models have a mathematical formulation, and you can write mathematics as symbols on paper. In fact, many models of computation, such as the lambda calculus (1936) and Turing machines (1936) were invented before there were general-purpose computing machines (there were numeric calculators and data sorters, but programmable machines didn't exist until the 1940s).

It is possible to model today's computers by mathematical tools. They're just finite-state machines, after all. There are a lot of states, so a complete pen-and-paper representation is not feasible, but if you only model the part that you're interested in, that can be within reach.

As to whether there is only a single notion of computation, we don't know. We think so: that's the Church-Turing thesis. We think so because we've invented a lot of models of computation, and they all turned out to be equivalent. Some of them are easier to work with than others, or more directly applicable to certain problems, or are a closer match for certain computing hardware (e.g. in terms of performance or locality). But they can express the same computations.

Are Turing machines (or any of the equivalent concepts) the last word on the topic? We don't know. We certainly have weaker models of computation, but we think of them as restricted computation. And we have stronger models of computation, but we think of them as “magic“ — we can reason about them, but we have no idea how they could be implemented.

Is the brain a Turing machine? That's a question about the brain, and we don't know. We know that it's at least as powerful as a Turing machine, since it can simulate one. We are very far from being able to accurately simulate a brain with a Turing machine, but we don't know whether that's a matter of scale (a brain has tens of millions of neurons — a PC doesn't have enough memory to even store all the connexions). We do tend to think of brains as being more powerful than computers — when a problem is undecidable (in the Turing computation sense), we offer to solve it by thinking, but that doesn't answer the question. When we solve a problem by thinking, the solution is expressible in Turing machine terms. The problem solving method, however, may or may not be more powerful than Turing machines.

Would aliens have the same notion of computations? We don't know. We think so — mathematics seems universal to us — but that's a question about aliens, and since we don't know anything about aliens except what your imagination tells us, we can't answer it.


Are vector clocks useful in centralized systems?

No, there's no need for a vector clock in a centralized system.

A vector clock uses a $N$-vector of timestamps, where $N$ is the number of computers in the distributed system and the $i$th component of the vector block is a timestamp chosen by the $i$th computer.  In a centralized system you'd use a $N$-vector with $N=1$, so it just reduces to a single number instead of a vector.  In other words, instead of a vector, all you need is a single timestamp, where the timestamp is chosen by the central computer.


Artificial Intelligence: theory vs processing power

AI spans many different areas.  If you are actually asking about machine learning, the conventional wisdom is probably that it's a combination of new ideas (e.g., neural networks, architectures, methods for training them), computation power (e.g., GPUs), and data (large labelled datasets).
See, e.g.,
https://qz.com/1307091/the-inside-story-of-how-ai-got-good-enough-to-dominate-silicon-valley/,
https://towardsdatascience.com/the-state-of-ai-in-2020-1f95df336eb0, and probably many more (I didn't spend much time looking).


Minimize cost and maximize quality of function in four variables

So, simplifying a bit, you want to maximize an objective function $\Phi(w,x,y,z)$, where $\Phi$ has the following properties:

$\Phi(w,x,y,z)$ is monotonically increasing in $w$, in $x$, and in $y$
for any fixed $w,x,y$, $\Phi(w,x,y,z)$ is monotonically increasing-then-decreasing in $z$, i.e., there exists some $z_0$ such that $\Phi(w,x,y,z)$ is monotonically increasing in $z$ for $z \le z_0$ and is monotonically decreasing in $z$ for $z \ge z_0$.

Here $\Phi(w,x,y,z)$ represents the accuracy.

There are efficient algorithms to maximize this objective function, if $\Phi$ has some additional nice properties.  I'll describe how to do so, in several steps.

Given $w,x,y$, it is possible to efficiently find the $z$ that maximizes $\Phi(w,x,y,z)$ using ternary search (see also here).  Let $\Phi_3(w,x,y)$ denote the value of $\Phi(w,x,y,z)$ for the value of $z$ that maximizes  $\Phi(w,x,y,z)$, i.e.,

$$\Phi_3(w,x,y) = \max_z \Phi(w,x,y,z).$$

The comment above indicates that you can efficiently compute $\Phi_3(w,x,y)$ using ternary search.  If $z$ comes from a discrete space with $N$ possible values, the running time to compute $\Phi_3(w,x,y)$ will be $\Theta(N)$; if it comes from a continuous space, you can find the approximate value of $\Phi_3(w,x,y)$, and for typical functions, it the convergence rate will often be very fast (the number of iterations will be proportional to the number of digits of accuracy you want in the answer).

Now, if we are lucky, $\Phi_3$ will be monotonically increasing in $w,x,y$.  If this happens, we can continue to apply a similar idea, as follows.

Under this condition, given $w,x$, it is possible to efficiently find the $y$ that maximizes $\Phi_3(w,x,y)$.  How?  Use binary search on $y$, and use the fact that we know how to efficiently compute $\Phi_3(w,x,y)$.  So, define

$$\Phi_2(w,x) = \max_y \Phi_3(w,x,y),$$

and note that this gives us an efficient way to compute $\Phi_2(w,x)$.  The running time will again be efficient, i.e., $\Theta(\lg N)$ evaluations of $\Phi_3$ if $y$ comes from a discrete space with $N$ possible values, otherwise we can get an approximate optimal value efficiently (typically, the number of evaluations of $\Phi_3$ needed is proportional to the number of digits of accuracy we want in the answer).

Suppose that $\Phi_2(w,x)$ is monotonically increasing in $w,x$ and $\Phi_1(w) = \max_x \Phi_2(w,x)$ is monotonically increasing in $w$.  Then Applying the same techniques, we can see that given $w$ it is possible to efficiently find the $x$ that maximizes $\Phi_2(w,x)$ (using binary search), and thus that it is possible to find the $w$ that maximizes $\Phi_1(w)$. Finally, the maximum value of $\Phi_1(w)$ is exactly the maximum value of $\Phi(w,x,y,z)$ over all $w,x,y,z$.

So if $\Phi$ has some additional nice properties, there are efficient algorithms.  The resulting algorithm will have running time $O(k^4)$, where $k = \lg N$ if each parameter comes from a discrete space; or where $k$ is typically proportional to the number of bits of accuracy desired if the parameter comes from a continuous space.

Therefore I suggest you try this and see if your $\Phi$ has the required nice properties.  If it does, you are in good shape and you can try a technique based on this.

What do you do if $\Phi$ doesn't have these nice properties?  Probably your best next bet is to try some standard black-box mathematical optimization routine, e.g., hill-climbing, gradient descent, or convex optimization.  If $\Phi$ is a relatively smooth function, I suspect they might work pretty well.


Is finding solution to a system of 2SAT equations seperated by OR (DNF form) in NP

First, let me note that the question's title is a bit misleading, because $P$ is a subset of $NP$. See also Yuval Filmus's comment. I assume what you intended to ask is whether it's in $P$ or in $NP \setminus P$.
Also, the name "DNF" specifically refers to a disjunction of elementary conjunctions, not a disjunction of arbitrary functions. What you are describing is not a DNF, but a disjunction of CNFs.

With that out of the way, here's my answer.

To satisfy a disjunction of 2-CNFs, all you need is to satisfy one of them. So, if you apply the 2-SAT algorithm to the first of the CNFs and get a "yes", then the answer to the whole problem is "yes". Otherwise, you just move on to the second one, and so on. Shouldn't take long, since you only have m of them. If none of them can be satisfied individually, i.e. they are all constant zeroes, then obviously the entire thing is a constant zero.
So the answer to the first part is: the problem is in P, with the following decision algorithm:
For every 2-CNF, apply the "normal" 2-SAT algorithm (the resolution rule) to determine if it's satisfiable or not. If "yes", just return "yes". If you went through all of them without finding a "yes", then return "no".

Now, finding the "False" cases of that formula (also known as the problem of tautology) is another question entirely. For one thing, tautology for ORs of ANDs of ORs is equivalent to satisfiability for ANDs of ORs of ANDs, by De Morgan's rule. But that's just a more general case of an already general SAT problem, isn't it?
Consider what happens when you restrict the set of possible formulas to those in which every two-element disjunction is really just one element, repeated. So it is a formula like
$$
F = [(x_1 \vee x_1 ) \& ( \neg x_2 \vee \neg x_2) \& (x_3 \vee x_3)] \vee [(x_2 \vee x_2) \& (x_4 \vee x_4) \& (x_5 \vee x_5)] \vee ...
$$
which is equivalent to
$$
F = [x_1 \& \neg x_2 \& x_3] \vee [x_2 \& x_4 \& x_5] \vee ...
$$
which is just a normal DNF. After the De Morgan transformation, you get a normal CNF, whose satisfiability is known to be NP-hard. Therefore, any problem that includes this one as a subset will also be at least NP-hard.
Obviously, the problem in question won't be outside NP, because it is still polynomially verifiable. So the answer to your second question is "in NP, but not in P".


Is the following language is a context free grammar language?

Consider the word $w = 0^n1^n0^n \# 0^n1^n0^n \in L$ for a sufficiently large value of $n$.

By the pumping lemma for context-free languages, we know that if $L$ is context-free then there are$a,b,c,d,e = \Sigma^*$, with $|bcd| < n$ and $|bd|>1$ such that $w=abcde$ and, for every $i \ge 0$, $a b^i c d^i e\in L$.

Notice that neither $b$ nor $d$ can contain $\#$, as otherwise setting $i=0$ would show that $a c e \not\in L$.

If $c$ contains $\#$, then $b,d \in 0^*$ and $a b^i c d^i e$ is a word of the form $0^n 1^n 0^{x + i|b|}\#0^{y+i|d|} 1^n0^n$ with $x+|b|=n$ and $y+|d|=n$.  If $|b|>0$ you can make the first part of the word (before $\#$) end with more than $n$ zeros by picking $i=2$, resulting in a contradiction. Otherwise $|d|>0$ and you can make the second part of the word (after $\#$) start with less than $n$ zeros by setting $i=0$.

If $c$ does not contain $\#$ then $b$ and $c$ either both precede or both follow the unique occurrence of $\#$ in $w$. If they precede $\#$, pick $i=2$. If they follow $\#$, pick $i=0$.
In this way the first part of the word becomes longer than the second (and hence not in $L$).


The common definition is that a family of graphs $G = (V, E)$ is sparse if $m \in o(n^2)$, with $n = |V|$ and $m = |E|$. Formally, that requires the family to be infinite, and we only know something in the limit.

The definition does not apply to graphs of a fixed size per se. One would certainly want $m \ll n^2$ in some sense. For instance, if $m \leq 5n$ or $m \approx \log n$ you would probably say that your graph is "sparse".

You can bridge this gap by requiring a bit more on the asymptotic side. Say we call a family of graphs sparse if

$\qquad\displaystyle m \leq f(n) + O(1)$ with $f \in o(n^2)$;

then we may want to call every graph with $m \leq f(n)$ sparse. The implicit assumption is that the error term hidden in $O(1)$ is well-behaved.


Extending the implementation of a Queue using a circular array

Using the Vector class is certainly a possibility, as a practical matter. Other solutions will amount to implementing functionality that is similar to what the Vector class provides (possibly in a way that is more efficient given that the data structure stores a queue).

Some languages offer inherently resizable arrays. For example, in C, to allocate an array, you allocate a block of memory of the required size with the malloc function, and you can later resize this block without affecting the data in the remaining part (when shrinking) or the initial part (when extending). Under the hood, realloc may allocate a new region (at a different address in memory) then copy the data, but it'll try to extend or shrink the region in place for efficiency, in which case no copying is necessary.

Most high-level languages do not support resizing existing memory regions. This is because resizing might change the address of the object, which requires modifying all references to that object — C gets away with it by shifting the burden of updating references to the programmer. If you want a resizable array, you can achieve that manually: access the array through an indirect reference, and when you want to resize the array, allocate a new array, copy the data and assign the indirect reference to the new array.

As a simple optimization, if the array size shrinks by a small amount (say, because you take an element from the queue), do not shrink the array: you'll waste a bit of space, but avoid incessantly reallocating the array and moving the data around if successive elements are removed. And if the array size increases by a small amount (say, because you push an element onto the queue), increase the array size by a margin over the requested amount, so that the array will still be good for the next few increases. The Vector class in Java does this: it maintains an elementCount for the array that contains the data; array elements beyond this position are not used.

Asymptotically, you get good behavior by varying the array size exponentially, for example sticking to powers of 2: if you add an element to a 128-element queue, resize the array to 256; if you remove an element from a 65-element queue (in a 128-element array), resize the array down to 64. With array sizes of the form $a^n$, the wasted space is at most $(a-1)$ times the array size. The cost of reallocations, dominated by moving elements when crossing a size boundary is $\Theta(a^n)$. Amortized over a sequence of additions from an empty array or a sequence of removals until the array is empty, the cost of reallocations is $\Theta(a^n/a^n) = \Theta(1)$. In general the amortized cost of reallocations is $O(1)$.

There are other implementations of resizable arrays that avoid reallocation altogether, at the cost of having slower access time to elements. Avoiding reallocations is especially good to avoid long pauses when a reallocation happens and a lot of data needs to be moved around. A simple one is to maintain a list or array of arrays of exponentially increasing size. The element number $2^i + j$ with $j < 2^i$ is stored at position $j$ in array number $i$. No data ever needs to be copied when the array grows or shrinks (except for the bookkeeping data to maintain the collection of array, which grows logarithmically over the total size).


What is the output of below algorithms on a disconnected Graph?

No.  The output of Dikstra's algorithm is a set of distances to each node.  It's not a graph or a tree.  This is true no matter whether the input graph is connected or disconnected.  The standard algorithm for Dijkstra's algorithm sets the distance correctly for all vertices in all components (not just the ones in the same connected component as the source).  The standard algorithm doesn't print anything, so if you are printing something, you're probably adding something extra to the standard algorithm, and we can't analyze that without seeing what your variation of the algorithm is.


Examples of simple/common problems with quadratic running time

It is true that many algorithms that have quadratic running time are not the state of the art for their problems today. Among which are quadratic sorting algorithms for example bubble-sort, select-sort and insertion-sort, which are overcome by merge-sort and heap-sort. On a side note, quick-sort, the standard sorting algorithm in different areas, has a worst running time of $O(n^2)$ and is only used because the probability of having bad running time (say worse than a constant factor of $O(n \log n)$ is very small and it has smaller overhead than the other efficient sorting algorithms).
Also solving maximum matching on bipartite graphs by reducing to maximum flow and solving with Ford and Fulkerson's method is $O(nm)$ which is quadratic in sparse graphs, which is again overcome by the algorithm from Hopcroft and Karp with running time $O(\sqrt n m)$.
However, some of the problems with quadratic running time are conjectured to be optimal up to a log factor. These problems are not only interesting because of their quadratic running time and that this time is probably optimal, but also because they lead a list of problems that are either as hard or strictly harder than them.
The 3-sum problem

The problem. Given a set of $n$ integers, find if 3 of them add up to zero.
Quadratic algorithm. Sort the values in the list. For each value $v$ in the list, look if there are two values summing up to $-v$. Such a search can be done in $O(n)$ in sorted array using sliding window technique. Since we do it for every element in the list we get a running time of $O(n \log n + n^2) = O(n^2)$. Note that the $n \log n$ is for sorting the array as a pre-processing step.
Similar problems. The problem has many variants that are equivalent in a sense that have the same running time. Including the version of the problem where repetitions are not allowed or the version where you get three sets of values and you have to choose a value form list to sum up to zero (or to some value $v$). More Interesting are the reductions from the 3-sum problem variants to different Geometry problems as checking a point-set in the plane if three are co-linear. This problem is solvable in quadratic time using the point/line dual construction and is also expected to be optimal by the 3-sum conjecture. Another example is the Geombase problem, where you have a set of points each lying on one of the lines $y=0;y =1$ or $y=2$ and you need to find if there is a non horizontal line crossing three of the points. This problem is also equivalent to three sum in the sense that the reduction can be done in both directions. Similarly, the problem given a set of $n$ lines, do three of them intersect in one point is almost optimal in $O(n^2)$ if 3-sum conjecture is true.

The orthogonal vectors problem.

The problem. Given a set of $n$ vectors of dimension $d$, are two of them orthogonal.
The algorithm. For constant values of $d$, checking all pairs of vectors is in $O(d n^2) = O(n^2)$.
Similar problems. Based on this conjecture, the following problems are almost optimal with a running time of $O(n^2)$. Edit distance, longest common subsequence and graph diameter in sparse graphs.

Here is a brief description for each of these problems:

Edit distance: Given two strings, what is the least number of modifications (deletions, insertions..) are needed to make the strings equal. The problem can be generalized to a set of operations on both or one of the strings and cost for each operation and we want to minimize the total cost.
Longest common subsequence: Given two strings, a subsequence of the string is a string resulting from the original string by deleting some characters. What is the longest string that is a subsequence of both input strings (Note that this problem is a special case of edit distance.
Graph diameter is the longest shortest path in the graph, that means the minimum $d$ such that you can go from any node to any other node in less than $d$ steps.

Note there is a reduction from SAT to Orthogonal vectors proving that if the Orthogonal vectors conjecture fails, then SETH fails as well.


Maximum sum of depths of all external nodes in a Binary Tree

Consider a tree that has a chain of length $n/2$ at the top, where each node has exactly one child. Then, the remaining $n/2$ nodes are attached at the bottom of the chain, as a complete tree of depth $\log_2 (n/2)$.

With this shape, every leaf is at depth $n/2 + \log_2 (n/2) = \Theta(n)$. There are about $n/4=\Theta(n)$ leaves.  So, the sum of the depths of the leaves is $E(T) = \Theta(n^2)$.

This is asymptotically optimal; no tree can have $E(T) = \omega(n^2)$, as the maximum possible depth is $n$, and the maximum number of leaves is $n$, so we have $E(T) \le n^2 = O(n^2)$.


What does it mean "given a NFA and its accepted language L build the DFA that accepts L*"?

$L^*$ is the Kleene closure of $L$. This is the language of all strings that can be made by taking a finite number of (not necessarily different) strings from $L$ and concatenating them.  More formally,

$$L^* = \{\varepsilon\}\cup\{w\in\Sigma^*\mid \exists k\geq 1\,\exists w_1, \dots, w_k\in L \text{ such that } w = w_1\cdot\dots\cdot w_k\}\,.$$

Or, if you prefer, for $k\geq 1$, let
$$L^k = \{w_1\cdot \dots \cdot w_k\mid w_1, \dots, w_k\in L\}$$
and then $L^* = \{\varepsilon\}\cup L^1 \cup L^2 \cup L^3 \cup\cdots\,$.

As for how to produce an automaton that accepts that, I suggest you think about it some more yourself, now that you know what it is you're trying to do. A hint would be to use nondeterminism to "guess" where the words $w_2, \dots, w_k$ begin.


Given three languages L1 L2 L3 that do not intirsect could one be TR and the other TD and the third neither

Is is indeed possible.

Consider the halting problem set $$H = \big\{ \big(\langle M \rangle, w\big): M \big( w \big) \space halts \big\}$$

and its complement $$\overline{H} = \big\{  \big(\langle M \rangle, w\big): M \big( w \big) \space doesn't \space halt \big\}$$

We know that H is recognizable and not decidable. That means that $$\overline{H}$$ is not recognizable because, otherwise, H would be decidable.

Now take $$L_1 = \emptyset \space \big( decidable \big) $$ $$L_2 = H \space \big( recognizable \space and \space not \space decidable \big) $$ $$L_3 = \overline{H} \space \big( not \space recognizable \big)$$

We have that $$L_1 \cup L_2 \cup L_3 = \Sigma^*$$ and
$$L_1 \cap L_2 = L_2 \cap L_3 = L_1 \cap L_3 = \emptyset$$


Solving Unary Constraint Satisfaction Problem other than branch and bound

A pragmatic approach will be to formulate this as an instance of integer linear programming, and feed the system to an off-the-shelf ILP solver.  The details of exactly how to do that will depend on the specific kinds of constraints you have.  There are many tutorials on integer linear programming, so you might start there.

If you need the solution to be deterministic (so solving the same problem multiple times is guaranteed to give the answer), and if you're not sure whether your ILP solver is deterministic, you can define an ordering on solutions (e.g., lexicographic search) and then use binary search to find the "first" valid solution out of all optimal solutions.


Sum of all distances in connected DAG in $O(n\log n)$

I think the question is not clear enough, but what I understood is that we want to find the sum of all the shortest path from $u$ to $v$ such that $u < v$. The trick is that the graph is actually a directed chain, so we can represent the edges in an array $A$ of length $n - 1$.

The brute force formula is $\sum_{i=1}^{n -1} \sum_{j=i + 1}^{n} \delta(i,j)$. Where $\delta(i,j)$ is the shortest path from $i$ to $j$, because our graph is a chain, we can simply express this as $\delta(i,j) = \sum_{k=i}^{j - 1} A_{k}$. In the example you provided with 4 nodes $A =[1,1,1]$. The above formulas have a complexity of $\Theta(n^3)$, which can be improved to $\Theta(n^2)$ by doing a prefix sum on $A$. But a pattern can easily detected by looking carefully where the items of $A$ repeat.

For example, if $A = [1,2,3]$ the above formulas would provide the following operations:

$(1 + (1+2) + (1+2+3)) + (2 + (2+3)) + (3)$, here each "big parenthesis" is the computation from each node. The last node is obviously ignored.

We can rewrite this as:

$3 *(3 * 1) + 2 *(2 * 2) + 1 * (1 * 3)$

For example $3 *(3 * 1)$ means that $3$ was repeated once ($1$) on $3$ parenthesis. Likewise, $ 2 *(2 * 2)$ means that $2$ is repeated two times on $2$ parenthesis and so on.

The repetitions have a pattern: the number of times it appears on a "big parenthesis" is actually the index of the element, but the number of times is repeated inside the parenthesis decreases as the index increases because less paths starts from nodes that are closer to the end of the chain. Work through the example and you will find the pattern, make sure you understand this paragraph.

As you mentioned that you have not found the pattern, the above discussion can be summarized in this formula: $\sum_{i=1}^{n - 1} A_{i} * i * (n - i)$. Remember that $n$ is equal to the number of nodes and $A$ contains the edges, which are $n - 1$.

The proof of the above intuition is left as an exercise for the reader :-).

EDIT: Just in case, the complexity is $\Theta(n)$ because we only do a loop to compute the summation and the inner operations are $\Theta(1)$. Depending on how you represent the graph in the input, the memory complexity can be either $\Theta(1)$ or $\Theta(n)$.


Here is how I would do it:
Algo: Verifier for DNF-SAT problem given as array of closures and a possible mapping of literals to booleans
Input:
Array of closures: [$C_1$,$C_2$,...,$C_m$]
where $C_j \subseteq \{x_1,...,x_n,\neg x_1, ... \neg x_n\}$
(Certificate) Array $M$ where $M_i$ is the boolean value of literal $x_i$
Output: true or false
for $i = 1$ to $m$:
  value = true
  for literal in $C_i$:
    if literal == $x_i$:
      value = value or $M[i]$:
    else if literal == $\neg x_i$:
      value = value or (not $M[i]$)
  if not value:
    return false
return true

Note: the math notation is indented and commonly used in pseudocode sadly cs stackexchange doesn't support it


When $k=1$, the problem is trivial: the optimal solution is to put each set in its own configuration.

When $k=2$, the problem can be solved in polynomial time using graph matching.  Build a complete undirected graph with one vertex per set.  The cost of the edge $(S_i,S_j)$ is the cost of putting $S$ and $T$ together in the same configuration (i.e., the weight of $S_i \cup S_j$).  Now the optimal solution to your problem is given by the minimum-cost perfect matching in this graph.  That matching can be computed in polynomial time using standard algorithms.

When $k=3$, the problem is NP-hard.  In fact, it is NP-hard to determine whether a graph can be covered by a disjoint union of cycles of length $\le 3$ (i.e., whether you can find a set of cycles, where each cycle has length 2 or 3, where no two cycles have any vertex in common, and where every vertex appears in one of these cycles).  This implies that your problem is intractible when $k\ge 3$.

The proof of the hardness result I alluded to can be found in Section 3 of the following paper:

Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges.  David J Abraham, Avrim Blum, Tuomas Sandholm. EC 2007.

That said, not all hope is lost.  There are techniques available for finding a solution that will be close to optimal, using integer linear programming.  For instance, you can express your problem as an instance of integer linear programming and then apply an off-the-shelf ILP solver.  See the paper above for some more sophisticated techniques that might be applicable in your situation as well.


What is the algorithm for Shannon-Fano code? am I correct?

You are confusing "Shannon coding" from "Shannon–Fano coding" (terminology could vary across sources). Per Wikipedia, Shannon–Fano coding is the algorithm you mention, while Shannon coding is any coding assigning a symbol occurring with probability $p_i$ a codeword of length $\ell_i = \lceil \log_2 \frac{1}{p_i} \rceil$. Per Wikipedia, Shannon–Fano coding always leads to codewords whose lengths are within one bit of $\log_2 \frac{1}{p_i}$. This is also a feature of Shannon coding, but the two need not be the same. In particular, Shannon–Fano coding always saturates the Kraft–McMillan inequality, while Shannon coding doesn't.


Quantum computing - Difference between a binary bit and a Q-bit

I think something worth pointing out early on is the ambiguity of the word state. In quantum information most things have very strong (shall I say natural?) physical interpretations / origins.
In classical information we represent information as bits. A bit might correspond to the state of some classical system, such as an electric sign in a circuit, etc. Evolution of classical bit vectors is arbitrary in the sense that its enforced by us humans.

In quantum computing information is represented using states of a quantum system (for example polarization of a photon).
The states of a quantum system can be identified with vectors of a Hilbert space. Qubits $|0\rangle, |1\rangle$ are just an arbitrary choice bases of a two dimensional space. A two-qubit state represents a quantum system which is a composite of two two-dimensional subsystems. Evolution of quantum state vectors are governed by the laws of physics.

For a classical two-bit vector, the permissible values are $00,01,10,11$, whereas for a two-qubit system you can have any $a|00\rangle+b|01\rangle+c|10\rangle+d|11\rangle$ for $a,b,c,d\in\mathbb{C}$ provided that $|a|^2+|b|^2+|c|^2+|d|^2=1$. This, together with the postulates of quantum mechanics, permits a completely different range of behaviors of quantum systems (and qubit vectors), behaviors that are unseen in classical systems. This gives the above representation of information a lot more power compared to classical information representation. A number of physical phenomena allow various interesting information theoretic operations (such as teleportation, superdense coding, etc), which are not admissible using classical systems.

The emphasis here really is on the fact that in quantum computing you can exploit a range of physical phenomena that is not typical in classical information theory.


How to find a lambda term to complete a function?

We can remove the dependence on what the values stored in the sequences are by assuming that we pass "the same thing" as the first two arguments. Regardless of what $b_1, b_2, b_3$ are:

$$([b_1b_2b_3]\,x)\,x = \lambda f. ((f\,x)\,x)\,x$$

This gives you an effective way to tell the difference between an empty sequence and a non-empty sequence :

$$(([]\left<M,u\right>)\left<M,u\right>)\,(\lambda x. x) = \lambda x. x$$
$$(([b_1]\left<M,u\right>)\left<M,u\right>)\,(\lambda x. x) = \left<M,u\right>$$
$$(([b_1b_2]\left<M,u\right>)\left<M,u\right>)\,(\lambda x. x) = \left<M,u\right>$$
$$(([b_1b_2b_3]\left<M,u\right>)\left<M,u\right>)\,(\lambda x. x) = \left<M,u\right>$$

So if $s$ is a sequence, consider this:

$$((((s\left<M,u\right>) \left<M,u\right>) (\lambda x. x))\,\hbox{false}$$

What does it reduce to if $s$ is empty? What does it reduce to if it's non-empty?


Algorithm - How to show Big O for 2 functions

Interpreting lg(n) as log2(n), set n=2^x so that the inequality transforms to

ln(2)*x <= 2^sqrt(2*x)

Now apply the square root,

sqrt(2*ln(2)) * sqrt(x/2) <= 2^sqrt(x/2)

and we are left to prove that for y>0

2^y/y > sqrt(2*ln(2))

Indeed, the minimum of the left side can be found for 0=ln(2)*y-1 or y=1/ln(2) with minimum value 2^(1/ln(2))*ln(2). Numerically, the gap between 1.88416938536372 and 1.1774100225154747 is large enough to exclude any floating point errors. Thus all the equivalent inequalities including the original one are true.


Data structures that store efficiently detected features of an image

A simple solution would be a 2D array containing a 1 in the locations that are detected as an edge, or a sparse 2D matrix.  A more sophisticated solution would be a quadtree.


Do fully optimizing compilers for terminating programs exist?

I assume you are interested in optimisation of runtime. As I've written in my comment, that does not sufficiently specify the goal: does an optimisation reduce runtime on any input, every input, all worst-case inputs or even on average?

I will show that all of them are impossible. The proof extends to optimising the length of the program.

Recall that the following problem is not computable:

  Given a context-free grammar $G$ with terminal alphabet $\Sigma$, decide whether
  $\mathcal{L}(G) = \Sigma^*$.

Note furthermore that given a context-free grammar $G$, we can hardcode, say, the CYK algorithm for that one grammar; denote this algorithm by $\mathrm{CYK}_G$. We observe that $\mathrm{CYK}_G$ terminates for all inputs (from $\Sigma^*$).

Now assume that there is an optimiser $\operatorname{Opt}$ which, given an always terminating algorithm $A$, outputs a result-equivalent algorithm which is optimal with respect to runtime. Clearly,

$\qquad \operatorname{Opt}(\mathrm{CYK}_G) = \text{'}\mathtt{return\ true;}\text{'}
        \iff \mathcal{L}(G) = \Sigma^*$

and we have thus constructed a decider for an uncomputable problem, contradicting the assumption.


Making a profit as a high-dimensional store owner?

I'm not sure why you would need to enumerate the cliques. You can encode the distance constraints explicitly in just a quadratic number of constraints.

\begin{align*}& &&\max_{S \in \lbrace 0, 1 \rbrace^n} \sum_{i=1}^n p_i s_i \tag*{}\\
&\text{subject to} &&\sum_{i=1}^n c_i s_i \leq B \\
& && s_i + s_j \leq 1 \hspace{1cm} \forall j > i \geq 1 \text{ where } d(x_i, x_j) \leq D \end{align*}


Fast software pipelining for stream processing

Do the work in batches.  Have a separate buffer for each stream that stores the unprocessed items.  When you invoke $f$ for stream $S_i$, invoke 100 times on the 100 oldest items in the buffer for $S_{i-1}$, then remove those items from the buffer.  This basically increases the granularity of operations, and should reduce the overhead from synchronization by about 100x.  You can of course tune the number 100 to adjust throughput vs latency.


Well, there is not really a completely satisfying way to have the big-O Notation with multiple variables. Therefore CLRS present one way of a generalization. Putting an and instead of the or would give a new definition with other problems.

See this article for a discussion on the subject.


Find a simple cycle in an undirected subgraph of a grid graph that encloses the most faces

Decompose your graph into biconnected components. Since only a biconnected component can border faces (why?). This can be done in linear time.
You can find the number of faces in each component by Euler's identity. This can be done in linear time per component.
Pick the component with the largest number of faces and find the cycle bordering that component. This can be done with a single line sweep, which is $O(V' \log V')$.


Alternatives to directly connected networks for representing frequently-updated graphs

You might be interested to know after all that I settled on an edge-list representation.  This allows easy cloning and has loosely coupled nodes and edges, which makes it idea for frequent editing operations.

Thanks for all the help and constructive comments.


No, 1/numeric_limits::max() is the probability that two randomly picked objects have same hash code, not more.

Probability of collisions during insertion into hash table is calculated differently.

Given your vector has size M (i. e. $M$ buckets), and you already inserted $N$ entries into the hash table, the fraction of empty slots, i. e. the slots with zero entries, is $e^{-N/M}$, because in hash tables with separate chaining slots with 0, 1, 2, ... entries are Poisson-distributed. This means that the probability of any collision during inserting N+1-th entry is $1 - e ^{-N/M}$.

For example, if your vector has size 64 and you inserted 32 entries, probability of collision during insertion 33-th entry is $1 - e ^{-0.5} \approx 0.39$.


Propositional truncation of excluded middle

The only way to prove ∥ X ∥ is to prove X (unless you admit some other axiom).
So, assuming P is a proposition, there is no way to prove ∥ ((A) ⊎ (¬ A)) ∥ if you cannot prove ((A) ⊎ (¬ A)).

It is not a correct intuition that undecidable propositions are either true or false, just we do not know about it.

A formal system S with an undecidable proposition P can always be extended either in S'=(S,p:P), or S''=(S,p:¬ P) where p is taken as a new axiom. Both S' and S'' are then consistent formal systems, provided S is.
If P were already true or false in S, then either S' or S'' would be inconsistent.

A formal system is meant to be interpreted, and can usually be interpreted in different ways. Undecidable propositions in a formal system are propositions that can be true in some interpretations, and false in other interpretations.
A proposition is said to be true (resp. false) within a formal system when it is true (resp. false) in all possible interpretations. So there are lots of propositions that are neither true nor false within the formal system.

The confusion comes from the different meanings for 'true': the truth within the formal system usually does not match exactly the truth in the interpretation (or intuition) that you have in mind when you are working with the formal system...


Is there some mathematical properties of the distribution which is the output of a probabilistic polynomial-time Turing machine?

Given a probabilistic algorithm $A$, define $f^A(x)=\Pr[A(x)=1]$. To make the question interesting, you have to ask whether $f^A$ (with polynomial $A$) can be close to $g$, for infinitely many values of $n$. Otherwise, as Raphael mentioned, you can pretty much obtain any $g:\Sigma^n\rightarrow [0,1]$, while keeping $A$ polynomial (there is no asymptotics). Consider the problem of how $dist_n(f^A,g)=\sum\limits_{x\in S^n}\left|g(x)-f^A(x)\right|$ grows as a function of $n$. Obviously $dist_n(f,g)\le 2^n$, and a random guessing $A$ achieves $dist_n(f^A,g)\le 2^{n-1}$, can we find a probabilistic polynomial algorithm $A$ such that $dist_n$ grows polynomialy?

Let $L\subseteq\Sigma^*$ be some language, and $f^L:\Sigma^*\rightarrow \{0,1\}$ be its indicator function, i.e. $f^L(x)=1\iff x\in L$.
If for large enough $n$ it holds that $\sup\limits_{x\in\Sigma^n}\left|f^L(x)-f^A(x)\right|\le\frac{1}{2}-\epsilon$, then $\mathsf{L\in BPP}$ (simulate $A$ several times and take the majority vote, this works for $\epsilon=n^{-d}$). If for large enough $n$ you have $\sum\limits_{x\in\Sigma^n}\left|f^L(x)-f^A(x)\right|\le poly(n)$, then $\mathsf{L\in P/Poly}$, since your advice can contain information about all strings $x\in\Sigma^n$ on which $f^L,f^A$ differ by more than (say) $\frac{1}{3}$, and on the rest of the strings you can take the majority vote as above.

Thus, to answer your question, if $g$ is an indicator function for a hard language, you can expect (under some hardness assumptions) that there is no probabilistic polynomial time algorithm $A$ for which $Dist_n(f^A,g)$ is polynomial in $n$.


What is the whole picture of the NP-hardness proof of Super Mario Bros?

Graph Connection and Gadget Orientation

Short answer to your first question is to use graph algorithms to compute gadget assembly. Erik mentions this briefly. Keep in mind the gadgets don't necessarily have to be oriented as shown above. You could rearrange the gadgets however you wish as long as you retain the edge connections and entrance/exits of the graph.

The idea of "falling down" from a variable is so that there is no way to get back up to it. After you fall down there could be a tunneling system or corridor that allows Mario to get to the bottom side of a clause and hit the question box from below.

Right-to-Left Check Path

You could use the mirror (about the y-axis) of the clause gadget to achieve the capability of going right to left. This would be true for any of these gadgets as long as you kept the entrances and exits hooked up properly using tunnels. You do not gain or lose anything from going right to left versus left to right in SMB. They would be equal movements and since the whole level is on the screen at one time, we are not restricted from going right to left.

The Crossover Gadget

The crossover gadget is placed where edges intersect (edges between literal and clause). This is because SMB is a 2-dimensional game and thus the graph
using all these gadgets must be planar. The crossover gadget will then act as a vertex where the two intersecting edges can safely connect and not interfere with each other. They will not interfere because if you enter top left, you can only leave top right and if you enter bottom left you can only leave top center. More on the planarity and edge interference here.

Importantly, the crossover gadget is directional. You can only go left to right through the gadget once. This means the edges must also be directional. Whenever you see an edge from literal to clause there are really two directional edges; (literal -> clause) and (clause -> literal). Which results in there being four crossover gadgets whenever the two directional edges cross with two other directional edges. Erik explains more in the video at 1h1m20s (It won't allow me to link to it because this is my first post).


The answer depends on the initial value. For example, if $T(0) = 2$ then you can prove by induction that $T(n) = 2$ for all $n$. More generally, let $S(n) = T(n)/2$. Then
$$
S(n) = \frac{T(n)}{2} = \frac{\sqrt{2T(n-1)}}{2} = \sqrt{\frac{T(n-1)}{2}} = \sqrt{S(n-1)}.
$$
Simple induction now shows that $S(n) = \sqrt[2^n]{S(0)}$, and so
$$ T(n) = 2 \sqrt[2^n]{\frac{T(0)}{2}}. $$
In particular, this shows that $T(n) \to 2$.

We can estimate the speed of convergence using the estimate
$$
\sqrt[2^n]{x} = \exp \frac{\log x}{2^n} = 1 + O\left(\frac{\log x}{2^n}\right).
$$
This shows that
$$ T(n) = 2 + O(2^{-n}). $$


Are the functions always asymptotically comparable?

Not every pair of functions is comparable with $O(\cdot)$ notation; consider the functions $f(n) = n$ and
$$
g(n) = \begin{cases}
 1 & \text{if $n$ is odd},
\\\
 n^2 & \text{if $n$ is even}.
\end{cases}
$$
Moreover, functions like $g(n)$ do actually arise as running times of algorithms.  Consider the obvious brute-force algorithm to determine whether a given integer $n$ is prime:

IsPrime(n):
  for i ← 2 to (n-1)
     if i·⌊n/i⌋ = n
        return False
  return True

This algorithm requires $\Theta(1)$ arithmetic operations when $n$ is even, $O(\sqrt{n})$ operations when $n$ is composite, but $\Theta(n)$ operations when $n$ is prime.  Thus, formally, this algorithm is incomparable with an algorithm that uses $\sqrt{n}$ arithmetic operations for every $n$.

Most of the time when we analyze algorithms, we only want an asymptotic upper bound of the form $O(f(n))$ for some relatively simple function $f$.  For example, most textbooks would simply (and correctly) report that IsPrime(n) runs in $O(n)$ arithmetic operations.  Typical upper bound functions are products of exponentials, polynomials, and logarithms (although more exotic beasts like factorials and iterated logarithms also show up occasionally).  It is not hard to prove that any two such functions are comparable.

See also this MathOverflow question.


Finding all "basic" cycles in an undirected graph?

You might be interested in a cycle basis, especially a fundamental cycle basis (which actually consists of cycles).


Brendan McKay and Adolfo Piperno have written a survey paper regarding this question in 2013. They present several efficient computer programs that canonicalize many graphs faster than you would imagine. There is no need (and no point) in implementing these algorithms yourself - they are available online, even as source code.