Is protein folding really NP-hard and how to show that? This question has two facets that are related.
Is the general problem of protein folding really NP-hard?
The hydrophobic-polar protein folding model (Ken Dill et al., 1985) stated the problem on a lattice (similar to self-avoiding walk):

Simplification significantly reduces the computational effort in handling the model, although even in this simplified scenario the protein folding problem is NP-complete.

However, this simplification takes a continuous problem which has some local convexity characteristics in real life into an integer programming problem, because protein folding resembles the problem of finding the global minimum on some continuous energy "cost function", also known as the energy landscape as illustrated by Ken Dill et al., 2012:

As stated by others, translating a problem defined over continuous domain into problems over the integers or a binary lattice may introduce higher complexity cost. You may think about it as taking a linear problem and solve it using 3SAT solver, any problem in $P$ is presumably reducible to 3SAT. I assume that there is a convex nature to the energy landscape, and this piecewise convexity is beneficial for the search for the minimal energy state.
How to reduce hydrophobic-polar protein folding to TSP/3SAT/CNF?
The work by Bahi et al. really confused me. I expected it to be something relatively simple to reduce 3SAT or TSP to the problem of protein lattice, because intuitively it seems that finding Hamiltonian path could be stated as finding a protein conformation on a lattice.

Bahi, Jacques M., et al. Computational investigations of folded
self-avoiding walks related to protein folding. Computational biology
and chemistry 47 (2013): 246-256.
Bahi, Jacques M., et al.  Chaos of protein folding. In IJCNN 2011,
Int. Joint Conf. on Neural Networks, pages 1948–1954, San Jose,
California, United States, July 2011.
Bahi, Jacques M., et al. Protein folding in the 2D
hydrophobic-hydrophilic (HP) square lattice model is chaotic.
Cognitive Computation, 4(1):98–114, 2012.
Bahi, Jacques M., et al. Is protein folding problem really a
NP-complete one ? First investigations. arXiv:1306.1372, October 2012.
Submitted to Journal of Bioinformatics and Computational Biology
(Elsevier).
Bahi, Jacques M., et al.  Unfoldable self-avoiding walks are infinite.
Consequences for the protein structure prediction problem. arXiv.org,
2013.
Bahi, Jacques M., et al. Protein structure prediction software
generate two different sets of conformations. Or the study of unfolded
self-avoiding walks. arXiv:1306.1439, 2013.

It follows immediately from the fact that protein folding is NP-hard that there exists a reduction from 3SAT to protein folding.   The definition of NP-hard says that there is a reduction from every NP problem to protein folding; and 3SAT is a NP problem.
There are papers in the literature that state that protein folding is NP-hard.  I'm not an expert on them, so I don't know to what extent they do or don't address your specific concerns, but you should be able to find them immediately and review their proof.  See, e.g.,
P. Crescenzi et al. "On the complexity of protein folding." Journal of computational biology 5.3 (1998): 423-465.
B. Berger et al. "Protein folding in the hydrophobic-hydrophilic (HP) is NP-complete." Proceedings of the second annual international conference on Computational molecular biology, pp. 30-39. 1998.
Our normal rules are to ask only one question per post.


How is the following ML Curry expression evaluated This question is not homework but it's related to material in a general course I take about programming languages, so I don't know whats the site policy about this

In ML the following expression:

fun f x y z = x (y , z) = x (z, y) ;

Evaluates to this:

val ('a, ''b) f = fn : ('a * 'a -> ''b) -> 'a -> 'a -> bool

I understand the type inference done here, but not the structure of the expression returned.

Can someone explain how this works ?

Thanks

It seems that what you are confused about is the common practice of Curryfication: the function
$$ (\alpha\times \alpha\rightarrow \beta)\rightarrow \alpha\rightarrow \alpha\rightarrow \mathrm{bool} $$

Is parenthesized as:

$$ (\alpha\times \alpha\rightarrow \beta)\rightarrow (\alpha\rightarrow (\alpha\rightarrow \mathrm{bool})) $$

and is equivalent to a different function:
$$ (\alpha\times \alpha\rightarrow \beta)\times \alpha\times \alpha\rightarrow \mathrm{bool} $$

The reason for this is the following. Take a function:

$$f:A \rightarrow (B\rightarrow C)$$
This is a function that takes an element $a:A$ and returns a function
$$ f\ a: B\rightarrow C$$
Apply this to an element $b:B$ and you have
$$f\ a\ b:C$$

It is clear that this is equivalent to a function $f':A\times B\rightarrow C$ that takes a pair $(a,b):A\times B$ and returns an element of $C$. The equivalence can be explicitely written:

curry : ('a * 'b -> 'c) -> ('a -> 'b -> 'c)
curry f' = function x -> function y -> f' (x,y)

or more simply

curry f' x y = f' (x,y)

The other direction goes:

uncurry : ('a -> 'b -> 'c) -> ('a * 'b -> 'c)
uncurry f = function p -> let (x,y) = p in f x y

or simply

uncurry f (x,y) = f x y


Minimum expected cost through an unconventional graph with probabilities at which edges are selected I'm having trouble identifying the approach to minimize the cost of reaching a certain state in an optimization problem. I've modeled it here as a game.

Problem Structure
You buy heroes and send them into a dungeon consisting of rooms containing each two challenges (random number check with a given threshold per room) that each hero can choose between (one hero completing a challenge does not allow another to skip it). The goal is to have any hero survive to the final room, and the secondary goal is to minimize the cost for doing so.

The first challenge costs a small fixed amount and success leads that hero to the next room (other heroes must complete their own challenges). The second challenge costs a medium fixed amount and if the challenge is successful, he rolls a fair 5-sided die. Anything below a 5 will move the hero to the next room. A 5 will move the hero 2 rooms ahead.

Failure on any challenge leads to the hero's death unless "divine protection" has been bought for this attempt at the chosen challenge (can only be used in the first two rooms). You can also buy a "charms" for your hero that will improve chances of success for a single attempt by various factors (1.5x, 2x, etc).

Example:

All heroes cost 300g.
The 1.5x charm costs 650g.
The 2x charm costs 1100g.
The 2.5x charm costs 2100g (but this can't be used at the same time as protection).
Divine protection for room 1 costs 2000g per challenge.
Divine protection for room 2 costs 4500g per challenge.
In the first room, challenge 1 costs 120g and has 40.5% success before charms.
In the first room, challenge 2 costs 210g (has same success rates but also 20% of successes move 2 rooms).
In the second room, challenge 1 costs 140g and has 13.5% success.
In the second room, challenge 2 costs 230g.
In the third room, challenge 1 costs 160g and has 10.% success.
In the third room, challenge 2 costs 250g.
In the forth room, challenge 1 costs 180g and has 4.1% success.
In the forth room, challenge 2 costs 270g.
In the fifth room, challenge 1 costs 300g and has 2.7% success.
In the fifth room, challenge 2 costs 390g.
The sixth room is the final room ("you win the game").

All g values can change due to market fluctuations, but I'm looking to solve the optimization problem for any snapshot in time (where we can say the costs are 'fixed' while we're calculating, but we'll have to plug the numbers in again the next time we calculate).

Question

Without the 20% chance on successes to skip a room, it can be modeled as a dynamic programming problem, but I haven't been able to figure out an approach to make that work.
What kind of approach would be appropriate for minimizing the expected cost of putting a hero in a given room?

Once you know the expected success rate for room 3 (given a certain budget), you should be able to work out the expected success rate for room 2 (given a certain budget).

In other words, let $A[r,b]$ denote the probability of success when starting at room $r$ and starting with budget $b$, using the optimal strategy.  Given $A[r+1,\cdot]$, you can compute $A[r,\cdot]$ via a simple recurrence (consider all possible things you could buy, and the probability of beating room $r$, and how much that reduces your budget when starting at room $r+1$).  This immediately leads to a dynamic programming algorithm for your problem.

If charms persist from one room to the next, use $A[r,b,c]$ where $c$ is the set of charms you already have when you start at room $r$.


Are these valid counterexamples to proofs for CF languages with Non-CF complements? Someone asked for examples of context-free languages with non-context-free complements.

The first answer says:

  The language $L_1= \{ww \mid w \in \{a,b\}^*\}$ is not context-free (as can be shown using the pumping lemma; see here).  Its complement $L_2 = \{a,b\}^* \setminus L_1$ is context-free (as shown here).

Maybe in reality this is true, but given the above information, I am not convinced this is a valid example of such a language. I have proved before that $L$ is not CF, so I have no problem accepting that. However, the CFG and proof given for $L_2$ are wrong. I can give a really simple counterexample: when the string $s=aaabaa$. Clearly $s \in L_2$ because it's not of the form $ww$. However, $s$ cannot be constructed using the CFG described for $L_2$.

Proof: The string $s$ is not of the form $A$ or $B$ since the length of the string is even. Therefore it must be of the form $AB$ or $BA$, but this is impossible because both halves of the string have the same character ($a$) in the center. Therefore $s \notin L_2$, which is a contradiction.

The second answer says:

  The example you see on Wikipedia: put $A=\{a^n b^n c^m\}$, $B=\{a^m b^n c^n\}$. It's easy to see $\overline{A}$ and $\overline{B}$ are context-free by defining a PDA; you can note that they're deterministic context-free languages, which is a class closed under complement. Therefore $\overline{A} \cup \overline{B}$ is a context-free language with a non-contextfree complement $A \cap B=\{a^n b^n c^n\}$.

This one is even easier to disprove. Sure, deterministic context-free languages are closed under complement, but they're not closed under union. Therefore, the language $\overline{A} \cup \overline{B}$ is not necessarily context free.

I am currently still taking Theory of Computing, so perhaps I've gotten something wrong or overlooked some obvious truth. Can anyone disprove my claims? If not, can you provide a valid example of a CF language with a non-CF complement?

For the first question, $aaabaa$ is generated by the grammar:
$$\begin{align*}
    S&\to AB \\
     &\to aB &&\text{using }A\to a\\
     &\to aaBa &&\text{using }B\to aBa\\
     &\to aaaBaa &&\text{using }B\to aBa\\
     &\to aaabaa &&\text{using }B\to b\,.
\end{align*}$$
Your attempt to prove the converse is incorrect because you assume that, when the string is split as $AB$, the part generated by $A$ must have the same length as the part generated by $B$. As the derivation above shows, this is not true.

For the second, you're correct that the class of deterministic CFLs is not closed under union. However, the class of CFLs is closed under union. That is, the union of two DCFLs is not necessarily a DCFL but it is definitely a CFL. The argument "$\overline{A}$ and $\overline{B}$ are deterministic context-free, so they are context-free, so $\overline{A}\cup\overline{B}$ is context-free" is implicit in the proof you quote.


Pattern classification: what goes into the sample? I am trying to compare the performance of a classification result with Bayes classifier, K-NN, Piece wise component analysis (PCA). I have doubts regarding the following (please excuse my lack of programming skills since I am a biologist and not a programmer thus finding the Matlab documentation hard to follow).

In the Matlab code

    Class = knnclassify(Sample, Training, Group, k)
    Group =  [1;2;3]   //where 1,2,3 represents Class A,B,C respectively.

What goes in the sample because my data is a 100 row 1 column for each of the classes? So Group 1 contains data like $[0.9;0.1;......n]$ where $n=100$. Would the sample be a vector containing random mixtures of the data points from the three classes? Same question for the Training matrix.

First a bit about the classifier:
The knn classifier works by majority voting. It takes an input record, finds the k nearest labeled data points, looks at the class labels on each data point and assigns the current record the most common class label. For instance, if I use a 3-NN classifier and my three neighbors are of class [1 1 2], then I will select class 1 for this record.

That being said, "Training" should contain the feature vectors of your labeled dataset (probably 1 record per row). "Group" contains the class label for the corresponding record. So the $i^{th}$ value in Group is the class label associated with the $i^{th}$ record in "Training". "K" specifies the number of neighbors you'd like to look at when classifying new objects. Lastly, "Sample" will be the data point you want to classify.

Also, I've never heard of piece-wise component analysis, do you mean Principle Component Analysis? If this is the case, just note that PCA is a method commonly used for dimensionality reduction, so you'll still have to use a classifier to get labels for your data.

One more note: Matlab has an SVM classifier as well, its calls are similar to that of the Naive Bayes classifier for training and testing.


Why doesn't my object code/machine code contain 1's and 0's I know when I compile my C program to machine code it gets compiled into something that specific computer can understand

But I thought computers can only understand 1's and 0's (high/low) so why doesn't my program look like a bunch of strange symbols and not 1's and 0's?

ie: "UHâÂHÉÏHç=7∞Ë1…âE¸â»HÉƒ]√êˇ%¶LçïASˇ%ÖêhÈÊ"

There must be one last piece I'm missing where these symbols get converted to 1's and 0's somehow

This is a result of the program that opened the file.

All files on the system are in binary. What matters is how you interpret it.

The editor you used has displayed the digits in their common form:

"UH...." is the equivalent hexadecimal "5548...."  which is binary "101010101001000...."

Thus you need a Hex or Binary editing program to 'view' the '1's and '0's.


What is the regular expression describing this language? The language is $\{w \mid \text{$w$ is any string except $11$ and $111$}\}$ where the alphabet is $\{0,1\}$.

Drawing the DFA recognizing $\{v \mid \text{$v$ is either $11$ or $111$}\}$, then switching the accept and non-accept states, and finally examining this resulting structure, I thought of it as being:

$(ϵ∪0Σ^*∪1∪10Σ^*∪110Σ^*∪111Σ^+)$

My reasoning was that it has to accept the empty string,
or a 0 followed by whatever
or just a $1$
or, if it begins with a $1$, a $10$ followed by whatever
or, if it begins with $11$, then a $110$ followed by whatever
or a $111$ followed by at least a $0$ or a $1$

Does this appear to be correct? If I'm wrong, could you please tell me why?

Thank you,

Yes, your idea is correct.
Basically here two things are happening.

Regular languages are closed under compliment operation
If L1 is accepted by DFA1 and DFA2 is obtained by interchanging the final states to non-final states and non-final states to final states of DFA1 then the language accepted by DFA2 is compliment of L1. That is, if

DFA1 is a quintuple (Q, Σ, δ , q0, F)
And L1 is language accepted by DFA1
DFA2 is (Q, Σ, δ , q0, (Q - F))
And L2 is language accepted by DFA2 Then L2 is compliment of L1.

In this case the languages L1 = {w∣w is any string except 11 and 111} and L2 =
{v∣v is either 11 or 111} are compliment o each other .
Hence your approach is correct.


Path to formal methods It is not uncommon to see students starting their PhDs with only a limited background in mathematics and the formal aspects of computer science. Obviously it will be very difficult for such students to become theoretical computer scientists, but it would be good if they could become savvy with using formal methods and reading papers that contain formal methods.

  What is a good short term path that starting PhD students could follow to gain the expose required to get them reading papers involving formal methods and eventually writing papers that use such formal methods?

In terms of context, I'm thinking more in terms of Theory B and formal verification as the kinds of things that they should learn, but also classical TCS topics such as automata theory.

In the preface of his book “Mathematical Discovery, On Understanding, Learning, and Teaching Problems Solving” George Pólya writes:

  Solving problems is a practical art, like swimming, or skiing, or
  playing the piano: you can learn it only be imitation and practice.
  This book cannot offer you a magic key that opens all the doors and
  solves all the problems, but it offers you good examples for imitation
  and many opportunities for practice: if you wish to learn swimming you
  have to go into the water, and if you wish to become a problem solver
  you have to solve problems.

I think there is no short path, especially for reaching the state of writing papers. It requires practice, a lot of it.

Some pointers:

If “limited background in mathematics and the formal aspects” means “has never conceived a proof and written it down” then something like this might be a start.

If something on the Theoretical Computer Science Cheat Sheet makes the student feel uneasy, then a refresher course of the according branch of mathematics would be advisable.

There are many  sources for mathematical writing: The lecture notes of the 1978 Stanford University CS209 course perhaps. Or this article by Paul Halmos.


Converting truth table to algebraic normal form Is there any efficient algorithm to convert a given truth table of a Boolean function to its equivalent algebraic normal form (ANF)?

I have seen that Sage has one implementation (official documentation):

sage: from sage.crypto.boolean_function import BooleanFunction
sage: B = BooleanFunction("12fe342a")
sage: B.algebraic_normal_form()
x0*x1*x2*x3*x4 + x0*x1*x2 + x0*x1*x3*x4 + x0*x1*x3 + x0*x1*x4 + x0*x2*x3*x4 + x0*x2*x4 + x0*x3*x4 + x0*x3 + x0 + x1*x2*x4 + x1*x3 + x1*x4 + x2*x3*x4 + x2*x3 + x2*x4

But, nowhere I could find the algorithm.

It would be helpful if someone kindly explains with a suitable example.

UPDATE The answer can be found here. It is copied below.

The sage source code implies that algebraic normal form is the same as the Fourier expansion of the function (over the group $\mathbb{Z}_2^n$, where $n$ is the number of input bits). You can compute the Fourier transform using the well-known FFT algorithm(s).


Regex for at least three 1's and at most four 0's The alphabet is {0,1}, express all finite strings containing at least three 1's and at most four 0's.

I've come up with a method that enumerate every possible number of 0's:

$$111^{+}+0111^{+}+1^{+}011^{+}+111^{+}01^{*}+00111^{+}+......$$
But for three 1's and four 0's this is far too complex.

Need some help.

Here is a solution for at least $a$ 1’s and at most $b$ 0’s:
$$
\sum_{a_0+\cdots+a_b=a} 1^{a_0}1^*\prod_{i=1}^b (\epsilon+0)1^{a_i}1^*,
$$
where $a_0,\ldots,a_b \geq 0$ are integers. For example, when $a=b=2$ we get
$$
\begin{align*}
&111^*(\epsilon+0)1^*(\epsilon+0)1^*+\\
&1^*(\epsilon+0)111^*(\epsilon+0)1^*+\\
&1^*(\epsilon+0)1^*(\epsilon+0)111^*+\\
&11^*(\epsilon+0)11^*(\epsilon+0)1^*+\\
&11^*(\epsilon+0)1^*(\epsilon+0)11^*+\\
&1^*(\epsilon+0)11^*(\epsilon+0)11^*.
\end{align*}
$$
With more effort, you can even create an unambiguous regular expression, that is, one which corresponds to a UFA rather than an NFA; in other words, whenever there is a sum, the corresponding languages are disjoint. As an example, here is an unambiguous regular expression corresponding to $a=b=1$:
$$
1^*+11^*01^*+011^*.
$$
Compare this to the ambiguous one constructed above:
$$
11^*(\epsilon+0)1^*+1^*(\epsilon+0)11^*.
$$
The words $1,101$ are both captured in both summands above, but in only a single summand in the unambiguous regular expression.


Selection of pivot in quicksort partitioning of Hoare and Lomuto There are two commonly mentioned partition methods:

algorithm lomuto_partition(A, lo, hi) is
pivot := A[hi]
i := lo - 1
for j := lo to hi - 1 do
    if A[j] ≤ pivot then
        i := i + 1
        swap A[i] with A[j]
swap A[i+1] with A[hi]
return i + 1

algorithm hoare_partition(A, lo, hi) is
pivot := A[lo]
i := lo - 1
j := hi + 1
loop forever
    do
        i := i + 1
    while A[i] < pivot

    do
        j := j - 1
    while A[j] > pivot

    if i >= j then
        return j

    swap A[i] with A[j]

(excerpt from Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms. MIT Press and McGraw-Hill. pp. 170–190.)

And it has been suggested that Lomuto's method is simple and easier to implement, but should not be used for implementing a library sorting method.

But why does Lomuto partitioning scheme use rightmost element(A[hi]) as pivot value and Hoare scheme use leftmost element (A[lo]) as pivot value?

It seems that there is no difference in number of comparisons or swaps and they will produce worst case behavior on already sorted arrays.

Is it just because they implemented and introduced them with rightmost element and leftmost element as pivot value respectively? Or is there a reason?

As you now correctly, every arbitrary but fixed choice of pivot is equally bad; the cases are symmetric.

The difference is probably historical and may not exist in all write-ups of the algorithms.

Note that you have to change the for-loops if you switch from hi to lo or the other way around, but that is not a conceptual difference.


To prove 4-SAT CNF is NP-complete To answer the question below,

4-SAT: Given a formula in Conjunctive Normal Form, where each clause contains exactly 4 literals, does it have a satisfying truth assignment?

I was going to prove that 4-SAT is in NP-complete. But I saw that the way to prove CNF-SAT is in NP-complete is a bit different to the way of proving 4-SAT is in NP-complete.

Is it sufficient that I just answer that question by proving 4-SAT is in NP-complete?

Thanks in advance!

In order to prove that 4-SAT is NP-complete, you need to prove that it is in NP and that it is NP-hard.

Prove 4-SAT $\in$ NP

Given an instance of 4-SAT and an answer that evaluates to TRUE, it's pretty quick to verify.

4-SAT is NP-hard

Like the comments suggested, reduce 3-SAT, which is a known NP-complete problem, to 4-SAT:

Assume that you are given an instance of 3-SAT. The goal is to convert it in polynomial time into an instance of 4-SAT in such a way that the answer is preserved.

Take each clause $(x \lor y \lor z)$ and turn it into $(x \lor y \lor z \lor a) \land (x \lor y \lor z \lor \neg a)$, where $a$ is arbitrarily set.

If any $(x \lor y \lor z)$ clause is satisfied, then $(x \lor y \lor z \lor a) \land (x \lor y \lor z \lor \neg a)$ will also be satisfied. If the instance of 3-SAT is satisfiable, then the new instance of 4-SAT is satisfiable.
If $(x \lor y \lor z \lor a) \land (x \lor y \lor z \lor \neg a)$ is satisfied, then $(x \lor y \lor z)$ must also be true because $a$ is opposite of $\neg a$. If the new instance of 4-SAT is satisfiable, then the instance of 3-SAT is satisfiable.


Orderability of Belief States in a POMDP? Consider a POMDP with integer states $1,2,\ldots,N$, where $N$ is finite. We thus have a complete order over the states.

It seems reasonable to think that belief states for this POMDP may be orderable in some partial order sense.

Does this orderability translate into any structure of the optimal policy? Anyone have any relevant literature?

Having recently worked on this topic, I can say that the answer to both of your questions is yes.

The belief states may be partially ordered for example applying the monotone likelihood ratio, or other appropriate stochastic orderings that tell when a probability mass function (pmf) $f$ -- here a belief state -- is "greater than" another pmf $g$.

Roughly speaking, if the POMDP state transition and observation models are such that the partial order is preserved on a belief update operation, structural statements about the optimal policy of the POMDP can be made. Details may be found in a recent journal paper: V. Krishnamurthy, U. Pareek, Myopic Bounds for Optimal Policies of POMDPs: An extension of Lovejoy’s Structural Results, Operations Research, 2014; available at the author's website. The article also provides a literature review on the topic where further references may be found.

Krishnamurthy and collaborators also have a paper where the MLR ordering is applied on a single line in the belief space, on which the MLR order applies to every belief state: V. Krishnamurthy, D. Djonin, Structured Threshold Policies for Dynamic Sensor Scheduling--A POMDP Approach, IEEE Trans Signal Processing, Vol.55, No.10, pp.4938--4957.


EXP-complete example Is there an explicit example of a language which is EXP-complete? Or a weaker question, i.e., is there an explicit example of a language which is proven to be in EXP but not in P? By diagonalization theorem, we know the existence of such a language but is there a construction or explicit example known till date?

Every EXP-complete problem is not in P, by the time hierarchy theorem.  Many games are EXP-complete, you can look up some starting from here.

As a concrete example (albeit not a very simple one), you can consider the problem of emptiness of the intersection of deterministic tree automata. Formally, the input consists of $n$ DFTs $A_1,...,A_n$ (deterministic automata over trees), and the problem is to decide whether $L(A_1)\cap...\cap L(A_n)\neq \emptyset$.


Can it be decided whether there exists a string accepted by a given NFA at least k ways? Can I think this way:

We can convert a NFA to a RE using GFA.

We build a series of GFAs. At each step, one state (other than start or accept) is removed and replaced by transitions that have the same effect.

So, if we can convert k REs which have different forms but accept same language, then there must exists a string that the NFA accepts along k paths.

Does that sound right?

How to prove it properly?

The idea is to use a construction very similar to the power set construction. In the usual power set construction, each NFA state has two possibilities: unreachable and reachable. In our case, each NFA state has three possibilities: unreachable, uniquely reachable, and multiply reachable. It is straightforward to carry out the construction, and I will not spell it out here. A state in the DFA is accepting if either it contains a multiply reachable NFA accepting state, or it contains at least two uniquely reachable NFA accepting states. There is a word accepted by the NFA using more than one path if the language of the new DFA is not empty. In fact, the language accepted by the DFA consists of all words accepted by more than one path.

Using the same idea, we can compute the language of words accepted by the NFA using exactly, at most, or at least $k$ paths.


Average between n numbers Is it possible to calculate the average between n numbers in a static random access array of some size in less than $O(n)$ time?
I know that the trivial approach is $O(n)$, but can I do it in less time using a data structure or a certain preparation? or both?
I am asking for hints, not a solution.

Note: The array is of some length. What and I mean by between is when given 2 indexes a and b, I have to calculate the average of the sub array $[a+1,b-1]$. And I have to keep it updated while the data structure is managed, that's why I said it was a dynamic set, in other words a random access array. I do not know of any restrictions, just asking if it's possible in less than $O(n)$.

I'll assume that you are computing the average of the elements of an array of fixed size and that you can change the value at some position at any moment. You want a data structure that supports the following two operations:

Update element at location $i$,
Query sum of elements in range [$i$, $j$].

A binary indexed tree (aka Fenwick tree) performs both in $\cal O(\lg n)$.


Common subset sum fast algorithm Suppose of I two sets of $n$ integers bounded in $[-B,B]$. The integers are $$a_1,\dots,a_n$$
$$b_1,\dots,b_n$$

I want to find if there is a common subset $I\subseteq\{1,\dots,n\}$ such that $$\sum_{i\in I}a_i=0$$$$\sum_{i\in I}b_i=0$$

This problem is $NP$-complete.

Is there a pseudo polynomial time algorithm with complexity for this problem like the regular subset sum problem on bounded integers which has an $O(B^2)$ algorithm (https://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution)?

Yes, we shall use dynamic programming and extend our subset-sum algorithm here.

Let $R(i, \ s, \ t)$ be true iff there exists a subset $K \in \{1, ...
   i\}$ such that $$\sum_{i \in K} a_i = s \quad and \quad\sum_{i \in K} b_i = t.$$

Which subproblem would then give us the result we need? $R(n, 0, 0)$!

Now, let's find a recursive relation for our subproblem in terms of smaller subproblems:
$$R(i, \ s, \ t) := [(a_i==s) \wedge (b_i==t)] \\\vee R(i-1,  \ s, \ t)\\\vee\ R(i-1, \ s-a_i, \ t-b_i) $$

where, $\vee$ is the OR operator and $\wedge$ is the AND operator.

This relation works on the inclusion-exclusion principle - either we include the $i$th index in our subset $K$ or not. But the caveat here is that if we include the $i$th index, we must include both $a_i$ and $b_i$.

If we do not include the $i$th index, $R(i, \ s, \ t)$ reduces simply
to $R(i-1, \ s, \ t).$
If we do include the $i$th index, either ($a_i$ should be $s$)  AND   ($b_i$ should be t). Or, we must have some common subset of the two sets summing to $s-a_i$ and $t-b_i$ respectively i.e. $R(i-1,  \ s-a_i, \ t-b_i)$ should be true.

For the sake of completeness, the base cases are $R(1, \ s, \ t) := (a_1 ==s) \wedge (b_1==t)$.

Edit:The runtime of the algorithm then is $O(n^3{B^2})$ (Why?), which is pseudo-polynomial too.


Proving $DTime(n^3) \subset PSpace$ It is pretty obvious that $DTime(n^3) \subseteq PSpace$, since $DTime(n^3) \subseteq DSpace(n^3) \subseteq PSpace$, but I fail to see how to find such a language $L$ so that $L\in PSpace\,\,\,$  yet $\,\,L\notin DTime(n^3) $. Can someone assist with an idea of how to find such $L$?

Hint: Use the time hierarchy theorem which shows, for example, that $\mathsf{DTIME}(n^3) \subsetneq \mathsf{DTIME}(n^4)$.


What is the significance of reverse polish notation? I teach computing to 18 year olds. After having reverse polish notation (RPN) explained to them, one asked why is it significant enough to be in the public exam. I explained the historical significance of '70s calculators, but this failed to really address the issue.
So, are there any modern practical or theoretical applications of RPN?

I've used RPN several times for rapid prototyping, e.g. of programs that have to read and interpret a user-supplied mathematical expression.

Whereas regular mathematical notation would require at least a recursive parser (think brackets, operator order, etc...), an RPN parser is basically a stack with a switch-like statement. I guess it's this combination of simplicity and expressive power that led HP to use it initially.

This is, however, usually for rapid prototyping and for convenience. I would never assume that a user can, or wants to, understand RPN.


Proving complexity of computing product of matrices If $A$ is a non-singular $n\times n$ matrix, $B$ is an $n\times p$ matrix, and $C$ is a $p\times n$ matrix (where $1\le p \ll n$), how does one prove that the complexity of $$D=A^{-1}(BC)$$ is $\frac{8}{3}N^3+2pn^2+O(n)$ flops?

I have no idea where to start. It is assumed that we do not compute $A^{-1}$ directly, but, instead, we compute the $LU$-factorization of $A$, and use $L$ and $U$ to compute the product $A^{-1}(BC)$ using the method of solving of multiple right-hand sides (whatever this means).

I would appreciate some help with this.

I'm afraid you can't.  As I mentioned in my response to your previous question:

  The complexity of a problem is the running time of the fastest algorithm for that problem.

There exist algorithms for this problem whose running time is much less than $N^3$.  As I described in my previous answer, there are much more efficient algorithms for matrix inversion (and for matrix multiplication).  I linked to algorithms for both.

Therefore, you cannot prove that the complexity is $\frac83 N^3 + \dots$ flops -- because that isn't true.

Given your pair of questions, and since you said you're not sure where to start, I would suggest you start by reviewing the following material here on this site:

What is the difference between an algorithm, a language and a problem?
How to come up with the runtime of algorithms?
How does one know which notation of time complexity analysis to use?
Is there a system behind the magic of algorithm analysis?

Then, read some material on fast algorithms for matrix multiplication and other matrix operations.  That'll be a starting point, at least.

If what you want is to understand the running time of LU-factorization of a matrix, that's a different question.  If that's your question, you should probably research that, and then post a new question, showing what research you've done.


In Minimax, how should we handle draws? A player playing the Minimax strategy should choose moves which minimise their maximum loss.

What should happen when draws can happen? Should we class the draw as a win because we aren't losing? Or should be class it as a loss because we are trying to win the game and a draw isn't a win? Or should we just class a draw as its own end point?

Minimax strategies apply to games with scores. A minimax strategy maximized the guaranteed score. Assuming that you prefer a win to a draw and a draw to a loss, you can choose three scores $a > b > c$ arbitrarily and assign them as your value in the case of a win, a draw, and a loss, respectively.


Calculate execution time from linear speedup Given an execution time $t(c_1)$ and linear speedup $s$, how do you calculate the execution time for $c_2$ processor cores?

(Assuming Gustafson's law, or in other words, $t(\infty)=0$)

My ideas:

I haven't found any references that give formulas for calculating execution time, surprisingly. However, I think you can derive a formula from the speedup equation:
$$speedup = t(1)/t(c)$$
The problem is, I'm pretty sure this is not what people are referring to when they give you a "linear speedup" factor $s$. I haven't been able to find any exact definitions on what "linear speedup" is. I can be sure that linear speedup means that $speedup$ is linearly dependent on cores. But what is the equation?

I looked at the superlinear speedup values from the introduction of this paper. The data points $(c, speedup)$ are $(2, 2.46)$, $(4, 4.68)$, and $(8, 9.59)$. From these, it would seem the formula is:
$$s = speedup/c$$
This gives $1.23$, $1.17$, and $1.20$ for $s$; since $s$ should be constant, this seems like it could be correct. Assuming this is correct, you get:
$$
t(1) = s*c_1*t(c_1)\\
t(c_2) = c_1*t(c_1)/c_2
$$
But that can't be right, can it? It's not even dependent on $s$ anymore.

Perhaps one potential problem is that $s$ is only linear for $c>1$; so maybe you cannot estimate $t(1)$ using that formula. I've thought of a way to correct for this, by devising this formula:
$$s*(c-1)+1 = speedup$$
This makes sure speedup is one for $c=1$, as you'd expect. With the modified formula, you get $1.46$, $1.23$, and $1.23$ for $s$. There is a greater variance in $s$, but not by much. So it seems like it could
be a correct model. Both models work for linear speedup of one. I tried to find more datasets of non-one linear speedup, but couldn't find any. So I can't confirm whether this model works universally. Assuming this model, we get:
$$
t(c_2) = \frac{t(1)}{s*(c_2-1)+1}\\
\text{given: } t(1) = t(c_1)*(s*(c_1-1)+1)
$$
This formula is at least dependent on $s$, as I would expect. But I feel like my corrected formula for $s$, from which this was derived, was rather arbitrary. For one thing, $s$ is undefined at $c=1$, even if it does make sure $speedup=1$. Secondly, the final equation for $t(c_2)$ is not very intuitive; given $s=.7$ you'd think $t(2)$ would get a $1.4x$ speedup, not a $1.7$ speedup.

What are your thoughts? What am I doing wrong here? What is the correct derivation?

The term you're looking for is called parallel efficiency, which is a measure of how efficiently an algorithm uses its parallel resources. And you are correct that it is:

E = parallel speedup / p

Where p is the number of processors (or cores).

Your equation for t(c_2) is still valid, when the parallel efficiency is the same for c_1 and c_2, as it's equivalent to:

t(c_1) / c_1 = t(c_2) / c_2

A parallel efficiency greater than one is truly possible. While it is observed sometimes, this is because of NUMA effects which accompany the access to more processors / cores (i.e., more of the problem fits in caches).

Also see:
https://computing.llnl.gov/tutorials/parallel_comp


Closed form of recurrence with two inputs This question comes from a relatively simple coding challenge at Codesignal, but represents an interesting CS/math puzzle. The question states:
"When a candle finishes burning it leaves a leftover. m leftovers can be combined to make a new candle, which, when burning down, will in turn leave another leftover.
You have c candles in your possession. What's the total number of candles you can burn, assuming that you create new candles as soon as you have enough leftovers?"
So the inputs are the number of starting candles and how many burned candles can be reused recursively to make new candles.
Now, I solved this with a while loop, and the loop itself just involves division and modulo math:
def candles(c, m):

    burned=c
    while c>=m:
        burned+=c//m
        c=(c%m)+c//m
    return burned

But many of the other solutions go straight to closed form (which is obviously better in terms of complexity). I tried to figure out how they were reaching this by writing out a recurrence relation, but I can't do it... Here's an example of an accepted solution:
return c + (c - 1) // (m - 1)
I was hoping someone could help me figure out what techniques are used to arrive at this solution.

The candle burning rules are as follows: if you have c>=m candles, you can remove (m-1) of them and score m points while doing so. If you have fewer than c<m candles, then you score c points and are then done.
The total number of points you can score are then the points you score at the end (c % (m-1)), and the number of points you score before then (m * (c // (m-1))).


If A is in P and B is non-trivial, then A ≤p B On wikipedia's article on Polynomial-time reduction it states:

  Every nontrivial decision problem in P (the class of polynomial-time
  decision problems, where nontrivial means that not every input has the
  same output) may be reduced to every other nontrivial decision
  problem, by a polynomial-time many-one reduction. To transform an
  instance of problem A to B, solve A in polynomial time, and then use
  the solution to choose one of two instances of problem B with
  different answers

Some looking into the history of this entry reveals a link to math.SE that was referenced as a proof at one time.

However I am still confused as to exactly how this works. I understand polynomial-time reductions but there are some specific questions I have in regards to this statement.

Is it required that A is non-trivial as stated on wikipedia? Some places seem to suggest that the requirement is only B has to be non-trivial, and A doesn't matter if trivial or non-trivial. Based on this question.
Can someone provide me a concrete example of this working. I don't quite understand how there are two instances of problem B with different answers and how it relies on problem A to choose

First, it's important to realize here that the output of a decision problem will always be "Yes" or "No." So what this is saying is basically that $B$ has at least two inputs $x,y$ where $x \in L_B$ and $y \not \in L_B$, if $L_B$ is the set (language) of all accepted inputs to $B$.

Let's let $B$ be SAT. We'll take two instances, $x = v_1 \vee \neg v_1$, which has a solution and thus is in SAT, and $y = v_1 \wedge \neg v_1$.

Let's let $A$ be the undirected graph-connectivity problem. We know that we can solve this in polynomial time using Breadth First Search.

So, given a graph $G$ as input to $A$, we'll define a function $f$:

$f(G) = x$ if $BFS(G)$ returns connected

$f(G) = y$ if $BFS(G)$ returns not connected

Clearly, we can compute $f(G)$ in linear time for any graph, since it's just a breadth-first search. Moreover, we see that $G$ is connected if and only if $f(G) \in SAT$.

The whole process is kind of trivial (in the mathematical sense), because we're basically saying "If we could solve $B$ in polynomial time, we could also solve $A$ in polynomial time". But we can always solve $A$ in polynomial time, so the whole thing is trivially true.

It holds for the same reason $P \implies \top$ is always true.


What is the novelty in MapReduce? A few years ago, MapReduce was hailed as revolution of distributed programming. There have also been critics but by and large there was an enthusiastic hype. It even got patented! [1]

The name is reminiscent of map and reduce in functional programming, but when I read (Wikipedia)

  Map step: The master node takes the input, divides it into smaller sub-problems, and distributes them to worker nodes. A worker node may do this again in turn, leading to a multi-level tree structure. The worker node processes the smaller problem, and passes the answer back to its master node.

  Reduce step: The master node then collects the answers to all the sub-problems and combines them in some way to form the output – the answer to the problem it was originally trying to solve.

or [2]

  Internals of MAP: [...] MAP splits up the input value into words. [...] MAP is meant to associate each given key/value pair of the input with potentially many intermediate key/value pairs.

  Internals of REDUCE: [...] [REDUCE] performs imperative aggregation (say, reduction): take many values, and reduce them to a single value.

I can not help but think: this is divide & conquer (in the sense of Mergesort), plain and simple! So, is there (conceptual) novelty in MapReduce somewhere, or is it just a new implementation of old ideas useful in certain scenarios?

 US Patent 7,650,331: "System and method for efficient large-scale data processing " (2010)
Google’s MapReduce programming model — Revisited by R. Lämmel (2007)

I can not help but think: this is divide & conquer, plain and simple!

M/R is not divide & conquer. It does not involve the repeated application of an algorithm to a smaller subset of the previous input.  It's a pipeline (a function specified as a composition of simpler functions) where pipeline stages are alternating map and reduce operations.  Different stages can perform different operations.

  So, is there (conceptual) novelty in MapReduce somewhere, or is it just a new implementation of old ideas useful in certain scenarios?

MapReduce does not break new ground in the theory of computation -- it does not show a new way of decomposing a problem into simpler operations.  It does show that particular simpler operations are practical for a particular class of problem.

The MapReduce paper's contribution was

evaluating a pipeline of two well understood orthogonal operators that can be distributed efficiently and fault-tolerantly on a particular problem: creating a text index of large corpus
benchmarking map-reduce on that problem to show how much data is transferred between nodes and how latency differences in stages affect overall latency
showing how to make the system fault tolerant so machine failures during computation can be compensated for automatically
identifying specific useful implementation choices and optimizations

Some of the critiques fall into these classes:

"Map/reduce does not break new ground in theory of computation."  True.  The original paper's contribution was that these well-understood operators with a specific set of optimizations had been successfully used to solve real problems more easily and fault-tolerantly than one-off solutions.
"This distributed computation doesn't easily decompose into map & reduce operations".  Fair enough, but many do.
"A pipeline of n map/reduce stages require latency proportional to the number of reduce steps of the pipeline before any results are produced."  Probably true.  The reduce operator does have to receive all its input before it can produce a complete output.
"Map/reduce is overkill for this use-case."  Maybe.  When engineers find a shiny new hammer, they tend to go looking for anything that looks like a nail.  That doesn't mean that the hammer isn't a well-made tool for a certain niche.
"Map/reduce is a poor replacement for a relational DB."  True.  If a relational DB scales to your data-set then wonderful for you -- you have options.


A "natural" decidable problem not in $\mathsf{NP}$? Are there any "natural" examples of decidable problems that are definitively known not to be in NP?  The decidable languages I know of that are not contained in NP are usually derived from the time hierarchy theorem, which produces "artificial" languages based on diagonalization.

From an answer to a related question on NP-hard problems which are not contained in NP: probably the most natural example is determining whether two regular expressions (including the Kleene star for arbitrary repetition, and a squaring operation to allow compact expressions of very large fixed numbers of repetitions) are equivalent. The resulting problem is EXPSPACE complete. Because EXPSPACE contains NEXP, which contains NP strictly (by the time hierarchy theorem), this is a decideable problem which is not in NP.


Where is the mistake in this apparently-O(n lg n) multiplication algorithm? A recent puzzle blog post about finding three evenly spaced ones lead me to a stackoverflow question with a top answer that claims to do it in O(n lg n) time. The interesting part is that the solution involves squaring a polynomial, referencing a paper that describes how to do it in O(n lg n) time.

Now, multiplying polynomials is practically the same as multiplying numbers. The only real difference is the lack of carries. But... the carries can also be done in O(n lg n) time. For example:

    var value = 100; // = 0b1100100

    var inputBitCount = value.BitCount(); // 7 (because 2^7 > 100 >= 2^6)
    var n = inputBitCount * 2; // 14
    var lgn = n.BitCount(); // 4 (because 2^4 > 14 => 2^3)
    var c = lgn + 1; //5; enough space for 2n carries without overflowing

    // do apparently O(n log n) polynomial multiplication
    var p = ToPolynomialWhereBitsAreCoefficients(value); // x^6 + x^5 + x^2
    var p2 = SquarePolynomialInNLogNUsingFFT(p); // x^12 + 2x^11 + 2x^10 + x^8 + 2x^7 + x^4
    var s = CoefficientsOfPolynomial(p2); // [0,0,0,0,1,0,0,2,1,0,2,2,1]
    // note: s takes O(n lg n) space to store (each value requires at most c-1 bits)

    // propagate carries in O(n c) = O(n lg n) time
    for (var i = 0; i < n; i++)
        for (var j = 1; j < c; j++)
            if (s[i].Bit(j))
                s[i + j].IncrementInPlace();

    // extract bits of result (in little endian order)
    var r = new bool[n];
    for (var i = 0; i < n; i++)
        r[i] = s[i].Bit(0);

    // r encodes 0b10011100010000 = 10000

So my question is this: where's the mistake, here? Multiplying numbers in O(n lg n) is a gigantic open problem in computer science, and I really really doubt the answer would be this simple.

Is the carrying wrong, or not O(n lg n)? I've worked out that lg n + 1 bits per value is enough to track the carries, and the algorithm is so simple I'd be surprised if it was wrong. Note that, although an individual increment can take O(lg n) time, the aggregate cost for x increments is O(x).
Is the polynomial multiplication algorithm from the paper wrong, or have conditions that I'm violating? The paper uses a fast fourier transform instead of a number theoretic transform, which could be an issue.
Have a lot of smart people missed an obvious variant of the Schönhage–Strassen algorithm for 40 years? This seems by far the least likely.

I've actually written code to implement this, except for the efficient polynomial multiplication (I don't understand the number theoretic transform well enough yet). Random testing appears to confirm the algorithm being correct, so the issue is likely in the time complexity analysis.

Your algorithm is very similar to Schönhage–Strassen. In the FFT step, there are large numbers involved - as you mention, their size can be up to $O(\log n)$. Arithmetic on them doesn't come for free. You need to apply the construction recursively, and you'll lose something.


Computing snapshot of Turing machine from previous snapshots in logarithmic space? To prove that $P \subseteq P_{\ poly}$ [see book by Arora and Barak, chapter 6, page no 105]

Proof : Let $M$ be an oblivious TM and running time is $T(n)$, let $x \in \{0,1\}^* $ be some input for $M$ and define the transcript of $M$'s execution on $x$ to be the sequence $z_1,z_2,..z_{T(n)}$ of snapshots (the machine's state and symbol read by all heads) of the execution at each step in time.

We can encode each such snapshot $z_i$ by a constant-sized binary string, and furthermore, we can compute the string $z_i$ based on input $x$, the previous snapshot $z_{i-1}$ and snapshot $z_{i_1},z_{i_2},\cdots ,z_{i_k}$, where $z_{i_j}$ denotes the last step that $M$ 's jth head was in the same position as it is in the ith step.

The composition of all these constant-sized circuits gives rise to circuit that computes from the input $x$ the snapshot $z_{T(n)}$. This requires polynomial space, but I want to do this whole computation in logarithmic space.

My question : How to compute snapshot $z_i$ of Turing machine $M$ from previous snapshots using logarithmic space?

What you seem to be asking is what is the complexity of computing each bit in the sequence of snapshots. The complexity depends on the way you encode the snapshots. Here are a few options:

Encode the state of the machine, the position of the head, and the tape. Computing a bit of the tape requires knowing whether the head is currently at that position or at a neighboring position. Since in general a polytime machine has a polysize tape, this requires circuits accessing $\Theta(\log n)$ inputs.
Encode the state of the machine and the tape, where the tape alphabet is enlarged to include another bit, signifying whether the head is at that position or not. Now each tape bit only depends on a constant number of bits. However, determining the next state is (still) very costly, since we need to know the value under the head.
Encode the state of the machine and the tape, where the tape alphabet is enlarged to include the "head bit" as well as the symbol currently under the head. Now each bit indeed depends only on a constant number of bits.

Of course, given any formula, we can always convert it to a 3CNF using auxiliary variables without blowing it up by too much. What I outline above is a particular way of doing this transformation in the case at hand.


Haskell type classes as ontological categories A paper uses Haskell type classes to represent ontological categories.
A type class hierarchy is used to represent "concept hierarchies" where "functions are the units of inheritance". Here is a diagram of the Haskell type classes based on the paper:

With respect to the code below the following claim is made:

The Haskell code given so far is complete and type checked, explaining
the entire refined concept hierarchies. With instantiations for types
of boathouses and houseboats, values can be declared and axioms stated
and evaluated to demonstrate semantic properties and differences. For
example, it can be shown that a passenger on a boat in a boathouse
cannot be said to be an inhabitant, while a passenger on a houseboat
can.

The spatial prepositions in and on form part of the semantics the whatsIn and whatsOn predicates in the code below.
I have a three  questions:
(Q1) Is the claim true?
(Q2) How would go about validating such a claim.
As regards Q2, I have create 72 instances with appropriately kinded data types   as advised by the GHCI compiler (not supplied in this post).
Then I checked the types with the following type level queries

Query 1 :  A passenger on a boat in a boathouse cannot be said to be
in the boathouse  (i.e. an inhabitant)

:t whatsIn (BoatHouse (Boat People)) =t=> OK whatsIn (BoatHouse (Boat People)) :: [Boat People]
:t whatsOn (HouseBoat  People) =t=> ERROR  No instance for (Surfaces BoatHouse (Boat People))

Query 2 : A person can be both on and in a houseboat (a passenger and an inhabitant).

whatsOn (HouseBoat  People) :: [People]
:t  whatsIn (HouseBoat  People)  =t=> whatsIn (HouseBoat  People) :: [People]
:t  whatsOn (HouseBoat  People) =t=> whatsOn (HouseBoat  People) :: [People]

(Q3) Both these queries seem to be apptropriately accepted and rejected by Haskell. Is there a better or easier way to validate this claim?
Listing 1 shows the source code from paper.
class Containers a b where
 insert :: b -> a b -> a b
 remove :: b -> a b -> a b
 whatsIn :: a b -> [b]

class Surfaces a b where
 put ::  b -> a b -> a b
 takeOff :: b -> a b -> a b
 whatsOn :: a b -> [b]

class Paths a b c where
 move :: c -> a b c -> a b c
 origin, destination :: a b c -> b
 whereIs :: a b c -> c -> b

class PeopleClass p
class HeavyLoads l
class Surfaces w o => WaterBodies w o
class Containers h o => Houses h o
class (Surfaces v o, Paths a b (v o)) => Vehicles v o a b
class (Vehicles v o a b, WaterBodies w (v o)) => Vessels v o a b w
class (Vessels v p a b w, PeopleClass p) => Boats v p a b w
class (Boats v p a b w, HeavyLoads p) => Barges v p a b w
class (Houses h (v p), Boats v p a b w, Contacts w (h (v p))) => BoatHouses h v p a b w
class (Barges v p a b w, Houses v p, PeopleClass p) => HouseBoats v p a b w

The code in Listing 1 represents my attempt to test the claim. I have simplified the classes, while retaining that ability to test the original claim, which is repeated here:
The Haskell code given so far is complete and type checked, explaining the entire refined concept hierarchies. With instantiations for types of boathouses and houseboats, values can be declared and axioms stated and evaluated to demonstrate semantic properties and differences. For example, it can be shown that a passenger on a boat in a boathouse cannot be said to be an inhabitant, while a passenger on a houseboat can.
Here is the simplified class hierarchy:

If we interpret an inhabitant as being directly in the boathouse then the claim is somewhat reasonable. This is because in Listing 1 whatsIn is not defined for type BoatHouseD, attempting to evaluate in GHCi:
whatsIn (BoatHouseDc (PeopleDc "joe"))

will cause error. In general, if a function is not defined for a data type that function will fail to type check. Note whatsIn is defined in an instance of ContainersC class for the type BoatD  and also defined in an instance of ContainersC class for the type BoatHouseD.  whatsOn  is defined for an instance of SurfacesC. These functions cannot be defined in the sub-classes  HousesC, BoatHousesC, and HouseBoatsC of ContainersC or BoatsC, BoatHousesC, and HouseBoatC of SurfacesC.
On the other hand the semantics of the Haskell code can be used to refute the claim. The test in Listing 1 shows that if someone is on a boat and that boat is in a boathouse then they are indirectly in the boathouse.
Conclusion
Based on the Haskell code in Listing 1 we can refute the claim. Reasoning about the Haskell code there is some credibility in the claim. The sub-classes seem to be redundant, because functions can only be defined in instances of the class where they were originally declared, not in any sub-class of that original class. So the functions whatsIn and whatsOn cannot be defined for the sub-classes.
Listing 1
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-#  OPTIONS_GHC  -Wno-missing-methods #-}
 -- The suffix D=data type,Dc=constructor
 -- The data types were chosen to match the type variables in the type classes
            data PeopleD = PeopleDc [Char] deriving (Show,Eq)
            data BoatD a  = BoatDc a deriving (Show,Eq)
            data HouseBoatD a  = HouseBoatDc a  deriving (Show,Eq)
            data BoatHouseD a  = BoatHouseDc a deriving (Show,Eq)

            class ContainersC a b where -- suffix C= class
             insert :: b -> a b -> a b
             remove :: b -> a b -> a b
             whatsIn :: (a b) -> [b]

            class SurfacesC a b where
             put ::  b -> a b -> a b
             takeOff :: b -> a b -> a b
             whatsOn :: (a b) -> [b]

            class PeopleC p
            class ContainersC h o => HousesC h o
            class (SurfacesC v o) => BoatsC v o
            class (HousesC h (v p), BoatsC v p) => BoatHousesC h v p
            class (BoatsC v p, HousesC v p, PeopleC p) => HouseBoatsC v p

            instance ContainersC BoatD PeopleD where
               whatsIn (BoatDc (PeopleDc x)) = [PeopleDc x]

            instance ContainersC BoatHouseD (BoatD PeopleD) where
                whatsIn (BoatHouseDc (BoatDc (PeopleDc x))) = [(BoatDc(PeopleDc x))]

            instance SurfacesC BoatD PeopleD where
               whatsOn (BoatDc (PeopleDc x)) = [PeopleDc x]

             test =  (head (whatsOn(head (whatsIn (BoatHouseDc (BoatDc (PeopleDc "joe"))))))) ==
                  (head (whatsOn(BoatDc (PeopleDc "joe"))))


Solving Subproblem in Logic (first-order, propositional, pddl) One sentence question

Is there any algorithm able to prove (solve) a logic problem (first-order, propositional, pddl) by finite induction?

Background

I am researching Hierarchical planning solvers and I found the following problem.
Let a problem climb a stairway. An agent is able to move up or down. For example, suppose the following "move up" action:

moveup(position):
    pre-condition: on(position)
    post-condition: ~on(position) ^ on(next(position)

Now, let a stairway be defined as:

stairway:
   next(first_step) = second_step
   next(second_step) = third_step
   ...
   next(nminusoneth_step) = nth_step

and, a start point from agent is on the first step:

on(first_step)

Now, I want to create a plan to bring the agent from the first step to last one.
Of course, I can solve that in many different ways (brute force for example), but I know how to climb an one-step stairway (just move up) so, I am able to infer that all I need to climb an n-step stairway is just moving up (it is not necessary to decide each action individually). Is there already any algorithm for that (recognize a subproblem structure and infer actions by induction)?

In general, using mathematical induction to prove theorems automatically is quite difficult. First, note that this isn't really a problem of first-order vs second-order logic, since induction can easily be expressed as a schema in FOL, and generally be reduced to a finite set of axioms. It's more useful though to keep it as a schema, and add induction as a logical rule rather than a list of axioms.

This has been studied quite a bit, but success of general purpose automatic theorem provers is somewhat limitied in the presence of induction, for the following reasons:

(Of course) the first order (quantifier free) theory with induction is undecidable. A good milestone of how undecidable a theory is is to measure how expressive the resulting theory is, and the theory with induction is essentially capable of expressing a large part of elementary mathematics quite easily. This is a pretty bad sign.
Induction is always applicable: any goal which contains some occurrence of an inductive data type (like a list or a natural number) may be proven (indeed, may need to be proven) by induction. Clearly there needs to be a clever heuristic to decide when to apply induction. The general rule is: do everything but induction, and apply induction as an absolute last resort! Even with this heuristic, you need to know when to give up, which is again undecidable, but necessary if any kind of backtracking is to be performed.
Sometimes the goal needs to be generalized. This is a distinctive phenomenon of induction, that sometimes the induction hypothesis is too weak to prove the conclusion, and as a result the whole goal needs to be strengthened, which is rather counter-intuitive (failure to prove a goal results in trying to prove a stronger one!). Finding and proving these strengthenings automatically is the subject of exciting current research in computer science (in the field of loop invariant synthesis).

Given all these difficulties, it's clear there's no general purpose algorithm for proving theorems by induction in full generality. However the problem itself is being actively studied, and I'll just leave you with this link to a workshop specifically addressing this problem.

As a footnote, your problem doesn't seem to be solvable with much else than standard "brute force" (or resolution), since the algorithm needs to verify that the last step is reachable by explicitly going through all the steps. Unless you have further knowledge (e.g. each step corresponds to a natural number), you need to verify that each step can be taken, and that there are no "breaks".


Is this a correct approch of finding expected runtime of an algorithm? Consider two algorithms; we analysis their run time only by counting the number of comparisons

TwoMax1(A):
     S = negative infinite
     L = negative infinite
     loop through the array A
         if A[i] > L:
             S = L
             L = A[i]
         else
            if A[i] > S
                S = A[i]
    return (L,S)

 TwoMax2(A):
     S = negative infinite
     L = negative infinite
     loop through the array A
         if A[i] > S:
            if A[i] > L:
             S = L
             L = A[i]
            else
                S = A[i]
    return (L,S)

Here is my approach for the first algorithm:

(1) define our sample space. Since the returned output is a pair, maximum and second maximum could be anywhere in the array. For each maximum, there are $(n-1)$ possible index for second maximum, and we have $n$ possible index for the maximum value; So sample space: $S = \{(A[0],A[1]),(A[0], A[2]),(A[0],A[3]),\dots\}$ and so on.

Define an indicator $I_i = 1$ iff $A[i] > \max \{A[0], A[1], \dots, A[i-1]\}$.

The total expected comparison of comparing to maximum would be $$\mathbb{E} (\sum_{i=0}^n I_i) = \sum_{i=0}^n \mathbb{E}(I_i) = \mathrm{Prob}(A[i] > \max \{A[0], A[1],\dots, A[i-1]\}) = \frac{n+1}{2}.$$

where $$\mathrm{Prob}(A[i] > \max \{A[0], A[1], \dots, A[i-1]\}) = \frac{i}{n}$$ because under the sorted array, we have $\frac{i}{n}$ chance of choosing a integer that greater than $A[0], A[1],\dots,A[i-1]$.

Now similar, the total expected comparison of comparing to second maximum would be same; and we sum two parts together up is $n+1$.

Is this a good way of approaching? If so, I also want to know some other ways of doing it, for example, define a different random variable to solve the second function.

First of all, notice that in TwoMax1, $A[i]$ is always compared to $L$. This already gives you $n$ comparisons. If $A[i]$ is not the current maximum, then it is compared to $S$. This happens with probability $1-1/i$ (see below). Therefore the total expected number of comparisons is
$$
n + \sum_{i=1}^n \left(1 - \frac{1}{i}\right) = 2n - H_n = 2n - \log n - \gamma + O\left(\frac{1}{n}\right).
$$

In TwoMax2, $A[i]$ is always compared to $S$. Again, this gives you $n$ comparisons. If $A[i] > S$, which happens when $A[i]$ is one of the two maximal elements, then $A[i]$ is compared to $L$. When $i = 1$, it is always the case that $A[i] > S$, and otherwise it happens with probability $2/i$. Therefore the expected number of comparisons is
$$
n + 1 + \sum_{i=2}^n \frac{2}{n} = n + 2H_n - 1 = n + 2\log n + \gamma - 1 + O\left(\frac{1}{n}\right).
$$

The second algorithm thus makes roughly half as many comparisons than the first algorithm.

You mention that the sample space consists of all outcomes. But in fact, the sample space consists of all inputs, or in your case, all input permutations. You are analyzing the algorithm with respect to the uniform distribution over this sample space.

Also, the probability that $A[i] > A[1],\ldots,A[i-1]$ (numbering elements from zero) is not $i/n$ (consider for example the case $i=1$!) but rather $1/i$. The reason is that if $A[1],\ldots,A[n]$ is a random permutation then $A[1],\ldots,A[i]$ is a random permutation of $\{A[1],\ldots,A[i]\}$. In particular, $A[i]$ is a random element of $\{A[1],\ldots,A[i]\}$, and so it equals the maximum with probability $1/i$.


Optimal scheduling order for two queues of jobs I have two queues of jobs and each job consists of the pair (utilization %, time to complete). I have one machine and its utilization cannot exceed 100%. The first job in a queue must be completed before the second one can be started (and so on). What is an algorithm to find the best schedule for these jobs so that the total time is minimized?

There is a simple pseudo-polynomial time algorithm that works when all tasks take the same unit time. You can transform your problem into this by rounding all completion times to some greatest common divisor, and splitting all longer tasks up into copies of unit portions. E.g. if your original completion times were $6$, $8$ and $12$ seconds you could use $2$ seconds as your unit time. Then you'd have respectively 3 copies, 4 copies and 6 copies of the unit task in a row.
Let's name the two queues $A$ and $B$. Let $T[i,j]$ be the optimal time needed to run the first $i$ tasks from $A$ and the first $j$ tasks from $B$. Let $A[i]$ be the resources required for task $i$ from $A$ and similarly for $B$. Let $m$ be the maximum number of resources available.
Of course $T[x,0] = T[0,x] = x$. Then:
$$T[i,j] = 1 + \begin{cases}T[i-1, j-1] & \text{if }A[i] + B[j] \leq m\\\min (T[i-1,j], T[i,j-1]) &\text{otherwise}\end{cases} $$
If you keep track of your choices you can reconstruct the optimal solution. The above is also amenable to bottom-up dynamic programming, in fact you only need to have two arrays $T_i[j]$ and $T_{i-1}[j]$.

I'm not claiming the above is terribly good or an optimal solution, but it's a simple algorithm that gets the job done. Perhaps someone else has a better answer.


Is O(mn) considered "linear" or "quadratic" growth? If I have some function whose time complexity is O(mn), where m and n are the sizes of its two inputs, would we call its time complexity "linear" (since it's linear in both m and n) or "quadratic" (since it's a product of two sizes)? Or something else?

I feel calling it "linear" is confusing because O(m + n) is also linear but much faster, but I feel like calling it "quadratic" is also weird because it's linear in each variable separately.

In mathematics, functions like this are called multilinear functions. But computer scientists probably won't generally know this terminology. This function should definitely not be called linear, either in mathematics or computer science, unless you can reasonably consider one of $m$ and $n$ a constant.


Explaining SAT to high school science teachers I am a high school sophomore who is interested in computer science. I developed a cool algorithm for #SAT, and I'm implementing and doing a science fair project on it. My adviser, who is the best science teacher at my school and is also the AP Comp Sci teacher, told me that she has absolutely no idea what my project is about, and that I need to be able to briefly explain her why #SAT is important in under 5 minutes. I told her SAT reduces to #SAT and tried to explain why SAT is important: I gave her some examples of NP problems, explained her how problems in NP reduce to SAT, and explained how with binary search you can reduce certain optimization problems to SAT, which allows you to fold proteins and make powerful AI models. Unfortunately, she didn't understand me at all. Could you give me a few pointers?

P.S. My adviser asked me what useful problems reduce to #SAT that don't reduce to SAT (assuming some problems in #P are harder than their corresponding NP versions). All I could come up with was finding how many models for a given data set are better than a given model (assuming each parameter of the model is smaller than a given number of bits). I looked for other ones on the web but I couldn't find anything I could understand. Are there any other good applications?

The permanent is #P-complete, even when restricted to $\{0,1\}$-valued matrices. The permanent can be used to compute certain parameters in statistical mechanics, see for example this paper on the dimer covering problem. Since I'm not a physicist, I cannot comment on whether these theoretical statistical mechanics problems are really useful; I suspect that they are not directly useful, but the area itself could lead to useful insights. It could also be the case that some of these parameters are useful on their own, but you'll have to consult with an expert.
Your 5 minute pitch could go something like this:

Statistical mechanics is a beautiful and deep part of physics and chemistry which studies how the emergent behavior of large systems results from microscopic physical laws operating on individual elements. It explains phenomena such as the laws of gasses, magnetization, and transitions between different phases of matter. Statistical mechanics is intimately connected to probability theory, computer science, operations research, and data science.
Many important quantities in statistical mechanics can be formulated as instances of #SAT. An algorithm for solving #SAT exactly or approximately can thus be used to predict physical and chemical phenomena.

This might somewhat overstate the case, but that's how sales pitches go.


Deriving the exact number of execution times So I'm studying for my data structures midterm and my professor gave out a sample midterm with the answers, but I'm having a hard time understanding one of the questions.

Here's a screen cap:

The answer is n^2(n+1)/2.

I would appreciate a very simple walk through and/or a pointer to some good material.

Hint: Summation. Also note you can optionally reorder the (non-dependent) loops.

Spoiler (mouse over):

   So what you normally do: the inside of a nested loop will run the $\text{number of loops of the outer loop} \times \text{the number of loops of the inner loop}$. It can also be done with repeated addition of the number of loops of the inner loop (after all multiplication can be done with repeated addition). In this case, one of the inner loops is dependent on the outer loop, so you can't just multiply them. You must add it more "manually". If you do this, you will see something like this: $ 1 + 2 + 3 ... n $, this can be done with summation, which in this case $\sum_{i=1}^n i = \frac {n\cdot\left(n+1\right)} {2}$. And multiplying the additional $\#n$-loop loop (you can reorder $k$-loop to the outside to make this simpler, after that you can calculate the two inner-loops, $i$ and $j$) , you get $n\cdot\frac {n\cdot\left(n+1\right)} {2} =\frac {n^2\cdot\left(n+1\right)}{2}$.

 So step by step:

 1. First let's decide the two outer loops: the outer loop, $i$ will run $n$ times.

 2. The $j$ loop will run $1...i$ each time. The first time it will run $1$ time, then $2$ times, then $3$ ... finally $n$ times, totaling $1 + 2 + 3 + ... + n$ times. That means the $j$ loop will run a total of $\frac{n\cdot\left(n+1\right)}{2}$ times, after calculating the summation (see linked wikipedia page on summation).

 3. For each time the $j$ loop runs, the $k$ loop will run $n$ times, thus we simply multiply the summation result by $n$ for $\frac{n^2\cdot\left(n+1\right)}{2}$.


How to reduce this regular expression into DFA $(a(aa|b)^*ab|b)((ba|a)(aa|b)^*ab|bb)^*((ba|a)(aa|b)^*)^*|a(aa|b)^*$

I know long algorithmic procedures but since regex is large I tried a lot by substituting common patterns for some regex definition but didn't seem to help.

What can be done so that this regex can be converted to DFA easily.

What can be done so that this regex can be converted to DFA easily?

Algorithmic methods are doomed, if you insist on a DFA. Your regular expression contains about sixty characters. Roughly speaking, any procedure for converting to an automaton is going to produce at least one state per character of the regular expression. That means you're going to end up with an automaton with at least sixty states, and it's probably going to be nondeterministic. Determinizing that naïvely is going to give you $2^{>60}$ states, which isn't quite as many as the number of atoms in the earth, but it's still an unmanageably huge number.

Do you really need a DFA? If, for example, you're trying to write a program that will accept strings that match this regular expression, it's straightforward to check if an NFA accepts a particular string: just scan along the string keeping track of the set of states the automaton could be in after each successive character. For a fixed automaton, this can be done in linear time.

If you do need a DFA, you're going to have to figure out what the regular expression does. Break it into chunks.  $(a(aa|b)^∗ab|b)$ matches $b$, along with all strings that have an even number of $a$s, begin with $a$ and end $ab$. It's not too difficult to see that this language is matched by the following automaton (I've omitted a trap state that's reached if any character is read from state $q_3$):

If you stare at that for a moment, you'll realise that states $q_0$ and $q_2$ are the same (both say "if $a$, go to $q_1$; else, go to $q_3$") so we can reduce the automaton to the following.

You could also use algorithmic state-minimization techniques to avoid having to notice things like this.

You can probably produce similar automata for the various "top-level" chunks of the regular expression, and chain them together to get a DFA for the whole thing.


Turing machine that increments a binary number by 1 I was asked to construct a Turning Machine that computes the increment of a binary string by 1- The Turing Machine receives a binary string and accept a string which is an increment by 1 of the input, written to the left of the head . I was given the fact that the head first reads the MSB.

I thought of an Idea but I do not see how to put it into action:
My idea was to:

1.First put a $ sign at the beginning of the string

2.Place the entire string right side to it

3.Starting to increment from the end, switching $1$ with $0$

4.Once I stumble upon $0$ I replace it with $1$ and then accept it or Once I stumble upon $ I replace it with  1 and accept

I can't seem to find a way to put a $ at the beginning of the string without losing any information..any help with will be very helpful!

Hint: First write an informal description of the machine, then give a precise description as a transition diagram. Use the state of the Turing machine to hold the carry bit.


Reduction function from A to its complement I wanted to ask a simple question.

Lets say we have A, language of all the words with more then 3 letters. so it belongs to R.

and its complement , is the language of all words with less then 3 letters.

is it possible to say that I can define a turing reduction between them?

i thought about something like this:
$$
f(x) = \begin{cases} 01 & \text{if }x \in A, \\ 1234 & \text{ } else.\end{cases}
$$

my friend is saying this solution is not good since, the definition is:
$\qquad\displaystyle x \in L_2 \iff f(x) \in L_1$

and what i got is

$\qquad\displaystyle x \notin L_2 \iff f(x) \in L_1$

If in this case it wont work can you explain me why?
Thank you!

This is true for any recursive language $A$ different from $\emptyset$ and $\Sigma^*$ for some finite alphabet $\Sigma$. Your definition is correct. In general you could define $f$ as following. Let $a\in A$ and $\overline{a} \in \overline{A}$.

$$f(x)=
\begin{cases}
      \overline{a} & x\in A \\
      a & x\notin A
\end{cases}
$$
From this definition it follows $x \in A \iff f(x) \in \overline{A}$. Moreover, since $A$ is recursive $f$ is computable for any $x$ and hence $A \leq_T \overline{A}$.

The whole point is to decide $x \in A$ by using $f(x)$ and $\overline{A}$. So, given $x$ you can effectively say whether or not $x \in A$ only by looking at if $f(x) \in \overline{A}$. If $f(x) =\overline{a} \in \overline{A}$ then $x$ is in $A$, otherwise $x$ is not in $A$. Hence $A \leq_T \overline{A}$.


Why can we not find the generally superior machine learning algorithm in practice? TL;DR Our mind is a superior meta-machine learning algorithm, it can figure out tradeoffs in a much more general case than any machine learning algorithm we have. Furthermore, its Kolmogorov complexity is 4MB or less, and thus should be fairly easy to discover. However, despite our best efforts, no algorithm we've discovered has even approached this meta-capability. Is there a CS grounded explanation for this?  The NFLT is not applicable because it does not apply in practice, and the human mind is an instance of said meta-algorithm.

There are many machine learning algorithms.  The no free lunch theorem (NFLT) says, in theory, all these algorithms are exactly equal according to an error function over all possible problem domains.  In practice, this doesn't matter because we are only dealing with a very small subset of these problem domains.

In practice, this often involves a tradeoff between multiple objectives.  Making a problem multi-objective instead of single objective often causes it to become much more complex and difficult.  There is no longer a single best solution, but there are still better and worse solutions.  One way of describing the set of better solutions is with the notion of "Pareto optimality," which is the set of solutions that dominate all other solutions in all objectives, but do not dominate each other.  These optimal solutions describe a surface in a graph of the solutions known as the "Pareto front."  The following Figure is an example of a Pareto front where solutions A-H dominate all other solutions, but not each other.

That being the case, if we ask "what is the best ML algorithm?" we cannot say "None, b/c NFLT," since we are asking about the best ML algorithm in practice.  If the NFLT does not matter in practice, then there must be a best ML algorithm, in practice.  If there is a set of algorithms that describe the Pareto front, then the best algorithm is any member of this set.

What is this best practical algorithm?  There does not seem to be one, to the best of our knowledge.  Even "magical" general ML algorithms such as deep learning or extreme boosting have many knobs to twiddle, and are only good for the right kind of problem.  There is no one size fits all ML paradigm.

Yet, there must be one, since data scientists are able to match the right algorithm to the right problem and achieve outstanding results, such as Google's search capabilities.  Whatever it is that powers the data scientist brain must be relatively simple, since human DNA can be compressed to 4 MB, not much bigger than, and often quite smaller than, many ML frameworks when zipped.

Furthermore, the data scientist brain algorithm is an extremely powerful program.  For a binary prediction problem of $N$ predictions, there are $2^N$ different possible predictions.  To be right more than half the time, we need to eliminate more than $2^{N-1}$ possibilities.  We also have to do this in polynomial time.  Both feats seem astounding for any reasonably sized $N$, especially since so many important problems are NP-Complete or worse in the general case.

Since we aren't dealing with a halting problem (data scientists reliably halt on good solutions), even some kind of assisted enumeration of 4MB programs in a Turing complete language would seem to hit on this master algorithm sooner or later.

Is there a CS explanation for this discrepancy, or flaw in my reasoning, that the super powerful and extremely quick master algorithm is <= 4MB, yet despite all our searching we've been unable to find it?

There are many dimensions that "intelligence" could potentially be measured on.  We already know of some artificial intelligence schemes that do better than humans on some dimensions.

It's true that we don't have artificial intelligence schemes that do better than humans, on the sorts of problems that tend to arise in practice as part of everyday human life and experience.  On the other hand, humans have had hundreds of millions of years to evolve and adapt.  Artificial intelligence has only been around for maybe half a decade.  That might be one possible explanation.

Separately: The question seems to be based on several misconceptions.  Let me point out a few things you've written, and try to clarify the misconceptions:

  The point is that our mind is a superior algorithm, it can figure out tradeoffs in a much more general case than any machine learning algorithm we have.

Our mind is better for some tasks, but not all.  There are other tasks where machines are better.  For instance, machines are superior at chess, or at adding up small integers billions of times in a row without making a single error.  Humans are superior at making other people laugh, cry, or feel better about themselves, or at folding laundry.

For instance, machines can solve Connect Four perfectly, but most people can't.  Thus, if we allow "performance at Connect Four" as one of the dimensions that we're measuring Pareto-optimality at, machines are Pareto-optimal: they dominate humans in at least one dimension.

Now what you're probably really asking is, why do humans dominate machines in most dimensions?  But to make that question well-defined, we have to define what is the set of all dimensions.  What's probably implicit in that question is the assumption that you mean "the set of all dimensions we (humans) care about", or "the set of all dimensions that are meaningful to us (humans)".  Now consider that the human brain has had hundreds of millions of years to evolve and get better at the dimensions that humans care about or that matter to us, whereas artificial intelligence hasn't.

  Furthermore, its Kolmogorov complexity is 4MB or less, and thus should be fairly easy to discover.

Actually, no, that doesn't follow.  Let's suppose for the sake of argument that an entire human organism can be described in 4MB of data (after compression; let's not quibble about whether that's actually biologically correct; and let's not worry about the fact that Kolmogorov complexity is primarily meaningful in an asymptotic sense, and ignore those issues), or equivalently, 32 megabits of data.

That means that a program that behaves like a human would require 32,000,000 bits of data to describe.  So, you're asking: Why is it hard to find such a program?  Perhaps implicit in your question is: How many programs can there be?  How hard can it be to find the right one?

The answer is: it might be very very hard.  There are $2^{32,000,000}$ possible programs (of that length).  That's an enormously large space -- and it's a space where maybe all but one of them are useless, and only one is any good.  Trying all of the possibilities is way beyond feasible: like, you couldn't do it within the lifetime of the universe, even if you imagine a universe full of supercomputers, where each atom in the known universe has the computational power of one of today's supercomputers.  $2^{32,000,000}$ is an unimaginably large number.

So, it shouldn't be such a great surprise that it might be hard to find an example of such a program explicitly.  Just because we know that it exists doesn't make it easy to find such a thing.

For instance, even if space aliens had landed 150 years ago and told us that there exists a proof of Fermat's last theorem, it still would have taken close to 150 years to find the proof.  Just knowing that a proof exists doesn't really help you in finding it.  I bet that the Latex source file for the papers that prove Fermat's last theorem correct could be compressed to less than 4MB.  Even if I tell you that there exists a proof whose Kolmogorov complexity is at most 4MB, it's still not at all easy to find that proof.


Why we can't have FPTAS for strong NP complete problems I understood that we can apply FPTAS to the weak NP problems like 0-1 knapsack.

But why we cant apply the same principle to the strong NP problems like bin packing? I also checked wiki page about the same but understood very less.

If there were an FPTAS for some strongly NP-complete problems then you could use the FPTAS to solve them in polytime. Consider for example bin packing. If the solution is of order $V$, then the input size is of order $V$. Therefore a $1-1/V$-approximation can be achieved in polytime, and since the answer is an integer, such an approximation actually gives the optimal answer. I'll let you work out the details.


Algorithms to convert 2D videos to 3D ones Are there published algorithms that can convert 2D videos to 3D ones? If there are few published algorithms for this I am also interested to know how the conversion quality is.

Sure, there are many algorithms for this:

Some works, which directly work on H264 domain, such as:

  Real-Time 2D to 3D Conversion from H.264
  Video Compression, Nir Shabat, Gil Shabat and Amir Averbuch
  http://www.cs.tau.ac.il/~amir1/PS/3d.pdf

Some deep learning methods already exist on the topic:
http://homes.cs.washington.edu/~jxie/pdf/deep3d.pdf
(this is the review version of the paper, so I could not cite)
There are many other works which use images in many ways to create 3D:

http://live.ece.utexas.edu/publications/2011/cao_mag_2011.pdf

https://people.mpi-inf.mpg.de/~pdidyk/papers/2D-to-3D/2D-to-3D.pdf


Solving a multivariate equation for asymptotic complexity I have a function $f(m, n)$ with time complexity $T(m, n)$ characterized by the recurrence relation

$$\begin{align}
T(m,\ n) &= 2T\bigl(\frac{m}{2}, \frac{n}{2}\bigr) + c_0 \log n + c_1.\\
T(m,\ 1) &= T\bigl(\frac{m}{2}, 1 \bigr) + c_1 \\
T(0,\ n) &= 1 \\
T(m,\ 0) &= 1
\end{align}$$

I can see that for fixed $m$, this is $O(n)$, and for fixed $n$, this is $O(m)$. But I don't see how I can get an expression that characterizes the performance in terms of variable $m$ and $n$.

How can I solve this to find the asymptotic complexity in terms of $m$ and $n$?


What is an instance of NP complete problem? I don't understand this definition of an "instance" of a problem.  Quoting from the CLRS book on page 1054 on abstract problems (Chapter 34.1):

  We define an abstract problem $Q$ to be a binary relation on a set $I$ of problem instances and set $S$ of problem solutions.

Other answers are good, I'll give only another trivial example:

problem: "given two numbers $k,n$ with $1 < k < n$, does a number $m$ smaller or equal than $k$ exist such that $n$ is divisible by $m$ ?"
the instances of the problem (or informally the input of the problem) are all the valid pairs $(k,n)$ such that $1 < k < n$; so $I = \{ (2,3),(2,4),...,(3,4),(3,5),...\}$
the set of solutions is the set $S = \{ YES, NO \}$, indeed the problem is a decision problem (the answer to the question "does exist ...?" is simply YES or NO)
the abstract problem $Q$ is a subset of $I \times S$ and is the relation that associates an instance of the problem to the correct answer

So:

Q = { ( (2,3), NO  ),
      ( (2,4), YES ),
      ( (2,5), NO  ),
      ....
      ( (6,13), NO ),
      ( (6,14), YES ),
      ...
      ( (7,13), NO ),
      ( (7,14), YES ),
      ...
    }

P.S. the problem $Q$ is known as INTEGER FACTORIZATION and probably you'll meet it again ... :)


regex - difference between $\Lambda+(a+b)^*b$ and $(b+aa^*b)^*$ $r_1=\Lambda+(a+b)^*b$
$r_2=(b+aa^*b)^*$
$r_3=b+\$+aa^*b+(b+\$+aa^*b)(b+aa^*b)^*(b+\$+aa^*b)$

For this FA, which i think of as accepting "$\Lambda$ or anything ending in $b$", i came up with $r_1$, then i used FSM2Regex which gave me $r_3$ which i simplified into $r_2$ using regex simplifier.
now $r_2$ seems better than $r_1$. Should I go with it? If so, what is lacking in $r_1$? I can't see the difference between $(a+b)^*b$ from $r_1$ and $(aa^*b)^*$ from $r_2$. Is one the subset of other? Are they overlapping or disjoint?

Inputting any of the three RE's back into FSM2Regex gives RIDICULOUSLY complex TG's especialy because for some reason that is beyond me, it also draws $\$$ (null string) transitions. Even $r_3$ doesn't give back the FA I used to generate it. So my question is : are $r_1$ and $r_2$ different? How? what should I go with?

Yes, the regular expressions $r_1=\Lambda+(a+b)^*b$ and $r_2=(b+aa^*b)^*$ are equivalent.  There are several ways of doing this.

Just observe that both of them match the empty string and all strings ending with $b$.

Convert them to automata and then produce automata for $L(r_1)\setminus L(r_2)$ and $L(r_2)\setminus L(r_1)$. Minimize both automata and find that they both accept the empty language.  (Actually, you'll find that you make a ton of mistakes and at least one of the automata accepts something, and at least one of the minimizations is wrong. But, if you were a computer, this wouldn't be an issue.)

Clearly both regular expressions match the empty string, so let's show that they match the same non-empty strings, too.  Suppose that $w\in L(r_2)\setminus\{\Lambda\}$. Then we can write $w=w_1\dots w_\ell$ where each $w_i$ is a string that either matches $b$ or $aa^*b$. In particular, $w_\ell$ must match one of these things, so the last character of $w_\ell$ is a $b$, so $w\in L(r_1)$.
Conversely, suppose that $w\in L(r_1)\setminus\{\Lambda\}$. Write $w=s_1\dots s_n$, where each $s_i\in\{a,b\}$. Suppose there are $\ell$ $b$s in $w$ and let these be at positions $p_1, \dots, p_\ell$. Because $w\in L(r_1)$, $p_\ell=n$ (the last character is $b$).  For convenience, let $p_0=1$. We can now write $w=w_1\dots w_\ell$, where $w_i=s_{p_{i-1}+1}\dots s_{p_i}$. For each $i\in\{1, \dots, \ell\}$, we have $w_i=a^{p_i-p_{p-1}-1}b$, so each $w_i$ matches either the regular expression $b$ or $aa^*b$. Therefore, $w$ matches $(b+aa^*b)^*= r_1$.

By the way, a fourth equivalent regular expression is $(a^*b)^*$, which you can see by observing that the inner part of $r_1$ is equivalent to $b+a^+b$, which is $a^*b$.


Can there be a context-sensitive pumping lemma? A "pumping" property (words of a certain length imply the existence of loops in the language-defining mechanism) are known to exist for regular and context-free languages and a few more (usually used to disprove a language's membership to a certain class).

Within the discussion around this question, Daisy's answer suggests that there can't be a pumping lemma for context-sensitive languages - since they're so complex.

Is that true - can it be shown that there can't be some type of pumping property - and is there a good reference for that (or against that)?

Here is some evidence that there is no pumping lemma for the context-sensitive
languages.

Of course, an answer hinges on the question what constitutes a pumping
lemma.  The weakest reasonable definition I could think of is this: A language
class $\mathcal{C}$ has a pumping lemma if there is a decidable ternary
predicate $P(\cdot,\cdot,\cdot)$ where $P(g,w,d)$ means:

$g$ is a word encoding a language $L(g)$ from $\mathcal{C}$ (think: grammar),
$w$ is a word in the language encoded by $g$
$d$ is a word encoding a pumpable computation/derivation for $w$ (think: NFA
computation with repeated state or CFG derivation tree with repeated
nonterminal). Here, pumpable means: there exist infinitely many words in $L(g)$.

Moreover, we want that given a language $L$ in $\mathcal{C}$ encoded by $g$,
for every sufficiently long word $w\in L$, there exists a word $d$ such that
$P(g,w,d)$.

For example, the pumping lemma for regular languages would give rise to
the predicate "$g$ encodes an $\varepsilon$-free NFA and $d$ encodes a
run that repeats a state and reads $w$". For suitable encodings, this
clearly satisfies the above conditions.

Now let us show that such a predicate does not exist for the context-sensitive
languages.

Observe that if a language class has a pumping lemma, then the infinity problem
(Given a grammar, does it generate an infinite language?) is recursively
enumerable: Given an encoding $g$, we can enumerate words $w$ and $d$ and check
whether $P(g,w,d)$. If we found such $w,d$, we answer 'yes', otherwise, we
continue the enumeration.

However, we show that the infinity problem for the context-sensitive languages
is not recursively enumerable. Recall that $\Pi_2^0$ is a level of the
arithmetic hierarchy that strictly includes the recursively enumerable
languages. Hence, it suffices to prove:

Claim: The infinity problem for the context-sensitive languages is $\Pi_2^0$-complete.

It is well-known that the infinity problem for recursively enumerable languages
is $\Pi_2^0$-complete (more often, one finds the formulation that the
finiteness problem is $\Sigma_2^0$-complete). Hence, it suffices to reduce the
latter problem to the infinity problem for the context-sensitive languages.

Given a TM $M$, we construct an LBA $A$ for the language
$$ \{u\#v \mid \text{$v$ is a shortlex-minimal accepting computation of $M$ on input $u$}\}. $$
Then, $L(A)$ is infinite iff $L(M)$ is infinite, which completes our proof.

Update: Tried to be clearer.
Update: Added example.


About the properties of the coresets in k-median clustering I have seen two observations from the paper by Har-Peled but I do not know how to prove them
(i) If $C1$ and $C2$ are the $(k, ε)$-coresets for disjoint sets P1 and P2 respectively, then $C1 ∪ C2$ is a $(k, ε)$-coreset for $P1 ∪ P2$.
(ii) If $C1$ is $(k, ε)$-coreset for $C2$, and $C2$ is a$(k, δ)$-coreset for $C3$, then $C1$ is a $(k, ε+δ)$- coreset for $C3$
Can anyone please figure it out?

The k-medians clustering objective is defined here as
sum_{p in points} weight(p) distance(p, centers)

where centers is the set of k centers and distance(p, centers) is the distance to the closest center.
The first observation amounts to observing that the objective function is additive. Letting (C1, w1) and (C2, w2) be the core-sets, we consider the core-set (C1 union C2, w1 union w2), which satisfies
sum_{p in C1 union C2} (w1 union w2)(p) distance(p, centers)
= sum_{p in C1} w1(p) distance(p, centers) + sum_{p in C2} w2(p) distance(p, centers)
<= exp(eps) sum_{p in P1} weight(p) distance(p, centers) + exp(eps) sum_{p in P2} weight(p) distance(p, centers)
= exp(eps) (sum_{p in P1 union P2} weight(p) distance(p, centers))

and similarly for the lower bound.
As for the second observation,
sum_{p in C1} w1(p) distance(p, centers)
<= exp(eps) sum_{p in C2} w2(p) distance(p, centers)
<= exp(eps) exp(delta) sum_{p in C3} w3(p) distance(p, centers)
= exp(eps + delta) sum_{p in C3} w3(p) distance(p, centers),

and similarly for the lower bound.


Why would $NP^ {SAT} \subseteq P^{SAT[O(\text{log }n)]}$ imply that $PH \subseteq P^{SAT[O(\text{log }n)]} $ I was reading the following paper by Jim Kadin, "$P^{NP[O(\text{log }  n)]}$ and sparse Turing complete sets for NP"

The main result is that if there is a sparse set $S \in NP$ such that $coNP \subseteq NP^S $, then $PH \subseteq P^{SAT[O(\text{log }n)]} $.

In the proof of this result he author claims that it is sufficient to prove $NP^ {SAT} \subseteq P^{SAT[O(\text{log }n)]}$ and this will imply that $PH \subseteq P^{SAT[O(\text{log }n)]} $.

I could not figure out why this is true. Perhaps this is trivial and there is some minor point (some inclusion of complexity classes) that I am missing. Please do point out why the above claim is true.

Simply put, even a weaker claim of $\mathrm{NP}^\mathrm{SAT}=\mathrm{NP}^\mathrm{NP}\subseteq \mathrm{P}^\mathrm{SAT}=\mathrm{P}^\mathrm{NP}$ would imply PH collapse to the second level (so even the consequence is a little bit weaker, you can adapt to your case).

We have $\mathrm{P}^\mathrm{NP}\subseteq \mathrm{co}$-$\mathrm{NP}^\mathrm{NP}$. So, from the assumption, we deduce that $\mathrm{NP}^\mathrm{NP}\subseteq \mathrm{co}$-$\mathrm{NP}^\mathrm{NP}$. As a result, PH collapse to the second level.


What is this turing machine doing There is a following Turing machine. I want to understand what it is doing :

I tried running it on input 100, 10000. Both these strings are accepted whereas 10,1000 are rejected
That leads to a good guess that it's accepting the string's with 1 followed by 0's where number of
0's = power of 2. But I can't prove it or deduce it from looking at the state diagram of it.
Any insights into it ?

I think your interpretation is correct. $q_i$ and $q_{ii}$ are states that guarantee that $10$ and $100$ will be correctly accepted. It is clear that any other input of size $\leq 3$ will be rejected.
Now suppose you are in state $q_s$, the tape is $1Z^{2^k}u$ (with $u\in \{0,1\}^*$), and the head is in position of the first $Z$ of the tape. The cycle $q_s, q_d, q_r, q_l$ will let you do round trips, each trip transforming a $Z$ in $Y$, and a $0$ in $X$.
On the last trip, you will transform the last $Z$ in $Y$, then cross all $X$'s (in $q_{pf}$), and transform a zero in $X$. Therefore, if $u\neq 0^{2^k}v$, the Turing machine will reject. If not, we will get in $q_f$.
If $u = 0^{2^k}v$, then three cases are presented:

$v = \varepsilon$, we finish in $q_{acc}$ so the word is accepted (and the input was necessarily $10^{2^{k+1}}$);
$v = 1w$, we reject;
$v = 0w$, we transform all $X$'s and $Y$'s into $Z$'s, reach the left most symbol (which must be 1), and finish in $q_s$. The tape is then $1Z^{2^{k+1}}v$ and we are in the first situation.