High Level Explanation of the Pumping Lemma I have a problem that I cannot figure out regarding using the pumping lemma to prove that a language is not regular. I don't understand how I go about proving through contradiction that the language is not regular.

When I read about the pumping lemma, all I am finding are complicated explanations involving $x$, $y$, $z$ and $m$ which seems difficult to understand.

I would appreciate if someone could provide a high level overview of the pumping lemma, and possible an example of proving a language is not regular with its use.

By definition, a language is regular if, and only if, it is accepted by a deterministic finite automaton (DFA). So, given a language $L$, suppose it is accepted by some DFA $M$. $M$ has some number of states: let's call it $p$.  Now, consider the operation of $M$ on a string $w\in L$ that has length greater than $p$.

If $M$ accepts $L$, then it must accept $w$.  By the pigeonhole principle, there must be at least one state $q$ that $M$ visits twice. Write $w=xyz$, where $x$ is the sequence of characters that $M$ reads until it first reaches $q$, $y$ is the sequence of characters read between the first and second visits to $q$ and $z$ is the rest of $w$. Note that $y$ must be at least one character, since it occurs between the first and second visit to $q$, which are different positions in the input. Observe that:

from the initial state, reading $x$ takes you to state $q$;
from state $q$, reading $y$ takes you back to $q$;
from state $q$, reading $z$ takes you to an accepting state.

The key point is that, from $q$, reading $y$ any number of times, including zero, will return you to state $q$ and you can then read $z$ to get to an accepting state. Therefore, the machine $M$ accepts any string of the form $xy^rz$ for $r\geq 0$.  We have just proved the pumping lemma.

For examples of using the pumping lemma, see our reference question. In essence, you say, "If this language was regular, it would have to obey the pumping lemma. But if it did that, it would have to include all of these strings that it doesn't include. Therefore, it's not regular."


How to do compare-and-increment different locations with in memory MVCC? I'm reading the paper An Empirical Evaluation of
In-Memory Multi-Version Concurrency Control which is about implementations of MVCC for in-memory databases. Section 3.3 on Two-phase Locking (MV2PL) says:

  To perform a read operation on a tuple A, the DBMS searches for a
  visible version by comparing a transaction’s T-id with the tuples’
  begin-ts field.  If it finds a valid version, then the DBMS
  increments that tuple’s read-cnt field if its txn-id field is
  equal to zero (meaning that no other transaction holds the write lock)

Here is the image in Figure 2c:

The confusion point is about how it actually does this operation atomically: Read location A (txn-id), if its value is equal to 0 then increment location B (read-cnt)

Atomic operation in C/C++ does compare-and-swap only for a single memory location, however, in this case we are dealing with two memory locations. Is there any other CPU intrinsic for this operation, or another trick is employed?

I asked the question directly from paper authors, and they replied to me:

  txn-id and read-cnt are 4-bytes each (not 8 bytes as I thought before), thus it is possible to compare-and-swap in one step.


Minimum difference of sums So hey, I've recently found this problem online and I tried hard to solve but couldn't found an efficient solution. The problem statement is:

Given and two integers $n$ and $k$ and an array $A$ containing $n$ pairs of integers of the form $(a, b)$ and $d$ defined as $d = |\sum_{x \in E} x[1] -x[0]| $ where is $E$ is a subset of $A$ containing exactly $k$ elements. Find the minimum value of $d$.

To illustrate the problem, consider $n = 3$, $k = 2$,  $A = [(2, 1), (0, 2), (1, 2)]$.

The minimum value of $d$ is $0$. We can pick $E = [(1, 2), (2, 1)]$ containing $k = 2$ values of $A$ then $d = |(1 - 2) + (2 - 1)| = |0| = 0$.

I tried to solve this problem but only came up with the brute force solution which is terrible in terms of time complexity.

  How can one solve this problem efficiently ?

I'm unable to add comments but I think this problem can be simplified to:

B = []
for pair in A:
    B.append(pair[0] - pair[1])

min_sum(B, k)

min_sum returns k elements that add up to give the smallest number possible (absolute value). This (at least to me) feels easier to work with.


How to write the turing machine processing operations? I have this Turing machine example given in my book:

For the language $0^n1^n$. I understand how it works because it's very similar to a Finite State Machine.
But what I want to know is the following:

What is the $|-$ symbol is for what are the states $q_0$, $q_1$ doing in middle of everything. Unfortunately my textbook doesn't explain any of it.

The state marks the position of the head (as well as the current state): for example, in $q_00011$, the head is to the left of $0011$, and in $xq_1011$, it is to the left of $011$.

The notation $\sigma \vdash \tau$ means that the configuration $\sigma$ leads, after one step of the Turing machine, to the configuration $\tau$.

As David Richerby mentions in his comment, all of this is explained in your textbook at some point.


What are the differences between approximation of AIXI and deep reinforcement learning AIXI is a theoretical formulation for artificial general intelligence. While AIXI is computationally intractable, there are approximations of AIXI like https://arxiv.org/abs/0909.0801 that are computable.

Some time ago, I stumbled upon theoretical artificial general intelligence, and I would like to know what are the practical differences between approximations of AIXI and deep reinforcement learning methods.

It's a bit of an apples and oranges comparison. AIXI is a proposal for how generalized learning should be structured, while neural networks are a specific learning implementation.

That being said, you probably wouldn't want to use an AIXI implementation for a known task such as game AI. Game AI is a specific learning task, so it's better and easier to use an AI specifically tailored to that task. The AlphaGo AI, for example, combined a deep learning neural network for finding interesting looking moves with a positional analysis engine for figuring out the strength of those moves. That sort of architecture works great for learning to play Go, but it's not general.


Turing machine for $u<v$ with $u$ and $v$ positive binary numbers I was wondering how would I go about constructing a Turing machine that accepts $u < v$ with $u$ and $v$ positive binary numbers: for example $10<100$ is accepted but $11<10$ would not be. (We can assume that the leftmost digit is always a $1$). I was thinking that I should start by changing the $1$s to $X$s but that doesn't seem to work out.

So, firstly let's define the input tape.
Let's say it looks like "10101<00101" i.e. "number1< number2" and accepts only if the expression is true. Also, let the head in the start be on the most left meaningful character. The idea of the algorithm is just to scan two numbers from the left (assuming big-endian encoding for the numbers), if noticed that there is 0<1 accept immediately, if 0<0 or 1<1 then continue working, if 1<0 then reject.

So, TM sketch:

alphabet is $\{0,1,*,<\}$ with empty symbol $\epsilon$.

Record the most left bit of the first number
If it is 0 you change you state to something like num1_0 which means number 1 had the leftmost digit 0. Then you go to the right and look for the leftmost digit for the second number. If it is greater than do no accept else move the head to the left most and start from the beginning. Also, when compared two bits just change them to * , so you know where to compare next.

The tape progression looks like this:

101<111

*01<*11

**1<**1

***<***

accept.

Using this simulator I have come up with the following code:

name: Accepting when num1<num2
init: s0
accept: sfin

//main program
s0,0
s1_0,a,>

s0,1
s1_1,a,>

//uncomment this to allow equality
//s0,<
//sfin,<,-

//s1_b means we read the leftmost symbol and it was b
s1_0,0
s1_0,0,>

s1_0,1
s1_0,1,>

s1_0,<
p0,<,>

s1_1,0
s1_1,0,>

s1_1,1
s1_1,1,>

s1_1,<
p1,<,>

//pb means the symbol read from the left number was b and we are looking for the digit from the right number
p0,b
p0,b,>

p1,b
p1,b,>

//COMPARISON LOGIC HERE

//if 0<0 continue exploring
p0,0
goleft,b,<

//if 0<1 immedaitely report yes
p0,1
sfin,b,-

//if 1<1 continue exploring
p1,1
goleft,b,<

//goleft state simply tells to go until reached a to start over
goleft,b
goleft,b,<

goleft,0
goleft,0,<

goleft,1
goleft,1,<

goleft,<
goleft,<,<

goleft,a
s0,a,>

This accepts only when the input tape has the true expression number1< number2 like

  100100<100101

and it is limited to compare only the numbers of equal length (easy fix if needed to compare with different length, think about adding zeros to the first number until it matches the length of the second or reject if the length of the first number is greater).


Maximum-coverage minimum-overlap intersection of sets I'm having troubles finding information on how to solve/optimize a problem I'm currently facing, which probably means I'm either approaching it poorly and/or I don't know what to search for.
The question I think I need the answer to: given several sets of possibilities, what is the smallest number of sets I must select to cover the entire range of possibilities? Alternatively, what is the smallest number of cameras I need to have 100% coverage of all points of interest? The latter is the real underlying form of the question, but the former may be an XY problem.
How do I optimize this problem?

My specific scenario is a little complex to describe here, but here's a simplistic scenario that should be sufficiently analogous:
Imagine I have a large facility with many specific places I want to be under the supervision of security cameras ("targets"), and imagine I have a lot of different places I could put cameras ("sentries").
Naturally, each possible sentry position can see some set of targets - some may not be able to see any, some may one see one, but many may see many.
I'm trying to find a way to place the smallest number of cameras to have complete coverage of all the targets. I suspect this will naturally also become a minimum-overlap problem, but does not have to be.

My sets are small enough that I am able to quickly fully enumerate every sentry position and the set of all target positions it can see, which I can either represent (in python) as the set of target indexes (e.g. set([1,3,4])) or a numpy array that's a bitmask of targets viewable (e.g. numpy.array([False,True,False,True,True],dtype=bool)), or another form if another form is more valuable. (Technically, I'm enumerating all sets of targets which are viewable by a single camera, and for every one of those sets there may be multiple camera positions which can see that set, but this difference is immaterial to the end goal).
I know from experience that if I start exhaustively enumerating all combinations of those to find full-coverage sets, even if I aggressively stop searching if I've exceeded my previous-best camera counts, that this will explode too quickly to run.
My end optimization goal is to find the minimum number of cameras. The minimum overlap isn't important (in fact, maximum overlap may be preferred when reasonable), but the number of cameras is the single most-important factor; given the choice between 6 cameras with no overlap and 7 cameras with lots of overlap, the 6 will always be preferred.

Without knowing anything about the restrictions to your problem, the general version is Set cover, one of Karp's 21 NP-complete problems.
However, if you know more about the structure of the data, you might be able to get better algorithms, see for example the Art gallery problem, where you are given a polygon, and want to find the minimum number of guards/cameras you should place that cover the entire polygon.


Why isn't coNP = NP? I am having trouble understanding the class $coNP$. We defined

$$coNP = \left\{ \overline{A} : A \in NP \right\}$$

As far as I know, a language $A$ is in $NP$ if, and only if, a non-deterministic turing machine $M$ exists, which outputs $1$ if $w \in A$ and $0$ if $w \notin A$. But if this is true, then a turing machine $M'$ must exist which simulates $M$ and inverts the output:

$$M' = \begin{cases}0 \text{ if } M = 1\\1 \text{ if } M = 0\end{cases}$$

Therefore, $w \in A \implies w \notin L(M')$ and $w \notin A \implies w \in L(M')$, meaning that $L(M') = \overline{L(M)}$.

As $M'$ works in non-deterministic polynomial time, $L(M') \in NP$, and as $L(M') = \overline{L(M)}$, $\overline{L(M)} \in NP$, but $\overline{L(M)} \in coNP$ as well. As this holds true for all languages in $NP$, why isn't $coNP = NP$?

A problem in NP can be solved quickly if the answer is YES. Your inverted Turing machine finds the answer quickly if the answer to the original question is YES and the answer to the inverted question is NO. You need an answer quickly if the answer to the inverted question is YES and to the original is NO, and you don't have that.

Edit: Take for example the "Travelling Salesman" problem. I give you a list of cities to visit and ask you "is there a tour to visit them all that is at most 957 miles"? If the answer is YES then there is such a tour, so all your nondeterministic TM has to do is take such a tour and verify in polynomial time that it is indeed 957 miles or shorter. You only need to check one tour (the right one) to prove the answer is YES. If the answer is NO then you have to check all possible tours and see that none is short enough. Proving the answer is NO is a lot, lot harder.


Database Theory - Does the dependency preservation and lossless join properties hold for every decomposition of a relation into 3NF? I was reading Database Systems, 6th ed by Ramez Elmasri and Shamkant Navathe. In the textbook they make a claim (in Chapter 15, section 15.2 Properties of Relational Decompositions) which I quote below:

  Claim 1. It is always possible to find a dependency-preserving decomposition $D$ with respect to $F$ [$F$ is the set of FDs of a relation $R$] such that each relation $R_i$ in $D$ is in 3NF

I have a few questions regarding this.

Is it possible to have multiple (different) decompositions of a relation into 3NF, as the claim seems to imply?
Is it the case that every decomposition (assuming the answer to first is Yes) of a relation into 3NF is dependency preserving? If not, please provide an example where a decomposition into 3NF does not uphold the dependency preserving property. Also, what about lossless join property?

Thanks!

Is it possible to have multiple (different) decompositions of a relation into 3NF, as the claim seems to imply?

Yes, consider for instance the relation schema R(A, B, C, D), with F, a cover of the functional dependencies holding in R, equal to:

A → B
C A → D
D → A

Both the decomposition:

R1(A B)
R2(A D)
R3(C D)

and

R1(A B)
R2(A C D)

are in 3NF (actually the first is also in BCNF).

  Is it the case that every decomposition (assuming the answer to first is Yes) of a relation into 3NF is dependency preserving?

No, in the first decomposition the functional dependency AC → D is not preserved.
Note that both decompositions are lossless (in general, there is no interest in lossy decompositions).

Final note: since there are different possible decompositions, these and their properties depends on the algorithm used to find them. For instance, the classical “analysis” algorithm for BCNF is guaranteed to produce a lossless decomposition, but it is not guaranteed to preserve the dependencies, while the classical “synthesis” algorithm to produce the 3NF is guaranteed to be lossless and preserve the dependencies, as well (but it could find a decomposition in which not all the anomalies are eliminated).


How to convert a decision tree to an automaton? From what I know,

a problem can be transformed to a yes/no answer, which can be
described by a decision tree.
Solution to a problem also can be represented by a set of strings (a language), which means the problem can be regarded as a membership problem.
This set of strings can
also be represented by an automaton, although how it is done is still
vague in my mind.

My questions are:

What is the relationship between a decision tree and an automaton?

How to convert a decision tree to an automaton?

I have tried to read some articles related to this, and somehow 'know' these concepts are related with each other, but still feel that I don't quite understand the relation and how to convert them to each other.

A decision tree is a model of computation which makes sense for instance of constant size. In contrast, a language is usually a collection of instances of unbounded size. An automaton (in this context) is a model of computation which describes a language.
The upshot of all this is that in most circumstances, it doesn't really make sense to convert a decision tree to an automaton.
Here are some examples:

Determining whether a person is overweight given their age, gender, height, and weight. This can be solved by a decision tree, or by a table.
Deciding whether a 64x64 image describes a dog or a cat. This can also be solved by a decision tree, though that's not recommended.
Deciding whether a given integer is a prime. This decision problem defines a language, the language of primes. Agrawal, Kayal and Saxena gave an efficient procedure for solving this problem in 2002, which however cannot be implemented by the kind of automata usually considered in theory of computation classes (DFA, NFA, PDA).
Deciding whether a given string is a palindrome. This decision problem defines a language, and can be solved by a pushdown automaton, but not by a DFA/NFA.


Busy Beaver machines on semi-infinite tape The Busy Beaver problem is to find the largest number of non-blank characters that are printed by a terminating Turing machine of no more than a given size on the blank input.

The usual Busy Beaver machines run on a blank tape that is infinite in both directions.

  Is there any research (and/or experiments) on Busy Beavers machines that run on a semi-infinite tape? (the Turing machine's head is initially positioned on the first cell of the tape)

With a semi-infinite tape we must also consider what happens if the head tries to cross the boundary at the beginning of the tape; the two approaches:

the computation halts
the head "bounces" to cell 2

probably lead to different results.

We look to the first approach in this answer.

Let us denote this new function by $\Sigma_{\mathrm{semi}}(n)$.

Also, call the function of the second approach $\Sigma_{\mathrm{bounce}}(n)$.

Also, denote the original Busy Beaver function by $\Sigma(n)$.

First note that $\Sigma(n) \geq \Sigma_{\mathrm{semi}}(n)$ and $\Sigma_{\mathrm{bounce}}(n) \geq \Sigma_{\mathrm{semi}}(n)$, since every program that works for semi also works for bounce and the original version.

 Uncomputability of $\Sigma_{\mathrm{semi}}(n)$

In this part of the answer, I'll prove that $\Sigma_{\mathrm{semi}}(14n+3)>\Sigma(n)$, therefore it is uncomputable. (If it were computable, then $\Sigma(n)$ would be upper-bounded by a computable function, contradiction.)

This implies that $\Sigma_{\mathrm{bounce}}(n)$ is also uncomputable.

 Definitions

Number all cells on the tape, starting with 1 for the first cell.

We call the number of the cell the index.

Group every pair of consecutive cells such that the first cell in the pair has an on the tape into one macro cell, so the tape looks like

(1,2)(3,4)(5,6)(7,8)....

 Constructing a new machine

Consider the Busy Beaver with $n$ states that leaves $\Sigma(n)$ ones on the tape with states $B_1, B_2, B_3, \cdots B_n$. We leave the new symbol and direction intact, but instead of going to a new state $B_i$, we go to $B_{i,\mathrm{left}}$ if the direction is left, and to $B_{i,\mathrm{right}}$ if the direction is right. (Exception: If the new state is $\mathrm{HALT}$, then it remains $\mathrm{HALT}$.) We construct a machine that needs additional states for each state $B_k$.

The idea of this machine is that all cells with odd index contain exactly two ones: One that is further to the right than any one in a cell with an even index, and one that is at the cell with index 1. If we read the leftmost one, we know that we are on the edge of the tape and then we move the whole tape with even index two indices to the right. Because of the rightmost one we know up to where we should move the tape. So every cell with an even index will be used for executing a normal Turing machine. The cells with odd index will be used to ensure the Turing Machine doesn't run of the tape.

Anyway, here are the states:

$B_{k,\mathrm{right}}$ (odd index): This has the following ruleset:

If it reads a zero, then we go to the right, keep the symbol a zero and go to state $B_k$.
If it reads a one, then we go to the right, make the symbol a zero and go to state $B_{k,1}$.

$B_{k,1}$ (even index): This has the following ruleset:

It doesn't change the symbol it reads and goes to the right and to state $B_{k,2}$.

$B_{k,2}$ (odd index): This has the following ruleset:

If it reads a zero, it changes this into an one and goes to the left and to state $B_{k}$.
It is not possible to read a one in this state. When the machine enters this state, it is on a cell with an odd index. However, we removed a one in state  $B_{k,\mathrm{right}}$ two steps before this, so only the leftmost one remains and we are certainly more to the right than that one.

$B_{k,\mathrm{left}}$ (odd index): This has the following ruleset:

If it reads a zero, then we go to the left, keep the symbol a zero and go to state $B_k$.
If it reads a one, then we go to the right, keep the symbol a one and go to state $B_{k,3}$.

$B_{k,3}$ (even index): This has the following ruleset:

If it reads a zero, it writes a zero and goes to the right and to state $B_{k,4}$
If it reads a one, it writes a zero and goes to the right and to state $B_{k,7}$

$B_{k,4}$ (odd index): This has the following ruleset:

If it reads a zero, it writes a zero and goes to the right and to state $B_{k,3}$
If it reads a one, it writes a zero and goes to the right and to state $B_{k,5}$

$B_{k,5}$ (even index): This has the following ruleset:

If it reads a zero, it writes a zero and goes to the right and to state $B_{k,9}$
It is not possible to read an one, because we read the rightmost one on the odd index before this cell and thus the rightmost one on the tape.

$B_{k,6}$ (even index): This has the following ruleset:

If it reads a zero, it writes an one and goes to the right and to state $B_{k,4}$
If it reads a one, it writes an one and goes to the right and to state $B_{k,7}$

$B_{k,7}$ (odd index): This has the following ruleset:

If it reads a zero, it writes a zero and goes to the right and to state $B_{k,6}$
If it reads a one, it writes a zero and goes to the right and to state $B_{k,8}$

$B_{k,8}$ (even index): This has the following ruleset:

If it reads a zero, it writes a one and goes to the right and to state $B_{k,9}$
It is not possible to read an one, because we read the rightmost one on the odd index before this cell and thus the rightmost one on the tape.

$B_{k,9}$ (odd index): This has the following ruleset:

If it reads a zero, it writes a one and goes to the left and to state $B_{k,10}$
It is not possible to read an one, because we read the rightmost one on the odd index before this cell and thus the rightmost one on the tape.

$B_{k,10}$ (even index): This has the following ruleset:

It doesn't change the symbol it reads and goes to the left and to state $B_{k,11}$.

$B_{k,11}$ (odd index): This has the following ruleset:

If it reads a zero, it leaves a zero, goes to the left and to state $B_{k,10}$.
If it reads a one, than this is the leftmost one. It leaves this one unchanged, moves to the right and to state $B_k$.

If this helps, here are informal explanations of what the states $B_{k,\mathrm{something}}$ do:

$B_{k,\mathrm{right}}$: Bring the head to the cell with the even index and notice that the rightmost one on the odd index needs to be moved.
$B_{k,1}$: Bring the head to the cell with the odd index.
$B_{k,2}$: Write the new rightmost one.
$B_{k,\mathrm{left}}$: Bring the head to the cell with the even index and notice that the tape needs to be moved.
$B_{k,3}$: Write moved zeroes on cells with even index.
$B_{k,4}$: Move the head to even index and notice the rightmost one.
$B_{k,5}$: Write moved zeroes on cells with even index after the rightmost one was noticed.
$B_{k,6}$: Write moved ones on cells with even index.
$B_{k,7}$: Move the head to even index and notice the rightmost one.
$B_{k,8}$: Write moved one on cells with even index after the rightmost one was noticed.
$B_{k,9}$: Write a new rightmost one.
$B_{k,10}$: Move to the position the head should be.
$B_{k,11}$: Move to the position the head should be and notice the leftmost one. Note that the original position where the head should have gone is one to the left of the end of the tape, so it is not one to the right of the tape.

 Initial setup for the new machine

Before we will run this machine, we will put an 1 in cell 1 and cell 3, and move the head of the machine to cell 2. So the tape looks like

(1,_)(1,_)(_,_)(_,_)....

This can be done using three states:

State 1: It reads a zero. It writes an one. It goes to the right. It goes to state 2.
State 2: It reads a zero. It writes a zero. It goes to the right. It goes to state 3.
State 3: It reads a zero. It writes an one. It goes to the left. It goes to state $B_1$, as defined above.

 Conclusion

We created a new machine with 14 states per original state and 3 states for the initial setup that simulates $\Sigma(n)$ on a semi-infinite tape. Therefore $$\Sigma_{\mathrm{semi}}(14n+3) > \Sigma(n)$$

Note that I didn't necessarily tried to optimize those constants, since I just wanted to show uncomputability.


how the instructions are stored in relocatable format on disk I understand how the instructions are kept in relocatable format in RAM. It is done so by keeping a base register and a limit register. Physical address = base register value + logical address. And logical address = the logical distance from the starting location of process's address space, just like an array.

But what I don't understand how are they kept in relocatable format on the disk, is there some base value there too. Plus how are they linked to a computer program say C Program or Java program using dynamic loading of shared libraries.

Please help me understand !!

Thanks.

A compiled entity (say, a library) has a sequence of instructions. Each instruction has a particular location in sequence. This location is a value which can be considered simply as an offset from a base address. Loader loads the library at a particular address in the virtual address space of process and this address becomes the base address for the library and subsequently each instruction's location added to this base address becomes the actual address of the instruction in virtual address space of process.


Distributed problems in Financial Services? When we talk about distributed computing - it often refers to problems in biology or web search where there is a large quantity of data to process, or email where there is a large number of concurrent users.

Often in financial services, the problem space is OLTP for online banking, or overnight batch processing for summing up EOD totals and reporting.

Is there an example problem in financial services that requires the tools available in distributed computing?

There is a lots of problems which might be solved by using distributed algorithms. However most of this problems are so specific that there is no existing general purpose tool for all of them.

Banks and some financial institutions keeps their own solutions hidden and i doubt that they would like to share their ideas and code.

For instance let's consider loans, some as far as I know some banks do long term calculations using Markov process. It is possible to compute is on single machine, but those processes are so complicated that I it just wouldn't be effient to calculate them on single machine.

I also found this presentation, you might want to look at it.


Collision resistant Hash function in chaos cryptography In my earlier Question asked here Help in understanding how to apply nonlinear function in hashing about chaos cryptography, since then I have come across several research papers that apply atleat theoretically chaos based cryptography. It is still an active area of research with advantages and disadvantages.

How can I prove that the has collision is minimum or collision resistance for any chaos function used for chaos based cryptography, where the chaos map is the hash function?

An algorithm to achieve cryptography hashing is the chaos based cryptographic hash function which indexes all items in hash tables and searches for near items via hash table lookup. The hash

table is a data structure that is composed of buckets, each of which is indexed by a hash code.

Two hash codes for two different messages can collide if they have the same hash code. This is often called the Birthday paradox.

The properties of a good hash function is
that there should be no hash collision. This property also holds for Locality sensitive hashing where a hash function is used  to search for the approximate nearest neighbor.

How can I proof this statement for chaos based hashing in cryptography? If the hashing function is a chaotic map, $f()$, then how to show the expression of collision probability? Please help.

Chaos-based encryption ain't an active area of research among the best crypto researchers; it's looking like a dead end.  You might find papers published on the topic, but they're generally in lower-reputation conferences.  Why is it a dead end?  Because it doesn't seem to work.  The schemes typically end up being either insecure, or worse than existing algorithms (e.g., slower).  Basically, it initially sounded like an intriguing idea, but at this point I would advise you that studying chaos-based cryptography appears to be a waste of your time, if you want to accomplish something useful or practical.  (See also https://security.stackexchange.com/q/31000/971, though it doesn't really address this point.)

You can't prove collision-resistance.  Even the state-of-the-art hash functions don't come with a mathematical proof of collision-resistance.  See https://crypto.stackexchange.com/q/18730/351 and https://crypto.stackexchange.com/q/26094/351 and https://security.stackexchange.com/q/5101/971.


What Is the Complexity Class of Deciding Whether a Problem Is in NP? Is It Decidable? Title says it all, but to clarify:

Define a problem, called $IsInNP$, as follows:

  Given a Turing Machine $M$ that always halts, $IsInNP$ is the problem of deciding if the problem that $M$ recognizes is in $NP$.

What is the complexity class of $IsInNP$? Is it even decidable? Is the answer the same for any other complexity class, like $NP$-hard? And are those questions even sensible to ask?

By the way, I am aware that the class $NP$ is not enumerable, but since I do not quite understand enumerability and it seems that recursively enumerable problems can be decidable, I do not know if that means that deciding whether a problem is in $NP$, or any other complexity class, is decidable.

Also, I am aware of Rice's Theorem, and I believe it can be interpreted as saying that deciding whether a problem is in $NP$ is undecidable, but I am not certain.

Bonus question if the above questions are sensible: given a property $S$ that only $NP$ problems possess, does the above also mean that deciding whether a problem decided by a Turing Machine $M_2$ has property $S$ is in the same complexity class as $IsInNP$?

Here are several interpretations of your question:

  $L_1$ consists of all descriptions of Turing machines which are deciders (always halt) and the language that they decide is in NP.

This is undecidable, by reduction from the halting problem. Given a Turing machine $T$, construct a new Turing machine $M$ which erased its input and transfers control to $T$. Then $\langle M \rangle \in L_1$ iff $T$ halts on the empty input.

Indeed, if $T$ halts then $L(M) = \Sigma^*$, while if $T$ doesn't halt, then $M$ is not a decider.

  $L_2$ consists of all descriptions of Turing machines which are either not deciders, or the language that they decide is in NP.

This is undecidable, by reduction from the halting problem. Given a Turing machine $T$, construct a new Turing machine $M$ which simulates $T$ on the empty tape, and if $T$ halts, solves some NEXP-complete problem on the original input. Then $\langle M \rangle \in L_2$ iff $T$ doesn't halt on the empty input.

Indeed, if $T$ halts on the empty input then $M$ decides an NEXP-complete problem, which by the nondeterministic time hierarchy theorem doesn't belong to NP. In contrast, if $T$ doesn't halt on the empty input, then $M$ is not a decider.

  $L_3$ is the promise problem in which the input is a description of a Turing machine which is promised to be a decider, and the goal is to determine whether the language it decides is in NP.

Alternatively, you can ask whether there exists any decidable language $L_4$ such that

The description of any machine deciding a language in NP belongs to $L_4$.
The description of any machine deciding a language not in NP doesn't belong to $L_4$.

This is undecidable, in the sense that there is no Turing machine that halts and answers YES on all YES instances, and halts and answers NO on all NO instances.

Given a Turing machine $T$, construct a new Turing machine $M$ with two inputs $n,x$. The Turing machine simulates $T$ for $n$ steps. If $T$ halts within these $n$ steps, then it solves some NEXP-complete problem on $x$. Otherwise, it simply returns YES. The new machine $M$ is a YES instance of $L_3$ iff $T$ doesn't halt on the empty input.

Indeed, if $T$ halts on the empty input then there exists an NEXP-complete language $L$ and an integer $n$ such that $(n,x) \in L(M)$ iff $x \in L$, and so $L(M) \notin \mathsf{NP}$. In contrast, if $T$ doesn't halt on the empty input then $L(M)$ consists of all pairs $(n,x)$, and so $L(M) \in \mathsf{NP}$.


Language described by inverting accepting states of NFA Connecting to When states that are not accepting states become accepting states in NFA, what happens?, what is the formal language described by inverting accepting states of NFA? By inverting, I mean that rejecting states become accepting states and accepting states become rejecting states.

Is there a nice expression for such a language reference to the original NFA language?

The answer is basically in the question you link, but to make it explicit: no, there is no "nice expression" since anything can happen.

For an example, let $L$ be any regular language; let's say it's accepted by NFA $A_L$:

[source]

Now consider this automaton $A'_L$:

[source]

Clearly, $A_L$ and $A'_L$ accept the same language $L$. However, the automaton obtained from flipping $A'_L$ accepts $\Sigma^*$ (since $s$ is accepting in this one).

So we see that we need further assumptions on the automata if flipping is to yield anything meaningful. For instance, if we require that for every input, either all computations are accepting or all are rejecting -- a property $A'_L$ above does not have -- then flipping yields the complement of the original language.


Rubik Cube Algorithm for general n I am not sure if this is the right place , but:

Is there an algorithm for solving $n\times n \times n$ rubik's cube (non-trivial one)? If so how efficent is it? Now say I have a $n \times \ldots \times n$ ($d$ times) rubic cube , is there an algorithm that works effiecently for this case?(of course now it depends also on $d$ and not just on $n$)

I haven't found anything online/on wikipedia and I was just wondering.

Algorithms for Solving Rubik's Cubes by Demaine et al. shows that an $n\times n\times n$ Rubik's Cube can be solved in $O(\frac{n}{\log n})$ moves and this is (asymptotically) optimal.

I am not certain on the complexity of actually computing such a solution but I suspect that (by closely following the steps in the proof) it can be done in polynomial time (probably $O(n^2)$ or $O(n^2\log n)$).

There likely isn't anything out there on higher-dimensional cubes. If there was, they would certainly have cited the Demaine paper. There is a trivial way to solve a $n\times n\times n$, since there exist move sequences that solve an individual cubie in $O(1)$ time. Therefore, if such sequences also exist for higher-dimensional cubes, they could be solved in $O(n^{d-1})$ steps since that is how many cubies are on the surface. And perhaps by extending Demaine's technique you could get that down to $O(\frac{n^{d-1}}{\log n})$ by solving multiple ($O(\log n)$) cubies in one go.

You might be able to find more information here: http://www.superliminal.com/cube/solution/solution.htm


Correctness of following algorithm for 3-QCNF? Let I have 3-QCNF formula.

Classic recursive algorithm for TQBF takes exponential time. However, following divide & conquer modification allows to do it in quadratic time (not sure about correctness, and that's the question).

ctr = 0

for i = 0..n

    Step 1. Take i'th clause, find E-quantified variable inside it.
    If can't, return 'NO'. Otherwise, if it's the clause containing 3
    variables, choose that variable v.

    Step 2. Find all 3-clauses with variable v. Move them from formula Ф
    to formula f_i. Reduce n (length of formula Ф) by number of moved
    clauses.

    Step 3. Copy f_i to f'_i.

    Step 4. Put v = 1 in f_i. Get 2-QCNF.

    Step 5. Put v = 0 in f'_i. Get 2-QCNF.

    Step 6. If f_i and f'_i have same clauses, move them to Ф.
    Increase n by number of moved clauses.

    Step 7. ctr = ctr + 1

for i = 0..ctr

    Step 1. Solve 2-QCNF Ф'^f_i. //Ф' is changed Ф.

    Step 2. Solve 2-QCNF Ф'^f'_i.

    Step 3. If both are false, return 'NO'.

return 'YES'

Notes:

Algorithm represents 3-QCNF as $\mathsf{\Phi = TAUT-CNF \land \Phi'(2-QCNF) \land (f_i(2-QCNF) \lor f'_i(2-QCNF))\land\ ..}$

Trivially, formula is false if TAUT-CNF contains clauses.

So, if TAUT-CNF has no clauses, formula is represented this way:

$\mathsf{\Phi' \land (f_i \lor f'_i)\land\ ...\ =((\Phi'\land f_i)\lor(\Phi'\land f'_i))\land\ ...}$

The question: have I violated any logical rule in my algorithm?

Your code ignores quantification levels.  Formulas prefixed with
$\exists{x_1}\forall{x_2}$ are not supposed to be evaluated the same way as those prefixed with $\forall{x_1}\exists{x_2}$.  Your code treats them the same, moving one existential quantifier ahead of all the other quantifiers in each of your 2-QBF subformulas.


Term for an approximation that becomes better as the problem grows For a certain maximization problem, a "constant-factor approximation algorithm" is an algorithm that returns a solution with value at least $F\cdot \textrm{Max}$, where $F<1$ is some constant and $\textrm{Max}$ is the exact maximal value.

What term describes an algorithm in which the approximation factor is a function $F(n)$ of the problem size, and $F(n)\to 1$ as $n\to \infty$?

You can say your algorithm is asymptotically optimal. One example is universal codes, which are a certain type of codes for the natural numbers. They satisfy the following property. Let $D$ be a monotone probability distribution over the natural numbers, that is $\Pr[D=n] > \Pr[D=n+1]$. The average codeword length under a universal code is $H(D)(1 + o(1))$. Since $H(D)$ is the optimal length, universal codes are asymptotically optimal, in exactly the same sense as the one you're after.


Show that f(x,y)=x+y (with |x|=|y|) isn't a one way function I have to prove that the function $f\colon \mathbb N × \mathbb N \to \mathbb N$ defined by $f(x, y) = x + y$ and $|x| = |y|$ isn't a one-way function. How do I go around doing that?

A function $f$ is one-way if given $f(z)$ for random $z$, it is hard to find an input $w$ such that $f(w) = f(z)$. So in order to show that $f$ isn't one way, you need to show that given $f(z)$ for random $z$, it is not hard to find an input $w$ such that $f(w) = f(z)$. Good luck!


Quantum Computing and Turing Machines: Are Turing Machines still an Accurate Measure? In class last week, my professor commented and said that Turing machines are used as a standard measure/model of what is computable and are a helpful basis of discussion for that subject. She also said that all variants of Turing machines are proven to be computationally equivalent -- read, just as powerful -- as one another. W

I commented and said yesterday that, regarding computability power, I noticed that some turing machines can take incredibly large amounts of time to compute something very simple, while a turing machine with more tapes can compute something in a lower asymptotic complexity with respect to the number of steps needed.

She said that with respect to class discourse, the runtime of a particular algorithm on a turing machine does not change the definition of computability, or the power with which we measure computability. "We're concerned about what is computable, not what is efficiently computable at this point." So, it doesn't matter if the turing machines has more and more tapes, and more and more tapes implies that it can compute in lesser steps. Okay, I get that we're really focusing on what IS computable, not the speed at which we can compute it.

Something about that just bothers me, because up to this point, algorithms with abnormally large asymptotic time and space complexity really define the limits of what is, maybe I should say, practically, computable.

So, I have a couple of questions:

Suppose we have a model for a quantum turing machine, this must be equivalent to a "regular" turing machine, right?

So, the answer to that question I think really is going towards my reason for writing this post. Does quantum computing technology antiquate the classical definitions of what is computable via a turing machine?

Is this something above my head and should I delete this post? I don't mean to be precocious, I just didn't see a question similar to mine.

You're mixing up computability theory (also known as recursion theory) and complexity theory (or computational complexity). Computability theory is a vast mathematical subject which studies the ramifications of the concept of computation. It does not deal with the complexity of computation. As your professor mentions, all (Turing-complete) computation models are the same from the point of view of computability theory. Computability theory, while an interesting mathematical subject, is not a good model for real-world computation for this reason, as you mention.

Complexity theory started its life as an attempt to address this issue. Complexity theory studies how difficult it is, in terms of time and space, to compute certain predicates and functions. From the point of view of complexity theory, not all computation models are the same, and Turing machines are taken as the reference model. However, even complexity theory is not very realistic, since it treats all computational models polynomially equivalent to Turing machines in the same way (two models are polynomially equivalent if any problem solvable in time $T(n)$ and space $S(n)$ in one model can be solved in time $T(n)^c$ and space $S(n)^c$ in the other, where $n$ is the input size and $c$ is some positive constant). For example, Turing machines are not good models for real computers since they do not support random access (accessing an arbitrary point in memory in time $O(1)$). Of course, random access can be simulated by a Turing machine, but the simulation can be slow. It is often said that sorting can be done in time $O(n\log n)$, but this is not the case for Turing machines, which probably require $\Omega(n^2)$ or move even for sorting integers. Therefore in the area of algorithms, other models such as the RAM machine replace Turing machines.

Finally, quantum computers can be modelled in several different ways, such as the quantum Turing machine. Everything computable using quantum computers is also computable using classical computers, and so from the point of view of computability theory, quantum Turing machines are just another equivalent model. However, quantum Turing machines are widely conjectured not to be polynomially equivalent to classical Turing machines: for example, factoring and discrete logarithm are "easy" for quantum Turing machines (solvable in polynomial time), while it is conjectured that they are "hard" for classical Turing machines (cannot be solved in polynomial time; though some people think that integer factoring might be solvable in polynomial time). So from the point of view of complexity theory, quantum Turing machines are different from classical Turing machines.


Finding the number of ways to partition $\{1,...,N\}$ into $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$ for a given $N$ I am trying to think of how to optimize the following problem:

Let $S = \{1,2,...,N\}$. How many ways can $S$ be partitioned into non-empty subsets $P_1$ and $P_2$ such that  $sum(P_1) = sum(P_2)$? I have implemented an algorithm that checks all partitions of $S$ into 2 subsets $P_1$ and $P_2$, but I am wondering if there is a faster algorithm.

Hint: find a recurrence $f(n, k)$ that tells you in how many different ways you can sum to $k$ using the first $n$ integers (ignoring order and using numbers at most once). Then the answer to your problem is $\frac 1 2 f(n, n(n+1)/4)$.

The trick is to realize that the sum of $P$, is $S= \displaystyle \sum_{k=1}^n = \frac{1}{2}n(n+1)$, and that if you partition a set in two with equal sums, both halves must sum to $\frac{1}{2}P$. After counting the number of ways to sum to $\frac{1}{2}P$ we must still divide by two due to order, as for example the partition $(\{3\}, \{1, 2\})$ is the same as $(\{1, 2\}, \{3\})$.


Why does the map function in MapReduce take two parameters? I am playing around with MapReduce and wanted to ask why the map function takes two inputs (key, value)? Why not just pass along the value?

Specifically, if you look at the word count example on Wikipedia page you will see that the map function is:

function map(String name, String document):
// name: document name
// document: document contents
  for each word w in document:
    emit (w, 1)

However, the function never does anything with the parameter "name". Why even pass it in?

Let me quote the documentation (emphasis mine):

  Map You write a map function that runs once for each input value. It returns a collection of name-value pairs which are passed on to the next stage. If there are many, many input values, then this function runs many, many times. The framework divides up the input so that subsets are handled in parallel on multiple instances of your application. A typical map function could count things that occur in each input value that matches some filter.

So there are two immediate uses I can imagine:

Use the "chunk" name in the returned names. For example, you might want to distinguish bible_author from fiftyshadesofgrey_author in the result.
Identify "subprocesses". If anything goes wrong (and something will go wrong) an error message like "Error processing bible: Illegal character at position 666" is obviously only useful if you include the document name.

And, of course, you may also want to use the name in the actual computation. A general API should cover that case.


How can I find matchings in a Bipartite graph beginning with specific vertices? Context: I'm modelling kidney exchanges through directed acyclic graphs. I convert these to Bipartite graphs (by splitting each node into a donor and receiver, and the edge from the original graph exist between corresponding donors and receivers). I want a way to find maximum number of edges through disjoint chains and I've been trying to do so through maximum wtd matching.

I know I can use ford-fulkerson to find a maximum wtd perfect matching, however, the main problem I'm facing is that the matchings can only exist for chains beginning with specific vertices. For example, if this is my directed acyclic graph:

Turning this into a Bipartite graph and using the maximum wtd matching way, I get the chain 0->1->3->5->6 but I also get 2->4. However, I can only have chains beginning with 0 so 2->4 should not come up.

I wanted to know if there were any ways to work around this problem? Someone suggested making this a minimum cost perfect matching problem but I'm confused how.

I realise this is a weird question but any help would be appreciated!

To make this a minimum-cost perfect matching problem, split each node as you indicated (sending/receiving).  Add a high-cost edge from each node's sending node to its own receiving node.  This high-cost edge will only be used if that node does not receive a kidney.  Additionally, I assume Node 0 in the above graph is supposed to be an altruistic donor or a deceased organ donor that does not need to receive a kidney.  (Otherwise, your example has no cycles and no exchange can take place.)  Assuming Node 0 is a 1-way donor, add low cost edges from every sending node to Node 0's receiving node.

Then solve the minimum-cost perfect matching problem.  A perfect matching is obviously possible (every sending node can send to its own receiving node).  A minimum-cost perfect matching will use as few of the high-cost edges as possible.  Minimizing the number of high-cost edges (nodes that send to themselves) is the same as maximizing the number of nodes that receive a kidney.

This is also known as the assignment problem and can be solved in polynomial time.  Most kidney-exchange research adds the significant complication of requiring cycles to be at most length k.  That complication makes the problem NP-hard.  Altruistic donors could allow for longer cycles in practice.


Shortest paths from a source in weighted graph with only one negative weighted edge Of course assuming there aren't any negative cycles.
I saw this question somewhere. And i saw a complicated solution which says to build three such graphs and connect between them in a very  complicated manner.
My question is why isn't my simple solution good for it?
My simple solution is to first find the negative edge . And then start traversing from that edge with dijkstra.
 I think once you start with that edge, dijextra should work.
So that way i mange it in O(e + vlogV) . So why isn't my easy solution mentioned there. Is my solution correct?

No. The negative edge will not always be part of the shortest path. For example, in the digraph

A <==[+1]== B ==[+4]==> C ==[-1]==> D ==[+4]==> E

the shortest path departing from B is the path from B to A, and does not include the negative edge (C,D).

Even when the negative edge is part of the shortest path, it won't necessarily be the first edge of the path.


How to prove semi-decidable = verifiable? A language L is verifiable iff there is a two-place predicate R ⊆ Σ∗ × Σ∗ such that R is computable, and such that for all x ∈ Σ∗: x ∈ L ⇔ there exists y such that R(x, y)

A language is semi-decidable iff there is some Turing machine that accepts every string in L
and either rejects or loops on every string not in L.

How can we show that the class of semi-decidable problems is equivalent to the class of verifiable problems? Or are they not?

Its obvious why a semi-decidable language is verifiable ($w$ would be the machine's computation history on $x$). Now, we will show the other way:

Let $V(x,w)$ be a verifier for $L$. Define $M(x)$ as the following algorithm:

Let $S$ be an empty array (of turing machine emulations)
For every $w\in\Sigma^*:$

Add a new emulation of $V(x,w)$ to $S$.
For every emulation $E\in S:$

Compute one step for $E$. If, $E$ accepted, then accept.

This algorithm is correct, since if $x\in L$ then there is some $w\in\Sigma^*$ with $V(x,w)=True$ and therefore the algorithm will accept.

If the algorithm accepted, then there must be some $w\in\Sigma^*$ where $V(x,w)=True$ and thus $x\in L$ by definition


Non-recursivity of language of TMs which have equivalent TMs of smaller and larger description length Prove that the language

$$ L=\{\langle M \rangle \mid \exists M_1, M_2 : L(M_1)=L(M_2)=L(M) \text{ and } |\langle M_1 \rangle| < |\langle M \rangle| < |\langle M_2\rangle| \}$$

is not recursive.

First, let us notice that in the definition of $L$, a machine $M_2$ accepting the same language as $M$ but having a longer description always exists, so only the condition on $M_1$ is pertinent.

Suppose that $L$ were computable. Consider the following Turing machine $T_\ell$. The machine enumerates all Turing machines of size at least $2^\ell$, until it finds a machine $M$ such that $\langle M \rangle \notin L$ (such a machine must exist, since there are infinitely many computable languages but only finitely many Turing machines of size less than $2^\ell$).  Then it transfers control to the machine $M$, i.e., it runs $M$ on the input.

By construction, $L(T_\ell) = L(M)$. Since $\langle M \rangle \notin L$, necessarily $|\langle T_\ell \rangle| \geq |\langle M \rangle| \geq 2^\ell$. However, by hardcoding $\ell$ into a Turing machine in which $\ell$ is an additional input, we see that $|\langle T_\ell \rangle| = O(\ell)$. We obtain a contradiction for large enough $\ell$.


Please explain a greedy algorithm in a naive manner I am a beginner in the topic of algorithms. I have a query about Greedy Algorithms.

From what I understand, if there is a function and we are supposed to find its maxima/minima, if we find the local maxima/minima, we become 'greedy' and declare that as the global maxima/minima.

I suppose that is wrong?

In simple words, an algorithm is normally considered "greedy" if

it builds solutions step by step without backtracking
in each step it picks what's best in the current state.

To learn more about it, check this pdf out.

The animated gif above illustrates a greedy algorithm for finding the path that adds up to the biggest number.

It does so by choosing the node with the biggest number at each step. (Since the actual solution is the 7-3-99 path, the greedy approach fails to bring forth the correct path.)

This is why greedy algorithm may not always yield the right solution to a certain instance of a problem.

The gif animation was created by Swfung8 on Wikipedia for the article on Greedy Algorithm.


Build PDA for a language with unknown input alphabet $L_1 ,L_2$ are regular language. We form a new language $L_{12}$ as follows:
$L_{12}=\left \{ w_1\cdot w_2|w_1\in L_1\wedge w_2\in L_2\wedge|w_1|=|w_2| \right \}$
In this exersice I am not given any alphabet and I'm required to build PDA for $L_{12}$, but by definition $M=\left \{Q,\sum,\Gamma ,\delta ,q_0,-|,F\right\}$ and I don't have any alphabet to work with.By intuition if the alphabet is similiar can effect the solution than if it wasn't similiar.

You might reason like this: If $L_1, L_2$ are regular, then $L_2^R$ is regular ($L^R$: reverse words). You can build regular grammars $G_1 = (N_1, \Sigma_1, P_1, S_1)$ and $G_2 = (N_2, \Sigma_2, P_2, S_2)$ that generate $L_1$ and $L_2^R$. The crucial point is that the regular grammars have the lonely non-terminal always at the end (or beginning!) of the sentential form. Build a CFG with nonterminals $Q = N_1 \times N_2$, and productions that build up $L_1$ to the left (using the first part of the nonterminal) and $L_2^R$ to the right (using the second part of the nonterminal, building from the end). From the resulting grammar you can build a PDA.
The basic idea is similar to the construction for $\{ w w^R \colon w \in \Sigma^*\}$ with $S \to x S x$ for all $x \in \Sigma$ and $S \to \varepsilon$ (or $S \to xx$ for purists).


$(Q\to R)\wedge (R\to Q)$ converting to sentence Well, I am following this video lecture (MOOC) and I came across this quiz where I have to convert $(Q\to R)\wedge (R\to Q)$  to sentence.

$Q$: "I will go to town"

$R$: "I have time"

My answer to $(Q\to R)\wedge (R\to Q)$  is

"I will go to town ONLY IF I have time AND I have time ONLY IF I will go to town".

Whereas, the professor teaching in video gave following answer:

"I will go to town ONLY IF I have time AND IF I have time I will go to town".

I don't get the answer given by professor because it changes the meaning of sentence after 'AND'.

NOTE: Further professor explain that this can be converted to equivalent "If and Only If", but my concern is not on equivalence. I understand that part.

Thank you in Advance!

Your answer and the professor's answer are both correct.  Other ways to say $p$ implies $q$ are: "if $p$ then $q$" and "$p$ only if $q$".  You can replace "only if" by "implies".

Thus, "I have time ONLY IF I will go to town" and "IF I have time I will go to town" both say the same thing - "I have time implies I will go to town".


What does "order of growth decreases exponentially" mean? I understand than function decreases exponentially, then order of growth of this function is exponential with negative exponent. But what does it mean that order of growth decreases exponentially?

I don't understand what should i look for in this exercise:

  Exercise 2.33 Find a recurrence describing a sequence for which the order of growth decreases exponentially for odd-numbered terms, but increases exponentially for even-numbered terms.

Could you provide several first items of such a sequence to let me understand the exercise?

I think it just wants a recurrence for a sequence where the even-numbered terms increase exponentially and the odd-numbered terms decrease exponentially. Talking about the order of growth changing sounds like some kind of second-derivative property but I think it’s just poor phrasing.

To be absolutely sure, you’d have to ask the person who wrote the exercise.


Grammar types constraint after adding a couple of types (and a statement involving them) to a "typeless" language Foreword : by "typeless programming language", I naively mean "language in which you don't write statements like type x (=) ... to declare(define) x". Maybe there is an internal typing deduced from what is in ... but I suppose that this is not the case, as it is not the case in the example interesting me. (If "typeless programming language" already means something, forbid me, but this is not the point.)

Consider the grammar of a "typeless" programming language, python (3.6.3) for instance :

https://docs.python.org/3/reference/grammar.html

I rather used its description here :

https://github.com/erezsh/plyplus/blob/master/plyplus/grammars/python.g

Then I lightened the grammar a lot and modified the resulting subgrammar by adding new features, but for the sake of simplicity, one can assume that I add features to the complete python grammar, not to a subgrammar of it.

Here are my modifications :

1) I added a date "type" (I put type in "" because there's no type in python)

date: US_DATE;

where :

US_DATE: '!(?:(?:(?:(?:(?:[13579][26]|[2468][048])00)|(?:[0-9]{2}(?:(?:[13579][26])|(?:[2468][048]|0[48]))))(?:(?:(?:09|04|06|11)(?:0[1-9]|1[0-9]|2[0-9]|30))|(?:(?:01|03|05|07|08|10|12)(?:0[1-9]|1[0-9]|2[0-9]|3[01]))|(?:02(?:0[1-9]|1[0-9]|2[0-9]))))|(?:[0-9]{4}(?:(?:(?:09|04|06|11)(?:0[1-9]|1[0-9]|2[0-9]|30))|(?:(?:01|03|05|07|08|10|12)(?:0[1-9]|1[0-9]|2[0-9]|3[01]))|(?:02(?:[01][0-9]|2[0-8])))))';

(thx to https://stackoverflow.com/a/16088645/1581875)

and I propagated date to atom.

Then d = !20171116 produce the following syntax tree :

2) I also added what I call an underlying, and this time it's a real type. Namely, I added a

UNDERLYING: 'underlying';

in the %unless part of NAME definition, and I introduced an underlying statement :

underlying_stmt : UNDERLYING name (COMMA name)*;

that I of course propagated to small_stmt.

Now one can write :

underlying z

which produces the following syntax tree :

3) Here comes the tricky (at least for me) part : after what preceeds, I introduced a new use of the @ symbol, namely a "stamp statement", stamp_stmt, as follows :

stamp_stmt: name AT (name | date);

(that I propagated of course to small_stmt)

Namely, I can write

z @ d #or
z @ !20171116

and this will produce the following syntax tree :

In fact, as I defined the stamp_stmt, I can write name @ date for any name (and date).

I cannot write 2 @ !20171116 for instance : this is already a constraint. I would like to be able, within the grammar, to also add the following constraint : name @ date could be written only for a name of an underlying.

How could I achieve this ? I mean, I could still introduce a kind of light "typing" in name by refining it by saying that date (resp. underlying) has datename (resp. underlyingname) and try to use it to achieve the wanted constraint, but I could also say that d = !20170823 is not an assignement statement (assign_stmt) and introduce a "date assignement statement", same for underlying.

Is it anyway a good idea to want to put such a type constraint already in the grammar or not ? (I am really not an expert in languages designing etc ... I am doing all of this because I need a small programming language with the aforementionned features and because around me, no one can help.)

Remark : I am doing all of this under windows with plyplus in python and producing syntax trees figures using graphwiz.

There is no way to express that constraint with a context-free grammar. (It is, almost by definition, context-sensitive since the validity of z @ … depends on the presence of underlying z.)

So you are left with two choices:

Perform the validity check as a semantic action.
Modify the lexical scanner's categorization of tokens on the fly, by recategorizing z after underlying z is seen.

Option 2 is usually called the "lexical feedback hack" and that is precisely what it is. Sometimes it cannot be conveniently avoided, but this is not one of them.


Is Huffman encoding for the entire language or the body of text? I am using language as a placeholder although I think it can be used in music too. I am unclear if the frequencies are given based on the text or the entire language. The latter would prove to be difficult because if we are to say that 'e' is the most common letter in English, wouldn't this shift over time with some new words being created and some being dropped due to fashion etc?
Say we are trying to encode the first book of Harry Potter, is the encoding basing the frequency of letters of the book only or of the English language at the time? Extending it to music, would the entire domain be all possible sounds the human ear can hear or only of the track being listened to.

The statistics used to derive the Huffman codes from can come from any source that you want. For a practical example, the popular DEFLATE format allows both "dynamic Huffman codes" (in this usage it is not a form of adaptive Huffman coding, it means the codebook is specified in the data stream) and "fixed Huffman codes" (a codebook that is specified in the DEFLATE specification).
A codebook based on the statistics of the actual data being compressed generally results in a smaller compressed size. The trade-off is that a codebook that is not pre-defined must be supplied along with the data (the decoder still needs it), adding to the overall size. Canonical Huffman codes can mitigate the impact (requiring only the code lengths to be transmitted, the codes themselves can be inferred in a simple way), but transmitting the codebook is going to cost some extra data, and may not be worth the size overhead for short texts (especially when the statistics of the given text happen to approximately line up with the statistics on which the pre-defined codebook was based).
Other practical considerations may favour using slightly inaccurate statistics, for example statistics based on some prefix of the data to be able to start encoding without having to wait until the input is fully known. The more accurate you want the statistics to be, the longer the latency is between the "first input" and the "first output" of the encoder. Even if the input is entirely known at the start, depending on the application, gathering fully accurate statistics may not be worth the time investment.


Does it matter for this function if the set we check membership of is finite? I have the following problem.

  Let $\Phi$ be an admissible numbering of the single-parameter partially-recursive functions. That is, $\Phi(i, x) = f_i(x)$ with $f_i$ the $i$th partially-recusive function with one parameter. Denote with $f(x)\!\uparrow$ that $f(x)$ is undefined in the sense that its computation does not halt.

  Now let $B$ be a partially computable set (finite or infinite) so that $\Phi(i,i)\!\uparrow$ for all $i \in B$.

  Show that

  $\qquad H_1(x) = \begin{cases}1 \text{ if }
\Phi(x,x)\downarrow \\ 0 \text{ if } x \in B \\ \uparrow \text{
otherwise}\end{cases}$

  is partially recursive.

I know from here that there is even an infinite set. I am preparing for an exam, so just assume that they give an suitable infinite set. How would the program differ if B is a finite set like $B= \{b_1,b_2,\cdots,b_n\}$?

Also a function obtained from composition, recursion is partially computable. So since definition by piecewise is primitive recursive , Could I say $x \in B$ is partially computable if $B$ is finite or would it be better to comeup with a program. I don't know how using just these four instructions, one could say  $x \in B$ or not.

\begin{array} \\
\;\;\;\;\;\;\;\;\;Y \gets 0 \\
\;\;\;\;\;\;\;\;\;\text{IF } X \neq 0 \text{ GOTO } A \\
[E] \;\;\;\text{ GOTO } E \\
[A]\;\;\;\; Y \gets Y+1
\end{array}

I am using the Davis book of Computability where this is mentioned in page 70 of second edition.

You can solve this problem in a straight-forward way: give an algorithm that (semi-)computes $H_1$.

Here is a rough sketch that you have to expand into appropriate detail in the model you want to work with and then show correctness and computability.

Let $M_B$ be a semi-decider for $B$.

Compute $\Phi(x,x)$ and $M_B(x)$ simultaneously.
If $\Phi(x,x)$ terminates first, return $1$.
If $M_B(x)$ terminates first (and accepts), return $0$.
Otherwise, loop.

Hints

   In step 1, use dovetailing.

   Steps 2 and 3 can not disagree.

   Step 4 only happens when it should.

You can show the necessary lemmas using the assumptions on $B$.

As you see, we don't care at all if $B$ is finite as we do not care what $M_B$ looks like; we just use it as a black box.

Aside: I am not sure that infinite $B$ with all the properties as listed in the question exist. We can ignore this, though: the problems is stated such that we show something for each such $B$ -- if there is none, we are good.


Getting O-bounds by applying regression methods to execution time measurements Does anyone of you know how to associate an algorithm execution time (of experimental execution) to a well known complexity time? For example, say a divide and conquer algorithm lasts theoretically O(n·logn·n^2) or Ω(n·logn), in a theoretical way, doing reccurence ecuations and all that stuff. But when you plot the data from a CSV, you can't say just by looking at it 'oh yea this is O(n^2).

The data from the CSV is like:

n, execution_time_for_that_n...

How can I use a regression method to derive O-classes from such data?

It's impossible. No finite set of measurements can prove asymptotic bounds.

Proof sketch: Assume you had such a method. Apply it to any algorithm $A$. If your largest measurement is for input size $n_0$, construct a new algorithm $B$ that branches into $A$ for all $n \leq n_0$, and one with a different $\Theta$-runtime class for $n > n_0$. The method fails for $B$.

That said, there are ways to perform reasonable experiments (for average-case performance). I recommend the book "A Guide to Experimental Algorithmics" by C. McGeoch.


Closure properties of languages Let $P$ be a regular language and $Q$ be a context-free language such
  that $Q \subseteq P$(For example, let $P =  a^*b^*$ and $Q = \{ a^nb^n | n \ge 0\}$). Then which of the following is always regular?

  $P \cap Q$
  $P - Q$
  $\Sigma^* - Q$
  $\Sigma^* - P$

Option 1
$P \cap Q = Q$ as $P \subseteq Q$. Thus $P \cap Q$ is context-free.

Option 2
I was not able to generally reason here. I used the example mentioned in the question.
Let  $P =  a^*b^* $ and $Q = \{ a^nb^n | n \ge 0\}$.
$P - Q = \{a^nb^m | n \neq m\}$ which is not regular but only context-free.

Option - 3
Let $\Sigma = \{ a, b\}$ and $Q = \{ a^nb^n | n \ge 0\}$.
Again $\Sigma^* - Q =  \{a^nb^m | n \neq m\} $ which is not regular but only  context-free.

Thus, the 4th option must be right, $\Sigma^* - P$ is regular. I am however unable to understand this result intuitively. Could somebody explain?

I got it on further thought. It is trivial. $\Sigma^* - P$ is $P'$, the complement of P and this is regular. I was unnecessarily concentrating on how $Q \subseteq P$ would play a role. It doesn't actually.


Structuring a Regression Model for NCAA Basketball Spreads/Totals I have a basic linear regression model that predicts the spread and total points of NCAA college basketball games. My inputs include various efficiency metrics about each team playing each other. A snippet of the data I am working with looks like:
Team_1 Team_2  Off_Eff_T1 Def_Eff_T1 Pace_T1 Off_Eff_T2 Def_Eff_T2 Pace_T2 Line Over_Under
UCLA   Michigan    116.9    95.2        64.2       118.9      88.7    66.8    6.5    135.5

These are my model coefficients:
adjO_T1 = offensive efficiency for Team 1 (UCLA), adjD_T2 = defensive efficiency for Team 2, etc.
(Intercept)  -5.39321
adjO_T1       0.65668
adjD_T1      -0.67104
adjT_T1       0.01819
Luck_T1      -2.79183
oppO_T1       0.16446
oppD_T1      -0.20572
adjO_T2      -0.66651
adjD_T2       0.66858
adjT_T2       0.09720
Luck_T2       0.30050
oppO_T2      -0.12808
oppD_T2       0.18562

As can be seen, I have efficiency metrics for both teams playing each other. As I have trained my model, the coefficients between "Team 1" and "Team 2" are obviously different. T_1 is the home team and T_2 is the away team. But if I were to switch these (enter T_2 as the home team), the prediction of the spread/total would be drastically different just due to the different model coefficients. Is there a way I can get around this? Aka, the prediction would be the same regardless of what team was entered as home or away. In the example above, if UCLA is T_1 it predicts they should be 2.5 point underdogs. But if Michigan is T_1, they are predicted to be 8 point favorites.
However, Home or Away is not an input to my model so I feel that the predictions should be the same. If someone could provide better suggestions as to how I could structure my data or if I am going about this the right way, that would be a huge help.

I think a natural approach would be to constrain the coefficient of adjO_T2 to be the negation of the coefficient of adjO_T1, the coefficient for adjD_T2 to be the negation of the coefficient for adjD_t1, etc.  Then, you could learn a logistic regression model subject to that constraint.
This could be implemented in practice by having only the coefficients of adjO_T1, adjD_T1, etc. be model parameters; the coefficients for adjO_T2, adjD_T2, etc., are not additional parameters, but are derived from the coefficients of adjO_T1, adjD_T1, etc.  You can write down a loss function, using the logistic loss, for the loss of any particular set of parameters, and then use optimization to find the parameters that minimize the loss on the training set.
Related: see the Bradley-Terry model.  The above is basically equivalent to using the Bradley-Terry model with exponential score function $p_i = e^{\beta_i}$ where here $\beta_i$ is a linear combination of the metrics for that team, and your goal is to learn the coefficients in that linear combination.  Then $\beta_i$ or $p_i$ represent the "strength" of team $i$, and the Bradley-Terry model says that the probability that team 1 beats team 2 is given by $p_1/(p_1+p_2)$, i.e., it is a function of their relative strengths.


Why using finite automata in implementing lexical analyzers I studied the subject of building a lexical analyzer using finite automata, through the classical way: Regular Expression -> NDA -> DFA. And I found it elegant, and a more solid approach for building a lexer.
Now my question is, what are other benifits from building a lexer this way, rather than the "ad hoc" way?

Speed and simplicity. A regular expression is a compact and declarative specification of lexemes. For most realistic regular expressions, simply writing code to mimic that specific regular expression would likely be something like an order of magnitude longer and less clear. This is especially true if you want high-performance.

A regular expression, on the other hand, can be compiled to very efficient code and is relatively simple to understand. You also get guarantees that are difficult or impossible to verify of code.  For example, a regular expression is guaranteed to be implementable using only a fixed, finite amount of memory and matching is, of course, guaranteed to terminate. This is very similar to the reasons we use primarily SQL to query relational databases rather arbitrary code.

So far this has been an answer to the question of modeling/implementing lexical analysis with regular expressions, and not to why we would implement regular expressions with DFAs. Again, the main reasons are speed and simplicity. There are however, many other options including: directly interpreting the regular expression operators, compiling regular expressions to machine code, differentiating regular expressions, NDAs clearly, converting a regular expression to a CFG and applying CFG techniques. Many of these approaches are arguably "inherently" slower than DFAs, e.g. using CFG techniques suggests that there will be overhead to support a degree of flexibility that is not used.

There are two obvious ways of implementing a DFA at least when the alphabet is reasonably small. One is to have a two dimensional table indexed by state and character. This approach is modular in that you can write the matcher once and just change the language by providing a different table (perhaps dynamically). Matching involves incrementing a pointer, one 2D table lookup, and a highly predictable jump. A second approach is to "store the state in the instruction pointer/program counter" by having each state be its own block of code. Matching in this case involves incrementing a pointer and a(n unpredictable) indirect jump. Ignoring instruction/data caching and branch prediction effects, it's hard to conceive of a more efficient approach than these. You are looking at two or three machine instructions per character of input. In the latter case, we can improve on the instruction caching and branch prediction performance by combining blocks of code together. Again, all this can be handled by a tool that takes a regular expression as input. There's no real way to beat this latter approach to implementing DFAs in performance except by improving instruction caching or branch prediction.


Finding maximum clique in a distance matrix created by certain pattern I have a distance matrix which is created through a predefined pattern (or formula) and I want to find elements with minimum distance "d" from each other, in order to do that I search for the maximum clique in the graph which is created with distance matrix.

Knowing that there exists a pattern in the distance matrix can I find the maximum clique more efficiently?

Although the question lacks some details, I propose my solution to the general version of your problem.

Yes. It really depends on the "pattern" based on which you create the graph. There is an infinite number of patterns. For example, one can propose a simple pattern that makes it easy to find the cliques in linear time:

Pattern 1: There is a link between two vertices if the labels of the vertices are two consecutive numbers.
Clique detection algorithm? Simply list the cliques "{1,2}, {2,3}, ..., {n-1, n}".

Pattern 2: There is a link between two vertices if their distance in the original graph is at most two.
Clique detection algorithm? Np-hard problem.


Quantum computer code cracking everyone! I don't know a whole lot about the fields of encryption or quantum computing, but I've read a lot of articles on the subjects and that is prescisley what caused this question. I've been a little scared about the whole NSA quantum computer that is build for the sole purpose of cracking encryption codes. I am fairly certain that they wouldn't use that power to get into random civilians' information, but if they did how hard would it be to block them out?

According to the numbers I've seen this computer could crack a typical encryption code within a little more than a week. And I recall seeing that a typical encryption key used in a consumer application is either 64 or 128 bits (or bytes?) long. I'm sorry if I'm getting these numbers wrong. Now, a week is an awful long time to to wait to crack a code (but wickedly better than with conventional computers), so they wouldn't waste their time on the password hash for your Facebook account. But say they did, wouldn't it be easy to overwhelm that system? According to mathematics the total number of time it would take to break the code would double with every bit longer the code is, and multiply by 256 with every byte. So, assuming a computer that could crack a 64bit code in up to a week, it would take 3.54^17 years to crack a 128 bit one.

Is this true? And if it is, then wouldn't this make the NSA computer useless? Because anyone that the angency would want to hack into could simply just increase the length of their encryption keys.

Thanks for any insight on the matter, and sorry if I have my facts wrong.

First of all, I seriously doubt that anyone would have a working quantum computer capable of doing anything useful in the foreseeable future (let's say 10 years). Even if someone does construct a "quantum computer", it will probably be quite useless, and it will take several years more until it can be used to, say, crack codes.

The quantum speedup for breaking symmetric encryption is quadratic: if a single decryption takes time $T$ and there are $N$ bits in the key (usually $N\geq128$ nowadays, unless you're using DES which has $N=56$), then a classical computer will take $2^NT_{\text{classic}}$ time while a quantum computer will take $O(2^{N/2}T_{\text{quantum}})$ time using Grover's algorithm (as far as I understand). In terms of real-world time, we expect $T_{\text{quantum}}$ to be several orders of magnitude larger than $T_{\text{classic}}$, at least at first. Decrypting $2^{64}$ blocks in "quantum speed" will take a lot of time, so quantum computing doesn't seem to break symmetric encryption, barring any weaknesses which enable one to use a smarter algorithm than the naive one.

The story is different for public-key encryption, though again, quantum computers capable of doing anything interesting are still far into the future. Shor's algorithm can be used to factor integers, thus breaking RSA. The algorithm also applies for the discrete log problem, even on elliptic curves. This is problematic for other public-key cryptosystems. You can check out this survey for some quantum-resistant protocols.


MCTS how to prevent Selecting a TERMINAL state in TRAVERSAL Phase? Hello I am currently working on an implementation of MCTS and I ran into the problem that my tree traversal policy selects nodes with terminal game states. Furthermore how do I prevent selecting a Node that only has children Nodes with terminal game states ( and so on and so on )?

What you can do is to add a counter $t$ to each node, initially 0, indicating how many of its children are terminal.
When $t = c$ where $c$ is the number of children of a node, the node itself becomes terminal and increments the $t$ counter of its parent. Note that with this definition leaf nodes are automatically terminal, as they have no children, giving $0 = 0$.
As one more optimization, if a node has a terminal child that is losing, you can immediately mark its parent as terminal and winning.
Then, during selection you can ignore any terminal child.


Use of Big O Notation in a recent paper by Khot et al I'm reading a paper about Constraint Satisfaction Problems, specifically "A Characterization of Strong Approximation Resistance", Subhash Khot, Madhur Tulsiani, Pratik Worah (ECCC TR13-075).

The following sentence appears in the third paragraph of the very first page:

  "... the fraction of satisfied constraints is at least $\rho(f) + \Omega(1)$"

At the bottom of page two we have a similar notation where GapCSP(f)$_{1-o(1), \rho(f) + o(1)}$ is defined.

It is confusing for me where the "limit" is being taken here. Put another way, what is the number that's varying inside the asymptotic notation?

I would think that maybe the limit is taken as the number of constraints goes to infinity, but the paper specifically mentions that fixed instances of CSP can have a fraction of $1 - o(1)$ constraints satisfied. But what values could be varying within a fixed instance? (page 2 paragraph 2)

In general, when you see big-O notation in algorithms, the default assumption is that the number that's varying is the size of the input.  Here the input size is $n+m$.

In this case the claim is valid if you think of it in terms of $m$, the number of constraints.

The claim that is being made here is a very basic claim.  It's basically a consequence of the fact that $\text{Var}[X] \to 0$ as $m \to \infty$, where the random variable $X$ is the fraction of constraints satisfied by a random assignment.  (Heuristically, if you were willing to assume independence, it would follow from the Central Limit Theorem.  In this case, you cannot assume independence, but a similar result follows nonetheless.)

If you are not sure how to prove this claim, or were unable to recognize this as a fairly standard concentration result, then you're probably going to find the  rest of the paper very difficult going, and you might  need to start by reading more basic textbooks and papers before diving into this paper.


Direct reduction from Near-Clique to Clique An undirected graph is a Near-Clique if adding one more edge would make it a clique. Formally, a graph $G=(V,E)$ contains a near-clique of size $k$ if there exists $S\subseteq V$ and $u,v\in S$ where $|S|=k$, $(u,v)\notin E$, and $S$ forms a clique in $(V,E\cup\{(u,v)\})$. How can I show a direct reduction from Near-Clique to Clique?

Let $(G,k)$ be an instance of Near-Clique, construct an instance $(G',k')$ of Clique as follows.

For each $uv \notin E(G)$, add to $G'$ a subgraph corresponding to $(N(u)\cap N(v))$, i.e.,

for each $x \in N(u)\cap N(v)$ add the vertex $x'$ to $V(G')$, and
for each edge pair of vertices $x,y \in (N(u)\cap N(v))$ if $xy \in E(G)$ add the edge $x'y'$ to $E(G')$.

Set $k' = k-2$

As $uv \notin E(G)$, $u \notin N(v)$ and $v \notin N(u)$. Note that each of these corresponding subgraphs is disjoint, so a vertex in $G$ may have several corresponding vertices in $G'$.

Now we claim that $(G,k)$ has a $k$-near-clique iff $(G',k'=k-2)$ has a $k'$-clique.

$(\Rightarrow)$ Let $D$ be the vertices of the near clique, then there are two vertices $u,v \in D$ such that

$uv \notin E(G)$,
$D\setminus\{u,v\}$ forms a clique of size $k-2$, and
$D \subseteq N(u)\cap N(v)$ (by definition).

Then $G[D\setminus\{u,v\}]$ (the subgraph induced by $D$) is a subgraph of $G'$ (via the construct and property 3). Therefore by property 2, $G'$ has a clique of size $k-2=k'$.

$(\Leftarrow)$ Let $C'$ be a $k'=k-2$ size clique in $G'$ and let $C$ be the corresponding vertices in $G$ (with induce a $k-2$-clique in $G$ as well). By the construction, there must exist $u,v\in V(G)$ such that $C\subset N(u)\cap N(v)$ (i.e. $u$ and $v$ are adjacent to all the vertices of $C$), moreover $uv \notin E(G)$. Therefore $C\cup\{u,v\}$ forms a $k$-sized near-clique in $G$.

The last step is to just assure ourselves that this is polynomial-time computable. In constructing $G'$, we examine at most each pair of vertices, and compute the intersection of their neighbourhoods. Just so we don't have to think too hard about details, that is at most $n^{2}$ neighbourhoods, and for each we take $O(n^{2})$ time to compute the intersection. So the total construction can be enacted in polynomial-time.


Theory of Complexity - Relation between a class and its complement i'm in trouble trying to prove the following proposition:

Proposition If $\ C$ is a class closed under reductions and a $\ C$-Complete problem belongs to $\ coC$, then $C=coC$.

Note: $C$ can be any class.

To prove that proposition i thought to split the proof in two ways:

(*): $C \subseteq coC$

I suppose it exists such an $L \in coC$ that is $C$-Complete. For all $L' \in C$ there is a reduction $R : L \rightarrow L'$. Thus $L \in coC$ and $coC$ is closed under reductions (because $C$ is), $L' \in coC$ also, so $C \subseteq coC$.

(*): $coC \subseteq C$

That's the part i'm not able to prove.

Thank you so much.

The first part is easy since there is a $C$-complete problem that belongs to $coC$ and since all problems in $C$ are reduced to that complete problem, $C \subseteq coC$

As for the second part let $L_C$ be a $C$-complete problem that belongs to $coC$. Then by definition of $coC$, $\overline{L}_C \in C$. So, $\overline{L}_C$ are in $C$ (decidable in $C$). Also since $L_C$ is $C$-complete, for any language $L \in C$ there is a reduction $f$ such as $x \in L \Leftrightarrow f(x) \in L_C$.

Now, if a problem $L \in coC$ then $\overline{L} \in C$ and $x \in \overline{L} \Leftrightarrow f(x) \in L_C$ meaning that $x \in L \Leftrightarrow f(x) \in \overline{L}_C$. So $L$ is reduced to $\overline{L}_C$ which is in $C$. Thus $coC \subseteq C$.


Prove that all non-recursive languages are infinite I am wondering this statement above [the title] is true or not.

Here is what I've already had : non-recursive means undecidable.

I've read this Are all infinite languages undecidable?

which says:

If a Language is undecidable(non-recursive), there must be some strings make the TM fail to halt.SO IT MUST HAVE INFINITE OF THEM WHICH MAKE THE TM FAILS TO HALT.

How could this prove my statement[title]? Can anyone explain it to me a bit more clearly?

Thanks

TM means Turing machine. And too be clear My question is : Does ALL non-recursive languages are Infinite?

First, not every infinite language is undecidable. Some infinite languages are very easy to decide. For example, the language of all words ($\Sigma^*$).

The converse is true, however: every undecidable language is infinite. In order to show this, we can simply show how to decide every finite language:

Consider a finite language $L=\{w_1,...,w_n\}$. In order to decide it, you can construct a TM $M$ that encodes in its states the words $w_1,...,w_n$. This is done as follows: the machine starts in $q_0$, which intuitively corresponds to the empty word $\epsilon$.

$M$ then reads an input letter. If there is no letter, meaning that the word is $\epsilon$, then $M$ either goes to $q_{acc}$ or $q_{rej}$, depending on whether or not $\epsilon\in L$. Now, if there is an input letter $\sigma$ on the tape, $M$ goes to a state that corresponds to $\sigma$. Then, again, it reads the tape. If there are no more letters, it either accepts or rejects, depending on whether $\sigma\in L$. Otherwise, it read the next input $\tau$ and moves to the state $\sigma\tau$, and so on, until the maximal length of a word in $L$ is reached, in which case $M$ rejects immediately.

So essentially, $M$ has a state for each word of length at most $k$, where $k$ is the maximal length of a word in $L$. Thus, $M$ can keep track of the word that was read so far, and decides if it needs to be accepted.


Myhill–Nerode equivalence classes of $\{0^n1^n \mid n \in \mathbb{N}\}$ I am told to find the equivalence classes of the Myhill–Nerode relation of the language $\{0^n1^n \mid n \in \mathbb{N}\}$. For one, I know it has an infinite number of equivalence classes given that it's a non-regular language. Im not sure how to find all the equivalence classes and show how I got those equivalence classes.

Here is how to think of this question. The equivalence relation is determined by which extensions of the current word belong to the language. There are three cases:

The current word is not a prefix of any word in the language. This happens if either the word is not in $0^*1^*$ at all, or if it is of the form $0^n1^m$ but $m > n$.
There is a unique extension of the current word which is in the language. This happens if the word is of the form $0^n1^m$ with $m \neq 0$ (and, to exclude the case above, $m \leq n$).
There are multiple extensions of the current word which are in the language. This happens for words in $0^*$.

Let us now get into more detail:

If $w = 0^n$, then we can extend $w$ to a word in the language by adding $0^m 1^{n+m}$ for arbitrary $m \in \mathbb{N}$. Note that this set of extensions is different for every $n$.
If $w = 0^n1^m$ where $0 < m \leq n$ then there is a unique way to extend $w$ to a word in the language, namely by adding $1^{n-m}$.
Otherwise, $w$ cannot be extended to a word in the language.

Accordingly, the equivalence classes are:

$\{0^n\}$ for every $n \in \mathbb{N}$.
$\{0^{n+m} 1^m : m \in \mathbb{N}\}$ for every $n \in \mathbb{N}$.
Everything else.


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

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

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

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

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


Is determining if a Turing machine runs in constant time decidable if one assumes it halts? As the title states, is determining if a Turing machine runs in constant time decidable if one assumes it halts?

The decision problem, more formally:

Given a Turing machine $M$ where it is assumed it halts on all inputs, determine if it runs in $O(1)$ time.

Is this decidable?

This answer is for the following version of the question:

  Can we decide whether an algorithm runs in constant time (that is, within $N$ steps, for some $N$), given that it is guaranteed to always halt?

This is not decidable. Given a Turing machine $T$, construct a new Turing machine $M$ which on input $t$ runs $T$ for up to $t$ steps. Then $M$ runs in constant time iff $T$ halts.


Converting to CFG from a CFL? I am trying to learn CFG.  Now to make a CFG from a CFL it is really difficult for me.

Is there any simple rule or steps so that I can easily find a CFG for a CFL. I am trying to solve one problem for generating a CFG. The Problem statement is to find a CFG that generates the following CFL: $$\{a^ib^jc^k \mid i,j,k\geq 0\text{ and } i\neq j\text{ or } i\neq k\}$$

Now I am trying hard to find one but I am not successful. Is there any easy approach to construct a CFG for a CFL?

As @babou indicated, there's no algorithmic way to produce a CFG from a description of a CFL, meaning that the problem is more art than science. There are, though, some idioms that turn out to be useful in practice.

Idiom 1. First, ignore the condition $i,j,k\ge 0$ for the moment, since that condition usually turns out to be easy to express in a grammar.

Idiom 2. See if the language can be expressed as the union or concatenation of simpler languages (intersection and complement are of less help, since CFLs aren't closed under these operations). In your case, the or in your original statement is a clue. Express your language as the union of simpler languages:
$$
\{a^ib^jc^k\mid i\ne j\}\cup\{a^ib^jc^k\mid, i\ne k\}
$$

Idiom 3. If you have an inequality, as you do here, note that we can express the $i\ne j$ condition as another or, namely $i\ne j\Longleftrightarrow (i > j) \lor (i< j)$, so
$$
\{a^ib^jc^k\mid i\ne j\}=\{a^ib^jc^k\mid i>j\}\cup\{a^ib^jc^k\mid i<j\}
$$
Idiom 4. Separate the problem into concatenated pieces if possible. For this example, we note that the $a^ib^j$ part will have nothing to do with the $c^k$ part, so we might start out grammar with the production $S\rightarrow TU$, where $T$ will generate the $a^ib^j$ and $U$ will generate the $c^k$ part. The latter is easy, and now we fill in the omission in idiom 1, writing $U\rightarrow cU\mid \epsilon$ (since if the requirement had been, say, $k>0$ we could just use $U\rightarrow cU\mid c$).

Idiom 5. Now what to do with the $a^ib^j$ part, where $i>j$? Simple, write it as $a^na^jb^j$ for some $n>0$. To get an arbitrary number of a's in front, we can use $T\rightarrow aT$. Eventually we'll stop generating a's and will switch to the matching a's and b's, using yet another variable $V$, so we'll have $T\rightarrow aT\mid aV$.

Idiom 6. Finally, to generate a matching number of a's and b's we work from the inside out, placing one of each on the ends, so we'll have $V\rightarrow aVb\mid \epsilon$. This is very common when dealing with CFLs.

Finally, then, we have the grammar for one part of our language:
$$\begin{align}
S&\rightarrow TU\\
T&\rightarrow aT\mid aV\\
U&\rightarrow cU\mid\epsilon\\
V&\rightarrow aVb\mid\epsilon
\end{align}$$
Of course, we still have a lot of work to do, but the rest is largely of the same form. Yes, it is complicated; all I can offer is that it gets easier with practice. Eventually, you might get to the stage where you'll often say "I've seen a problem like this before; maybe I can do something similar".


Applicative-order languages don't support constant time array writes? If not, why not? I'm reading Steven Skiena's "The Algorithm Design Manual", and in one of his War Stories on page 155 he states:

  Efficiency is a great challenge in Mathematica, due to its applicative
  model of computation (it does not support constant-time write
  operations to arrays) and the overhead of interpretation (as opposed to compilation).

I've already read SICP so I'm familiar with the difference between applicative and normal-order languages (i.e. that normal-order languages delay evaluation of procedure arguments until they're needed, whereas applicative-order languages evaluate them as soon as the procedure is called).  But Skiena's sentence above appears to link the idea of applicative-order languages with the idea of worse-than-constant-time array writes.  I don't remember Abelson and Sussman mentioning this in their text, so this came as a surprise.

If true, what are the under-the-hood reasons for why applicative-order languages don't write to arrays in constant time?  Why would the order of evaluation matter in determining array write time?

I'm also curious what the Big-O write performance is in this case, but I imagine that depends on the language implementation, so I'll skip that question unless there's a definitive answer.

Skiena didn't say "applicative order", just "applicative". This is sometimes used as meaning something like "purely functional", or a language that evaluates via the application of functions as opposed to the execution of state manipulating commands. Mathematica (at least nowadays) isn't purely functional, but it does seem that it strongly encourages a purely functional style of programming.

In a purely functional language, such as Haskell, you apply functions to values and produce new values just as in mathematics. Like math, in such a language, variables are just names for values. If you say "let $x$ be $1$", then $x$ and $1$ are everywhere interchangeable. It makes no more sense to talk of "mutating" $x$ to be $2$ than it does to say to set $1$ to be $2$. For array this means that to "update" an array, you build a new array with the changes. Obviously, building an entire copy of an array except for the one entry you're changing is expensive. This is almost certainly the issue Skiena is referring to.

There is, to my knowledge, no fully satisfactory answer to this. That is, there is no purely functional data structure that provides constant time lookup and updates to all versions. You can make (externally) pure data structures that provide constant time lookup and update for the latest versions, but accesses to older versions of the array become slower. You can use monads or uniqueness types to enforce a usage of arrays that allows the compiler to use in-place updates, but this is tantamount to using an imperative approach (albeit in a controlled and contained manner). In practice, programmers in purely functional languages simply don't use arrays nearly as much as imperative programmers, and when they do use arrays, they tend to use bulk operations. If you are going to touch every element of an array anyway, then the cost of copying the array is constant per element.

While there are definitely times where the limitations of purely functional programming make efficient implementation non-obvious, most of the time it is just a matter of applying different design and implementation techniques than are typical/practical in imperative languages. Purity also affords guarantees that make many designs, optimizations, and sometimes entire technologies practical. For the first, most purely functional data structures are designed to share as much as possible. For the second, a major technique for improving performance of bulk operations is fusion which combines multiple bulk operations into one to avoid intermediates. For the last, there was an attempt to add Software Transactional Memory to C# that was given up because it relied on the programmer not using side-effecting procedures in the transactions but could not enforce this practically.