Lazy concatenative functional language Can the idea of concatenative programming languages be extended to call-by-need evaluation strategy?

I see some problems that I will explain with few examples. I will use a prefix instead of a postfix notation, so evaluation takes place from left to right.

Duplicate an argument seems trivial:

drop A B  ->  B

However, we can not forget that A is unevaluated, so the previous example only work for literals or quotations, but not for unevaluated code:

drop 123 B      ->  B
drop "abc" B    ->  B
drop [+ 1 2] B  ->  B
drop + 1 2 B    ->  1 2 B  -- NON SENSE!

This can be solved in two ways. First, we can impose some structure (unflat) to the code based on the functions arity in the parsing stage:

drop + 1 2 B    ->  drop [+ 1 2] B  // at parse time
drop [+ 1 2] B  ->  B               // at run time

The problem with this approach is that we lose all the benefits of concatenative programming (for example, flatness and multiple return values). In fact, we are converting function composition to function application in prefix notation... In this case:

dup + dup 2 3

Naively translates to:

dup [+ [dup 2] 3]  ->  dup [+ 2 2 3]  // `+` arity mismatch. What to do with the extra value? Which one is it, 2 or 3?

But it result in an strict language is:

4 4 3

The second solution is to instruct the evaluator to reduce the stack just enough to get as many arguments as the current word needs:

drop + 1 2 B  ->  drop 3 B  ->  B

Looks good, but the target of lazy evaluation is to evaluate arguments only when needed. In this case we are evaluating + 1 2 needlessly. It is not a big problem until we found:

drop + bottom 2 B  ->  bottom

What contradicts the expected call-by-need semantics:

drop + bottom 2 B  ->  B

It can be done. Here's a presentation explaining the language and how the compiler works (so far).

You can play with an asm.js version at http://hackerfoo.com/eval.html


Algorithm to determine whether two regexes are equivalent Given two arbitrary regular expressions, is there an "efficient" algorithm to determine whether they match the same set of strings?

More generally, can we compute the size of the intersection of the two match sets?

What algorithms are there to do this, and what complexity class do they live in?

If we disallow the Kleene star, does that alter the picture at all?

Hendrik Jan gives a good answer for complexity class, but not an algorithm itself.

The simplest algorithm to do this that I know of is to convert the regular expression to a DFA. There are known techniques for converting a regular expression to an NFA, and an NFA to a DFA.

Once you have two DFAs, testing for equivalence is efficient and decidable, since the minimal form of a DFA is unique up to isomorphism.

However, constructing these DFAs from NFAs could take lots of time, and produce extremely large DFAS, exponentially large in the worst case.


Sketch an IP proof for minSAT I have to sketch an IP proof for the minSAT problem. The minSAT problem is define in this way:

For a given formulae find a satisfying assignment with a min subset of variables assigned to True;

My sketched IP protocol is:

Prover and Verifier share the input formula
Prover sends to the Verifier a set of variables assigned to True, which should be the minimum
Verifier checks if the given set indeed satisfies the formula. If it is the case, it chooses one variable, re-computes the formula and sends the new formula to the Prover

I would iterate this process untill the Prover gives an empty set or I reach a contradiction.

My questions are:

Is this a right protocol? If not, how can I exploit the cases in which the protocol doesn't work?
How can I evaluate the probability of completness and soundness for this protocol?

Your protocol is not very clear. What do you mean at step 3 by "it chooses one variable, re-computes the formula"?

I assume the verifier just sets that variable to 1 and re-computes the formula without that variable.

Then, this protocol still has some problems. Let's say that there are two sets of variables that satisfy the formula: $\{x\}$ and $\{y,z\}$. The minSat is $x$.
But what happens if the prover says it is $y,z$?
the verifier checks this proposed set, and  sees that the set satisfies the formula; then the verifier removes one variable, say $y$, and sends the formula back to the prover. The prover will then reply with $\{z\}$ and the verifier will accept it.

Even if the verifier renames the variables in a random way, (say, replace $x$ with $a$ and $z$ with $b$), it's not clear that this protocol works.
Still, maybe the prover is able to identify the variable that previously was $z$ from the structure of the formula, and repeat the faulty behaviour described above.

So although in the suggested protocol the prover cannot reply with a set that doesn't satisfy the formula, the prover can give a non-minimal set, and the verifier will (wrongly) accept it.


primitive recursive functional equivalence Given two primitive recursive functions is it decidable whether or not they are
the same function? For example lets take sorting algorithms A, and B which are
primitive recursive. While there are many algorithms for sorting they all
describe the same relation. Given two primitive recursive implementations of A,
and B, can they be proven to represent the same function? Please note that this
question is not about unrestricted recursion, and as such not limited by the
properties of Turing machines.

I know that if you have two functions that halt, and have a finite domain they
can be proven to be the same function because you can simply try every possible
input, and compare the output of each function. My confusion is when working
with things working on say natural numbers because they are not finite.

If this is not decidable for the primitive recursive functions is it possible
for weaker classes like say the elementary recursive functions. I also know that
this IS possible for weaker things like finite state machines, and deterministic
pushdown automata. Thanks.

It is well known that equivalence is undecidable even for CFGs resp. PDAs (see even Wikipedia). This provides a proof that the same property is undecidable for every model of any superset of CFL (by a simple special case reduction).

Since solving the word problem for any given CFL is clearly primitive recursive (by virtue of your favorite parsing algorithm), this includes the set of primitive recursive functions/algorithms.


Are "Flow Free" puzzles NP-hard? A "Flow Free" puzzle consists of a positive integer $n$ and a set of (unordered) pairs of distinct vertices in the $n \times n$ grid graph such that each vertex is in at most one pair. A solution to such a puzzle is a set of undirected paths in the graph such that each vertex is in exactly one path and each path's set of ends is one of the puzzle's pairs of vertices. This image is an example of a Flow Free puzzle, and this image is an example of a solution to a different Flow Free puzzle.

Is the problem "Does there exist a solution to this Flow Free puzzle?" NP-hard? Does it matter whether $n$ is given in unary or binary?

In the terminology of Nikoli Puzzles this is known as "Nanbarinku" or "Numberlink". The description does not always explicitly mention all squares must be covered, but this is indeed the case in all solutions I checked.

According to Wikipedia Numberlink the problem is NP complete, with reference: Kotsuma, Kouichi; Takenaga, Yasuhiko (March 2010), NP-Completeness and Enumeration of Number Link Puzzle, IEICE technical report. Theoretical foundations of Computing 109 (465): 1–7

I did not check the fine print.

Added. Following a comment from domotorp, Numberlink usually has an additional constraint. Indeed, quoting from Adcock etal:

  Our hardness result can be compared to two previous NP-hardness proofs: Lynch's 1975 proof without the “cover all vertices” constraint, and Kotsuma and Takenaga's 2010 proof when the paths are restricted to have the fewest possible corners within their homotopy class.

Adcock et al. Zig-Zag Numberlink is NP-Complete, Journal of Information Processing 23 (2015) 239-245, doi:10.2197/ipsjjip.23.239


What is the difference between decidability and computability? If they are different, what are the typical problems in each that do not fall on the other category? Or are the mutually exclusive or does one completely capture the other?

A function over finite strings is called computable if it can be computed by a program (more formally, a Turing machine).

A set of finite strings is computable if it membership problem in that set (given $x$, is $x \in L$?) can be decided algorithmicaly (more formally using a Turing machine).

They are used for different kind of objects.

The word "computable" can be used for a set. When we say that a set is computable we mean that the set is decidable (which is equivalent to saying that the characteristic function of the set is computable).

It makes no sense to say a function is decidable.


Subset on boolean cube with largest sum of biases On the boolean cube $\mathcal{B}=\{0,1\}^n$, we assign each vertex a value by $p:\mathcal{B}\rightarrow[0,1]$. Let
$$\tilde{p}_i=\sum_{x\in\mathcal{B}}(-1)^{x_i}p(x).$$
What is the value of $\max_p\sum_{i=1}^n|\tilde{p}_i|$?

Since the objective $\sum_{i=1}^n|\tilde{p}_i|$ is convex on $p$, we can safely assume that $p(x)$ is either $0$ or $1$. So $p$ represents a subset of $\mathcal{B}$, and $|\tilde{p}_i|$ indicates the 'bias' of this subset on the direction of $x_i$. That's where the title comes from, but you can also think of it as bounding the L1 sum of some specific Fourier coefficients.

I tried to solve it combinatorially: let $f(n,k)$ denote the maximum value when $p$ represents a subset of size $k$. By considering the size of the intersection with $\{x\in\mathcal{B}\mid x_n=0\}$, we have the following recursive relation:
$$f(n,k)=\max_{0\leq\ell\leq k} f(n-1,\ell)+f(n-1,k-\ell)+|k-2\ell|,$$
for all $0\leq k\leq 2^{n-1}$. And clearly $f(n,2^n-k)=f(n,k)$. I ran a program to compute the first several terms of $\max_k f(n,k)$, which is always $f(n,2^{n-1})$:
$$1,2,6,12,30,60,140,280,630,\cdots$$
It seems to be $n\cdot\binom{n-1}{\lfloor n/2\rfloor}$, and this value can indeed by achieved when the subset consists of those $x$ with Hamming weight at most $\lfloor n/2\rfloor$.

It would be great to have a formal proof of this observation. A direct proof via the properties of Fourier coefficients on the boolean cube would be even better. Thanks in advance.

It will be slightly cleaner to replace $\{0,1\}^n$ with $\{-1,1\}^n$, and to normalize your function $\tilde{p}_i$ so that we get the $i$'th Fourier coefficient
$$
\hat{p}(\{i\}) = \mathbb{E}[x_i p].
$$
Let $\sigma_1,\ldots,\sigma_n \in \{ \pm 1 \}$. Then
$$
\sum_{i=1}^n \sigma_i \hat{p}(\{i\}) = \mathbb{E}\left[\left(\sum_{i=1}^n \sigma_i x_i\right)p\right].
$$
If we define a function
$$ q(x_1,\ldots,x_n) = p(\sigma_1 x_1, \ldots, \sigma_n x_n) $$
then $q \in [0,1]$ and
$$
\sum_{i=1}^n \sigma_i \hat{p}(\{i\}) = \mathbb{E}\left[\left(\sum_{i=1}^n x_i\right) q\right].
$$
Under the constraint $q \in [0,1]$, the right-hand side is clearly maximized when
$$
q = \begin{cases} 1 & \text{if } \sum_i x_i > 0, \\
0 & \text{if } \sum_i x_i < 0, \\
\ast & \text{if } \sum_i x_i = 0, \end{cases}
$$
where $\ast$ means that the value doesn't matter. In other words, $q$ is the majority function, and so
$$
\begin{align}
\sum_{i=1}^n \sigma_i \hat{p}(\{i\}) &\leq 2^{-n} \sum_{k \geq n/2} (k-(n-k)) \binom{n}{k} \\ &=
2^{-n} n \sum_{k \geq n/2} \binom{n-1}{k-1} - 2^{-n} n \sum_{k \geq n/2} \binom{n-1}{k} \\ &=
2^{-n} n \binom{n-1}{ \lceil n/2 \rceil - 1 } \\ &=
2^{-n} n \binom{n-1}{ \lfloor n/2 \rfloor }.
\end{align}
$$
Therefore
$$
\sum_{i=1}^n |\hat{p}(\{i\})| \leq \max_\sigma \sum_{i=1}^n \sigma_i \hat{p}(\{i\}) \leq 2^{-n} n \binom{n-1}{ \lfloor n/2 \rfloor }.
$$
Furthermore, this is achieved for the majority function.


Can repeated runs of a Las Vegas algorithm equate to a better Las Vegas algorithm? Let's say I have a Las Vegas algorithm $L$ for some problem $P$, which runs in $n^3$ steps with 50% likelihood. My friend asks me for an algorithm for $P$ that runs in $n^3$ steps with 75% likelihood. My intuition says, "No problem! I'll just run $L$ once, and if it doesn't return after $n^3$ steps, I'll terminate it. Then, I'll run it again. The likelihood that it fails to return after $n^3$ steps twice in a row is only 25%."

Is my intuition correct? I know that if it's running twice, that's technically $2n^3$ and that would be subsumed by big-O notation. Maybe the problem that was posed to me was not carefully worded enough...

Monte Carlo and Las Vegas algorithms are equivalent and this question is more naturally asked in terms of the former so I will pretend you asked about Monte Carlo.

Any Monte Carlo algorithm can be run multiple (say, a constant number of) times to amplify the probability of success while slowing down the algorithm. And in fact you can achieve any fixed probability of success $< 1$ while slowing down by a constant factor.

Where you "cheat" is that you adopt the convention of ignoring the constant factor in run time while simultaneously caring about the constant probability of success. As the probability can be freely adjusted by multiplying run time by a constant, caring about its particular value is equivalent to caring about the constant factor in run time so big O is inappropriate in this situation.


Greedy strategy for computing the minimum number of rays that hit all balloons The minimum zap problem below is Exercise 11 in Jeff Erickson's lecture on "Greedy Algorithm".

  The minimum zap problem can be stated more formally as follows. Given a set $C$ of $n$ circles in the plane, each specified by its radius and the $(x, y)$ coordinates of its center, compute the minimum number of rays from the origin that intersect every circle in $C$. Your goal is to find an efficient algorithm for this problem. (See a "9-balloons-with-4-rays" example in the figure below)

  Question: Suppose it is possible to shoot a ray that does not intersect any balloons. Describe and analyze a greedy algorithm that solves the minimum zap problem in this special case.

I'm having trouble approaching this problem. I thought a greedy approach would be to use the ray that intersects the most circles and recurse, but I was told this was wrong. Why is this?

And what is the point of the fact that there is a ray that does not intersect any balloons? Am I supposed to prove that some optimal solution uses this fact?

Any help would be appreciated! I just recently started learning algorithms :)

Algorithm based off of hengxin's answer: https://cs.stackexchange.com/a/52293/42816

Proof by mathematical induction

Note: Did not use O( n log n) implementation

Now we will prove the correctness of this algorithm using mathematical induction. We will show that our greedy algorithm cannot do worse than the optimal solution.

Let $S'$ be the set of rays shot by our greedy algorithm. Let $S$ be the set of rays shot by another optimal solution.

Our base case is when $n = 1$. There is only one object to destroy, and our greedy algorithm uses 1 ray, which also happens to be optimal. So this checks out.

Now for our induction hypothesis, we will assume that our greedy algorithm is optimal for up to $n$ objects.

We now claim that the first ray from $\alpha$ of $S'$ cannot do worse than that of $S$.

Now let's consider an $n+1$ object situation. Then, we sort $S'$ and $S$ according to $\alpha$, clockwise. Now let's examine the first ray that occurs from $\alpha$ clockwise. In $S'$, this first ray, call it $R'$, cannot possibly do worse than that of $S$, call it $R$, because our greedy algorithm says that this ray will intersect the most objects, including the first one from $\alpha$. Therefore, $R$ either intersects just as much or fewer objects than $R'$. Thus, we can replace $R$ with $R'$ in the optimal solution $S$.

Now, we have to figure out if the rest of $S'$ is optimal, cutting out $R'$, which we'll call $T'$. However, since there are now at most $n$ objects, our induction hypothesis says that our greedy algorithm finds an optimal solution to $T'$. As such, the $R' + T'$ problem has an optimal solution from our greedy algorithm. Q.E.D.

Principle: You need to shoot the rays in some order and choose carefully the proper direction/angle for the first ray.

  $Q_1:$ I thought a greedy approach would be to use the ray that intersects the most circles and recurse, but I was told this was wrong. Why is this?

See the figure in the problem. Suppose there are only 4 balloons: the two green ones and the two blue ones. If you shoot your first ray along the x-axis (this is allowed by your greedy strategy. note that I suppose that the three bigger balloons cannot be hit by a single ray; otherwise, move them around slightly), you will leave the two other balloons far apart. As a result, it costs you 3 rays, but the optimal is 2.

  $Q_2:$ What is the point of the fact that there is a ray that does not intersect any balloons?

So the key point is to shoot the first ray along the right direction. Here comes the fact that "there is a ray that does not intersect any balloons".

The basic idea is as follows:

first find the direction/angle $\alpha$ along which a ray does not intersect any balloons;
then identify the first balloon (say, clockwise) $b$ with respect to this direction/angle $\alpha$; Here $b$ is defined to be the first balloon you leave when you sweep a line starting from the direction/angle $\alpha$ clockwise.
shoot a ray which is $b$'s rightmost (clockwise) tangent line $l$， remote all balloons hit by $l$,
and then recurse.

  $Q_3:$ Am I supposed to prove that some optimal solution uses this fact?

It is not easy to prove a greedy strategy is correct. You can try to prove the idea above by applying mathematical induction and exchange argument (or maybe show it is wrong!). A hint is to consider the set of rays shot by an arbitrary algorithm, sort them by angles with respect to $\alpha$ (clockwise), then compare it to the optimal solution one by one.

Implementation: In the comments, OP asks for an $n \log n$ algorithm. Well, $n \lg n$ often means that you can sort some things first. Maybe sort all the balloons by the angles of their right (clockwise again) tangle lines. Then it is easy to apply the greedy strategy above.
This is a rough idea. How to implement it efficiently by choosing/designing good data structures is left as an exercise.


Can a Formal Language be of a type (RE, REC, Regular, etc) for one TM, but of a different type for another? I'm new to the study of formal languages, and I wondered if languages of a certain type are objectively of that type (RE, REC, regular, etc), or if their type varies on their context? I had this thought:

If I had a language A that is recursive for some Turing Machine, TM(A), would it be possible to design another TM, TM(A2), where you add in a feature that instead makes TM(A2) loop for one or more words in A?

Now, A is no longer recursive.

This seems to be intuitively obvious for at least some examples (though my example is with a very simple language). Say A = {1}, and TM(A) is a program that just says:

'if (x=1)
{return true}'

For TM(A), A is accepted.

Now, let TM(A2) be a program that says 'while (x>_1) {x+=1}', and so now A causes TM(A2) to loop forever.

Granted that this example may unbenkownst to me be too simple to prove a real point, but if the above holds, then yes, languages can be of 'different types' depending on their context.

However, in none of the literature I've seen has this been written to be the case? If a language is recursively enumerable in one given example, it's recursively enumerable altogether - that seems to be the description of how it works.

To combat this confusion then, and given also that a language type in the Chomsky hierarchy is a subset of the types above it in the hierarchy, would this be a correct definition of the 'type of a language': if there exists at least one machine  (a DFA, a PDA, TM, etc) of a given language type, type X, that can be found to accept on a language, and it can be proven that no machine from the type below in the Chomsky hierarchy can accept on that language, then that language is of 'type X', and all the types above it?

If I'm correct in that rather long definition, then, it means that when a textbook says for example that a language is context free, then it means yes there are an infinite number of PDAs or TM's the can be thought of for which the CF language doest not accept, or loops even. But, there exists at least one PDA for which the language accepts on, and there can be no DFA that can accept on the language?

Further, when a textbook says a language is not even recursively enumerable i.e. unsolveable, it means that this language is above recursively enumerable in the Chomsky hierarchy, and that truly it is impossible to solve - that no TM can be designed to accept/reject on it?

If I've missed the point entirely or have been unclear, please do let me know.

A language $\mathcal L$ is recursive if there exists a Turing machine $\mathcal M$ (and therefore, an algorithm) that stops on every input, and that accepts exactly words from $\mathcal L$ (i.e. $\forall w, \mathcal M$ accepts $w\iff w\in\mathcal L$). Designing a Turing Machine that doesn't comply with those conditions won't help you prove that there isn't another Turing Machine that actually works as needed. Therefore, the recursivity of a language doesn't depend on a "choice" of a Turing Machine.

However, to prove a language is recursive, you usually find a Turing Machine that falls under our definition. We denote such a Turing Machine as a witness, or you could say that it witnesses that your language is recursive*

Moreover, classes of languages are often included in each others. By instance, if a language $\mathcal L$ is regular, then there is a DFA that recognizes it, and therefore witnesses the regularity of $\mathcal L$. But if there is such a DFA, you can easily build a Turing machine that "simulates" that DFA, stopping of every input, and accepting exactly the same words as the DFA. Therefore, $\mathcal L$ is REC as well, as you pointed out. But this shouldn't lead you to make more assumptions than needed. When you read "$\mathcal L$ is recursive", you shouldn't make the assumption that it isn't regular but you shouldn't make the assumption that it is either. You simply don't know.

As all of this suggests, it is usually easier to prove that a language belongs to a class, than to prove it doesn't. To prove belonging, you only have to provide a witness. To prove that $\mathcal L$ doesn't belong, you basically have to prove that no TM/DFA/... can be a witness. This is usually relies on "tricks", as the diagonal argument (you should look into the Halting problem for more information) for recursivity, or the pumping lemma for regularity.

(*) : Sometimes, it will be more convenient to use the fact that $Rec = $R.E.$\cap$ co-R.E., but this relies on a constructive proof, which means this is a "mechanical" way to build a witness for recursivity when you have both a witness for recursive enumerability and corecursive enumerability


Categorising problems into complexity classes Am I correct in saying that there are two ways to categorise a problem in complexity theory:

Find an algorithm that solves it. If the algorithm runs in polynomial time, then we can put it into P-class. If not, then we can put it into EXP.
Provide a reduction that this problem is no hard than another problem, to which we know the complexity class for.

If I cannot find a reduction and I do not have an algorithm, what is the "default" complexity class? I'm guessing it would be in the class of problems which cannot be solved until we find an algorithm.

Your reasoning seems correct, but you are missing a crucial step once the second bullet point is done with: You check that your problem is also complete for the class $C$ you have found for it. For instance, if you have a problem $P$ and show it is reducible to a complete problem in $\mathsf{PP}$, then you are not done yet. For all we know, $P$ could be $\mathsf{PP}$-complete, but it could also be in $\mathsf{NP}$, or $\mathsf{BPP}$, etc. Therefore, to finish classifying $P$, you should be able to find a class it is complete for—if possible; after all, there are classes which are not closed under (poly-time many-one) reductions—, or provide some good evidence why it could not be in a class which is known (or conjectured) to be strictly below $C$.

  If I cannot find a reduction and I do not have an algorithm, what is the "default" complexity class?

Assuming your problem is decidable, the "default" complexity class is $\mathsf{R}$, the class of recursive languages. Improving on this is only possible by producing an algorithm whose time complexity you can prove or, alternatively, proving a reduction to some other problem for which this is the case; that is, essentially what you wrote in your question. There is no such thing as a "class of problems which cannot be solved until we find an algorithm" in complexity theory; that would be the domain of computability theory (i.e., problems which are not known to be decidable).


How much math does one need to know to understand discrete math/structures for computer science? Normally universities teach discrete math / discrete structure. My question is, how much math does one need to know to understand this area? Is calculus required or will precalculus do just fine? Does one need to have done proofs before to be able to understand this area?

Thank you all for your answers.

Note: My apologies if this has already been asked. after my investigation i could not find any similar questions. If you believe this is the case please share where this has been answered and i will gladly end/remove this.

Normally, classes at universities have prerequisite lists. If there are some courses on the list you haven't taken, you should ask the professor whether you really need them.

Discrete math courses can vary dramatically in what you really need to understand them. You may or may not need to have done proofs; (some discrete math classes teach you how to do proofs). I'd guess you probably don't need to know calculus. Calculus isn't really needed to understand discrete math, but if calculus is a prerequisite for the class, there are a number of good examples and homework problems that the professor might use that would indeed require calculus. And you can certainly teach discrete math classes that require basic abstract algebra as a prerequisite.


How can I improve my algorithm for finding optimally balanced P-way partitioning of array I have an array of $N$ weights $w_i$, say $w_i=\{4, 5, 12, 16, 3, 10, 1\}$, and I need to divide this array into $P$ partitions such that partitions are optimally balanced, i.e. that maximum sum of weights of any partition is as small as possible. Luckily the problem is constrained by the fact that the weights can't be reordered. If the number of partitions is three, the above example would give the optimal partitions: $\{4, 5, 12\}, \{16\}, \{3, 10, 1\}$.

I have found efficient recipes (e.g. partition problem, subset sum, Optimal Partition of Book Chapters, A partition algorithm, An algorithm for k-way array partitioning) for many similar problems for the cases where the weights are unordered sets and/or the number of partitions is fixed at 2 or 3, but none that seem to exactly address my problem where the number of partitions is arbitrary.

I have solved the problem myself using divide-and-conquer algorithm (written in Python below), but it seems to be awfully slow for many partitions (e.g. N=100, P=8). So I was thinking that there got to be a better way, using dynamic programming or some other clever tricks?

Does anyone have any suggestions?

Slow Python divide-and-conquer algorithm:

def findOptimalPartitions(weights, num_partitions):
    if num_partitions == 1:
        # If there is only one partition, it must start at the first index
        # and have a size equal to the sum of all weights.
        return numpy.array([0], dtype=int), sum(weights)

    # Initially we let all partitions start at zero, meaning that all but the
    # last partition gets zero elements, and the last gets them all.
    partition_offsets = numpy.array([0] * num_partitions)
    max_partition_size = sum(weights)

    # We now divide the weigths into two partitions that split at index n.
    # We know that each partition should have at least one element, so there
    # is no point in looping over all elements.
    for n in range(1, len(weights) - num_partitions):
        first_partition_size = sum(weights[:n])

        if first_partition_size > max_partition_size:
            # If the first partition size is larger than the best currently
            # found, there is no point in searching further.
            break

        # The second partition that starts at n we now further split into
        # subpartitions in a recursive manner.
        subpartition_offsets, best_subpartition_size = \
            findOptimalPartitions(weights[n:], num_partitions - 1)

        # If the maximum size of any of the current partitions is smaller
        # than the current best partitioning, we update the best partitions.
        if ((first_partition_size < max_partition_size)
                and (best_subpartition_size < max_partition_size)):
            # The first partition always start at 0. The others start at
            # ones from the subpartition relative to the current index, so
            # add the current index to those.
            partition_offsets[1:] = n + subpartition_offsets
            # Find the maximum partition size.
            max_partition_size = max(first_partition_size, best_subpartition_size)

    return partition_offsets, max_partition_size

EDIT: A trivial Greedy algorithm where the last partition will typically be too large.

def greedyPartition(weights, num_partitions):
    target_size = sum(weights) / num_partitions

    partition_offsets = numpy.zeros(num_partitions, dtype=int)
    partition_sizes = numpy.zeros(num_partitions, dtype=int)
    current_divider = 0
    for p in range(0, num_partitions - 1):
        partition_size = 0
        for n in range(current_divider, len(weights)):
            if partition_size + weights[n] > target_size:
                current_divider = n
                partition_offsets[p + 1] = current_divider
                partition_sizes[p] = partition_size
                break

            partition_size += weights[n]
    partition_sizes[-1] = sum(weights) - sum(partition_sizes[:-1])
    max_partition_size = max(partition_sizes)

    return partition_offsets, max_partition_size

Binary search is a general strategy that can often be applied to problems that seeks a single optimized number as an answer.

Let $A=[a_1, \cdots, a_N]$ be the given array of weights. Assume $1\lt P\lt N$; otherwise, the problem becomes trivial.

Given a weight $w$ such that $1\le w\le\sum a_i$, we can associate a partition $\mathcal P(w)$, $A = P_1\,P_2\,\cdots P_m$ such that

Subarray $P_1$ is as long as possible such that the sum of all weights in it is no more than $w$.
Then subarray $P_2$ is as long as possible such that the sum of all weights in it is no more than $w$.
Then subarray $P_3$ is as long as possible such that the sum of all weights in it is no more than $w$.
And so on.
Finally, we are left with non-empty subarray $P_m$, the sum of all weights in which is no more than $w$.

Note that $m=\#\mathcal P(w)$ is the minimum number of subarrays in a partition where the sum of all weights in every subarray is at most $w$. We want to find $w$ such that $\#\mathcal P(w)=P$ and $\#\mathcal P(w+1)<P$. Since the map from $w$ to $\mathcal P(w)$ is decreasing, we can use binary search to find it.

Here is the outline of an algorithm that finds the largest $w$ such that $\mathcal P(w)=P$. Assume the given weights are integers; otherwise, we need to tweak the algorithm a bit. .

Let $ma=\max\{a_i\}$. If $P\ge \#\mathcal P(ma)$, the least maximum sum is $ma$. Deal with this easy case and return.
Let $low=ma$ and $high=\sum a_i$.
If $low\lt high-1$, $ mid = (low + high)//2$ and compute $m= \#\mathcal P(mid)$.

If $m\le P$, lower $high$ to $mid$.
If $m\gt P$, raise $low$ to $mid$.

Go back to the start of this step.
Let $H$ be the partition $\mathcal P(high)$. If $\#H\not= P$, divide some subarrays of $H$ into smaller subarrays so as to increase the number of subarrays by $P-\#(P)$. Return $H$.

The loop invariant for step 3 is $\#\mathcal P(low)>P$, $\#\mathcal P(high)\le P$ and $low\le high-1$. When the loop ends, i.e., when $low==high-1$, we must still have  $\#\mathcal P(low)>P$ and $\#\mathcal P(high)\le P$. That means, $high$ is the minimum of the maximum sum of weights of any subarray in a partition of size no more than $P$, which explains largely why this algorithm is correct.

This algorithm runs in $O(N\log(\sum a_i))$ time, since the most of time is spent on computing $\mathcal P(w)$ and it takes $O(N)$ time to compute $\mathcal P(w)$ for any given weight $w$.

Exercise (the dual problem). Given an array of $N$ positive integer weights $w_i$ and an integer $P$,  divide the array into $P$ parts such that the parts are optimally balanced, i.e. that minimum sum of weights of any part is as large as possible.


How to construct this generalized xor without needing an extra vector? Operator - Generalized Symmetric Difference

If you take binary xor and generalize it to other radices
you can do so by the absolute value of the difference of each
element in a radix vector.
However this doesn't have the same properties as the binary
symmetric differene.
The reason is that in throwing away the "sign" of the difference
we are unable to reconstruct an operaand given the result and the other
as we can in binary xor. So we lose the nice property

ABA = B

However we keep other nice properties like

A0 = A

AA = 0

There is a way to maintain this property. However, as far as I can tell
it involves emitting 3 vectors for any result. The first vector is the usual
symmetric difference, the other two vectors are binary vectors of equal length
to the first that record the sign of the result, one such vector for each
order of the operands, on being the binary complement of the other. In this way, an original operand can be recovered, given the result and the other opernad, AND that other operands "sign" vector.

For example :

Say we have 2 base 10 vectors corresponding to the numbers 1137 and 9284, what i
s the xor of these two numbers in base 10?

        7  3  1  1              4  8  2  9

        4  8  2  9              7  3  1  1

Signed
Result  3 -5 -1 -8             -3  5  1  8

Sign
Vector  0  1  1  1              1  0  0  0

Symmetric
Difference              3 5 1 8

Recover 1137 given 8153 and 9284

3  5  1  8
+  -  -  -
4  8  2  9

7  3  1  1

My question is : is there a better construction of generalized symmetric difference in any radix > 2 such that we don't need to 'remember the sign' ?

The most common definition of xor is $a\oplus b=(a+b)\bmod 2$, on vertices applied to every coordinate seperately of course. In base-10 case, you have to introduce two operations: $a\oplus b=(a+b)\bmod 10$ and $a\ominus b=(a-b)\bmod 10$. (Notice that in base-2 case they coincide). Now you have

$$c=a\ominus b \quad\text{for coding}\quad\text{and}\quad a=c\oplus b \quad\text{for decoding.}$$

Actually, you can use $\ominus$ for both operations, just a bit cleverer:

$$c=b\ominus a \quad\text{for coding}\quad\text{and}\quad a=b\ominus c \quad\text{for decoding.}$$

This works because $a=b\ominus c=(b-c)\bmod 10=(b-(b\ominus a))\bmod 10 $ $= (b-(b-a)\bmod 10)\bmod 10=a\bmod 10=a$.


Proving 2 heuristics are admissible We have $h_1(n)$ and $h_2(n)$ which are both admissible heuristics. We know that $h_1(n) < h_2(n)$ for every state $n$ in a search problem.

Now we are given two heuristics $h_3(n)=\frac{h_1(n)}{1+h_2(n)}$ and $h_4(n)=\frac{h_2(n)}{1+h1(n)}$ and we want to prove $h_3(n)$ and $h_4(n)$ are both admissible.

The only additional constraint which is required for $h_3$ and $h_4$ to be admissible is that both $h_1(n)$ and $h_2(n)$ return non-negative values for any state $n$, but this is always accomplished ---even if a heuristic function might return a negative value it just suffices to take the maximum between the value returned and 0, and this operation clearly preserves admissibility.

Thus, given that $h_1(n), h_2(n) \geq 0$ for every state $n$ and that both are admissible, it is easy to see that the values of $h_3(n)$ are upper bounded by those of $h_1(n)$ (the maximum value taking place when $h_2(n)=0$) Since $h_1$ is admissible so it is $h_3$; conversely, if $h_2(n)$ returns any strictly positive value then $h_3(n) < h_1(n)$. Now, if $h_1(n)$ is not overestimating the effort to reach the goal, then $h_3(n)$ is neither as well and thus, $h_3$ is admissible in this case also.

The proof of admissibility of $h_4$ follows the same lines.

Note that in these proofs it is never required for any heuristic function to strictly dominate another, i.e., the condition $h_1(n) < h_2(n)$ is useless and not necessary at all. The only important requirement is that none ever return negative values, but this is a trivial requirement.

To conclude, I think this is mostly a theoretical exercise. Note that as mentioned above $h_3$ and $h_4$ are upper bounded by $h_1$ and $h_2$ respectively so that, in other words, they are less informed than them. In other words, these transformations are of no interest.

Hope this helps,


Basic Set Theory problem So i'm relatively new to computer science and have been learning set theory and am stumped on a question in it.

The question specifies that we're only looking at subsets of universe U = {0,...,n-1}. For a set S ⊆ U, the characteristic vector denoted by Xs is an n-bit string where j is 1 if and only if j ∈ S.
Example, n = 4, S = {1, 3} Xs = 1010.

it is asking what is XØ and XU. I think I am completely overthinking this but I can't figure out what XØ and XU are referring to.

Characteristic vector is a string representation of a set in this case.
For a set $S$, the characteristic vector is denoted by $X_S$. $X_\emptyset$ and $X_U$ are referring to the characteristic vector of $U$ (Universal set) and $\emptyset$ (Empty set) respectively.
In your example,
$$\text{If }n = 4 \text{ and } S = \{1, 3\} \text{, then } X_s = 1010.$$
We simply need to replace $S$ with a set $\{0, 1, 2, \dots n-1\}$ to find $X_U$ and with $\{\} = \emptyset$ to find $X_\emptyset$. I think you can leave $n$ as a variable unless it is fixed to some value.


Karp hardness of searching for a matching split UPDATE: In 2 days, if no more convincing answer is posted, then bounty of 50 rep. will go to xskxzr. Due to lack of connectedness and a clean & clear cut, the bounty is still open for 2 days. (UTC is now 17 Sep 01:57)

This is yet another follow-up question in the series:

Karp hardness of searching for a matching cut

Karp hardness of searching for a matching erosion

In this question, we further restrict the notion of a matching erosion (which is already a restricted notion of a matching cut). Formally, our definition is as follows.

Given an undirected graph $G(V, E)$, a matching split $M=(A, B)$ is a partition of $V$ into two disjoint subsets, i.e. $A\cap B = \emptyset \land A\cup B = V$ that satisfies the following conditions:

$G[A]$ and $G[B]$ are two disjoint induced subgraphs
The edge set of the cut $M = \{uv\in E\vert u\in A \land v \in B\}$ is a matching (here, we abuse the notation a little bit, $M$ is both the partition $(A, B)$ and the edge set of the matching cut)
Each vertex $u\in A$ is incident to exactly one edge in $M$
Each vertex $u\in B$ is incident to exactly one edge in $M$

Clearly, we should have $|A|=|B|=|V|/2$, hence the name of this concept.

Our decision problem Matching Split naturally asks whether a given graph $G$ has a matching split.

Our question is: What is the complexity of deciding Matching Split?

It is NP-complete. Clearly it belongs to NP. To prove its NP-completeness, we'll reduce not-all-equal 3-satisfiability (NAE3SAT) to this problem.

Given an instance of NAE3SAT with $n$ variables and $m$ clauses, construct a graph as follows:

For each literal $l$, construct a complete graph with $m+1$ vertices $v_0(l),\ldots,v_m(l)$.
For each variable whose positive and negative literals are respectively $l_i$ and $l_j$, add an edge between $v_0(l_i)$ and $v_0(l_j)$.
For each clause $c_i=l_i^1\vee l_i^2\vee l_i^3$, add the following structure:

In addition, for each literal $l$ other than $l_i^1,l_i^2,l_i^3$, add a new vertex $v_i'(l)$ and an edge between $v_i(l)$ and $v_i'(l)$.

Now we assert that the instance of NAE3SAT is satisfiable if and only if the graph has a matching split.

If the instance of NAE3SAT is satisfiable, consider a valid truth assignment. If $l$ is a truth literal, we put $v_i(l)$'s into $A$ and $v_i'(l)$'s (if exists) into $B$ for all $i=0,\ldots,m$, otherwise we put $v_i(l)$'s into $B$ and $v_i'(l)$'s into $A$. In addition, for the structure corresponding to $c_i$ (we assume $l_i^1$ and $l_i^2$ are truth literals while $l_i^3$ is a false literal without loss of generality), we put $v_i^{12}, v_i^{123}$ into $A$ and put $v_i^{23}, v_i^{31}, v_i^{122331}$ into $B$. We can see this partition is a matching split.

If the graph has a matching split, we can observe firstly that $v_0(l),\ldots,v_m(l)$ should be put into the same part since they make up a complete graph (assume $m\ge 2$ without loss of generality). In addition, if $l_i$ and $l_j$ correspond respectively to the positive and negative literals of the same variable, $v_k(l_i)$ and $v_k(l_j)$ should be put into different parts otherwise $v_0(l_i)$ or $v_0(l_j)$ has no neighbor in the other part. If the positive literal corresponding to a variable is put into $A$, we assign the variable to True, otherwise we assign it to False. Note for each clause $c_i$, $v_i(l_i^1), v_i(l_i^2)$ and $v_i(l_i^3)$ cannot be put into the same part otherwise $v_i^{123}$ has either no neighbor or $3$ neighbors in the other part. Hence this assignment is a valid assignment for the instance of NAE3SAT.

Edit: One can simply add edges among $v_0(l)$'s to make the graph connected. For example, if the clauses are $l_1\vee l_2\vee l_3$ and $l_4\vee l_5\vee l_6$, one can simply add an edge between $v_0(l_3)$ and $v_0(l_4)$. The idea is that for a valid assignment, if we flip all the values of variables involved in one connected component, the assignment is still valid. In the example, this means we can always assume $v_0(l_3)$ and $v_0(l_4)$ are put into the same part.


On clarification of intersection of classes definition How do you define $\oplus P\cap PP$?

$L\in\oplus P$ iff $\exists\mbox{ NTM }M:\forall x,\#acc_M(x)\mod2\equiv0$.
$L\in PP$ iff $\exists\mbox{ NTM }M:\forall x,\#acc_M(x)>\#rej_M(x)$.

Consider the classes $C_1,C_2,C_3$.

$L\in C_1$ iff $\exists\mbox{ NTM }M:\forall x\#acc_M(x)>\#rej_M(x)\mbox{ and }\#acc_M(x)\mod2\equiv0$?

$L\in C_2$ if $\exists\mbox{ NTM }M_1:\forall x\#acc_{M_1}(x)>\#rej_{M_1}(x)\mbox{ and }\#acc_{M_1}(x)\mod2\equiv0$ and $L\not\in C_2$ if $\exists\mbox{ NTM }{M_2}:\forall x\#acc_{M_2}(x)\leq \#rej_{M_2}(x)\mbox{ and }\#acc_{M_2}(x)\mod2\equiv1$.

$\exists\mbox{ NTM }M'$ such that
$L\in C_3$ if $\forall x\#acc_{M_1}(x)>\#rej_{M'}(x)\mbox{ and }\#acc_{M'}(x)\mod2\equiv0$ and $L\not\in C_3$ if $\forall x\#acc_{M'}(x)\leq \#rej_{M'}(x)\mbox{ and }\#acc_{M'}(x)\mod2\equiv1$.

Which of $C_1,C_2,C_3$ defines $\oplus P\cap PP$ and which one $\oplus P\wedge PP$? What about last one?

Complexity classes are sets of languages. Intersection of sets is intersection of sets.


Symmetric Difference of Turing Recognizable and Finite Languages Let A be a Turing Recognizable Language and B a finite Language.
I want to prove that their symmetric difference is Turing Recognizable.

My reasoning: B is finite, therefore the finite number of strings can be put through a DTM , M, such that L(M)= A. If M accepts, then remove that string from B and put it in a list, R. * Otherwise, leave it in B. The DTM for the symmetric difference just checks if it is either in B, which it accepts, R which it rejects or if M accepts.

I feel like I have simplified this somewhere, but I would appreciate any pointer in the right direction.

I am unsure how to determine the strings in both A and B. The way I have done it (above) would run forever, because if it is not in A and is in B, it would never halt. This would result in never getting past the * above.

How can it be determined if a string is in A and B?

The symmetric difference $A\ominus B$ of a Turing Recognizable Language $A$ and a finite
language $B$ is Turing Recognizable (i.e. recursively enumerable, or RE).

What you must do is prove that there is a Turing machine that
recognizes $A\ominus B$, but you do not have to actually construct the
machine.  And that is very fortunate because, in general, you cannot.
[More precisely you can build that machine, but you will have in general no way to know it is the right one, as explained below.]

This is a sketch of the proof, which you should know how to complete.

First you prove that the union of a RE set $C$ and a finite set $D$ is
a RE set $C\cup D$
(i.e. a Turing recongnizable set). That is pretty easy.

Then you prove that subtracting a finite set $D$ from a RE set $C$ produces a
RE set $C\setminus D$. That is easily done by modifying the Turing machine that
recognizes the RE set.

   You simply modify the Turing machine recognizing $C$ so that it loops or reject when the input is an element of $D$

Now consider the finite set $B$. It can be split into two parts:

$B_1=B\setminus A$ containg all elements of $B$ that are not in $A$,
$B_2=B\cap A$, the intersection of $A$ and $B$.

Since $B$ is finite, both $B_1$ and $B_2$ are finite too.

It is easy to show that the symmetric difference is

$A\ominus B= (A\setminus B_2)\cup B_1$

Since we have shown that RE sets are closed under union with a finite
set, and under subtraction of a finite set, the set $A\ominus B$ is
also RE, i.e. Turing recognizable.

Thus there is a Turing machine that recognizes $A\ominus B$, but this
proof does not tell you which. The reason is that there is no general
way to determine what part of $B$ is the set $B_2$.

Actually you could construct $2^{|B|}$ Turing machines, each
corresponding to one possibility for the set $B_2$ as subset of $B$.
One of these Turing machines is the one you want. But there is no
general procedure to determine which.

This kind of proof is called non constructive, because you can prove
that an answer exists (i.e. the recognizer for the symmetric
difference), but you cannot actually tell what it is.


For tiling simply connected regions with shapes beyond just rectangles, is there a lower # of tile shapes needed for NP-completeness? In "TILING SIMPLY CONNECTED REGIONS WITH RECTANGLES" by Igor Pak and Jed Yang, they show there is a set of "no more than $10^6$ rectangles" such that the problem of tiling an arbitrary simply connected region with these rectangle shapes is NP-complete. However the number of rectangle shapes $10^6$ seems pretty extreme. Maybe it's hard to close the gap on P vs. NP-complete for tiling in terms of the number of rectangle shapes available, but what if we allow more complex pieces such as non-rectangular Tetris pieces and larger non-rectangular pieces? (We could insist the piece shapes are all simply connected, but I'm not adamant about that).

Can we show NP-completeness for tiling a simply connected region with a much smaller set of (potentially non-rectangular) pieces available, compared to $10^6$?

The authors mention and rely upon an NP-completeness result for tiling with "Generalized Wang Tiles" that seem to use coloring as well as shape, and claim that NP-completeness can be achieved with a fixed set of 23 generalized Wang tiles. However I wasn't able to decipher this result to figure out how many ordinary non-colored (and e.g., perhaps also simply connected) tile shapes are needed to establish NP-completeness.

Found their paper on ArXiv. It is quite easy to go from coloured Wang tiles to uncoloured shapes by introducing zig-zag boundaries, like a jig-saw, as illustrated in their Figure 3. So then still 23 tiles are needed, as colours are simply replaced by boundaries.

Their contribution is to move from boundaries to only rectangular tiles. The authors state in Lemma 3.3 how many rectangles are needed to replace coloured Wang tiles, and a long Section 5 is devoted to the proof of that lemma.


Does the word "efficient" usually refer to polynomial time or polylogarithmic time? This question is strictly about terminology.

I'm not an expert in CS, but I've almost always seen the word "efficient" applied to an algorithm to mean "of polynomial runtime". E.g. this question and the Wikipedia article on computational complexity theory use the word in that way.

However, other sources (e.g. the Wikipedia articles on NC and P-complete) reserve the word "efficient" for algorithms with polylogarithmic runtimes and use "tractable" for algorithms with polynomial runtimes.

This conflicting terminology is obviously confusing. Of course, any (good) formal discussion of algorithmic complexity will precisely define its terminology, but in general, are either of the two usages above clearly more conventional than the other? If someone uses the term "efficient" in an informal discussion of computational complexity without defining it, is it more likely that they mean "polynomial time" or "polylogarithmic time"?

There is no one true answer.  It depends on context.  The most common context is one where polynomial-time is taken as more or less synonymous with efficient, so if you had no further context, I would certainly guess "polynomial time".  Polylogarithmic time is used only in very narrow contexts.

In general, if you think your audience might not be sure about the meaning, then I recommend you to define your terms.


Pseudo-Proof of Constrained Sudoku is co-np The definition of CO-NP

  A decision problem X is a member of co-NP if and only if its
  complement X is in the complexity class NP. In other words,
  co-NP is the class of problems for which there is a polynomial-time algorithm that can verify "no" instances - wikipedia

Sparse-Language

  Where all strings have the form 1k, where "1" can be any fixed symbol.
  For example, the language {1, 111, 1111} is unary, as is the language
  {1k | k is prime}

  For a string s over an alphabet Σ, let shift(s) denote the set of circular shifts of s, and for a set L of strings, let shift(L) denote the set of all circular shifts of strings in L. If L is a cyclic code, then shift(L) ⊆ L; this is a necessary condition for L being a cyclic language.

  My algorithm follows a 3x3 shift language allowing valid Sudoku Grids. Valid grids up to 50x50 and seemingly 100x100 so far have been generated.

  Wikipedia,
  Cyclic language,
  Sparse Language

The language used by this algorithm is a 3x3 circular shift. A cyclic code of permutes allowing valid grid.

Constrained Sudoku Pseudo Proof

What I'm trying to do/Decision Problem

I'm trying to compare two grids. One non-constrained and the other constrained. Both grids are technically valid but within their own "class"

Determine if a valid Sudoku grid is of the conventional class or the constrained class following the shift(L) circular language.

As mentioned in the co-NP definition a decision problem "X" is a member of co-np if and only if its complement X is in the complexity class "NP." As said before, co-np is the class of problems for which a poly verifier can say no instances. The algorithm verifies no instances for grids. If it does not follow the circular language. It says, "not a constrained puzzle."  Therefore, Constrained Sudoku is co-np.

Assuming, that the cyclic language is maintained indefinitely.

  Cyclic Permutation

  let n = input

  let k = shift(L)

  Pn = (n-k)!

  (n-3)! == lim_(n->∞) 3 = 3

  In reduced form

  (n - 3)! = n->∞-k

Pseudo-Code

if indexes/elements match in grid and follows  shift(L) language:

                                   print "yes"
else:

                                   print "no"

Overall, is this sufficient proof that Constrained Sudoku is co-np?

Constrained Sudoku Algorithm

No, it's not a persuasive proof.

Before you can have a valid proof, you must first precisely state whatever it is you are trying to prove.  You haven't done that.

A language (a decision problem) is in co-NP if it satisfies certain requirements.  You have not defined a language; you have not defined a decision problem.  You use the phrase "Constrained Sudoku" but you have not given a precise definition of what formal language that is intended to refer to.

What you list as a "definition" of co-NP is actually an English-language summary of the definition; it's not a substitute for knowing the precise mathematical definition.

The reasoning in your "proof" is faulty.  You write:

  I use an algorithm that in essence says "no" when [...]. Therefore, Constrained Sudoku is co-np.

That doesn't follow.  Just because you have an algorithm that sometimes says no, doesn't mean that the corresponding problem is in co-NP.  There are additional requirements, which you haven't checked.

I'd like to give some general advice.  Before trying to tackle this problem, I suggest you spend a bunch of time studying the fundamentals.  Set aside Sudoku and your ideas for a few weeks, and find an online course where you can learn complexity theory.  That will give you a mathematical framework that, once you've learned it, you can come back and apply to Sudoku.  Until you've done that, it is pointless to continue trying to frame questions like this.


Longest Path A*, Admissible Heuristics, and Optimalness Im working on a modified A Star algorithm, that instead of attempting to find the shortest path, it tries to find the longest past, or in my specific case, the highest weighted path.

I have some number of classes, each with a list of unique nodes, with each node having its own value.  Im attempting to determine the best possible combination of a node from each class to determine the combination or path that has the greatest weight.  To do this, I am viewing these classes as a tree, with each Level having the nodes contained within a single class.

Then I search through this tree using A Star, or more specifically, im searching through my tree based on a search stack.  Once a node is explored, its children are inserted in a sorted order based on their weight (plus their ancestors weight) plus the possible future weight (my heuristic).  Then the top of the stack, with the highest value is selected to search next.

To do this I have an overestimating heuristic, that is it never underestimates the the optimal solution.

If I am looking for the highest weight and not the lowest weight, is this heuristic admissible, and thus my algorithm optimal?

PS: A FormalIsh defination of the current algorithm.

Let S = {S1, S2, ... , Sn}

and each Si has a set of items and a NULL, which represents an item not chosen from this set.

Si = {I1, I2, ... , Im, NULL}

Also each item only ever exists in one set, IE Si U Sj = Si + Sj

Each Item, Ii has an associated value, Vi.

The problem is to select a maximum of M offers, one from each set, when summed yield the highest value. I call this selection a Path, Pi.  A path can be complete, meaning it has a selection from all S, or it can be partial where only x offers are contained within it.  Also M

In addition, there exists a function IsCompatable(path) that returns true if a path is compatible. Whether a path is compatible or  is completely arbitrary.  The Max valued path must be compatible.  This is why I can not trivially select the M largest Items from each set.

In addition each set contains a NULL item, so that an item need not be selected from that set.

The Trivial Algorithm would to make a search tree and generate all possible combinations of items in S, with each path to the trees leaves said to be a path.

let G(P) be the current value (the summed value of each item) of the partial path.
Let H(P) be an estimation (heuristic) of the value of the future path.
H(P) = The Y values from Y items from Y Si in S. Each item is the item with the maximum value in the Si where i > len(P). Y = M - the current length of the partial path P.

To Find the path with the greatest value, I keep a sorted Queue of partial paths, sorted on their values + their possible future values, ie G(Pi) + H(Pi).  I Initialize this Queue by adding paths contained in S1.

While the Queue is not empty or a path has not been found:
    p = Pop the path from the top of Q
    if p is Complete:
        A full path has been found
        return p
    find the possible children of p by adding an item to p from the next set.
    for child in Children:
        if IsCompatable(child):
            add child back to Q in sorted order on G(child) + H(child)

There it is, now is my Heuristic admissible?

It seems to me (and correct me if I'm wrong) that a regular A* algorithm would work absolutely fine with your problem. The problem is that you're confused about the word underestimates. When we're searching for the shortest path we want a heuristic that will never lead us down a path that will be longer than what we estimate it to be, in your case you never want to be led down a path that will be less than what you estimate it to be (which you say you have).

A heuristic is a function that gives $h(n) = 0$ at the goal.

An admissible heuristic is one that never overestimates the distance to the goal. In your cause you want the longest path rather than the shortest, so an admissible heuristic never underestimates the distance to the goal.

So if you have a heuristic that gives you at least the correct distance from the current node to the goal node or a larger value and you order your queue by largest $f(n)$ then you have a correct implementation of A*.

On the other hand if your heuristic both may underestimate or overestimate you're aren't guaranteed to find an optimal path.

We can prove the optimality of this easily (this is an adapted proof from Russell and Norvig's Artificial Intelligence A Modern Approach).

Let $G$ be an optimal goal state, with path cost $f^*$. Let $G_2$ be a suboptimal goal state with path cost $g(G_2) < f^*$. Now assume that A* has selected $G_2$ from the queue. Because $G_2$ is a goal state it would terminate the search with a suboptimal solution.

Consider a node $n$ that is a leaf node on an optimal path to $G$. Because $h$ is admissible (never underestimates), we must have

$f^* \leq f(n)$

And if $n$ was not chosen over $G_2$ then

$f(n) \leq f(G_2)$

Combining these we get

$f^* \leq f(G_2)$

Because $G_2$ is a goal state $h(G_2) = 0$ thus $f(G_2) = g(G_2)$. So we have a contradiction that $f^*$ is an optimal longest path and that $G_2$ is suboptimal. Thus A* will never expand a suboptimal solution and is an optimal algorithm.


Universal/existential quantification? I'm struggling to understand the purpose of universal and existential quantification of types. I'm playing around with writing a toy language based on the calculus of constructions. I've been reading about Morte and Henk to help me get a better understanding.

I don't understand why the CoC has both lambda and forall abstraction.

$$(\lambda x:A . B)$$
$$(\forall x:A . B)$$

It seems to me that lambda subsumes forall in a system where types are passed manually. In other words, that the following

$$(\forall x : *. \lambda a : x. a)$$

Could be replaced with

$$(\lambda x : *. \lambda a : x. a)$$

If it was first applied to the type being used.

What am I missing? What papers or blogs or articles are there to read that might help me?

Thanks.

It helps to remember that $\forall$ (or $\Pi$ as you sometimes see) is a type. It's generalizing $\to$. So while it makes perfect sense to say $(\lambda x : A. M)\ N$, it doesn't make sense to say $(\forall x : A. M)\ N$ because $\forall ...$ is just a type. You wouldn't say $(A \to B)\ N$ becaues $\to$ isn't for computing per-se, it's there to classify lambda terms which can be applied like this.

This was something that tripped me up as well, but this is how the calculus of constructions (as well as any other dependently typed system is defined).

The two programs you wrote have very different intentions and the first one is ill-typed. It doesn't make sense to say $\forall x : A.\ \lambda x.\ x$ because $\forall$ requires both its arguments by types which means that if $\forall x : A. B$ is to be well-typed, we must have $B : *$. However, $\lambda x. x$ isn't a type, it can only ever be assigned a type of the form $\forall x : A. B$, never $*$. The second one on the other hand is almost (I think you meant to return $a$ not $x$) is a function and is given a type using two $\forall$s.


Smallest segment after whose removal all elements are distinct I am interested in the following problem:

  We are given an array of integers and we need to find the size of smallest subsegment such that after removing it all elements in the array are distinct.

How to solve this problem using binary search in $O(n\log n)$? I tried to read various submissions which use binary search, for example this one, but I couldn't understand them.

My attempt - I solved this problem in $O(n^2\log n)$ using brute force, but I want to know how to apply binary search to solve this problem in $O(n\log n)$.

The idea is that you can check whether the answer is at most some value $m$ in time $O(n)$. Applying binary search on $m$, you obtain an $O(n\log n)$ solution.

How do you check whether the answer is at most $m$ in time $O(n)$? The idea is to slide a window of length $m$ across your array. If at some point all elements outside the window are distinct, then we are done.

How do we implement this sliding algorithm? Let $A$ be the original array. We initialize an array $M$ which contains the histogram of the elements in $A_{m+1},\ldots,A_n$, as well as the number of distinct elements $x$. If $x = n-m$ then we are done. Otherwise, we modify $M$ to contain the histogram of $A_1,A_{m+2},\ldots,A_n$:

We remove one copy of the element $A_{m+1}$ from $M$. If the new count of this element is $0$, then we decrease $x$.
We add one copy of the element $A_1$ to $M$. If the new count of this element is $1$, then we increase $x$.

In this way, we can update $M$ in time $O(1)$ per shift.

The solution you link to does all this, apart from maintaining $x$; this is done automatically by the C++ map data structure.

Another point is the time complexity of this solution, which might depend on your exact computation model.


Does hiding variables work in terms of blocks or line-by-line? Let's assume I have the following code:

declaration of a
declaration of b
..a..b
{
  ..a..b
  declaration of a
  declaration of b
  ..a
}

In this code {} represent the inner block. declaration represents binding occurrence, and .. represent applied occurrence.

So my question is that is it legal to use the outer scope variables inside an inner scope and then redeclare them ? If so how does the hiding of outer variables system work (Does it start to work when it sees a redeclaration)? Thanks in advance.

It depends on the programming language.  It's up to each language to specify whether this is legal or not, and what it means.

In many languages this would be legal.  It is called variable shadowing.


In NLP, does the lexer have to tag the tokens before the parser? In NLP, does the lexer have to tag the tokens before the parser?

I.e. does the lexer have to classify the tokens to morphological categories before the parser?

I'm thinking yes, but is this also the only way to do the parsing?

Morphological tags can help the parser. On the other hand, the complete sentence structure, maybe even the paragraph context may help to finally disambiguate possible tags for a token. So there is no yes/no answer. Except, maybe, that tagging is, afaik, usually not attributed as work of the lexer, but rather a module of its own.


Meaning of $ e^x = 1 + x + Θ(x^2)$? In the CLRS chapter 3: When $x → 0$, the approximation of $e^x$ by $1+x$ is quite good:

  $$e^x = 1 + x + Θ(x^2).$$

How is it to be interpreted, what is the role of asymptotic notation here?

There are constants $c,C,\epsilon > 0$, such that $1+x+cx^2 \le e^x \le 1+x+Cx^2$ whenever $|x| \leq \epsilon$.


Is there any algorithm that finds the time complexity of another algorithm provided that it halts? Let us suppose that we have some algorithm A that halts for all valid inputs, can we prove the existence of another algorithm B that takes A as input and calculates the time complexity of A.
Are there any examples of existing algorithms/programs that do this?

I think this is correct and incorrect at the same time. It depends on how we define the problem we want to solve.
Formulation I
If we are interested in an algorithm that given $\langle M, w\rangle$ will tell you how much time $M$ runs on $w$ (assuming it halts), then there is such an algorithm: emulate $M$ on $w$ and count the number of steps it does until it halts.

Formulation II
But, if we are interested in an algorithm that given $\langle M\rangle$ will give you a function $f:\mathbb{N}\rightarrow \mathbb{N}$ that bounds the running time of $M$, things get a little bit more complicated.
First, how do we describe a function $f$ with finite storage? there are $|\mathbb{N}^\mathbb{N}|=2^{\aleph_0}$ functions, and $2^{\aleph_0}$ words in $\{0,1\}^*$ as well. This means there is some way to map each word to a function and vice versa. We will ignore from now the problem of computing this mapping between words and functions, and will still show there is no algorithm for the problem.
Assume towards contradiction there is some $\hat M$ that solves our problem. Let us create a new machine $M'$ that given input $\langle M\rangle $, will first emulate $\hat M$ on $M$ to find some $f$ which describes the upper bound on the time it takes $M$ to halt (assuming it halts). Then, $M'$ will enter a loop for $f(|\langle M'\rangle |) + 1$ steps.
Now, consider what happens when $M'$ runs on the input $\langle M'\rangle$. $\hat M$ will give an upper bound $f$ on the running time of $M'$, and $M'$ will run for more than $f(|\langle M' \rangle|)$ steps, contradicting that $f$ is an upper bound (since the original input of $M'$ was $\langle M'\rangle$).
Thus, no such $\hat M$ can ever exist!


String similarity problem We are given two strings $x=x_1,x_2,x_3,\ldots,x_m$ and $y=y_1,y_2,y_3,\ldots,y_n$ over some finite alphabet.
  We consider the problem of converting $x$ to $y$. Using the following operations:

  1.Substitution: replace one symbol by another one.

  2.Insertion: inserts one symbol

  3.Deletion: delete one symbol.

For example, if $x$="logarithm" and $y$="algorithm", we convert $x$ to $y$ in the following way:

start with "logarithm"
inserting "a"at the front gives "alogarithm".
deleting "o"gives "algarithm"
replacing the second "a"by "o"gives "algorithm".

The similarity problem between the string $x$ and $y$ is defined to be the minimum number of operations needed to convert $x$ to $y$.

For example, the similarity between $x$="logarithm" and $y$="algorithm" is 3, because $x$ can be converted to $y$ using three operations. If the string $x$ has length $m$ and the string $y$ is empty, then the similarity between $x$ and $y$ is similar to $m$.

Give a dynamic programming algorithm (in pseudocode) that computes, in $\mathcal o(mn)$ time, the similarity between the string $x$ and $y$.

It is as the edit distance problem but there is the corresponding minimization problem problem where we measure similarity instead of distance .

Just like @Hendrik mention all you need to do is calculate Levenshtein distance which does exactly what you need.

Levenshtein distance can be expressed in following formulae
$$
\mbox{lev}_{a,b}(i, j) = \begin{cases}
    \max(i,j) &, \mbox{if } \min(i,j) = 0
    \\ \min \begin{cases}
           \mbox{lev}_{a,b}(i-1,j) +1 \\
           \mbox{lev}_{a,b}(i, j-1)+1 \\
           \mbox{lev}_{a,b}(i-1,j-1) +[a_i \neq b_i]
       \end{cases}
    &, \mbox{else}
\end{cases}
$$
Where $a, b$ are compared strings, $i, j$ are strings length and $[a_i \neq b_i]$ is $1$ iff $a_i \neq b_i$ and $0$ otherwise.

From this formula it can be easy translated to pseudocode.

Lev(a, b)
  len_a = len(a)
  len_b = len(b)
  cost = 0

  if(a[0] != b[0])
    cost = 1

  if (len_a == 0 or len_b == 0)
    return max(len_a, len_b)
  return min(Lev(a[1..len_a-1], b) + 1,
             Lev(a, b[1..len_b-1]) + 1,
             Lev(a[1..len_a-1], b[1..len_b-1]) + cost)

However there is small problem with this solution, its running time is $\mathcal O(nm)$ and you requested $\mathcal o(nm)$ so I hope you just made a typo.

You can also calculate this distance online using this website.


Are Turing machines more powerful than pushdown automata? I've came up with a result while reading some automata books, that Turing machines appear to be more powerful than pushdown automata. Since the tape of a Turing machine can always be made to behave like a stack, it'd seem that we can actually claim that TMs are more powerful.

Is this true?

You can't go to the bottom of the stack without "forgetting" the rest of the stack. With a Turing machine you can easily go back and forth on the tape.

This simple task cannot be done with a pushdown transducer (roughly the same thing as the pushdown automata, but that can write things at each step), but can easily be done with a tape:

  Read a string $w$ and then write the string twice: $ww$

If you don't want to hear about transducers, the similar problem is for you: this language is easily recognized by a Turing machine, but not with a pushdown automaton:

$$L = \{ ww \mid w \in Σ^* \}$$

but I think with a transducer you get a grasp of the difference.


Free variables of (λx.xy)x and bound variables of λxy.x I was solving exercises on Lambda calculus. However, my solutions are different from the answers and I cannot see what is wrong.

Find free variables of $(\lambda x.xy)x$.
My workings: $FV((\lambda x.xy)x)=FV(\lambda x.xy) \cup FV(x)=\{y\} \cup \{x\}=\{x,y\}$.
The model answer: $FV((\lambda x.xy)x)=\{x\}$.
Find bound variables of $\lambda xy.x$.
My workings: A variable $y$ has its binding but since it is not present in the body of the $\lambda$-abstraction it cannot be bound and thus $BV(\lambda xy.x)=\{x\}$ only.
The model answer: $BV(\lambda xy.x)=\{x, y\}$.

Your answer is correct, $y$ is surely free. The model one is wrong. Maybe there was a typo and the answer was meant for $(\lambda y.xy)x$
It depends on the precise definition of $BV$. Often only $FV$ is defined formally, because it's more important. (Bound variables can be freely renamed in a subterm, but free variables can't.) So if $BV$ is defined as
\begin{eqnarray*}
      BV(x) &=& \{\} \\
      BV(M N) &=& BV(M)\cup BV(N) \\
      BV(\lambda x.M) &=& \{x\}\cup BV(M) \\
    \end{eqnarray*}
then the model answer is correct. Note that this definition makes sense: If you have a term $M$ and substitute for a free variable $x$ another term $N$ with no bound variables ($BV(N)=\{\}$), you expect that $BV(M)=BV(M[x:=N])$. If you'd consider only bound variables that also appear under the $\lambda$, this property wouldn't hold.


Help on the notation of the 2-bit operation: $\frac 12{(I+Z_1Z_0)}$ This was adapted from Quantum Mechanichs for Computer Scientists.
On this equation, we have $I$ representing the identity operator, with $Z$ being defined for 1 bit as:

$$ Z|0⟩ = |0⟩, \quad Z|1⟩ = -|1⟩\,.$$

The operation $\frac 12{(I+Z_1Z_0)}$ acts as the identity for the two-bit states $|00⟩$ and $|11⟩$  while returning $0$ for the states $|01\rangle$ or $|10\rangle$.

I'm assuming the operator addition is the linear algebra definition, but I can't understand the $\frac 12$ fraction and its effect on the operation.

Could you point me to what concept I am missing, so I can derive the resulting states of this operation?

The operation $I$ on two bits can be written as the identity matrix,
$$
I =
\begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 1 & 0 &0 \\ 0 & 0 & 1 &0 \\ 0 & 0 & 0 &1
\end{pmatrix}\,.
$$

The operation $Z_0Z_1$ that performs $Z$ on both qubits can be written as
$$
Z_0Z_1 =
\begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & -1 & 0 &0 \\ 0 & 0 & -1 &0 \\ 0 & 0 & 0 & 1
\end{pmatrix}\,.
$$

Now, the operation that you ask about, $\frac12(I+Z_0Z_1)$ is simply the operation described by

$$
\frac12(I+Z_0Z_1) =
\frac12 \begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 1 & 0 &0 \\ 0 & 0 & 1 &0 \\ 0 & 0 & 0 &1
\end{pmatrix} +
\frac12 \begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & -1 & 0 &0 \\ 0 & 0 & -1 &0 \\ 0 & 0 & 0 & 1
\end{pmatrix}
=
\begin{pmatrix} 1 & 0 & 0 &0 \\ 0 & 0 & 0 &0 \\ 0 & 0 & 0 &0 \\ 0 & 0 & 0 &1
\end{pmatrix}\,.
$$
This indeed performs as you describe. If the $1/2$ wasn't there, we would get that $|0\rangle$ becomes $2|0\rangle$. Note that his operator is not unitary (it returns "$0$" for $|01\rangle$ and $|10\rangle$, which means the qubit "disappears", this shouldn't be allowed by quantum mechanics.)


Generate Evenly Distributed Pattern Based on Weights I have an array of items $A = \{A_i\}, i \in I $ with integer weights $W_i, i \in I$. I need to build a function $f: I \rightarrow A $, that produces evenly distributed patterns of array elements predictable manner.

For example: an array of 3 elements: $A_1 = 1, A_2 = 2, A_3 = 3$ and weights: $W_1 = 1, W_2 = 2, W_3 = 2$. This means that pattern will consist of 5 repeating elements. One example of this pattern: $1, 2, 3, 2, 3, 1, 2, 3, 2, 3, 1$ (each iteration of 5 elements has exactly one 1, two 2's and two 3's).

What I need is the name of this problem to search for suitable algorithms. Thank you!

Normalize $W$ by calculating the greatest common divisor of $W$ and dividing every element by it.

Then just repeatedly iterate over $W$ in order, and if $W_i > 0$ subtract $1$ from it and output $A_i$. You stop when all $W_i = 0$.

If $1, 2, 2, 3, 3, 1, 2, 2, 3, 3, \dots $ in your example is also fine then just output $W_i$ copies of $A_i$ after normalization.


Measuring the hardness of SAT instances Lemma I am reading the paper Measuring the hardness of SAT instances by Ansótegui, Bonet, Levy and Manyà (Proc. 23rd AAAI Conf. on AI, pp. 222–228, 2008) (PDF).I have two questions the first one is I would like to undersatnd the demonstration for the last claim. Specifically I need an example of the proof tree of $[x\rightarrow b](\Gamma)\vdash \{\Box\}$. And the second one is I would like an example of the last part of the Lemma 3, that is an example of the definition $s(\Gamma)$.

  Lemma 3 The space satisfies the following three properties:

  $s(\Gamma \cup \{\Box\})$ = 0
  For any unsatisfiable formula $\Gamma$, and any partial truth assignment $\phi$, we have $s(\phi(\Gamma))\leq s(\Gamma)$.
  For any unsatisfiable formula $\Gamma$, if $\Box\notin\Gamma$, then there exists a variable $x$ and an assignment $\phi\colon\{x\}\to\{0,1\}$, such that $s(\phi(\Gamma))\leq s(\Gamma)-1$.

  The space of a formula is the minimum measure on formulas that satisfy (1), (2) and (3). In other words, we could define the space as:3

  $$s(\Gamma) = \min_{x, \overline{x}\in\Gamma, b\in\{0,1\}} \big\{
\max\{s([x\mapsto b](\Gamma))+1, s([x\mapsto\overline{b}](\Gamma))\}\;\big\}$$
  when $\Box\notin\Gamma$, and $s(\Gamma\cup\{\Box\}) = 0$.

  3 Note that, since $\Gamma$ is unsatisfiable, it either contains $\Box$ or it contains a variable with both signs.

I trying to understand the proof of that Lemma using this UNSAT formula: $\Gamma = (a+b)(a+b')(a'+c)(a'+c')$. Specifically, in this point:  "From the proof tree of
$[x \rightarrow b](\Gamma) \vdash\{\Box\}$ , adding the literal $x'$ in the clauses where
$[x \rightarrow b]$ has removed it, but preserving the structure of the
proof tree, we get a proof of $\Gamma \vdash x'$". I consider $x=a=1$ then replacing $a'$ in the formula $[a\rightarrow 1](\Gamma)$ I get $(a'+b)(a'+b')(a+c)(a+c')$ that also by resolution is $\{\Box\}$. What is wrong in my example How Do I get $\Gamma \vdash x'$?

*$\{\Box\}$ means the empty clause

First, $[a\to 1]\Gamma = (1)(1)(c)(c')$. A refutation of this consists of resolving $c$ and $c'$. Following the proof, we reinstate $a'$ to get the CNF $(1)(1)(a'+c)(a'+c')$, and then resolve $a'+c$ and $a'+c'$ to get $a'$.

Similarly, $[a\to 0]\Gamma = (b)(b')(1)(1)$, which can be refuted by resolving $b$ and $b'$. Reinstating $a$, we get $(a+b)(a+b')(1)(1)$, and resolving $a+b$ and $a+b'$ we get $a$.

Note that your notation, which is different from the paper's, is confusing you. For example, $x'$ is not the negation of $x$ but rather a new variable symbol.


Coloring a Unicyclic Graph I am trying to design an efficienct algorithm to color a unicyclic graph. I know if a graph does not contain any cycles (it's a tree) then it is 2-colorable. But cycles are either 2 (is even number of vertices) or 3 (is odd number of vertices) colorable. So if there contains just one cycle then the chromatic number of this unicyclic graph should be 3 (if the cycle contains an odd number of vertices).

So enough of that. on to the algorithm.

I would start at a vertex and color it color1. Now I would perform a BSF from the originator. Then each vertex that is adjacent to the originator vertex i would color it color 2, and continue this process of switching from color1 to color 2 unless if one of the vertices has an adjacent vertex that is already colored the same color. That means i found the cycle and will color that vertex color 3. If it had an adajcent vertex that was a different color than what i was going to color it then its an even number cycle and it would be 2-colorable.

So that means, each step of the BFS I would check each vertex adjacent to the vertex selected for that step of the BFS. Therefore $O(|E|)$?

is there a more efficient algorithm to color a unicyclic graph and is my time complexity correct?

Yes, your algorithm is correct. The maximum number of edges that a graph can have without forming a cycle is when it is a tree. Lesser number of edges is only when the graph is disconnected. We will assume that the graph is connected, without loss of generality. In such a case, there would be $|V| - 1$ edges in the graph. Any other edge will create one cycle. So, any connected graph with exactly one cycle will have $|V|$ edges.

In such a case, you are right in doing a BFS to color alternatively the nodes alternatively. What you are doing is essentially starting from a root, and all nodes at odd depth have a different color than the root, and all nodes at an even depth have the same color as the root. If you encounter any node which has 2 colored neighbours (parent is always colored, but one of the children is also colored), then you have found a cycle. As you rightly note, if the second vertex is of a different colour than what you planned, it is an even cycle, and you can just go ahead - you will get a 2-coloring. Otherwise, just assign this vertex the third color, and go on with the alternating between two colors for the rest. This gives a 3-coloring.

As for the complexity, you are doing one BFS, checking for colored neighbors while putting them in the queue. Thus, complexity is $O(|V| + |E|)$, as you are visiting every edge and vertex once. However, since $|E| = |V|$, the overall complexity is $O(|V|)$. To color $|V|$ vertices, you need at least $\Omega(|V|)$ time, and so the algorithm is asymptotically optimal (no asymptotically faster algorithm is possible). This algorithm is $\Theta(|V|)$.


What is the meaning of undecidability in Rice Theorem? Rice theorem says every non-trivial property of languages of Turing machines is undecidable. what is the meaning of undecidability here? is it semi-decidable?

As an example the following language is R.E but it contains a non-trivial property

$A = \{x | \phi_x$ is defined for at least one input$ \}$

this language equals to $Empty$ $Complement$ and it is clearly r.e.(m-complete in fact) while non-emptiness property is non-trivial.

Undecidable means not decidable. Undecidable problems may or may not be semi-decidable.

To see that an undecidable problem is not necessarily semi-decidable, observe that there are uncountably many problems but, since each decidable or semi-decidable problem corresponds to a Turing machine, there are only countably many decidable and semi-decidable problems.


Can lambda-calculus be used for knowledge representation? Natural language semantics (in computational linguistics) uses lambda terms for expressing the semantics of natural language sentences. There is vast literature about combinatorial categorial grammars and lambda semantics of natural language, e.g. tutorial about framework http://yoavartzi.com/tutorial/

The question is - if lambda calculus can be used to represent the meaning of the natural language text, then can we use lambda calculus for the universal representation of knowledge? Why there are so few results in this direction? Or maybe there are efforts to bridge the meaning as expressed in lambda calculus with some of the common knowledge representation approaches?

Maybe (extended) Curry-Howard isomorphism between lambda calculus and logical/deductive systems can be used to translate the semantics in terms of lambda calculus into knowledge in terms of logical expressions, e.g., maybe translation to description logics and action logics is possible?

The λ-calculus was invented to be a logic and foundation of  mathematics (1-4). The most well-known logic to use λ-calculus for formulae (as opposed to proofs in the Curry-Howard approach) is HOL (= Higher-Order Logic). The most well-developed implementation of HOL is Isabelle/HOL (5). To the extent that you believe logic can represent knowledge, you can use HOL to do that, hence λ-calculus.

There is a third approach to using λ-calculus as logic: higher-order Prolog (aka λProlog) (6), which -- like Prolog -- is based proof search, but in HOL.

The relationship between the three approaches (HOL, Curry-Howard and λProlog) is not well-understood.

1. A. Church, A Formulation of the Simple Theory of Types.

2. P. B. Andrews, Churchs Type Theory.

3. F. Cardone, J. R. Hindley, History of Lambda-calculus and Combinatory Logic.

4. J. B. Rosser, Highlights of the history of the lambda-calculus.

5. T. Nipkow L. C. Paulson, M. Wenzel, A Proof Assistant for Higher-Order Logic.

6. D. Miller, G. Nadathur, P. Pfenning, A. Scedrov, Uniform Proofs As A Foundation For Logic Programming.


Decidability of $\lbrace \langle D \rangle \mid \text{$D$ accepts $a^kb^k$ for some $k > 0$}\rbrace$ I'm trying to understand decidable languages. In particular, I would like to show that
$$B = \lbrace \langle D \rangle \mid \exists k \geq 0 \,.\,\text{DFA $D$ accepts $a^k b^k$}\rangle.$$
I don't quite understand the process of proving these. I know that $a^kb^k$ is not regular, so then no DFA accepts it. I also know that $A_{DFA}$ (acceptance DFA) is decidable, I also know several other decidable languages like $E_{DFA}$ and $EQ_{DFA}$. How can I use these to prove that $B$ is decidable?

If no DFA accepts $a^kb^k$, doesn't that mean that $A_{DFA}$ will reject? So if $A_{DFA}$ rejects then shouldn't the decider for $B$ accept?

Hint: Let $s_0$ be the starting state, $F$ the set of accepting states, and $q$ the transition function. The mapping $k \mapsto q(s_0,a^k)$ is eventually periodic and can be determined explicitly. The predicate $(s,k) \mapsto q(s,b^k) \in F$ is eventually periodic and can be determined explicitly. So the predicate $k \mapsto q(q(s_0,a^k),b^k) \in F$ is eventually periodic and can be determined explicitly.

Similarly, you can check whether a DFA accepts some word of the form $a^k b^k c^k$. The fact that the languages $\{ a^k b^k \mid k \in \mathbb{N} \}$ and $\{ a^k b^k c^k \mid k \in \mathbb{N} \}$ are not regular doesn't play any role here.


Software or program, what is the difference? I am a CS student.  When I first came to school, I thought that programming was to make a software.  Now I found I was wrong.  Now I want to know what the difference is, and what is the difference between a programmer and a software engineer. I hope people can give me some advice.  (forgive my broken English)

Expanding Pradhyuman's answer. From Wikipedia:

Software Engineering can be divided into ten subdisciplines that correspond to distinct phases of the software development process. They are:

Software requirements: The elicitation, analysis, specification, and validation of requirements for software.
Software design: The process of defining the architecture, components, interfaces, and other characteristics of a system or component. It is also defined as the result of that process.
Software construction: The detailed creation of working, meaningful software through a combination of coding, verification, unit testing, integration testing, and debugging.
Software testing: The dynamic verification of the behavior of a program on a finite set of test cases, suitably selected from the usually infinite executions domain, against the expected behavior.
Software maintenance: The totality of activities required to provide cost-effective support to software.
Software configuration management: The identification of the configuration of a system at distinct points in time for the purpose of systematically controlling changes to the configuration, and maintaining the integrity and traceability of the configuration throughout the system life cycle.
Software engineering management: The application of management activities—planning, coordinating, measuring, monitoring, controlling, and reporting—to ensure that the development and maintenance of software is systematic, disciplined, and quantified.
Software engineering process: The definition, implementation, assessment, measurement, management, change, and improvement of the software life cycle process itself.
Software engineering tools and methods: The computer-based tools that are intended to assist the software life cycle processes, see Computer Aided Software Engineering, and the methods which impose structure on the software engineering activity with the goal of making the activity systematic and ultimately more likely to be successful.
Software quality: The degree to which a set of inherent characteristics fulfills requirements.

...

As you can see, programmers are mainly required for software construction and maintenance.

A software engineer should have strong knowledges of all the software development phases and should be a good programmer, too (actually most programmers employed in big companies are engineers :-).

Obviously for small software projects some phases may overlap (or may be ignored) and programmers may be involved directly in many of them. For large software projects (like an operating system) there can be hundreds (thousands) of software engineers and programmers involved.


What is a "trap" in the context of system virtualization? My professor's notes on system virtualization refer a lot to the term "trap", but don't seem to explicitly define it. I can't seem to find any definition on Google either, other than a small article on "trap-and-emulate".
From context I sort of understand that trapping is 'catching' any operations that the virtual OS performs which it no longer has the privilege for (as it is now operating in restricted mode), and forwarding them to the hypervisor to be handled.

However could someone who has a more solid understanding of this give me a better definition?

(also I apologize for poor tagging, as there doesn't seem to be a relevant tag for virtual systems)

A trap is basically a localized exception/fault which occurs when the guest OS does not have the required privileges to run a particular instruction. Operating systems running on top of a virtual machine monitor (a hypervisor) do not know that they are running in the 'user' mode i.e. they can only execute a limited set of instructions, since they do not have full control over the bare-metal. So, when the operating system executes some privileged instructions (instructions which can only be run in the 'kernel' mode or some privileged mode), those instructions create a trap that goes into the hypervisor which then emulates the expected functionality of the OS. Note: that the hypervisor runs the commands and emulates it to the application in a VM, so that the application never knows that it is running in a VM.

Source: https://stonefly.com/blog/deep-dive-virtualization


What do we mean by polynomially upper bounded and lower bounded I just came across this asymptotic bound :

$(\log n)!= \Theta \left(n^{\log \log n}\right)$

Which had the following remark:

    Hence, polynomially lower bounded but not upper bounded.

I found this here:

https://gateoverflow.in/12928/%24-log-and-log-log-are-polynomially-bounded-anybody-can-prove

I am confused on how can we conclude whether it's polynomial lower bounded and not upper bounded.

Could someone please help me on understanding this.

Now a polynomial is of the form,$n^{c}$ where $c$ is constant.

Now let $f(n)$ be a constant function. Now it being a constant function we have,

$f(n) \in O(lg (n))$

$\implies lg(f(n)) \in O(lg(lg(n))$

Now $lg(f(n))$ is yet another constant function and let it be $g(n)$

So we have from the previous implication,

$ g(n) \in O(lg(lg(n))$

$\implies n^{g(n)} \in O(n^{lg(lg(n)})$

$\implies n^{lg(lg(n))} \in \Omega(n^{g(n)})$

But $g(n)$ is after all a constant so let it be $c$ then we have from the previous implication,

$n^{lg(lg(n))} \in \Omega(n^{c})$

Now $n^{c}$ is a polynomial and hence $n^{lg(lg(n))}$ is polynomially lower- bounded.

We cannot have the other way around i.e. $n^{lg(lg(n))}$ is upper bounded by a polynomial simply because of the observation, $n^{c} \in O(n^{lg(lg(n)})$ as clearly $lg(lg(n)$ shoots up faster(no doubt) than $c$ a constant.


Regular expression: b|b equal to b? I am solving some example exercises in preparation of a Computational Theory examination.

In Exercise 2, I am tasked with building an NFA and DFA of the regular expression: $(b|bba)^*a$

My question is: Can I simplify $b|bba$ inside the parentheses to $bba$? Are they indeed equivalent or will I be breaking some generality?

I am asking this since it is going to be easier for me to construct the automata after the simplification.

Usually, concatenation is assumed to bind stronger than alternative, so you have $b \mid (bba)$, not $(b \mid b)ba$.

Then no, you can't drop "$b\ \mid$" since $b^+a \subseteq \mathcal{L}\bigl((b \mid bba)^*a\bigr)$ but $b^+a \cap \mathcal{L}\bigl((bba)^*a\bigr) = \emptyset$.

For what it's worth, $\mathcal{L}(b \mid b) = \{b \} = \mathcal{L}(b)$, so that simplification would be valid. More generally, if $\mathcal{L}(r_1) \subseteq \mathcal{L}(r_2)$, then $\mathcal{L}(r_1 \mid r_2) = \mathcal{L}(r_2)$.


How does (non)deterministic time relate to verifiability? So far, from all the research I've done, I've come across 2 different ways that NP time is explained. One is that a nondeterministic turing machine is able to solve the problem in polynomial time. It seems like this is the exact same as being able to verify that a result is correct in polynomial time, but not necessarily solve the problem in polynomial time. Both these ideas make sense, but these ideas seem very different to me. One is talking about solvability of a problem in a nondeterministic context while the other is talking about solvability vs. verifiability. Can you please intuitively explain why they're related, and if this relationship between solvability, verifiability, determinism, nondeterminism applies to harder complexity classes such as EXP vs NEXP?

Here's some intuition for the equivalence proof

$(\implies)$: Suppose we have a non-deterministic Turing Machine $M$ that solves a problem $P$ in polynomial time. When we run $M$ on some accepted input $x$, we make a bunch of decisions non-deterministically, essentially choosing an execution path. If we record each of those choices, this gives is a string with is polynomial in the size of $x$ (since we know $M$ runs in non-deterministic polynomial time). Then the trace of running $M$ on $x$, with each decision point, is a certificate for $x$. We can follow the steps again and check that any string represents a valid run on $M$, and see whether it ends in a YES or NO state.

$(\impliedby)$: Suppose we have a verifier which takes a string $c$ and input $x$ and checks if $c$ is a valid certificate that $x$ is accepted by problem $P$, where  $|c| \leq |x|^k$ for some fixed $k$. Then we can make an NTM which looks at any $x$ and determines whether it is in $P$ by "guessing" non-deterministically guessing a certifier $c$ of length less than $|x|^k$ and running the verifier on that.

EDIT: to apply this to $EXP$ and $NEXP$, just replace the word polynomial with exponential and change the bound on $c$, and the rest should still work. It doesn't really apply to classes like $PSPACE$, since it's not defined in terms of non-deterministic machines. Not being able to make these kinds of guesses are what makes PSPACE harder (as far as we know) than NP.


How come finding an $n/2$ size clique in a directed/ non directed graph is not in $\sf NL$? obviously the "Finding an $n/2$ size clique in a directed/ non directed graph" is not $\sf NL$ but I'd really like to understand where does it fall in terms of the definition of the $\sf NL$ definition.

I have to have an input and witness tapes, both of them can be polynomial and a logarithmic size of work stripe. So why can't I just guess an $n/2$ clique, each time put 2 vertices on the work tape, check that they share an edge, and count them. The witness tape provides me each time two vertices from left to write, in total $O({\frac{n}{2}}^2)$. In order to count that I need $O(\log ({\frac{n}{2}}^2))$ which is logarithmic. so what's lacking or wrong with this attempt?

(Turning my comments into an answer.)

You have to deterministically verify that the $\mathcal{O}(n)$ vertices on your witness tape form a clique.  Since you can only move to the right, you can only do linear amount of work for this set, however there are $\mathcal{O}(n^2)$ pairs of vertices in the clique, and you have to check every pair.  Hence you cannot check every pair and thus not verify if it is a clique or not.

Note that this is not a proof that $\mathbf{Clique}$ is not in $\mathsf{NL}$, only that this algorithm (or idea) doesn't work.


Choosing error rates for probabilistic algorithms Probabilistic algorithms often have a parameter that allows one to tune the error rate, typically by running the algorithm repeatedly. This often gives an error rate of something like $2^{-k}$ for $k$ iterations. This is a fine situation to be in, because $2^{-k}$ can be made as close to $1$ as you like without having to make $k$ very big at all. At this point, the theoretician sits back contentedly, his or her job done.

In practical terms, though, are there any guidelines as to which value of $k$ should one choose? Obviously, there's no universal answer, since the answer in any particular situation will be a trade-off depending on the importance of avoiding errors and the cost of doing more iterations.

For example, choosing $k=10$ gives an error rate of about one in a thousand, which seems rather high for most purposes; choosing $k=60$ means the expected number of errors would still be less than one even if you'd run the algorithm once a second since the big bang.

This is the arithmetic for Juho's answer.  (Run it for the length of time it takes to make the algorithm failure probability equal the hardware failure probability).

Suppose it takes time $t$ seconds to perform one computation, and thus time $kt$ to get the algorithm error probability down to $2^{-k}$.

Suppose that the hardware probability of failure per second is $p$.  Then the probability of a hardware failure is approximately $ktp$ (see lemma below).  So you want the $k$ that is the solution to

$$ \frac{1}{2^k} = ktp. $$

Lemma

Assume a memoryless failure process with a failure rate per time period of $p$.  Let $P=1/p$ (makes the arithmetic easier).  Then for very small $p$ (large $P$) the probability of success in $k$ time periods is

$$ 1 - (\frac{P-1}{P})^k = \frac{P^k - (P-1)^k}{P^k}.$$

By the binomial theorem this is

$$ \frac{P^k - P^k +kP^{k-1} + \frac{k(k-1)}{2}P^{k-2} + \cdots }{P^k} \approx \frac{k}{P} = kp.$$

Value of $p$

Also assuming memorylessness and independence and all that good stuff, the numbers in the paper that Juho provided give a failure rate (memory, disk and cpu) of about $1/180$ in 5 days, which is 432000 seconds, so the probability of failure in 1 second is something like $p = 1/77543800 \approx 2^{-26}$, but you want a lower probability than that, so you should probably use $2^{-27}.$

Thus you want k such that

$$ 2^{27-k} \lt kt$$
$$ 27-k \lt \log_2 k + \log_2 t $$
$$ 27 - \log_2 k - \log_2 t \lt k.$$

But for $k > 1$, $\log_2 k > 0$ so choose

$$ k > 27 - \log_2 t.  $$


What are flops and how are they benchmarked? Apple has just proudly stated that their new mac pro will be able to give up to 7 teraflops of computing power. Flops stands for Floating Point Operations Per Second. How exactly is this benchmarked though? Certain floating point operations are much heavier than others, so how exactly would a FLOP be a benchmark for computing power?

As far as I know, they give peak performance values. Given clock speed $f$ (in Hz) and number of cycles per (shortest) floating point operation $c$, the peak performance is essentially $f \cdot c$.

Of course, modern machines execute multiple floating point operations in parallel, have multiple cores etc. A more accurate formula can be found on Wikipedia.

This measure ignores all of the pain any real program encounters, e.g. cache misses and pipeline stalls. That is, any (reasonable) benchmark will not reach this number. But as an (unattainable) ultimate figure it can be useful to compare machines and even programs (how close to peak performance do they get?) -- take such statements with a grain of salt, always.