# Question
Title: Create a PDA that accepts the following language
I need to create a PDA that accepts by empty stack and accepts the language formed by strings over the alphabet $\\{a, b\\}$ of the form: $uw$, where $w$ is the string $u$ reversed and doubled. So, for example, if $u=ab$ then $w=bbaa$ (the $ab$ is reversed then its characters are doubled).

Examples of strings in the language: $\epsilon$, $aaa$, $baaabb$, $abbbbbbaa$, etc.

I'm really struggling with setting up a PDA that satisfies the criteria. Any help is appreciated.

# Answer
> 0 votes
The PDA operates as follows :

1. Push the symbols you read to the stack
2. Non-deterministically guess when u ends and w starts
3. Now for the rest of the string , we consider 2 symbols by 2 symbols , if the 2 symbols are not the same reject , if the 2 symbols are the same , compare them to top of stack , if they are not the same symbol reject , if they are the same pop the stack
4. After reading the entire input , if the stack is empty accept , else reject

Ex : s = ab bbaa , we push a,b to stack , then we guess u ends and w starts , now we read b , then b , both are same symbol , we look at top of stack we have b we pop the b , now the stack has a , and we will read aa , repeat the above again and we accept

If you get how it works , you may want to try to sketch the PDA

Here is a sketch of the PDA to check your answer :

---
Tags: automata, pushdown-automata
---


# Question
Title: How can I prove that the language is not CFL?
I have this language: $L=\\{x^ny^jz^k:k=j\cdot n\\}$, I know I can use the pumping lemma for CFL, but I have managed to do it for $k, j, n \leq 0$, and with $k = j \cdot n$ I have not been able.

# Answer
We will replace the symbols x,y,z by a,b,c respectively , so we don't get confused when using the pumping lemma

Consider the string w = a^p b^p c^(p^2) , clearly w ∈ L , we will show that w cannot be pumped

Neither v or y can have 2 type of symbols or the order gets messed up when pumping , so both v and y must have one type of symbols ( so for ex v has only as , y has only bs )

Now if v and y don't have cs the string can't be pumped , if they have only cs the string can't be pumped too , since you can't maintain k=jn

So we know now that each of v and y must have only one type of symbol and that they must include cs but no only cs ,so y must have cs , and v must have bs (it can't have as or |vxy| \> p)

The only way to pump the string now is for v = b and y = c^p , in this way whenever the string is pumped , when we add a b we add c^p , maintaining k=jn

But for this to happen |vxy| \> p which is unacceptable

So w can't be pumped and thus L is not a CFL
> 1 votes

---
Tags: context-free, pumping-lemma
---


# Question
Title: Proving some subsets of a regular languages to be regular languages
I have to prove that if a language $L$ is regular then:

a) $NONPREFIX(L)=\\{u \in L / $none of the prefixes (not $\epsilon$ or $u$) of $u$ are elements of $L \\} $ is regular

On this one I think I can divide the words of L in two parts and get it, since regular languages are closed under concatenation, I dont know if this is correct.

And the other one:

b) $NONEXTENSION(L)=\\{u \in L / $ $u$ is not a prefix (not $\epsilon$ or $u$) of any element of $L \\} $ is regular

In this one I've no idea how to begin.

Any help would be pretty apreciated. Thanks!

# Answer
a) Proving NOPREFIX(L) is regular :

The idea is simple , for a string w ∈ NOPREFIX(L) , w must be in L , and no proper prefix of w is in L

So , if we have a DFA M for L , we run string w on M , changing M a bit , if M enters the accept state before the end of the input , then a proper prefix of w is accepted by L and so we reject , if not and we reach an accept state just by the end input we accept , of course if by the end of w we don't enter an accept state we reject since w is not in L an so not in NOPREFIX(L)

Now you may want to try constructing M' based on the above explanation , then check your answer

Proof :

Let M = (Q,Σ,δ,q0,F) recognising some regular language L ,construct M' = (Q',Σ,δ',q0',F') to recognise NOPREFIX(L) as follows :

Q' = Q

for r ∈ Q' , a ∈ Σ

δ'(r,a) = δ(r,a) , if r is not in F

δ'(r,a) = ∅ , if r ∈ F

q0' = q0'

F' = F

Hopefully you can see how changes in δ' achieve our purpose , M' simulates M , till it reaches an accept state , if the input ends we accept ( note that w is not a proper prefix of w) since w ∈ L , and we did not encounter any accepted proper prefixes , but if we enter an accept state and the input is not yet finished we reject since this means that we encountered an accepted proper prefix

b) Proving NOEXTEND(L) is regular

This is an easier one , for a string w ∈ NOEXTEND(L) , we need to make sure that no string wx ∈ L , x ∈ Σ^+ , so for w not to be a proper prefix of a string in L ,we need to make sure that no symbols could be added to w to form a string in L ,

Once again you may want to try M' that recognises NOEXTEND(L)

Proof :

Let M = (Q,Σ,δ,q0,F) recognising some regular language L ,construct M' = (Q',Σ,δ',q0',F') to recognise NOEXTEND(L) as follows :

Q' = Q δ' = δ q0' = q0'

F' = { q| there is no path from q to an accept state in F)

M' works exactly as M , when the string end we consider the final state we reached q , if there is a path from q to any accept state in F ( the accept states of M) , then we reject since this means we can extend w by x to reach a string wx ∈ L , with x being the string of symbols on the path from q to accept state , and thus w is a proper prefix of some string wx ∈ L , if there is no path from q to an accept state so w cannot be extended to form a string in L and thus we accept
> 2 votes

# Answer
A negation in the description of a given language, such as "none" and "not", is a strong indication that you should consider the complement of that language. Together with the property that regular language is closed under complementation, we can get a proof easily.

For problem a), consider its complement $$WITH\\\_PREFIX\\\_FROM(L)=\\{u \in L\text{ at least one of the proper prefixes of }u\text{ belongs to }L\\}.$$

Suppose $L$ is recognized by a DFA $D$. Let us build a new DFA $D'$ from $D$. $D'$ has exact the same states, alphabet, transition function and start state as $D$. For each state $s$ of $D$, if it can be reached by a word that contains a proper prefix that is in $L$, we will mark the corresponding state in $D'$ as a accept state of $D'$. Every state that reachable from those accept states will be marked as accept state as well. Now you can check that $WITH\\\_PREFIX\\\_FROM(L)$ is recognized by $D'$. As its complement, $NONPREFIX(L)$ is regular, too.

I will leave problem b) as an exercise.
> 1 votes

---
Tags: formal-languages, regular-languages, automata, regular-expressions
---


# Question
Title: What is the diference between $\lambda x.1$ and $1$?
I know that I can $(\lambda x.1) 0 \rhd\_\beta 1$. This is the constant 1, but can I contract it automatically? I mean, is $1$ the normal form of $(\lambda x.1)$?

It seems reasonable to do it but when goes to combinators this sense stops, I mean, if I can $\lambda x.1 \rhd\_\beta 1$, then I would $\lambda xy.y \rhd\_\beta \lambda y.y$ but $(\lambda xy.y) a b \rhd\_\beta b$ and $(\lambda x.1) a b \rhd\_\beta 1 b$ so that $\lambda x.1 \not\equiv\_\beta 1$

What rules I'm missing on Lambda cauculus that forbids the contraction $\lambda x.1 \rhd\_\beta 1$?

# Answer
> 6 votes
$\lambda$-contraction is defined as $(\lambda v.M)N \triangleright\_\beta M\[v/N\]$. A $\lambda$-term of the form $(\lambda v.M)N$ is called a **redex** (= reducible expression). In order to reduce a term, you need a redex -- that's just how $\lambda$-contraction is defined.
The reason that $\lambda x.1$ can not be any further reduced is that it does not contain any redex: It is not and does not contain any terms of the form $(\lambda v.M)N$, so $\lambda$-contraction is just not applicable anywhere. The term thus already is in normal form.
In contrast, $(\lambda x.1)0$ contains a redex, namely itself -- with $v = x$, $M = 1$ and $N = 0$ --, and $\lambda$-contraction yields the normal form $1$.
Obviously $\lambda x.1$ and $1$ are non-equivalent normal forms: One is a function that yields a number, the other one is a number.
$(\lambda x.1)$ is different from $(\lambda x.1)0$ in the same way in which, say, $f: x \mapsto x^2$ is different from $f(2)\ (= 4)$. A function is not the same as the value of the function at an argument, and a function can not be applied to yield a value without an argument present.

---
Tags: lambda-calculus
---


# Question
Title: Find close pairs of real points in a set
Given an array $S$ with $n$ real numbers. Design a linear time algorithm that finds $x,y \in S$ such that that $|x-y| \leq \frac{max(S)-min(S)}{n-1}$.

I was thinking that it is similar to the closest point problem but that can only be solved in O(nlogn).

Please help

# Answer
> 1 votes
Hint: by the pigeon principle, if $n$ pigeons have to go into $n- 1$ holes, at least one hole has two pigeons in it. Now let your pigeons be numbers, and make sure that if two numbers go in the same hole, they solve your problem.

---
Tags: algorithms
---


# Question
Title: Find maximal difference between two consecutive numbers
You are given $n$ real (unsorted) numbers $\_1,\_2,...,x\_n$. We want to compute the maximal difference between two consecutive numbers in sorted order. Explain how to do it in $()$ time when you are allowed to use additions, subtractions, multiplications, divisions and “floor” function. Notice that sorting immediately leads to $( log)$ time.

Please help !

# Answer
> 0 votes
Determine the minimum $a$ and maximum $b$ in a first pass.

Create $n+1$ buckets, each of width $\frac{b-a}{n+1}$, with the first beginning at $a$. We have $n+1$ buckets and only $n$ points, so by the pigeonhole principle, there must be at least one empty bucket. Since we know that the first and last buckets contain at least one point, we know furthermore that there must be an empty bucket with a nonempty bucket somewhere to its left and another nonempty bucket somewhere to its right, implying that the solution must be at least $\frac{b-a}{n+1}$.

This means that **no two points within the same bucket can provide the solution**, since they must be strictly less than $\frac{b-a}{n+1}$ apart from each other. So, any solution will consist of a pair of points from *different* buckets.

A valid solution must consist of the rightmost point from some bucket $i$ and the leftmost point from some bucket $j \> i$ with all buckets in between (which may be no buckets at all, when $j=i+1$) empty. So it is sufficient to know, for each bucket, its leftmost and rightmost points.

To compute these, iterate through all the points again, updating the leftmost and rightmost positions of the current point's bucket whenever necessary. (For the first point in a bucket, both of these positions will need to be updated.) A point's bucket can be computed by subtracting $a$ and dividing by $\frac{b-a}{n+1}$.

Finally, iterate through all the buckets, keeping track of the rightmost point in the last nonempty bucket seen, and comparing it with the leftmost point in the current bucket: Update the maximum whenever this exceeds the current maximum.

---
Tags: algorithms
---


# Question
Title: Number of vertices and edges lies on the boundary of bounded cells in line arrangement
I am learning computational geometry by myself using these lecture notes from ETH Zurich. Here is an exercise (8.9) I have been stuck for a few days:

> For a line arrangement $A$ of a set of $n$ lines in $R^2$, let $F$ denote the union of the closure of all bounded cells. Show that the complexity (number of vertices and edges of the arrangement lying on the boundary) of $F$ is $O(n)$.

My intuition is to use induction, proving that when a new line $l$ is added, the number of added edges is a constant. This is similar to how we proved the zone theorem. However, I cannot figure it out. Can someone provide me with some hints?

# Answer
> 3 votes
Consider 3 additional lines such that their arrangement consists of a single bounded (triangular) cell $C$ and $F \subset C$. Then every edge of $F$ belongs to a zone (using a terminology from your textbook) of at least one of the 3 added lines. And all 3 zones of 3 added lines contain at most $30n$ edges according to Zone Theorem. So $F$ has no more than $30n$ edges which is $O(n)$.

---
Tags: computational-geometry
---


title: Benford's law is not working?

text:
# Question
Title: Benford's law is not working?
So I recently came across Benford's law and immediately tried to code it out but the answer I got was rather confusing. I've been thinking about it for about an hour now and still can't get it, I think my code is correct I'm pretty sure it is but the result is just not the one others get. Here's the code:

```
float[] a=new float[10000],flag=new float[10];

for(int i=0;i<10000;i++)
  {
    a[i]=floor(random(0,99999));
      if(a[i]>10000)
         a[i]=floor(a[i]/10000);
      if(a[i]>1000)
         a[i]=floor(a[i]/1000);
      if(a[i]>100)
         a[i]=floor(a[i]/100);
      if(a[i]>10)
         a[i]=floor(a[i]/10);

      for(int k=1;k<10;k++)
       {
          if(a[i]==k)
            flag[k]++;
       }

  }

```

Though I get roughly the same *flag\[k\]* (around 1100) but according to Benford's law that should not be the case. Can someone help me tell how my code is wrong?

# Answer
> 1 votes
That's because for the numbers from 10,000 to 99,999 the first digit is equally likely, same for numbers from 1,000 to 9,999 etc.

Benford's law depends on random numbers whose logarithm has a linear distribution over a not too small range. Take random numbers x from 0 to 999,999, then calculate 10^(x/200000) and you'll find that Benford's law will hold.

But measure the height of adult people in feet, and 95% start with 5 or 6, a few percent start with 4, and very few with 7 or 3. It's not a law that applies to every set of numbers. (Measure people in meters, and 98% start with 1, a few with 2, and very few start with a 9 or even 8. )

# Answer
> 0 votes
Well I found the answer, We need to make the maximum possible digit random too. The result keep better-representing benford's law the more and more random variables I use

here's the new code that gave me a very satisfactory result

```

float a,p,q,r;

  for(int i=0;i<10000;i++)
  {
    r=random(0,99999);
    q=random(0,r);
    p=random(0,q);
    a=floor(random(0,p));
      while(a>=10)
       a/=10;

      flag[a]++;
  }

```

Result : *flag\[1\]* = 3050 (expected 3010) . *flag\[2\]* = 1746 (expected 1760) and so on(of course they keep changing but do remain within 2-3% of the expected outcome).

---
Tags: graphs, randomness
---


# Question
Title: Connection between Pseudo random generators and hardness
For a boolean function $f:\\{0,1\\}^n\longrightarrow\\{0,1\\}$ $H\_{avg}(f)$ is defined as the largest $S(n)$ s.t. for all circuit $C\_n$ of size $S(n)$, $\Pr\_{x\in U\_n}\[C\_n(x)=f(x)\]\<1/2+1/S(n)$. Here $U\_n$ is uniform distribution over $\\{0,1\\}^n$.

According to Nisan Wigderson 1988, I know that if there exists $f\in E$ with $H\_{avg}(f)\geq S(n)$ then there is a $S'(l)$-Prg where $S'(l)=S(n)^{0.01}$. For any general $S(l)$, a Pseudo-random generator, is called an $(S(l),\epsilon)$-Prg if for circuit family $C\_{S(l)}$ of size $S(l)$ $|Pr\_{x\in U\_{l}}\[C\_{S(l)}(G(x))=1\]-Pr\_{x\in U\_{S(l)}}\[C\_{S(l)}(x)=1\]|\<\epsilon$. Here $G$ is a pseudo random function $G:\\{0,1\\}^l\longrightarrow\\{0,1\\}^{S(l)}$, generates an $S(l)$ length strings from length $l$.

I was thinking if the converse is also true or not. Means, if we can show the existence of $S(l)$-Prg, then does it follows that there is $f$ with $H\_{avg}(f)\geq S(n)$?

# Answer
> 1 votes
Theorem 1 in \[Nisan Wigderson 1988\] implies:

For any function $l\le s(l)\le 2^l$, the following are equivalent:

1. For some $c\>0$, there exists a quick PRG $G: l\to s(l^c)$.
2. For some $c\>0$, there exists a function $f$ in EXPTIME with hardness $s(l^c)$.

Although their definition of (quick) PRG and hardness are slightly different from yours, I think the conclusion is still the same (as long as $\epsilon \<1/2$, and your conclusion should be $H\_{avg}(f)\ge S(l^c)$ for some $c$ rather than $H\_{avg}(f)\ge S(n)$).

The proof can be summarized as follows:

1. Regard the PRG as an extender from string of length $l$ to string of length $l+1$, and consider the boolean function $f$ corresponding to this extender.
2. Show that $f$ cannot be approximated by circuits of size $S(l^c)$, i.e., for some constant $k$, all large enough $l$, and all circuits $C\_l$ of size $S(l^c)$, $\mathrm{Pr}\_{x\in U\_l}\[C\_l(x)\neq f(x)\]\>n^{-k}$ (note this is a weaker condition compared to the definition of hardness, i.e. your $H\_{avg}$).
3. Use Yao's lemma \[Yao 1982\] to xor multiple copies of $f$ to obtain a function $f'$ such that $H\_{avg}(f')\ge S(l^c)$.

You can see more details in \[Nisan Wigderson 1988\].

---
Tags: complexity-theory, circuits, cryptography, lower-bounds, pseudo-random-generators
---


# Question
Title: Is this statistical group summation unambiguously reversible?
Let $X$ be a finite multisubset of $\mathbb{N}^2$. Let's introduce the following notation:

$A$ is a set of all first elements of pairs from $X$ and $B$ is a set of all second elements of pairs from $X$.

$cnt\_1(n) = |\\{(n, b)|(n, b) \in X\\}|$ (that is a number of elements in a corresponding set).

$cnt\_2(n) = |\\{(a, n)|(a, n) \in X\\}|$

$sum\_1(n) = \sum\_{(n,b) \in X}b$

$sum\_2(n) = \sum\_{(a,n) \in X}a$

$Y=\\{(a, cnt\_1(a), sum\_1(a))|a \in A\\}$

$Z=\\{(b, cnt\_2(b), sum\_2(b))|b \in B\\}$

**The question:** Given only $Y$ and $Z$ is it always possible to unambiguously reconstruct $X$?

---

Equivalently, phrased in terms of SQL: Given an (unordered) set of 2-tuples (`X`) of natural numbers:

```
CREATE TABLE X (
    a int,
    b int
);

```

the following statistical summaries and are derived:

`Y`:

```
SELECT a, COUNT(1) AS ca, SUM(b) AS bs FROM X GROUP BY a ORDER BY a;

```

`Z`:

```
SELECT b, COUNT(1) AS cb, SUM(a) AS as FROM X GROUP BY b ORDER BY b;

```

Is it possible to unambiguously re-construct `X` when knowing only `Y` and `Z`?

# Answer
The answer is no . I found it helpful to think of the information in the form of a picture: mark each pair $(a, b)$ as a point on a grid, then in each column and row write both the count of the entries in that row, and the "sum" of the entries (the sum of the 'other' coordinate). Your example may be pictured as follows:

I'm writing the count of the dots in each row/column as the number closest the the column, and the "sum" as the number further away. The original data is the set of dots, the new data are Y and Z (understood to not just be sets of points, but to be positional: for example we remember that in the $Y$ data we have $(2, 3)$ in column $1$, $(1, 3)$ in column 2, and so on).

Here are two configurations of points with equal $Y$ and $Z$ data:

Hence the operation is not reversible. Per-column ambiguity arises when there are multiple integer partitions with the prescribed number of parts: eg if a column counts to 2 and sums to 5, its possible entries are 1 + 4 or 2 + 3.
> 2 votes

---
Tags: algorithms, statistics, one-way-functions, reversible-computing
---


title: Is Conjunctive Normal Form or not?

text:
# Question
Title: Is Conjunctive Normal Form or not?
I have one formula that I do not understand why it is CNF and one that is not CNF, namely.

1. p && !q (NOT NCF)

and

2. !!p(CNF).

According to the exercise where I found these examples, 1 is not CNF and 2 is CNF.

How can the first formula not be CNF, when for example p && q is CNF. If for example !!p is part of a formula we will translate it to p, how can we say that it is CNF?

# Answer
> 1 votes
Your examples do not look correct according to my understanding of the definition of CNF. The first formula is CNF; it has two clauses, each with a single literal. I would say that the second isn't, but the equivalent formula p is. See https://en.wikipedia.org/wiki/Conjunctive\_normal\_form.

---
Tags: algorithms, terminology, logic, propositional-logic, normal-forms
---


# Question
Title: Describe a data structure to track visitors
> Given $n$ cities, describe a data structure which supports the following functions:
>
> Init$(n)$ \- initializes the data structure in $O(1)$
>
> Visit$(j,i)$ \- adds "citizen from city $j$ would like to visit city $i$" in $O(1)$
>
> Favorite($k$) - prints the $k$ most favorite cities in descending order in $O(k)$ (ignore ambiguity such as 2 cities with same amount)

I can't find how to do the last one in $O(k)$, hints would be appreciated.

# Answer
> 2 votes
The idea is to keep a sorted list of non-empty "buckets". Each bucket $v$ is associated to a certain number $n\_v$ of people that wish to visit some city and contains all the cities $c$ that wish to be visited by exactly $n\_v$ people.

By keeping a suitable set of pointers cities can be moved from one bucket to the next in constant time. To perform a Favorite($k$) operation it suffices to look at the "last" buckets in the sorted list.

---

The data structure consists of:

* A doubly-linked list $L$. Each node $v$ of $L$ is associated to an integer $\eta\_v$ and to a (pointer) to an inner list $\ell\_v$ of cities $c$ such that exactly $\eta\_v \> 0$ people want to visit $c$. The integers $\eta\_v$ are appear in increasing order when traversing $L$.
* An array $N$ of $n$ elements. The $i$-th element $n\_i$ of $N$, if initialized, is the number of people that want to visit the $i$-th city.
* An array $P^L$ of $n$ elements. The $i$-th element $p^L\_i$ of $P^L$, if initialized, is a pointer to the node $v$ of $L$ such that $\eta\_v = n\_i$.
* An array $P^\ell$ of $n$ elements. The $i$-th element $p^\ell\_i$ of $P^\ell$, if initialized, is a pointer to the node containing the $i$-th city in the list $\ell\_v$, where $v$ is the node of $L$ pointed by $p^L\_i$.

**Init$(n)$**:

* Create an empty list $L$. Allocate (but do not inizialize) the arrays $N$, $P^L$, and $P^\ell$ in $O(1)$ time.

**Visit$(\cdot,i)$**:

* If $n\_i$ is initialized, delete (in constant time) the node pointed by $p^\ell\_i$ from the list $\ell\_v$ where $v$ is the node of $L$ pointed by $p^L\_i$. If $\ell\_v$ is empty, delete $v$ from $L$. Increment $n\_i$.
* Otherwise, if $n\_i$ is not initialized, set $\eta\_i=1$.
* Find the node $v'$ of $L$ such that such that $\eta\_{v'}=n\_i$, if it exists. Notice that $v'$ can only be the node of $L$ following (the possibly just deleted) node $p^L\_i$ in $L$.
* If $v'$ did not exists, then create it (in constant time).
* Add city $i$ to a new node $z$ of $\ell\_{v'}$.
* Make $p^L\_i$ point to $v'$.
* Make $p^\ell\_i$ point to $z$.

**Favorite$(k)$**:

* Let $v$ be last node of $L$.
* While $k\>0$ and $v$ exists:
    + Let $x$ be a pointer to the first node of $\ell\_v$
    + While $k \> 0$ and $x$ exists:
        - Return the city stored in $x$.
        - Set $x$ to the vertex following $x$ in $\ell\_v$ (possibly none).
        - Decrement $k$
    + Set $v$ to the vertex preceding $v$ in $L$ (possibly none).

---
Tags: data-structures
---


# Question
Title: If there is an algorithm $A$ that guesses the entire message, given an encryption, with probability of $0.2$, then it's not $(O(A) +O(n), 0.1)$-secure
Let $(E,D)$ be a cipher with message space $M = \\{0,1\\}^n$ and key space $K = \\{0,1\\}^n$.

Assume that there is an algorithm $A\colon \\{0,1\\}^n \to \\{0,1\\}^n$ of size $T$ that given an encryption of a message can guess the entire message with probability $0.2$. Namely, for a message $m \in M$ it satisfies $$P\[A(E(k,m)) = m\] = 0.2$$

I want to prove that $(E,D)$ is not $(T + O(n), 0.1)$-secure.

A cipher $(E,D)$ is called $(T + O(n), 0.1)$-secure if for every two messages $m\_1, m\_2 \in M$ and every algorithm $B\colon \\{0,1\\}^n \to \\{0,1\\}$ of size at most $T + O(n)$, it follows that: $$| P\[B(E(k,m\_1)) = 1\] - P\[B(E(k,m\_2)) = 1\] | \le 0.1$$

My idea was to assume on the contrary that $(E,D)$ is $(T+O(n), 0.1)$-secure, and then find an algorithm $B\colon \\{0,1\\}^n \to \\{0,1\\}$ of size $T+O(n)$ that uses $A$ to break this encryption.

Namely I need to show that for any two messages $m\_1, m\_2 \in M$ it satisfies:

$$| P\[B(E(k,m\_1)) = 1\] - P\[B(E(k,m\_2)) = 1\] | \> 0.1$$

Basically I need to describe such $B$ and two messages $m\_1, m\_2$ that satisfy this inequality.

My idea was to pick two random messages $m\_1, m\_2 \in M$. Then, somehow use $A$ to get the probability $P\[B(E(k,m\_1)) = 1\] = 0.2$, and use randomness somehow to get the probability $P\[B(E(k,m\_2)) = 1\] = 0.2 \times 0.5 = 0.1$

However, I don't really know how to do that.

Help or some hint would be very appreciated!

# Answer
Let $m\_1$ be an arbitrary message. We are guaranteed that $P(A(E(k,m\_1)) = m\_1) = 0.2$. Averaging over all other messages, there is some message $m\_2$ such that $P(A(E(k,m\_1)) = m\_2) \leq 0.8/(2^n-1) \leq 2^{-n}$.

Consider the following algorithm $B$: on input $x$, if $A(x) = m\_2$ then output $1$, else output $0$. By assumption, $P(B(E(k,m\_1))=1) \leq 2^{-n}$, whereas $P(B(E(k,m\_2))=1) = 0.2$. When $n \geq 4$, the difference between the two probabilities is larger than $0.1$.
> 1 votes

---
Tags: cryptography
---


# Question
Title: Annotated type system problem about conditional branch
I am reading the book "Principle of Program Analysis" by Flemming Nielson for annotated type systems. In the first chapter, section 1.6 they mentioned the simple type system for various statements(S). And S maps a state to a state, and may therefore to have type Σ --\> Σ where Σ denotes the type of state. So they mentioned a system of axioms and inference rules like below for sequential statements and if-else block:

1.
2.

And later it is explained, an if-else statement in terms of Reaching Definition as below,

Also, I can visualize the sequencing rule seems natural, but they mentioned conditional rule is more dubious. I am not able to understand how this is dubious? As per my understanding reaching definition after after 'if' block execution will may execute then block or else block, then how this is even conflicting? S1 may have different statements and S2 will also have different statements but these two blocks would not execute at same time. I am not getting this scenario, can you please help me with this

# Answer
With the above expression, two branches (if and else) have the same analysis information at their respective entry and exit points i.e. In simple terms we can say that then-branch gives rise to the same set of reaching definitions as the else-branch does.

So, this is dubious, depending on the condition of if-block it is decided control will go to `then` or `else` block which will become the exit of if-block. To follow this idea we can modify the equation like below.

We assume that if if-block gets executed as true then final(S1) is executed i.e. RD2 and for false statement final(S2) i.e. RD3 is executed. The exit of the if-block is the subset of the union of then-block and the else-block.
> 0 votes

---
Tags: compilers, type-inference
---


title: Position in the Linked-list

text:
# Question
Title: Position in the Linked-list
I am reading **Data Structures and Algorithms** by Alfred Aho, Jeffrey Ullman, et al. In the section about lists it's said:

> We should note that a position in a linked-list implementation of a list behaves differently from a position in an array implementation. Suppose we have a list with three elements a, b, c and a variable p, of type position, which currently has position 3 as its value; i.e., it points to the cell holding b, and thus represents the position of c. If we execute a command to insert x at position 2, the list becomes a, x, b, c, and element b now occupies position 3. If we use the array implementation of lists described earlier, b and c would be moved down the array, so b would indeed occupy the third position.
> However, if the linked-list implementation is used, the value of p, which is a pointer to the cell containing b, does not change because of the insertion, so afterward, the value of p is "position 4," not 3. This position variable must be updated, if it is to be used subsequently as the position of b.†

I don't understand how do position works? It's said that position works differently in pointer implementation that that of array but, the result seems to be the same on both. In both implementation position (pointer) moves forward. Then, what's the difference? I appreciate your answers.

# Answer
> 0 votes
First of all, let me strongly recommend avoiding outdated textbooks such as Aho, Hopcroft and Ullman.

Let me also replace Aho, Hopcroft and Ullman's use of "position" with the more common notion of pointer. In a linked list, each cell consists of a value and pointer to the following cell (if any). The linked list itself is represented as a pointer to its first cell (if any). Therefore, if we consider the list $a,b,c$, then a pointer which is pointing at the third element will be pointing at the cell containing $c$.

(This is also a good place to mention that unless you're programming in Fortran or in Excel, then your arrays are zero-based; that is, the first element is element number 0.)

Now suppose that $p$ is a pointer which currently points at the cell containing $c$. If you insert $x$ between $a$ and $b$, then $p$ will still be pointing at $c$. However, $c$ is now the fourth element rather than the third element.

In contrast, if the list were implemented as an array, then $p$ will be a pointer to the third element of the array. Therefore, after inserting $x$ between $a$ and $b$, the pointer $p$ will be pointing at $b$.

---
Tags: data-structures, linked-lists, lists
---


# Question
Title: Prove that if for every vertex in $G[U]$ there is an edge in to every vertex in $G[V-U]$ then there is a path from every $u$ to every $v$
> Given a connected directed acyclic Graph $G=(V,E)$ and a subset $U\subseteq V$. Prove that if for every vertex in $G\[U\]$ with out-degree zero there is an edge in $G$ to every vertex in $G\[V-U\]$ with in-degree zero, then there is a path from every $u\in U$ to every $v\in V\backslash U $.

I thought maybe to try a proof by contradiction- suppose that $u\in U$ and $v\in V\backslash U $ so there isn't a path $u\leadsto v$. Divide to four cases based on the out-degree of $u$ and the in-degree of $v$,
so when the out-degree of $u =$ the in-degree of $v= 0$, it is straight forward contradiction, but with the other case I'm having some trouble.
Maybe there is an easier way to prove the given proposition?

# Answer
You can use a direct proof. There is no need to assume that the graph is connected.

Take any $u \in U$. We will construct a directed path $u\_0\to\cdots\to u\_\ell$ in which $u\_\ell \in U$ has out-degree zero in $G\[U\]$, as follows. First, $u\_0 = u$. Given $u\_i$, if $u\_i$'s out-degree in $G\[U\]$ is zero, then $\ell = i$. Otherwise, let $u\_{i+1}$ be an arbitrary out-neighbor of $u\_i$. Since $G$ is acyclic, the vertices $u\_i$ do not repeat, and so the path must terminate eventually.

Similarly, for any $v \in V \setminus U$ there is a directed path $v = v\_0 \gets \cdots \gets v\_r$, where $v\_r \in V \setminus U$ has in-degree zero in $G\[V \setminus U\]$. By assumption, there is an edge $v\_\ell \to u\_r$. Combining both paths with this edge, we obtain a path from $u$ to $v$.
> 1 votes

---
Tags: algorithms, graphs
---


title: Map data structure terminology

text:
# Question
Title: Map data structure terminology
I'm looking for the correct terminology in regard to map (dictionary) data structure.

When I'm talking about the semantics of the values stored in map in the direction from keys to values, I'd say, for example

> messages keys are mapped to message strings

When I'm using the opposite direction - describing the values first, I'd need to say something like

> message strings are ??? by message keys ("being mapped by" just doesn't feel right here)

# Answer
> 0 votes
How about "message strings are associated with keys"?

---
Tags: data-structures, terminology
---


# Question
Title: Distinguishability of distributions that are not close given just one sample
Consider (over $n$-bit strings) the uniform distribution $U$, and another distribution $D$ such that \begin{equation} \text{Distance}(D, U) \geq \frac{1}{e}, \end{equation} where $\text{Distance}$ stands for the total variation distance, given by \begin{equation} \text{Distance}(D, U) = \sum\_{z \in \\{0, 1\\}^{n}} \left|\underset{\text{Z} \sim D}{\text{Pr}}\[\text{Z}=z\] - \underset{\text{Z} \sim U}{\text{Pr}}\[\text{Z}=z\]\right|, \end{equation} for a random variable $\text{Z}$. In other words, $D$ and $U$ are quite far from each other. Even then, it seems intuitively true to me that we should not be able to distinguish between these two distributions with a polynomial-time algorithm if we are given one (and just one) sample as input, with the promise that the sample comes from one of these two distributions.

By this, I mean that it seems intuitive to me the quantity \begin{equation} \left|\underset{x \sim D}{\text{Pr}}\[A(x) =1\] - \underset{x \sim U}{\text{Pr}}\[A(x) =1\]\right| \end{equation} is small, for a polynomial time algorithm $A$.

Is my intuition correct? If not, it just doesn't seem obvious to me how we could distinguish these distributions with just one sample. Isn't it too little information? Can you show how we are to distinguish by any explicit description of such an algorithm for any such $D$?

# Answer
Total variation distance, which is exactly half of your notion of distance, is equal to $$ d\_{TV}(D,U) = \frac{1}{2} \operatorname{Distance}(D,U) = \max\_A \bigl|\Pr\_{x \sim D}\[A(x)\] - \Pr\_{x \sim U}\[A(x)\] \bigr|. $$ You can take $A$ to be the indicator of $\Pr\[D(x)\] \geq \Pr\[U(x)\]$. The event $A$ might be hard to compute, but it could also be easy to compute. In the latter case, you will be able to efficiently distinguish between $D$ and $U$, even using only one sample. This may even be possible in the former case, though with an advantage less than the total variation distance.

---

Here is a proof of the equivalence between the two formulations.

Since $$ \Pr\_{x \sim D} \[A(x)\] - \Pr\_{x \sim U}\[A(x)\] = -\left(\Pr\_{x \sim D} \[\overline{A(x)}\] - \Pr\_{x \sim U}\[\overline{A(x)}\]\right), $$ where the overline represents negation, we have $$ \delta\_{TV}(D,U) = \max\_A \bigl( \Pr\_{x \sim D} \[A(x)\] - \Pr\_{x \sim U}\[A(x)\] \bigr). $$ Let $S = \\{ x : A(x) \\}$. Then $$ \Pr\_{x \sim D} \[A(x)\] - \Pr\_{x \sim U}\[A(x)\] = \sum\_{z \in S} \bigl(\Pr\_{Z \sim D}\[Z = z\] - \Pr\_{Z \sim U}\[Z = z\]\bigr). $$ This formula makes it clear that an optimal choice for $S$ is $$ S = \\{ z : \Pr\_{Z \sim D}\[Z = z\] \geq \Pr\_{Z \sim U}\[Z = z\] \\}. $$ For this choice of $S$, we have \begin{align} d\_{TV}(D,U) &= \Pr\_{x \sim D} \[A(x)\] - \Pr\_{x \sim U}\[A(x)\] \\ &= \Pr\_{x \sim D}\[x \in S\] - \Pr\_{x \sim U}\[x \in S\] \\ &= \bigl(1-\Pr\_{x \sim D}\[x \notin S\]\bigr) - \bigl(1-\Pr\_{x \sim U}\[x \notin S\]\bigr) \\ &= \Pr\_{x \sim U}\[x \notin S\] - \Pr\_{x \sim D}\[x \notin S\]. \end{align} By definition of $S$, we have \begin{align} \Pr\_{x \sim D}\[x \in S\] - \Pr\_{x \sim U}\[x \in S\] &= \sum\_{z \in S} \Pr\_{Z \sim D}\[Z = z\] - \sum\_{z \in S} \Pr\_{Z \sim U}\[Z = z\] \\ &= \sum\_{z \in S} \bigl| \Pr\_{Z \sim D}\[Z=z\] - \Pr\_{Z \sim U}\[Z=z\] \bigr|. \end{align} Similarly, we have $$ \Pr\_{x \sim U}\[x \notin S\] - \Pr\_{x \sim D}\[x \notin S\] = \sum\_{z \notin S} \bigl| \Pr\_{Z \sim D}\[Z=z\] - \Pr\_{Z \sim U}\[Z=z\] \bigr|. $$ It follows that \begin{align} \mathrm{Distance}(D,U) &= \sum\_{z \in S} \bigl| \Pr\_{Z \sim D}\[Z=z\] - \Pr\_{Z \sim U}\[Z=z\] \bigr| + \sum\_{z \notin S} \bigl| \Pr\_{Z \sim D}\[Z=z\] - \Pr\_{Z \sim U}\[Z=z\] \bigr| \\ &= \Pr\_{x \sim D}\[x \in S\] - \Pr\_{x \sim U}\[x \in S\] + \Pr\_{x \sim U}\[x \notin S\] - \Pr\_{x \sim D}\[x \notin S\] \\ &= 2\bigl(\Pr\_{x \sim D} \[A(x)\] - \Pr\_{x \sim U}\[A(x)\]\bigr) \\ &= 2d\_{TV}(D,U). \end{align}
> 1 votes

---
Tags: algorithms, probability-theory
---


# Question
Title: Is there an algorithm to find all connected sub-graphs of size K?
I was just wondering if there is an efficient algorithm that given a undirected graph `G`, finds all the sub-graphs whose size is `k` (or less)?

I searched around, and only found problems about finding the connected components. But I am interested in the smaller and more local connected sub-graphs.

To clarify, the graph of interest (road networks) has `n` vertices, and has a relatively low degree (`4` to `10`). I am interested in finding/enumerating all connected sub-graphs with size `k`(in terms of nodes), e.g. by listing the vertices of each. `k` is relatively small.

# Answer
There can be exponentially many such subgraphs, so any such algorithm will necessarily be slow.

To enumerate all of them, choose any number $i$ in the range $\[1,k\]$, choose any subset $S$ of $i$ of the vertices, discard all edges that have an endpoint not in $S$, choose any subset of the remaining edges, then check if the graph with vertex set $S$ and the chosen edge subset is connected; if not, discard the graph; if yes, output the subgraph. If you implement each "choose" with an for-loop that enumerates over all possibilities, this will enumerate over all graphs. There are standard ways to enumerate all subsets of a set.

You can make it a bit more efficient by choosing the edges in a particular order:

* for each $i \in \[1,k\]$:
    + for each subset $S$ of exactly $i$ of the vertices: (\*)
        - let $E\_1 = \\{(u,v) \in E : u \in S, v \in S\\}$ and $T := \emptyset$.
        - for each $v \in S$:
            * let $E\_2 = \\{(u,v) \in E : u \in S\\}$.
            * if $E\_2$ is empty and $T$ has no edge incident on $V$, go to the next iteration of the loop marked (\*).
            * if $E\_2$ is non-empty:
                + choose a non-empty subset $E\_3$ of $E\_2$.
                + set $T := T \cup E\_3$ and $E\_1 := E\_1 \setminus E\_2$.
        - if the graph $(S,T)$ with vertex set $S$ and edge set $T$ is connected, output it

I don't know how to guarantee polynomial delay, but this might be fine for your particular application.
> 3 votes

# Answer
If you are still interested, this paper proposes an algorithm of complexity $\mathcal{O}(n(d-1)^{k})$, with $d$ the max degree of your graph. Good luck in understanding, these guys are crazy
> 3 votes

---
Tags: graphs
---


title: What is a task type?

text:
# Question
Title: What is a task type?
I have an unlabeled dataset: 500 X-rays of seeds in husk. In each image there are different number of seeds, for instance, from $10$ to $50$.

A seed has some features. The main features are a seeds' square and a husks' square in pixels. I need to calculate the these features ratio.

I am looking for an objects recognize algorithm. My problem is: I don't know what is a task type.

The dataset is unlabeled and I can use unsupervised learning and identify a similarity in groups (clustering task). Or I should to label data and use supervised learning and identify a real values (regression task)?

*Question* What is a task type?

**Literature**

1. The Plant Pathology 2020 challenge dataset to classify foliar disease of apples
2. Exploring Survival on the Titanic

# Answer
This is likely to be a challenging task, and if you're not familiar with image classification, I suspect it may be beyond what you can reasonably do right now.

I would suggest you investigate classical image processing techniques. You might try applying morphological operators, such as closing (dilation followed by erosion) or opening followed by thresholding. You may need to experiment. If you search on Stack Overflow and Signal Processing sites, you'll find many examples.

See also blob detection and watershed segmentation.
> 2 votes

---
Tags: machine-learning, reference-request, image-processing
---


title: Integer programming with indicators

text:
# Question
Title: Integer programming with indicators
I have the following question, and I need to write it as an integer programming problem:

A manager of a company wants to by presents to his 100 employers. He can buy the presents from two different suppliers:

1. Every present costs 110\\$. For any present above 500, the manager would have to pay 5\\$ extra for insurance (for example, for 502 presents, there will be 10\\$ extra for insurance).
2. Every present costs 120$. For any present above 300, there is a discount of 30% (each present above 300 costs 84\\$).

I need to find how many presents he should buy from each supplier, in order to spend the minimal amount of money.

I defined:

$x\_1, x\_2$ \- The number of presents to buy from each supplier.

$z\_1$ \- Indicator which represents whether or not $x\_1 \ge501$

$z\_2$ \- Indicator which represents whether or not $x\_2 \ge301$

I know how to represents the indicators using linear functions, but I don't know how to find a linear objective function.

My best suggestion is:

$$ 110x\_1+5z\_1(x\_1-500)+120x\_2-36z\_2(x\_2-300) $$

However, this is not a linear function, because I multiply the decision variables.

How can I turn it into a linear function?

# Answer
> 1 votes
You can multiply variables in ILP with https://blog.adamfurmanek.pl/2015/08/29/ilp-part-2/ and https://blog.adamfurmanek.pl/2015/09/26/ilp-part-6/ and https://blog.adamfurmanek.pl/2015/10/03/ilp-part-7/

You don't need multiplication, though. Your objective function is effectively:

$ \min(500, x\_1) \cdot 110 + \max(x\_1 - 500, 0) \cdot 115 + \min(300, x\_2) \cdot 120 + \max(x\_2 - 300, 0) \cdot 84 $

You can represent max/min functions as comparison + absolute value, as explained in https://blog.adamfurmanek.pl/2015/09/19/ilp-part-5/

---
Tags: linear-programming, integer-programming
---


# Question
Title: Is there a simple argument why graph isomorphism is not NP-complete?
I need to provide one simple evidence that graph isomorphism (GI) is not NP-complete.

I saw a number of papers on google scholar and answers on StackExchange. However, I have very limited knowledge of graph isomorphism, and I would like to just provide one simple evidence which I both understand and can explain clearly.

---

Below is what I can think of. Is this a valid argument?

Currently, we can solve GI in Quasipolynomial Time. If GI is NP-complete, then we should be able to solve other NP-complete problems in Quasipolynomial Time as well. However, right now, we are unable to solve any NP-complete problem in Quasipolynomial Time. Therefore, GI cannot be in np-complete.

# Answer
The type of argument you are looking for is as follows:

> If graph isomorphism were NP-complete, then some widely believed complexity assumption fails.

There are at least two such arguments:

1. Schöning showed that if graph isomorphism is NP-complete then the polynomial hierarchy collapses to the second level (equivalently, $\Sigma\_2^P = \Pi\_2^P$).
2. Babai's quasipolynomial time algorithm implies that if graph isomorphism is NP-complete then the exponential time hypothesis fails.

Whether such arguments are "valid" or not is a sociological question, not a mathematical one.
> 15 votes

---
Tags: complexity-theory, graphs, np-complete
---


# Question
Title: DFA to accept a String containing even number of both A and B, but rejects empty String
I want to draw a DFA to accept a String containing even number of both A and B, but rejects the empty String(ε)

I have already drawn the DFA which accepts the above language, without rejecting the empty string.

# Answer
> 1 votes
I'm going to assume that your DFA has 4 states with the start state also being the singular accepting state.

Add a new (non-accepting) state where the outgoing transitions are a copy from your existing accepting start state. Make that new state the start state.

If my assumption about your existing DFA is correct then this way you should not be able to get into an accepting state with the empty string.

# Answer
> 0 votes
Your DFA probably has 4 states; $a\_e b\_e , a\_o b\_o , a\_e b\_o , a\_o b\_e$ ,

$a\_o$means odd number of $a$s , $b\_e$ even number of $b$s and so on

replace the $a\_e b\_e$ state by 2 states , a state for empty string and one for $a\_e b\_e$ then try again

Here is the DFA

---
Tags: automata, finite-automata
---


# Question
Title: Definitions of Computer Architecture and Computer Organization seems confusing
So there was this question in one of my class tests. It may seem very simple and straight-forward, but I am unable to catch up with its meaning or explanation. I have referred my textbook of **COMPUTER ORGANIZATION AND ARCHITECTURE** by *William Stallings*. But that has just got me more confusing.

The definitions according to my textbook are:

> **Computer architecture** refers to those attributes of a system visible to a programmer or, put another way, those attributes that have a direct impact on the logical execution of a program. **Computer organization** refers to the operational units and their interconnections that realize the architectural specifications.

I even referred to some websites which students at our university, if not the whole country, mainly depend on, but that didn't me help either.

The question is to mark which of the following is/are true:

1. Computer Organization refers to the design of functional blocks in a computer system.
2. Computer Organization is responsible to integrate functional blocks in a computer system.
3. Computer Architecture refers to the design of components and functional blocks in a computer system.
4. Computer Architecture concerns with the integration of functional blocks to build a computer system.

My marking was 2nd and 3rd option. My explanation about the same was: architecture would include designing of a structure while organization would be, well, the very English definition of how things are organized in a particular manner. I know this may be wrong, hence I am asking you for an explanation regarding which options are correct. Any help will be appreciated. Thank you.

# Answer
It seems that the important difference between the terms as used here is that *computer architecture* is about useful things the system can do for its user (the programmer), and that *computer organization* is about how to build and connect "units" in order to create such a system.

I will first note that your argument here is not correct: while I agree *architecture* is about organizing and building things, *computer architecture* is, according to your book, **not** about building things. Note that "computer architecture" and "architecture" are not the same. **A technical term with a definition is what the definition says it is, no more, no less.**1 Any relation the name may have with the English language is irrelevant.2

For example, if I define a particular combination of points and lines to be a *caterpillar*, then a caterpillar is exactly that and any complaint that a combination of points and lines cannot turn into a butterfly is irrelevant.3

According to what the definitions *computer architecture* and *computer organization* say, it seems to me that (assuming "integrating functional blocks" and "interconnecting operational units" are interchangeable) Statements 1 and 2 are true, while 3 and 4 are false. I encourage you to work out the details on your own, using the definitions of the terms involved.

---

1: Or, as Lewis Carroll wrote:

> "When I use a word," Humpty Dumpty said, in rather a scornful tone, "it means just what I choose it to mean—neither more nor less."

 2: That said, it certainly is *annoying* when the name of a term seems to outright contradict its definition (cf. the lines in the poem preceding the quoted line of Mr. Dumpty), and I think the particular names chosen for the definitions in your book are not that good, to be honest. Naming concepts is an art in itself and not many good scientists are also good artists, or even want to be. So many concepts have unfortunate names, but if you read a book that uses those names, you will have to live with it.
3: No, I did not make this up. Someone else beat me to it.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Graph coloring with fixed-size color classes
I'm interested in coloring a graph, but with slightly different objectives than the standard problem. It seems like the focus of most graph-coloring algorithms (DSATUR etc) is to **minimize** the number of color classes used.

My goal, in contrast, is to **maximize** *the number of color classes of fixed size N*.

As a concrete example, say I have a graph with `100` nodes, and I'd like to color the graph with color classes of size `N = 30`. With an optimal algorithm and the right graph, I could find 3 such groups that color 90 total nodes, with 10 nodes left over. A lesser algorithm might only produce 2 such groups, with 40 nodes left over that cannot be colored with a size-30 color class.

I figure I can solve this problem with a Greedy Algorithm, but it won't be optimal. Or I could model this in a constraint solver, but it might not employ some clever graph-specific tricks that could come in handy.

Does this specific problem have a name? Or an established algorithm to solve it? Thank you!

EDIT:

It was rightfully pointed out that my question is ambiguous! I can explain much more thoroughly, my apologies for the confusion.

First, let me define the **size of a color class**. I've seen this terminology elsewhere but might be using it incorrectly. The size of a color class is the number of nodes assigned to that color. I will denote this: `size(C_i) = <number of nodes colored C_i>`.

Now, to define a **fixed size color class**. This is a color class with size `N`. To use the example above, I'm interested in colorings with colors such that `size(C_i) = 30`.

As far as the optimization objective: I want to color a graph to maximize the number of size-30 color classes. If you'll permit me some Python pseudocode:

```
n_size_30_colors = len([c for c in colors if size(c) == 30])
maximize(n_size_30_colors)

```

To complete the example, take these two possible colorings of a graph with 100 nodes. Each number represents the number of nodes colored by that color:

```
Coloring 1: {55, 25, 20} (n_size_30_colors = 0)
Coloring 2: {30, 30, 20, 20} (n_size_30_colors = 2)
Coloring 3: {30, 30, 30, 10} (n_size_30_colors = 3)

```

Even though Coloring 1 uses fewer colors, Coloring 3 is optimal because it returns the *most size-30 color classes*. The size-55 color class in Coloring 1 is "wasteful" in that those 25 extra nodes are not useful; an optimal solution for this problem would distribute those nodes to other color classes, hopefully yielding more size-30 colors.

I hope this clarifies things somewhat, and thanks again!

# Answer
This problem is NP-hard: it is at least as hard as independent set. In particular, if you want to know whether there exists an independent set of size $N$, ask for a coloring with as many colors of size $N$; if you find any coloring where a single color occurs $N$ times, you know there's an independent set of size $N$. So, you should not expect any efficient algorithm for this problem that works on all problem instances.

One plausible approach is to use a ILP solver. You can define zero-or-one variables $x\_{v,c}$, where $x\_{v,c}=1$ means that vertex $v$ is assigned color $c$. Then it is easy to express the requirement that a color $c$ be assigned to exactly $N$ vertices: we require $\sum\_{v \in V} x\_{v,c} = N$. The constraint that two adjacent vertices $v,w$ be assigned different colors can be expressed by $x\_{v,c} + x\_{w,c} \le 1$ for all $c$, and that each vertex $v$ receive a color by $\sum\_c x\_{v,c} = 1$. Without loss of generality, to test whether it is possible to have $k$ colors be assigned to $N$ vertices, you can constrain the first $k$ colors to have $N$ vertices and put no constraints on the remaining colors. Then, use binary search on $k$ to find the largest $k$ for which a solution exists.

Another plausible approach is to use a SAT solver. You could define variables $x\_{v,c}$, where if $x\_{v,c}$ is true then vertex $v$ is assigned color $c$, and express your constraints in SAT. You can require that color $c$ be assigned to exactly $N$ vertices, by requiring that $N$ out of the variables $x\_{\cdot,c}$ are set to true (see Encoding 1-out-of-n constraint for SAT solvers and links for methods). Otherwise, this is similar to using an ILP solver.

These might work if $N$ is small enough and the graph is small enough, but eventually will run into exponential behavior once the problem gets large enough.
> 4 votes

---
Tags: graphs, optimization, colorings, constraint-programming
---


# Question
Title: If f(n) = O(g(n)), then is log(f(n)) = O(log(g(n)))?
I guess this is true, because log is a strictly increasing function, but how do I prove it formally?

I tried something like:

Let $f(n)$ and $g(n)$ be monotonically increasing functions, $c \in \mathbb{R}$ and $n\_0 \in \mathbb{N}$, such that $0 \leq f(n) \leq c g(n)$, for all $n \geq n\_0$. We must find $c'$ and $n\_0'$ such that $$\log(f(n)) \in \\{h(n) \mid 0 \leq h(n) \leq c' \log(g(n)), \forall n \geq n\_0'\\}\\,.$$

I got as far as $$f(n) \leq c g(n) \implies \log(f(n)) \leq \log(c g(n)) = \log(c) + \log(g(n))\\,.$$

Then I got stuck.

Thanks in advance!

# Answer
> 2 votes
You need to find a number $n'\_0,c'$ such that

$$\log(c) + \log(g(n)) \le c' \log(g(n)) \text{ for all $n \ge n'\_0$,}$$

and such that $n'\_0 \ge n\_0$.

So, see what you can find. Note that it's ok for $n'\_0,c'$ to depend on $c$ and on $g(\cdot)$.

Hint: If you can find $n'\_0,c'$ such that $\log(c) \le \log(g(n'\_0))$, does anything good happen? Can you find such a $n'\_0,c'$?

# Answer
> 1 votes
If we assume all functions are nonnegative and strictly increasing, then I think this relationship is true, however if we take the following cases: Let $f(n) = 2$ and $g(n) = 1$ then clearly ()=(()), however, (())=1,(())=0, therefore, (())≠((())).

# Answer
> 0 votes
It is of course wrong. But why? Assume you have two functions 1 ≤ f(n) ≤ 2 for all n, and 1 ≤ g(n) ≤ 2 for all n. So f(n) = O (g(n)) with a constant c, 0.5 ≤ c ≤ 2.

But the logarithm of f(n), g(n) is between 0 and log 2. We can't say anything about the relation between log(f(n)) and log(g(n)) if all we know that both functions are between 0 and log 2. For example let g(n) = 1 + 1/n and f(n) = 2.

But the simplest counterexample is **g(n) = 1 for all n, and f(n) = c for some constant c \> 1**, giving log (f(n)) = some constant \> 0, and log(g(n)) = 0.

---
Tags: asymptotics
---


# Question
Title: Cube 3x3: Using just face rotations, transform the cube from configuration A to B
I'm looking for some tips on how to best implement the algorithm to accomplish the following:

* Imagine a 3×3 cube with a rubik's cube mechanism, i.e. you can freely rotate any of the 6 faces.
* You don't care about colors.
* Instead you index the component 26 cubes A–Z and ignore the middle.

Illustration image (component cubes): https://paste.pics/AOYUS

Now, I would like to generate a list of face rotations that would get me from this configuration to some other configuration. E. g. this: https://paste.pics/AOYWM

Note: I don't care which component cubes end up in positions labeled as `*`

Ideally the algorithm produces the shortest list of transformations necessary, but it's not a firm condition. Any suggestions welcome, thanks!

# Answer
> 2 votes
If the number of "don't care" colours is large, as it is in this example, you probably can't do much better than A\* search.

One simple heuristic function is the minimum number of moves required to move the currently-least-correct piece to its correct position. Since you're willing to tolerate some non-optimality, summing over all pieces that are not in their correct locations will probably do quite well in practice.

# Answer
> 0 votes
Answering this will be similar in difficulty to answering question's about Rubik's cube. The only difference is that in Rubik's cube some stones can come in two or three different orientations, which you want to ignore.

Optimal solution will be slightly shorter on average than optimal solution for Rubik's cube. Finding an optimal solution will be slightly easier than finding the optional solution for Rubik's cube, since there are probably no clever tricks that would allow you to find the optimal solution for Rubik's cube faster.

---
Tags: algorithms
---


# Question
Title: Is decidability closed under the mapping f where f(a)=f(b)=0 and f(c)=1?
Consider the function $f$ that maps strings over $\\{a, b, c\\}$ to strings over $\\{0, 1\\}$ by replacing each $a$ by 0, each $b$ by 0, and each $c$ by 1. For example $f(cabbc) = 10001$. The function $f$ extends naturally to languages: if $L$ is a language over $\\{a, b, c\\}$, then $f(L)$ is the language over $\\{0, 1\\}$ defined as $\\{f(w) \mid w\text{ is in }L\\}$.

Prove that if a language $L$ is decidable, then so is $f(L)$.

I am thinking that since $L$ is decidable it must be regular so there exists a DFA for $L$. $f(L)$ is closed -- dk how to prove though. Then $f(L)$ is also regular. Therefore is also decidable.

# Answer
Let $f$ be any computable mapping such that $|f(x)| \geq c|x|$ for some $c \> 0$. For every language $L$, if $L$ is computable then so is $f(L)$.

To see this, let us be given an input $y$. We go over all strings $x$ of length at most $|y|/c$. For each of them, we check whether $x \in L$ and $f(x) = y$. If we found such a string $x$, then $y$ is in the language, otherwise it isn't.
> 1 votes

# Answer
Ok , if L is decidable , then some TM machine decides L

Let M be a TM that decides L

Now we construct a TM N that decides f(L) :

N on input w : "

Generate all possible mapped (original) strings x from w by :

1. Replacing all 1s in w by c
2. Replacing all 0s in w by all possible combinations of as & bs

Run M on every x if M accepts any x accept , else reject "

So for ex , w =100 , N generates all possible mapped strings , caa , cab , cba , cbb , if M accepts any of these , then there is a string x , such that f(x) = w and x is in L , if none of them is accepted then we reject
> 0 votes

---
Tags: formal-languages, turing-machines, regular-languages, undecidability
---


# Question
Title: Sort an array where $0\leq a_n\leq n^2$ and $a_n\in\mathbb{N}$
sort an array where $0\leq a\_n\leq n$
sort an array where $0\leq a\_n\leq n^2$(hint represent every element in base $n$)
All the elements are integers
for the first 1 I used counting sort and for the second one I thought maybe after changing to base $n$ using raddix? ONe more thing,i've been asked to prove correctness for this first 1 but I've never see how to do this.
Any hints?

# Answer
You can make a list of length $n^k$ which $k$ is $1$ for the first case and $2$ for the second one.

So you have an array and you can put each element in the relevant position. This idea may waste space but it's fast.

Time complexity of this algorithm is $O(n)$.

Space Complexity is $O(n^k)$.
> 1 votes

---
Tags: algorithms, sorting
---


# Question
Title: Approximating longest path on graphs with average degree n/2
I have a graph with average degree $n/2$. How I can find an approximation algorithm for the longest path problem with factor $1/4$?

# Answer
> 0 votes
Here is something to get you started.

Suppose that your graph were $n/2$-regular, and consider the following algorithm. Start at an arbitrary vertex $v\_1$. Choose one of its $n/2$ neighbors $v\_2$. Choose one of $v\_2$'s $n/2$ neighbors $v\_3 \neq v\_1$. And so on. The process will continue for at least $n/2+1$ steps. Since every path has length at most $n$, this gives a $1/2$ approximation. In fact, this would work even if the *minimal* degree were at least $n/2$.

---
Tags: approximation
---


# Question
Title: If $f(n) = O(g(n))$ then $\log\lfloor f(n) \rfloor = O(\log \lfloor g(n) \rfloor)$?
I need to prove that $\log\lfloor f(n)\rfloor = O(\log\lfloor g(n) \rfloor)$ if $f(n) =O(g(n))$.

I know that if $f(n) = O(g(n))$ then $\log f(n) =O(\log g(n))$, but I can't prove the current statement because it involves the floor function.

# Answer
> 1 votes
Let's attempt to prove your original statement, that if $f(n) = O(g(n))$ then $\log f(n) = O(\log g(n))$.

According to the definition, there exist $C,N\>0$ such that if $n \geq N$ then $f(n) \leq Cg(n)$. Taking the logarithm of both sides, if $n \geq N$ then $$ \log f(n) \leq \log C + \log g(n). $$ Is this enough to imply that $\log f(n)= O(\log g(n))$? Not in general. For example, $2 = O(1)$ but $\log 2 \neq O(\log 1)$. However, it suffices to assume that $g(n) \geq 2$ for all $n \geq N$, since this implies that $$ \log f(n) \leq \log C + \log g(n) \leq (\log C + 1) \log g(n), $$ using $\log g(n) \geq 1$.

Now back to your case. Since $\log \lfloor f(n) \rfloor \leq \log f(n)$, it suffices to show that $\log f(n) = O(\log \lfloor g(n) \rfloor)$. For this, it suffices to show that $\log g(n) = O(\log \lfloor g(n) \rfloor)$. Indeed, recall that by assumption, $g(n) \geq 2$ for all $n \geq N$. We will show that if $x \geq 2$ then $\log x \leq \frac{\log 3}{\log 2} \log \lfloor x \rfloor$. Therefore $\log g(n) = O(\log \lfloor g(n)\rfloor)$.

It remains to show that $\log x \leq \frac{\log 3}{\log 2} \log \lfloor x \rfloor$. Let $\rho(x) = \frac{\log x}{\log \lfloor x \rfloor}$. Our goal is to show that $\rho(x) \leq \frac{\log 3}{\log 2}$ for all $x \geq 2$. Fixing $\lfloor x \rfloor = m$, it is clear that $\rho(x) \leq \frac{\log (m+1)}{\log m}$, hence it suffices to show that $\frac{\log(m+1)}{\log m} \leq \frac{\log 3}{\log 2}$ for all integer $m \geq 2$. This can be shown in various ways. For example, the function $\frac{\log(x+1)}{\log x}$ is decreasing for $x \geq 2$ by calculus: its derivate is $$ \frac{x\log x - (x+1)\log(x+1)}{x(x+1)\log^2 x}, $$ which is clearly negative for $x \geq 1$ (since $x\log x$ is increasing – its derivative is $\log x + 1$).

---
Tags: algorithms, time-complexity
---


# Question
Title: Check if a linear function or an affine function can be a pseudo random function
Let $G = \\{0, \cdots , p-1 \\}$ be a field. Let $K = G^{m \times n}$ and $F:K \times G^n \to G^m$ be a family of functions.

For $A \in G^{m \times n}$ and $x \in G^n$ we have $F(A,x) = Ax$.

I need to check if $F$ is a secure pseudo random function.

We say that PRF $H: K \times X \to Y$ is $(T, \epsilon)$-secure if for every algorithm $B: X \to \\{0,1\\}$ of size $T$ it follows: $$|P(B^{H\_k()} = 1) - (B^{R()} = 1)| \le \epsilon$$ where $H\_k(x) = H(k,x)$, $R:X \to Y$ is a random function, and $B^{S()}$ means $B$ has oracle access to the function $S$.

Now, back to the question, I tried to describe the following adversary B:

on input $x \in G^m$ and access to oracle $Z()$, $B$ will take $n$ base elements of $G^m$ and run $Z()$ on them. Then, $B$ will check if $ x \in span\\{Z(e\_1), \cdots , Z(e\_n) \\}$ and return 1 if it is.

This way I get that $P(B^{H\_k()} = 1) = 1$ and if $ m \> n$ then $P(B^{R()} = 1) \le \frac{1}{p^{m-n}}$, which proves that $H$ is not secure.

The only problem is when $n \ge m$, since I am not sure how to get a good bound on $P(B^{R()} = 1)$ in this case.

Help would be very appreciated!

There is also the same question but with $K = G^{m \times n} \times G^m$ and $F:K \times G^n \to G^m$, $F((A,b), x) = Ax+b$.

# Answer
Intuitively, pseudorandom functions are functions that *look* random. A linear function $f$ satisfies $$ f(x+y) = f(x)+f(y) $$ for *all* $x,y$, which is highly unlikely for a random function. Similarly, an affine function $f$ satisfies $$ f(x+y) - f(x+z) = f(y) - f(z) $$ for all $x,y,z$, which is highly unlikely for a random function.
> 2 votes

---
Tags: algorithms, reductions, cryptography, pseudo-random-generators
---


# Question
Title: If A is not in NP, and A reduces to B, does this mean B is not in NP?
I know it is true that if A is not in P, and A reduces B, then B is not in P.

But is it true for NP as well?

If A is not in NP, and A reduces to B, does this mean B is not in NP?

Why or why not?

Thanks!

# Answer
> 1 votes
I'm assuming that both $A$ and $B$ are decision problems and that we are talking bout Karp reductions.

Suppose towards a contradiction that $A \not\in NP$, $A \le\_p B$, and $B \in NP$. Then, a non-deterministic polynomial-time Turing machine that decides $A$ would be the following:

* Use the Karp reduction $f$ from $A$ to $B$ to transform an instance $x$ of $A$ into an instance $f(x)$ of $B$;
* Simulate a non-deterministic polynomial-time Turing machine $T$ that decides $B$ on input $f(x)$ ($T$ exists since $B \in NP$);
* If $T(x)$ accepts, accept. If $T(x)$ rejects, reject.

This is a contradiction.

---
Tags: complexity-theory, np-complete, reductions, np, polynomial-time-reductions
---


title: Cardinality of formal languages

text:
# Question
Title: Cardinality of formal languages
Given the theorem:

Let $\Sigma$ be an alphabet. The set $\mathcal{P} \left( \Sigma^{\star} \right) $ is uncountable. In other words, there are uncountably infinite languages over any alphabet.

Can someone explain to me how does it hold for $| \Sigma | = 1$ ?

# Answer
The thing you need to remember is that even if Σ has only one symbol , Σ\* still has infinite strings over that one symbol , even if Σ = {a} , Σ\* = {ε,a,aa,aaa,....} , (a^n , n≥ 0) , Σ\* has infinite strings just like with any other alphabet , and so we can form infinite languages over an alphabet with a single symbol just like other alphabet , if now you are convinced that Σ\* is infinite even if |Σ|=1 just like any other alphabet , then just as you believe that P(Σ\*) for |Σ| \>1 is uncountably infinite , hopefully you can see now that P(Σ\*) for |Σ| = 1 is also uncountably infinite , since in both cases it is P(some infinite language) , which in both cases is uncountably infinite
> 1 votes

---
Tags: automata
---


title: Does $\{0, 1\}^*\in \text{co-NP}$?

text:
# Question
Title: Does $\{0, 1\}^*\in \text{co-NP}$?
There is trivially $\emptyset\in\text{NP}$. From the definition of $\text{co-NP} = \\{L : \overline{L} \in \text{NP}\\}$ where $\overline{L} = \\{0, 1\\}^\*-L$ follows $\\{0, 1\\}^\*\in \text{co-NP}$. Is this true? If so, it is also true that $\\{0,1\\}^\*\in \text{NP}$?

# Answer
> 0 votes
Both $\emptyset$ and $\\{0,1\\}^\*$ are in $P$, and therefore they are also in $NP \supseteq P$ and $co-NP \supseteq P$.

---
Tags: complexity-theory
---


title: Averaging a list of variances

text:
# Question
Title: Averaging a list of variances
In a setting where I have n clients each owns a subset of the dataset, each computes the mean and variance on his data and send them to the server. The server would average all means and variances. For mean, I simply do the averaging by: $\mu = \frac{\mu\_1+\mu\_2+.....+\mu\_n}{n}$

However, for the variance, I can't figure out to average n variances. For only two I found this answer here

$\sigma^2 = \frac{1}{2}(\sigma^2\_1 + \sigma^2\_2) + (\frac{\mu\_1-\mu\_2}{2})^2$

But how about n variances? thank you

# Answer
Let's assume you have $n$ datasets, $x\_k$ is the $k$th dataset. It's length we denote by $l\_k$, its elements are $$x\_k =\big\\{x\_k(1), x\_k(2), \dots, x\_k(l\_k)\big\\},$$

and its mean and variance are respectively \begin{align} \mu\_k &= \frac{1}{l\_k}\sum\_{i=1}^{l\_k} x\_k(i),\\ \sigma\_k^2 &= \frac{1}{l\_k}\sum\_{i=1}^{l\_k} x\_k(i)^2 - \mu\_k^2. \end{align}

Then, noting that $l\_k\mu\_k = \sum\_{i=1}^{l\_k} x\_k(i)$:

\begin{align} \mu &= \frac{1}{\sum\_{k=1}^nl\_k}\sum\_{k=1}^n\sum\_{i=1}^{l\_k} x\_k(i)\\ \mu &= \frac{1}{\sum\_{k=1}^nl\_k}\sum\_{k=1}^nl\_k\mu\_k \end{align}

and in similar fashion

\begin{align} \sigma^2 &= \frac{1}{\sum\_{k=1}^nl\_k}\sum\_{k=1}^n\sum\_{i=1}^{l\_k} x\_k(i)^2 - \mu^2\\ \sigma^2 &= \frac{1}{\sum\_{k=1}^nl\_k}\sum\_{k=1}^nl\_k\left(\sigma^2\_k + \mu\_k^2\right) - \mu^2 \end{align}

When $l\_k = N$ for all $k$ the above simplifies:

\begin{align} \mu &= \frac{1}{n}\sum\_{k=1}^n\mu\_k\\ \sigma^2 &= \frac{1}{n}\sum\_{k=1}^n\left(\sigma^2\_k + \mu\_k^2\right) - \mu^2 \end{align}

however when the datasets have different sizes the above does not simplify, and you need to take that into account.
> 1 votes

---
Tags: distributed-systems, statistics
---


# Question
Title: Explanation of pseudocode and time complexity analysis
I am trying to work my way through some computer science training and I am not able to properly understand the following pseudo code:

```
COUNTING-1 (n)             cost          times

1  for r=1 to n            c1               n+1

2    for c=1 to n          c2               n(n+1)

3      sum = sum+1         c3               n2

4  return sum              c4               1

T(n)=c2*n(n+1)+c3*n2 +c1*(n+1)+c4=an2+bn+c

```

Could someone explain why the outer loop is n+1, and not just n?

Also what are the constants c, a and b? I don't understand why they need to factor into the explanation equation as it isnt clear what their value will.

Apologies if these are really simple questions. If there are some useful things I should read I would appreciate a pointer in the right direction.

\*Edit: I think looking at it again the c constant is the cost of the operation which for each is constant time, so 1. Is the cost of a single operation ALWAYS 1? If it is (which it appears to be in this RAM model) what is the point in over complicating the formula underneath with those values?

Why not just `T(n)=n(n+1) + n2 + (n+1)`

# Answer
First question: some book, for example well known CLRS 3ed. p25-26, counts, that in for loop test in loop header is executed one times more, then loop body. Accordingly you see $n^2=n(n+1)-n$ in 3-d line.

Second question: simplify $T(n)$ and write it as polynomial from $n$. Then you obtain representations for $a,b,c$: $$T(n)=c\_2n(n+1)+c\_3n^2 +c\_1(n+1)+c\_4=\\\=(c\_2+c\_3)n^2+(c\_2+c\_1)n+(c\_1+c\_4)=\\\=an^2+bn+c$$

So $a=(c\_2+c\_3)$, $b=c\_2+c\_1$ and $c=c\_1+c\_4$. If we speak about asymptotic estimation, then $T(n)=O(n^2)$.
> 1 votes

---
Tags: time-complexity, pseudocode
---


title: {a^n b^n c^n | n>=1} - PDA

text:
# Question
Title: {a^n b^n c^n | n>=1} - PDA
I just started learning context free grammar and Pushdown Automata, I tried implementing this particular language via a PDA, despite being told this language is context sensitive.

How I attempted it is by popping every 2 'a' for 1 'b' and then popping 1 'b' for 2 'c'. I don't understand why is this wrong.

I feel I am be overlooking something really minuscule.

# Answer
Yes you missed something ,

Lets review how your PDA works :

1. we push a for each a we read
2. we pop 2as for each b we read , then when stack is empty we push b for each b we read
3. we pop b for each 2cs we read

Your PDA will accept strings of form a2nbn+mc2m

for ex , a4b5c6 , here n = 2 , m = 3

You push 4 as , then for each 2as you pop b , you pop 2bs , and 3 bs remain which are pushed to stack !!!

Hopefully you can see the problem here , no one told you that you are half way bs when you finished popping as

You continue , for each of the 6 cs you pop a b then you accept

You expect the string in the form a2nbn+mc2m , you compare a2nbn then bmc2m , of course if n = m you are correct , but there is no way to ensure this
> 0 votes

---
Tags: automata, context-free, pushdown-automata, context-sensitive
---


# Question
Title: Human computing power: Can humans decide the halting problem on Turing Machines?
We know the halting problem (on Turing Machines) is undecidable for Turing Machines. Is there some research into how well the human mind can deal with this problem, possibly *aided* by Turing Machines or general purpose computers?

*Note*: Obviously, in the strictest sense, you can always say no, because there are Turing Machines so large they couldn't even be read in the life span of a single human. But this is a nonsensical restriction that doesn't contribute to the actual question. So to make things even, we'd have to assume humans with an arbitrary life span.

So we could ask: Given a Turing Machine T represented in any suitable fashion, an arbitrarily long-lived human H and an arbitrary amount of buffer (i.e. paper + pens), can H decide whether T halts on the empty word?

---

*Corollary: If the answer is yes, wouldn't this also settle if any computer has a chance of passing the turing-test?*

# Answer
It is very hard to define a human mind with a such mathematical rigor as it is possible to define a Turing machine. We still do not have a working model of a mouse brain however we have the hardware capable of simulating it. A mouse has around 4 million neurons in the cerebral cortex. A human being has 80-120 billion neurons (19-23 billion neocortical). Thus, you can imagine how much more research will need to be conducted in order to get a working model of a human mind.

You could argue that we only need to do top-down approach and do not need to understand individual workings of every neuron. In that case you might study some non-monotonic logic, abductive reasoning, decision theory, etc. When the new theories come, more exceptions and paradoxes occur. And it seems we are nowhere close to a working model of a human mind.

After taking propositional and then predicate calculus I asked my logic professor:
"Is there any logic that can define the whole set of human language?"
He said:
"How would you define the following?
To see a World in a grain of sand
And a Heaven in a wild flower,
Hold Infinity in the palm of your hand
And Eternity in an hour.
If you can do it, you will become famous."

There have been debates that a human mind might be equivalent to a Turing machine. However, a more interesting result would be for a human mind not to be Turing-equivalent, that it would give a rise to a definition of an algorithm that is not possibly computable by a Turing machine. Then the Church's thesis would not hold and there could possibly be a general algorithm that could solve a halting problem.

Until we understand more, you might find some insights in a branch of philosophy. However, no answer to your question is generally accepted.

http://en.wikipedia.org/wiki/G%C3%B6del%27s\_incompleteness\_theorems#Minds\_and\_machines http://en.wikipedia.org/wiki/Mechanism\_(philosophy)#G.C3.B6delian\_arguments
> 32 votes

# Answer
I think there is no way how give a definitive answer to this question, as nobody really knows the capabilities of human mind (and I doubt anyone ever will).

But there is a view that gives one possible solution or explanation to this question:

When we're searching an oracle to solve the halting problem (or decide provability of first-order logical formulas etc.), we naturally want the oracle to be *correct*, it must not make any mistakes. But human mind *isn't consistent*, it makes mistakes. Nobody can honestly say that all statements (s)he believes are true are really true. This inconsistency can be viewed as the source of the power human mind has. Due to its inconsistency, it isn't subject of limitations that follow from the halting problem, Gödel's incompleteness theorem etc. We make mistakes, we mistakenly believe in false statements, and as our knowledge grows, we correct them (and of course find new false statements we believe in). On the other hand, we want all formalizations of the notion of algorithm or all logical calculi to be consistent, so that we can prove once and for all that they're free of such mistakes. And this makes them limited.
> 17 votes

# Answer
Just to make things clear: **The Church-Turing hypothesis has nothing to do with some dogma of a hypothetical Church of Turing.** There is nothing religious about it. On the contrary, it is just a hypothesis summarizing the best of our knowledge. There is no metaphysical Implication. The question whether humans could do better, that they could achieve more than machines, is a metaphysical question as we have strictly no handle on it, no hint whatsoever of what could differentiate a human from a machine. So this question should be migrated to metaphysics.stackexchange.com.

But let us assume that the human brain can solve the halting problem for Turing Machine. Then the computational model of Turing Machines becomes much less important, and the Church-Turing Hypothesis becomes much less relevant, as we have a more powerful model called the Human Model (to avoid the word *machine*). Of course this (arbitrarily long-lived) human model comes with its own hypothesis on computability.

But then, while the halting problem for Turing Machines is no longer critical, we now have to deal with the Human Model Halting problem. And diagonalization will show that the Human Model Halting problem is not decidable by a Human. Then what?

Now, you might object that diagonalization would not be applicable. That would mean, I guess, that associating some form of Gödel numbering with computing devices, proofs, or whatever we describe with notation would no longer be possible, though it is currently the basis of all science. In other words, we would have to deal with entities, concepts that have no written representation, that cannot have a written representation, or to say it more generally concepts without a syntactic representation, whether written, oral or otherwise.

Of course, this would be in opposition with the teaching of John whose very first sentence is: "*In the beginning was the Word, and the Word was with God, and the Word was God.*" Negating the fundamental importance of syntax, of the word, is thus a very anti-christian statement. I am of course not taking a stand on this, but since my first take on this question is that it is a metaphysical one, and since the question is not on hold, it seems natural to consider all consequences, including the metaphysical consequences.
> 10 votes

# Answer
Consider this from a different perspective.

* First-order logic is undecidable, that is, there is no decision procedure that determines whether arbitrary formulas are logically valid. (But the set of true first-order formulas is semi-decidable, that is if a formula is true, it's possible to find a proof by an algorithm.)
* Proof assistants help prove theorems in first-order (or even higher-order) logic. The proof assistant ensures that the proof is done correctly and can even help resolve some cases. However, human interaction is require to guide the proof assistant to the correct answer.

Proof assistants could be used to prove properties of individual Turing machines.
> 9 votes

# Answer
Carl Mummert's comment nailed it.

1. My understanding (correct me if I am wrong) of the Church-Turing thesis is the idea that anything that can be computed can be computed by a Turing Machine.
2. And also, if a Turing Machine could compute if another Turing Machine would halt or not on an input (halting problem), then you could also compute if another Turing Machine would **not** halt on a given input (just swap yes for no, and no for yes!) - significant because then you could feed this Turing Machine to itself - would it **not** halt on itself on the input? If yes (not halting), then no (is halting??). If no, then yes. If yes, then no. If no, then ye... hmmm.

So, 2. shows it is impossible for a Turing Machine to solve the halting problem. But I don't think there is any clear evidence to contradict 1. at this time. Every model of computation known still can solve (decide) as much as a Turing Machine can.

The burden of proof seems to be on the person coming up with a new model of computation, which has more power (that is, can decide more problems) than the classical Turing Machine.

By the way, some great lectures on this can be found here.
> 3 votes

# Answer
There isn't any evidence that the human brain is in fact anything more than a Turing machine. In fact, it seems like the entire universe can be simulated on a (sufficiently large) Turing machine.

Humans are "smart" because of smart algorithms that are cleverly written in neurons so computer scientists can't steal or efficiently implement them. However clever these algorithms are, they most likely cannot *reliably* solve the halting problem.
> 3 votes

# Answer
as with DCs answer (and to expand on it somewhat) there is a strong sense in which this question (combination of human and computer in finding special-case solutions to the halting problem) is related to the field of ATP, automated theorem proving and the closely related computer assisted proofs. also it has long been known there is a strong correspondence between programs and proofs in the Curry-Howard correspondence. also related/similar to this is proving program termination (eg via loop invariants or loop variants). in fact there is a deep sense in which *all* of mathematics is about this problem, because virtually all mathematical statements can be converted to questions about specific programs on TMs halting or not halting. see eg \[2\] for some further info & lots of further refs on ATP etc.

\[1\] is a semifamous book on the subject that examines the question in detail, relating it to the possibility artificial intelligence. briefly Penrose's idea is that true AI must be impossible because humans can come up with proofs of undecidability such as Turings halting problem or Godels incompleteness proof, whereas computers could not due to the same phenomena.

\[1\] Emperors new mind by Penrose

\[2\] adventures & commotions in ATM, vzn
> 2 votes

# Answer
**In short: NO**

there are Turing machines for wich we don (yet) know if those machines Halt (Collatz Conjecture in example).

Until we find a way to enumerate all Turing Machines for wich we don't have a Halting-proof, and until we don't find a way to proove Halt-ness of those machines we are not any better than a Turing machine (If I am correct someone already prooven that we cannot prove everything, a points toward the fact we are as limited as Turing Machines). Oh wait, we cannot enumerate all those machines because infact we have a limited memory and a limited lifespan.

However you question, is self-answering:

You are asking if human are able to "decide", but the decision itself is defined as an algorithm, so or we run an algorithm on our minds and comes to a correct conclusion (or to no conclusion at all: open problems), or we just make a guess.

Computation theory is about:

* Assume there exist a black box algorithm (Oracle) than can answer yes or no to certain questions
* You can then use it to answer unanswerable questions by building another algorithm that use it
* By doing that you ends with a contradiction

That means that as long you have any system that want a `No` or `Yes` answer, the Oracle is not compatible with that system, **so Oracles may actually exists, but we have no way to communicate their results**, because if we are able to communicate their results then we ends up with a contradiction somewhere.

Assume Quantum mechanics is made of many small oracles, then you cannot communicate their results because when you read the status of a particle, you also change the status of that particle.

*I had the answer, but I've read it..*

Infact we can proove anything if we start from fake hypotesis. So we can proove that an algorithm halt, but we can also proove that an algorithm does not halt, that can be interesting, but it is useless since a contradictory (you want a `Yes` or `No` answer) result is not what you want.
> 2 votes

# Answer
**Short Answer**

Basically no in the general case (at least, not without guessing). Though, certain subproblems are indeed solvable.

**Long Answer**

In order for this to happen, you would have to assume that a human has the ability to solve mathematical problems that a TM can't in some algorithmic way. This would imply that the Church-Turing thesis is false, even though, TMK, it has been shown to be true for every known computational method discovered so far (except maybe probabilistic/quantum computation, which no longer meets the firm criteria for 'algorithm' since it involves inexact results).

However, there are indeed solvable subsets of the halting problem, such as determining whether or not a TM will halt within a certain number of computational steps (think 'ticks') upon a given input, which would be reasonably doable for both a TM and a human.

Though, considering how poor the general populus is at performing any sort of mathematics, you might get your answer of 'no' in a much different way.

**Epilouge**

You should look up a proof of the halting problem's unsolvability. There is at least 1 exceedingly simple proof that gives an example of a machine who's halting state cannot be properly predicted given the machine itself as an input, which serves as a counterexample to the very existence of an arbitrary machine that could solve the halting problem in the general case (for TM's).
> 0 votes

# Answer
Modern supercomputer systems can certainly simulate the behavior of at least one atom. If individual atoms can be simulated then one can simulate the human mind as well by building a big enough computer system for the simulation of the individual atoms. However I think that this alone wouldn't be enough. You would also need an entropy source in order to obtain true random numbers for the simulation of the human mind. The best entropy source would probably be radioactive decay or something like that. What does this mean?

I think that the human mind is more powerful than a Turing Machine, because a TM is deterministic. You cannot simulate true randomness on a Turing Machine. (At least this is the impression, I got from the following discussion

https://cstheory.stackexchange.com/questions/1263/truly-random-number-generator-turing-computable

) However I think that a Turing Machine, attached to a true entropy source would be capable of simulating a human mind.

If one also takes the randomness of the environment into account, which interacts with a human mind (e.g. the food, we eat, how the sleep, walk, basically live our lives), then I certainly think that a TM with entropy is needed for the simulation of the human mind. Don't forget that the human mind is also constantly exposed to background radiation, which may also unpredictably interact with the molecules in our brain. But I think that even if we consider a completely "isolated" environment (Is that even possible? Because the following seems to indicate that it may not be possible: http://hps.org/publicinformation/ate/faqs/faqradbods.html ) - basically a "brain in the jar" - scenario, you would probably still get truely random processes, which would occur somethere in the human brain. I'm sure that a biologist could settle this part of the question? Also don't forget that a human is in a sense also part of his or her environment:

http://en.wikipedia.org/wiki/Human\_Microbiome\_Project

Perhaps some of these bacteria also influence the inner workings of the human brain in some way and the composition of this bacteria can change in a human's lifetime (also within certain boundaries I suppose?). The question is whether the behavior of these bacteria is random within certain boundaries. If at least one process within at least one of these organisms is truely random and also somehow indirectly affects the human brain then one would need a TM with an entropy source to simulate a human mind.

So to answer the original question:

Can a "human" (as defined in the question) solve the halting problem? Yes, if it is the halting problem for all deterministic TMs and no if it is for all TMs, attached to an entropy source.
> -1 votes

# Answer
All human thought conflates single problems into personal experience. We might satisfy ourselves that we have adequately solved a problem sufficiently to halt, but we never know for sure in the algorithmic sense a computer would acquire a solution. Be still and watch your own mind. 99.9% of the messaging going on in our neural circuitry has nothing to do with a logical representation of the world. Instead, we are dealing with "gut" feelings, sensory data and a flood of memories, associations and attitudes which vary constantly. That's why we have scientific method.
> -2 votes

---
Tags: computability, turing-machines, halting-problem, human-computing
---


title: Can a No-Knowledge Proof exist?

text:
# Question
Title: Can a No-Knowledge Proof exist?
A Knowledge Proof is a mechanism by which a 'prover' entity can show to a 'verifier' entity that it possesses some certain information without revealing what that specific information is (within some arbitrarily small tolerance of certainty).

Is it possible for a 'prover' to show to a 'verifier' that it **does not** possess some certain information (without the 'prover' being computationally limited, etc.)?

# Answer
No. An algorithm that has access to some information can always ignore it and make decisions without looking at it, and then its externally observable behavior will be indistinguishable from an algorithm that doesn't have access to that information; so no verifier can tell the two apart.

I suggest being a bit cautious: when we talk about words like "knowledge" in the context of algorithm, we are applying some human intuition and interpretation to the underlying mathematics. The precise meaning is given by the formal mathematical definition.

Incidentally, it's called a proof of knowledge, not a knowledge proof.
> 1 votes

---
Tags: knowledge-proof
---


# Question
Title: approaching dynamic programing for problem
I want to find a solution to a problem that asked before. in the following question: https://stackoverflow.com/questions/43435799/path-with-the-minimum-number-of-alterations-in-graph-with-colored-edgest

> I have a directed graph with colored edges (red & blue) that may contain cycles. The question is to write an algorithm given two vertices (s,t) that finds the path with the minimal number of color changes between s and t (if such path exists). $

suggesting a reduction to solve the problem.

I want to find an optimal structure for the problem by: $opt(v) = \min\_{u \in In(v)}(opt(u) + f(u,v))$

$f(u,v)$ define:

$f(u,v) = \begin{cases} 1, & \text{the color of (u,v) same as the color that appears more}, \\ -1, & \text{the color of (u,v) the color different from the color that appears more}.\\ 1, & \text{else} \end{cases} $

the problem with that formula is that the optimum of the neighbors, not gratitude the optimum solution for $v$ because considering v that have 1 neighbor with a blue edge that has a path with the same blue and red edges and another path with 1 more red edge than my structure return 1 however there is a path with 0 alterations.

then I thinking to save for all the vertices 3 paths, optimum path most optimum path with more blue and path with more red but its seem to complicated to build a formula with that filed.

# Answer
This problem is easily solved if you:

* transform the input graph $G=(V,E)$ by either creating $n-1$ "levels", where each level is a copy of $G$ and edges go from one level to the next; or
* consider the line graph $G'$ of $G$ instead (so that edges in $G$ become vertices in $G'$, and two vertices in $G'$ are adjacent if the corresponding edges in $G$ share an endpoint); or
* For each color $c \in \\{red, blue\\}$, identify the maximal components $C$ of $G$ such that connectivity within $C$ is preserved using only edges of color $c$.

If you insist in using a dynamic programming algorithm, then the problem can be solved in $O(m)$ time using a Dijkstra-like algorithm. Let's start with some definitions:

Given a color $c \in \\{red, blue\\}$, define a $c$-ending path as a simple path $P$ such that either 1) $P$ is empty, or 2) $P$ ends with an edge of color $c$.

Given a path $P$, let $\ell(P)$ be the number of color changes encountered when traversing $P$. We will say a path $P$ from $s$ to $v$ is a shortest $c$-ending path if there exist no other $c$-ending path $P'$ such that $\ell(P') \< \ell(P)$.

We will call $\eta(v,c)$ the value of $\ell(P)$, where $P$ is a shortest $c$-ending path from $s$ to $v$.

According to the above definitions $\eta(s, red) = \eta(s, blue) = 0$. Moreover, the following suboptimality property holds:

**Claim:** Let $P$ be any shortest $c$-ending path from $s$ to $v$, let $u \in P$. The subpath $P\[s:u\]$ of $P$ going from $s$ to $u$ is a shortest $c'$-ending path where $c'$ is the color of the incoming edge in $u$ (if $u=s$ then $c'$ is any color).

**Proof:** Assume that $u \neq v$, otherwise the claim is trivial. Let $c''$ be the color of the edge leaving $u$ in $P$.

Suppose towards a contradiction that $P\[s:u\]$ is not a shortest $c'$-ending path. Let $P'$ be a shortest $c'$-ending path from $s$ to $u$, and notice that $Q = P' \circ P\[u:v\]$ is a (not necessarily simple) path from $s$ to $v$. $Q$ ends with an edge of color $c$ and we have: $$ \ell(P) = \ell(P\[s:u\]) + 1\_{c' \neq c''} + \ell(P\[u:v\]) \> \ell(P') + 1\_{c' \neq c''} + \ell(P\[u:v\]) = \ell(Q), $$ contradicting the fact that $P$ is a shortest $c$-ending path. $\square$

For each node $v$ we will maintain two upper bound $\tilde{\eta}(v, red)$ and $\tilde{\eta}(v, blue)$ on $\eta(v, red)$ and $\eta(v, blue)$, respectively. Initially $\tilde{\eta}(s, red)=\tilde{\eta}(s, blue)=\eta(s, red) = \eta(s, blue) = 0$ while, for $v \neq s$, $\tilde{\eta}(s, red)=\tilde{\eta}(s, blue) = +\infty$.

Finally, we will maintain a priority queue $Q$ in which keys are pairs $(v,c)$ where $v$ is an unmarked vertex and $c$ is a color, and the corresponding priority will be $\tilde{\eta}(v, c)$. Initially all pairs $(v,c)$ are in the queue.

The algorithm proceeds as follows: while $Q$ is not empty, extract $(u,c)$ from $Q$; for each edge $e=(u,v) \in E$ let $c'$ be the color of $e$ and set $\tilde{\eta}(v, c) = \min\\{\tilde{\eta}(v, c), \tilde{\eta}(u, c) + 1\_{c \neq c'} \\}$ (thus possibly updating the priority of $(v,c)$, if such a pair is in $Q$).

It is clear by construction that all values $\tilde{\eta}(v, c)$ are upper bounds to $\eta(v,c)$ as claimed. We now prove that, when the pair $(v,c)$ is extracted from $Q$, $\tilde{\eta}(v, c)$ is also a lower bound to $\eta(v,c)$, thus proving that $\tilde{\eta}(v, c) = \eta(v,c)$.

**Claim:** When $i$-th pair $(v\_i,c\_i)$ is extracted from $Q$, $\tilde{\eta}(v, c) \le \eta(v,c)$.

**Proof**: Let $i$ be the smallest value such that, when $(v\_i, c\_i)$ is extracted from $Q$ we have $\tilde{\eta}(v\_i, c\_i) \> \eta(v\_i,c\_i)$.

Since the values $\tilde{\eta}(v\_i, c\_i)$ never decrease during the execution of the algorithm and cannot become negative we know that $v\_i \neq s$. Let $P$ be a shortest $c\_i$-ending path from $s$ to $v\_i$ and consider the last vertex $x$ such that the incoming edge in $x$ in $P$ has color $c\_x$ (if $x=s$ let $c\_x$ be any color) and $x=v\_j$ and $c\_x=c\_j$ for some $j\<i$ (notice such a vertex always exists since the above conditions are satisfied for $x=s$). Let $y$ be the vertex following $x$ in $P$ and $c\_y$ be the color of the incoming edge.

Since $(v\_i, c\_i)$ was extracted instead of $(y, c\_y)$ we must have: $$ \tilde\eta(v\_i, c\_i) \le \tilde\eta(y, c\_y) $$

Moreover, since $(x, c\_x)$ was already extracted from $q$ we have: $$ \tilde\eta(y, c\_y) \le \tilde\eta(x, c\_x) + 1\_{c\_x \neq x\_y} = \eta(x, c\_x) + 1\_{c\_x \neq x\_y} $$

And, by suboptimality: $$ \eta(x, c\_x) + 1\_{c\_x \neq x\_y} = \eta(y, c\_y) \le \eta(v\_i,c\_i), $$ which is a contradiction $\square$.

The sought quantity is then $\min\\{\tilde\eta(t,red), \tilde\eta(t,blue) \\}$.

Finally, notice that the the priority can only decrease in $Q$, that the priority of the extracted pairs is monotonically increasing, and that the only possible values of the priorities are $\\{0, 1, \dots, n\\} \cup \\{ +\infty \\}$. Therefore it is possible to implement a priority $Q$ that requires $O(n+m) = O(m)$ time to perform all the required $O(n)$ insertions and $O(m)$ priority updates.
> 0 votes

---
Tags: dynamic-programming
---


# Question
Title: Decidable language that has no finite description?
A language is a collection of strings--assuming we have an infinite number of words then concatenating this collection (keeping things simple, normally you need to at least be able to tell where one word ends and another begins) and viewing the language as the resulting single big string, if the Kolmogorov complexity of this string is infinite can the language still be decidable?

This is asking if a language without a finite description can be decidable...also maybe sort of like asking if a language that is not constructible can still be decidable?

If I were to guess, I would say why not..? For example, a language could be given to you as an infinite table of rules (programs) for membership (that, per our condition above, can't be compressed into a smaller set of rules) paired with all words, but have only a finite number of the them be conditions for any particular word or group of words to be members. It is not your job to build such a table but once given such a table you could, when given a word, seek the rule in the table corresponding to that word (if the table is neatly organized this should be possible as to decide any particular word you ever only need to access a finite position on the table), check that word against that rule (run the program that is there on its word), and if doing so is computable for every rule in the table then the language specified by the infinite table should be decidable but at the same time not necessarily be finitely expressible.

Thanks!

# Answer
Unless you want to be more rigid in what you allow as a "description", every decidable language has a finite description - precisely the Turing machine that decides it. This Turing machine must exist (otherwise the language would not be decidable).

Although we often thing of automata as machines that do work, mathematically they're just a way of, in a certain sense, compressing the table that says "yes" or "no" for every string (over the given alphabet).
> 3 votes

---
Tags: complexity-theory
---