6-coloring of a tree in a distributed manner I have some difficulties in understanding distributed algorithm for tree 6 - coloring in $O(\log^*n)$ time.

The full description can be found in following paper: Parallel Symmetry-Breaking in Sparse Graphs. Goldberg, Plotkin, Shannon.

In short, the idea is ...

Starting from the valid coloring given by the processor ID's, the procedure iteratively reduces the number of bits in the color descriptions by recoloring each nonroot node $v$ with the color obtained by concatenating the index of a bit in which $C_v$ differs from $C_{parent}(v)$ and the value of this bit. The root $r$  concatenates $0$ and $C_r[0]$ to form its new color.

The algorithm terminates after $O(\log^*n)$ iterations.

I don' have the intuitive understanding why it's actually terminates in $O(\log^*n)$ iterations. As it's mentioned in the paper on the final iteration there is the smallest index where two bit string differs is at most 3. So 0th bit and 1th bit could be the same and $2^2=4$, so this two bit will give us 4 colors + another 2 colors for different 3th bit, and in total 8 colors and not 6 like in the paper, and why we cannot proceed further with 2 bits, it's still possible to find different bits and separate them.

I would appreciate a little bit deeper analysis of the algorithm than in the paper.

In the paper, the authors mention that after $\log^* n$ iterations, the number of bits used to encode any of the color labels is at most 3. That means that there are at most eight colors. If we have six or fewer colors, we're done, and otherwise we go through the loop once more.

Let's say that we do one last loop iteration. The root gets the color label 0 or 1. Every other node gets a label equal to the first bit position where that node's old label disagrees with its parent's label, plus one extra bit. Since on entry to this iteration all colors are three bits long in the worst case, there are three possible positions where the bits could disagree. Therefore, each new color is formed from a combination of one of three choices and a bit (one of two choices), so at exit of this loop iteration there are only six possible color labels, so we have a six-coloring. The total number of loop iterations is then $\log^* n + 1 = O(\log^* n)$

Hope this helps!


Is the ambiguity of a regular tree grammar decidable? Is there an algorithm which decides whether a regular tree grammar $G$ is ambiguous, i.e. there exists a tree $t\in L(G)$ which can be parsed by the grammar in more than one ways, using only leftmost derivations?

Is there a proof available about the decidability, or a cite to a paper which proposes such an algorithm?

Start by considering regular string grammars. We can determine whether one such grammar $G$ is ambiguous by constructing the intersection of the grammar with itself, with a direct product construction. The nonterminals are pairs $(A,B)$ of nonterminals from the original string grammar $G$. The new grammar of course also derives the original language $L(G)$, but the new grammar has a nonterminal $(A,B)$ with $A\neq B$ in a succesful derivation, iff $G$ is ambiguous. It is decidable whether any given nonterminal occurs in a succesful derivation, so ambiguity is decidable for regular grammars.

The same is true, mutatis mutandis, for regular tree grammars.


Topological Ordering I have learnt to solve topological ordering using $in-degree$ method where we have to take the vertices having in-degree $0$ at an instance and arrange them in that order.

  For example consider this question asked in Graduate Aptitude Test in
  Engineering more commonly known as $GATE$ the entrance exam for $IIT$
  $M.Tech$ in India. The question goes like this,

  Find the number of topological ordering possible for the given
  graph-->

Here we can see that in-degree of A is 0 so we take $A$ as the stating vertex, then we have 2 options either $B$ or $C$, and so on....
The number of possible topological ordering in this case is $6$ as explained below

This method works well for these examples where the number of in-degree 0 vertices is less at a time, but how to solve problems where there are many number of 0 in-degree vertices as the one given below

I think combinatorics will come into picture in such cases, but I am unable to apply it properly. Any help will be highly appreciated.

Unfortunately, there is no "fast" way to count them generally as this problem is #P-Complete. This means that it is basically as hard as every counting version of NP-problems, and is likely not solvable in polynomial time.

For small examples such as this one you can come up with some ad-hoc counting technique however. In this case would try listing all permutations of E,F,G and see how many choices I have for the rest if I insert them in some order. Like this:

EFG: 1+2+4+6 = 13
(1 choice for A, then 2 for B, 4 for C, 6 for D)
EGF: 1+2+4+5 = 12 (in A,B,C,D order)
FEG: 1+2+4+5 = 12 (in B,C,A,D order)
FGE: 1+2+4+6 = 13 (in B,C,D,A order)
GEF: 1+2+4+5 = 12 (in D,C,A,B order)
GFE: 1+2+4+5 = 12 (in D,C,B,A order)

So in total 4*12 + 2*13 = 74 topological orderings (with some non-negligeable probability that I miscounted somewhere).


Time Complexity of k-clique problem with fixed k My question expands on a related question on the link, Why is the clique problem NP-complete?
In that post the author argued that while the $k$-clique problem is NP-complete; for a fixed $k$ the $k$-clique problem is polynomial time solvable. The question "Prove that the presence of 3-clique in a graph can be decided in polynomial time" also appears in the book, S. K. Basu, "Design Method and Analysis of Algorithms, PHI, 2005, pg159.

To avoid any confusion, I felt it important to clarify that this would only be possible if the graph $G=(V,E)$ ($V$ is the set of vertices and $E$ is the set of edges) is fixed. In such a case a polynomial number of steps $R^m,$ (where $R=f(V,E)$, i.e. $R$ is a constant given by some function of vertices and edges) can be used to find the solution of 3-clique for example.  So the conclusion that finding 3-clique for a fixed graph has polynomial time complexity works perfectly fine until this point.

But such a polynomial time algorithm with time complexity less than or equal to linear time complexity can not be designed to find 3-clique, i.e. $m>1$. Assuming that $k$ is fixed but $G$ is not fixed, in that case the complexity of finding 3-clique will then be exponential, unless someone can provide a polynomial time algorithm with complexity $R^m$, where $m\leq 1$ to find 3-clique for a fixed arbitrary graph. Since we are unable to prove that a polynomial time algorithm does not exist for 3-clique problem on an arbitrary graph, the computational complexity of the problem will hence be treated as being NP-complete based on the relationship $3SAT\leq_p k$-clique, a proof of which can be found in many standard books on algorithms.

A polynomial algorithm does exist for finding whether a graph contains a triangle. For one, you can go over all triplets $x,y,z$ of vertices, and check if the graph contains the triangle $\{x,y\},\{y,z\},\{x,z\}$. This algorithm takes $O(n^3)$. Surprisingly, there is a faster algorithm: take the adjacency matrix $A$ of the graph, and compute the trace of the matrix $A^3$. The graph contains a triangle iff the trace is positive. This algorithm takes $O(n^\omega)$, where $\omega < 2.373$ is the exponent of matrix multiplication.


How to represent circles in x-y coordinates I would like to be able to represent circles in x-y coordinates.

Each circle contains an x and y coordinates and radius in double data type.

My goal is to compare circles with each other whether they are partially or completely overlapping.

I am looking for efficient ideas. Honestly the only idea that comes to my mind is draw a line(let's say l1) from x1,y1 to x2,y2 and the length of this line is larger than addition of r1 and r2 then it does not overlap, if r1+r2 =< l1 then it overlaps, but I don't know how to find whether it is completely overlapping or partially. Also this wouldn't work for cases where I am combining more than one circle.

This answer considers two cases:

the overlapping relation between two disks, which is a very simple problem.
the ovelapping or covering of a disk by a set of other disks, which is somewhat harder in general.

Case of two disks

It is indeed a good idea to use center and radius to represent your
circles. However I think you are not thinking of circles, which are
closed planar lines formed of all points at a given distance $r$,
called radius, of a point $c$ called the center. The planar surface
enclosed by a circle, which also includes all points at a lesser
distance fron $c$ is called a
disk (also
spelled disc).

Regarding the various overlap situations for two disks, you have the
following test, assuming the two circles have radius $r_1$ and $r_2$
(assuming witout loss of generality that $r_1\geq r_2$), with their
centers at distance $d$ (computable from the centers coordinates,
thanks to Pythagoras):

$r_1+r_2<d$ : disks are disjoint, no overlap.
$r_1+r_2=d$ : disks are tangent externally, a single point of overlap.
$r1-r2<d<r_1+r_2$ : disks are partially overlapping.
$r_1-r_2=d$ : disks are tangent internally, total overlap of disk 2 by disk 1.
$d<r_1-r_2$ : disk 1 overlap totally disk 2.

There can be exact overlap of each disk by the other only when
$r_1=r_2 \wedge d=0$

Regarding the case of several disk, it is not clear whether you want
to see whether one distinguished disk is overlapped totally, partially
or not at all by the others, or whether you want to check that for
each disk with everyone of the others, or possibly something else. You should make that more precise.

Case of several disks

This is only a rough sketch, hopefully correct. Working out all details is a lot more work than can be included in an answer.

As suggested in the question, we can represent a disk $D$ by a
triple $(x,y,r)$ which gives the coordinates of the center, and the radius.

Now if you have a disk $D_0=(x_0,y_0,r_0)$ and a set of disks
$L=\{D_i\mid D_i=(x_i,y_i,r_i),\; i\in[1,n]\}$, your question, as
made more precise in a comment, is
how to check whether the disks of set $L$ together overlap partially,
totally or not at all the disk $D_0$.

First you want to make a list of the disks in $L$ that actually
overlap $D_0$. For that you can simply apply the above test to $D_0$ and
$D_i$ for every $D_i$ in $L$. You get a set $I\subseteq[1,n]$ of indices
such that D overlaps every $D_i$ for $i\in I$.

If this set $I$ is not empty, you know that $D_0$ is overlapped by $L$.

The question remains of a total overlap of $D_0$ by $L$.

For this, you create a new set $J\subseteq I$ by removing indices of
disks $D_i$ that are only externally tangent to $D_0$, overlapping it on
only one point.

If $J$ is empty, you had only tangential overlapping in a finite
number of point, but the set $L$ does not cover (fully overlap) the disk $D_0$.

If $J$ is not empty, then $L$ completely overlap $D_0$ iff it does it
with the disks $D_i$ such that $i\in J$. Tangential overlapping on a
single point cannot contribute usefully to overlapping a surface.

Now, all disks in $M=\{D_i\mid i\in J\}$ overlap $D_0$ on a fragment
of its surface.

If one disk in $M$ completely overlaps $D_0$, then we have an answer
of complete overlap. We can now assume it is not the case.

Then the problem is to find an orderly strategy to check whether the
disks in $M$ completely cover $D_0$. We will now use disks from $M$
one by one, removing them from M, to cover $D_0$. The strategy is in
choosing them.

We chose first a disk in M (which we remove from M), such that it is not
internally tangent to $D_0$, but intersect the edge circle of $D_0$. There
must be at least two such disks, else $D_0$ cannot be covered, as its
perimeter circle will nor be covered except for a finite number of
points.

We compute the two points where the two circles intersect. They define
two arcs, one on each circle, that delimit a surface yet to be covered
by the other circles. With respect to this surface, the arc belonging
to $D_0$ is convex, while the other is concave.

For simplicity and intuition, we call these intersections the angles
of the remaining surface. We call sides or edges the arcs between 2
angles that delimit the remaining surface to be covered.

We then chose one of the two angles, and look in M for another circle
covering this intersection. This new circle removes at least this
angle, and adds usually two new angles. We discuss this further below.

One remark is that the arcs coming from $D_0$ are always convex, while
the others are always concave. This is useful to visualize what can occur.

Then we repeat the same step, until there are no angles left, in which
case we have a covering of $D_0$, which is tested first, or until
there are no disk left in M that can cover a chosen angle, in which
case the overlap is incomplete.

To understand this we have to look at intermediate steps in more
details. During execution of the algorithm, we may have actually
created an uncovered curvy polygon with many angles. When we chose a
new disk $D_i$ to cover a chosen angle $A$, we may actually cover
several angles of the polygon, and the edges in between, so that we
actually reduce the number of edges.

So after choosing the disk $D_i$, we have to find the first edge on
both sides of the angle $A$ (not necessarily adjacent to $A$) that are
intersected by the circle bounding $D_i$. These two intersections, one
on each side, define two new angles and a new edge provided $D_i$, and
may replace several edges and angles. Hence the number of sides of the
polygon may be reduced rather than increased. It may be also that all
sides are covered, in wich case we have covered the whole disk.

There may be cases when the new disk will cut the curvy polygon into two
polygons, that will both have to be covered. To check for that, the
circle bounding the disk has to be checked for intersection with all
edges of the curvy polygon(s).

All this implies of course to keep an up-to-date description of the
curvy polygon and the relations between angles, edges and disks.
To keep correspondence between the relative positions of angles, if
they are listed counter-clockwise on the curvy polygon(s), then they
should be counter-clockwise on the circle of the disk $D_0$ and
clockwise on the disks from $M$.

There are quite a few details to be worked out, which I would not try
without at least checking an implementation. But I believe this basic
idea can be implemented.

From this analysis, I think the time complexity is $O(n^2)$, since
every steps considers a new disk, and has to look at intersections
potentially with all disks that have already been considered.

The extension to spheres is left as an exercise.


Ramifications of P?NP Being Undecidable Godel proved there are true statements in arithmetic that can't be proven true in any sufficiently strong Formal Axiomatic System (FAS). The authors of this paper use similar arguments to prove there are TM's that belong to a certain complexity class that cannot be proven to belong to that class. They refer to these type of algorithms as "hidden machines".
ON THE EXISTENCE OF HIDDEN MACHINES IN COMPUTATIONAL TIME HIERARCHIES
What happens to the quesion of P?NP if there exists a TM that can solve any satisfiable 3SAT instance in polynomial steps, yet, it is impossible to prove this TM does so?

In some sense, nothing much.  We still have P = NP.  It's possible for there to be statements that are true even though we can't prove them true.
In another sense, something interesting happens: in your scenario, we can explicitly write down a new algorithm that is guaranteed to solve 3SAT in polynomial time, using Levin universal search.  See https://cs.stackexchange.com/a/92095/755.  So, if there is a non-constructive proof that 3SAT is in P, then you can find a constructive proof that 3SAT is in P.
See also Is P decidable?, Assuming P = NP, how would one solve the graph coloring problem in polynomial time?, Explicit algorithms and algorithms involving unknowns.


Saving on array initialization I recently read that it is possible to have arrays which need not be initialized, i.e. it is possible to use them without having to spend any time trying to set each member to the default value. i.e. you can start using the array as if it has been initialized by the default value without having to initialize it. (Sorry, I don't remember where I read this).

For example as to why that can be surprising:

Say you are trying to model a  worst case $\mathcal{O}(1)$ hashtable (for each of insert/delete/search) of integers in the range $[1, n^2]$.

You can allocate an array of size $n^2$ bits and use individual bits to represent the existence of an integer in the hashtable. Note: allocating memory is considered $\mathcal{O}(1)$ time.

Now, if you did not have to initialize this array at all, any sequence of say $n$ operations on this hashtable is now worst case $\mathcal{O}(n)$.

So in effect, you have a "perfect" hash implementation, which for a sequence of $n$ operations uses $\Theta(n^2)$ space, but runs in $\mathcal{O}(n)$ time!

Normally one would expect your runtime to be at least as bad as your space usage!

Note: The example above might be used for an implementation of a sparse set or sparse matrix, so it is not only of theoretical interest, I suppose.

So the question is:

  How is it possible to have an array like data-structure which allows us to skip the initialization step?

This is a very general trick, which can be used for other purposes than hashing. Below I give an implementation (in pseudo-code).

Let three uninitialized vectors $A$, $P$ and $V$ of size $n$ each. We will use these to do the operations requested by our data structure. We also maintain a variable $pos$. The operations are implemented as following:

init:
  pos <- 0

set(i,x):
if not(V[i] < pos and P[V[i]] = i)
  V[i] <- pos, P[pos] <- i, pos <- pos + 1
A[i] <- x

get(i):
if (V[i] < pos and P[V[i]] = i)
  return A[i]
else
  return empty

The array $A$ simply stores the values that are passed through the $set$ procedure. The arrays $V$ and $P$ work as certificates that can tell if a given position in $A$ has been initialized.

Note that at every moment the elements in $P$ ranging from $0$ to $pos-1$ are initialized. We can therefore safely use these values as a certificate for the initialized values in $A$.
For every position $i$ in $A$ that is initialized, there is a corresponding element in the vector $P$ whose value is equal to $i$. This is pointed by $V[i]$. Therefore, if we look at the corresponding element, $P[V[i]]$ and its value is $i$, we know that $A[i]$ has been initialized (since $P$ never lies, because all the elements that we're considering are initialized). Similarly, if $A[i]$ is not initialized, then $V[i]$ may point either to a position in $P$ outside the range $0..pos-1$, when we know for sure that it's not initialized, or may point to a position within that range. But this particular $P[j]$ corresponds to a different position in $A$, and therefore $P[j] \neq i$, so we know that $A[i]$ has not been initialized.

It's easy to see that all these operations are done in constant time. Also, the space used is $O(n)$ for each of the vectors, and $O(1)$ for the variable $pos$, therefore $O(n)$ in total.


Proving that $T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n$ is $\in O(n)$ Show $T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor
n/8 \rfloor) + n$ is $\in O(n)$.

I will make the bound to be $\in O(cn)$ instead.

Proof by strong induction.

Base case n =1

$T(1) = c$ and $cn=c*1=c$ $\checkmark$

Inductive Hypothesis : $T(k) \in O(ck)$ for $1\le k<n, n>1$.
Inductive Step: Prove for n.  So prove that $T(n) \le O(ck)$.

Right away we can write
$T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n \\
\leq T(n/2)+T(n/4)+T(n/8) + n\\ = c(n/2)+c(n/4)+c(n/8)+n \ \ \  \ By \ Inductive \ Hypothesis$

$$= c(7n/8)+n \le cn+n ... $$ I am stuck here

*Goal: $\le cn - (some \ stuff)$ and some stuff needs to be $\ge 0$.

First, let me mention that $O(n)$ and $O(cn)$ are exactly the same thing. What you are really after is showing that $T(n) \leq cn$ for all $n$.

Let us aim at a slightly more relaxed goal: showing that $T(n) \leq An$ for some possibly larger constant $A$. For the base case, we need $A \geq c$. For the inductive step, we know that
$$
T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n \leq A(n/2+n/4+n/8)+1 = (\tfrac{7}{8}A+1)n.
$$
Recall that our goal is to deduce that $T(n) \leq An$. This would follow if $\tfrac{7}{8}A + 1 \leq A$, that is, if $A \geq 8$.

In total, if we take $A = \max(c,8)$ then both the base case and the inductive step go through.

As an aside, you can also use the Akra-Bazzi theorem to directly conclude that $T(n) = O(n)$.

Now let us try to obtain more insight on the recurrence. Let $S(n) = 8n - T(n)$. Then
$$
S(n) = S(\lfloor n/2 \rfloor) + S(\lfloor n/4 \rfloor) + S(\lfloor n/8 \rfloor) + 8n - 8\lfloor n/2 \rfloor - 8\lfloor n/4 \rfloor - 8\lfloor n/8 \rfloor - n.
$$
Since $8(n/a-1) < 8\lfloor n/a \rfloor \leq 8(n/a)$, we see that
$$
S(n) = S(\lfloor n/2 \rfloor) + S(\lfloor n/4 \rfloor) + S(\lfloor n/8 \rfloor) + r(n),
$$
where $0 \leq r(n) < 24$. Applying the Akra-Bazzi theorem, we get $S(n) = O(n^p)$ for some $p < 1$ (the solution to $(1/2)^p + (1/4)^p + (1/8)^p = 1$), and so $T(n) = 8n + O(n^p)$.


Smallest subarray problem Say you have an array of integers like [1, 2, 3, 4, 5, 6], the problem is to find the smallest way to break up the array into sub-arrays where each sub-array satisfies the following requirement:

sub-array.first_integer and sub-array.last_integer must have a common divisor that is not 1.

So for [7, 2, 3, 4, 5, 6] the answer would be 2, because you can break it up like [7] and [2, 3, 4, 5, 6], where 2 and 6 have a common divisor of 2 (which is > 1 so it meets the requirement).
You can assume the array can be huge but the numbers are not too big. Is there a way to do this in n or n*log(n) time? I think with dp and caching n^2 is possible but not sure how to do it faster.
Here is my current attempt with a BFS, but it's still N^2:
https://onlinegdb.com/ryZwkYnA8
Edit: OK I think I found an improvement which is a polynomial times the square root of a pseudo-polynomial: n * sqrt(magnitude of the values). Seems much faster, it basically builds an adjacency list; and can be done BFS, DP, and caching all the same. Although I wonder if anything better is available?
https://onlinegdb.com/SJpl4930L

In my answer I will assume that all numbers are at most $M$ big, i.e. $A[i] \le M$.
First some comments about your both approaches.
Computing the GCD takes $O(\log M)$ time. So your first approach is actually $O(N^2 \log M)$.
I also don't think that your second approach is actually better than $O(N^2)$. For instance assume if all the numbers of the first half of the array are equal. Then for each of those numbers you have at least $\Theta(N)$ effort for each divisor of $N$. Which means that the complexity for such a test case is something like $O(N^2 \sqrt M)$.

Let's first discuss a very trivial (but slower) dynamic programming solution, on which I will later base a better one.
Let's define the function $f$ as $f(i)$ is the smallest number of subarrays in which you can split the prefix of size $i$ of the array (the first $i$ numbers). Also let $f(i) := \infty$ if it is not possible to split the array, and $f(0) := 0$.
It's easy to see, that you can compute $f(i)$ using the recursion:
$$f(i) = \min_{\substack{1 \le j \le i\\ \gcd(A[i], A[j]) > 1}} f(j-1) + 1$$
This formula is very trivially to implement together with dynamic programming, and will have the complexity $O(N^2 \log M)$.
f(0) = 0
for i = 1 to N:
    f(i) = infinity
    for j = 1 to i:
        if gcd(A[i], A[j]) > 1:
            f(i) = min(f(i), f(j-1)) + 1
print f(N)

Now to a better approach. We need two mathematical facts that will help us:

If two numbers have a common divisor greater than one, then they have a common prime factor.
A number $\le M$ has at most $\log M$ prime factors.

Let the set of prime factors of $x$ be $P(x)$.
Then we can also rewrite the recursion for $f$ as:
$$f(i) = \min_{p \in P(A[i])} \left( \min_{\substack{1 \le j \le i\\ p ~|~ A[j]}} f(j-1) \right) + 1$$
In other word, if $A[i] = 20 = 2^2 \cdot 5$, then we look for all previous numbers who are divisible by 2, and take the minimum of $f(j-1)$, and for all previous numbers who are divisible by $5$ and take the minimum of $f(j-1)$. The actual optimal value $f(i)$ will one more than the minimum of both.
If we define $g(p, i)$ as the minimum of $f(j-1)$ with $p ~|~ A[j]$ and $1 \le j \le i$, then the formula simplifies to:
$$f(i) = \min_{p \in P(A[i])} g(p, i) + 1$$
We can actually apply some sort of dynamic programming also to the function $g$.
We store the values in a hash table.
First we initialize the function for every possible prime factor with $g(p) = \infty$, and whenever a $f(j-1)$ changes, we update $g(p)$ for every $p \in P(A[j])$.
This means, after we update $f(i)$, we only need to update $O(\log M)$ different values of $g$.
This gives us the following algorithm:
# initialize g
for all p:
    g(p) = infinity

# set the first value f(0)
f(0) = 0
# update g
for p in P(A[1]):
    g(p) = min(g(p), f(0))

for i = 1 to N:
    # first compute f(i)
    f(i) = infinity
    for p in P(A[i]):
        f(i) = min(f(i), g(p)) + 1

    # and then update g
    if i < N:
        for p in P(A[i+1]):
            g(p) = min(g(p), f(i))
print f(N)

It's easy to see that this algorithm runs in $O(N \log M)$ time.
A shorter variation, but with the exact same approach and complexity, would also be:
for all p:
    g(p) = infinity
f(0) = 0
for i = 1 to N:
    f(i) = infinity
    for p in P(A[i]):
        g(p) = min(g(p), f(i-1))
        f(i) = min(f(i), g(p)) + 1
print f(N)

The only thing to discuss is, how we get the prime factorization of each number.
There are loads of different approaches.
For instance if $M$ is not too big, you can compute the Sieve of Eratosthenes in $O(M \log M)$ and during the computation store a prime factor for each number $\le M$. This allows to compute the prime factorization of each number in $O(\log M)$.
Another option would be just to compute the prime factors on the fly, which would give take additionally $O(N \sqrt{M}$) time if you use the typical trial division until square root algorithm.


Neural net that alters its own parameters Is it possible for an AI neural net to be able to modify its own parameters/hyperparameters and/or add new parameters/hyperparameters? If so, how has it been implemented? For example, to simulate a human mind, could the net utilize 3 basic emotional parameters before realizing it needs many more and subsequently creating them?

One can do whatever he likes.

If your algorithm allows richer structure modification than simply adjusting weights, then you can obtain a "net which alters itself", though this doesn't have any special/magical meaning.

Suppose for example that your net's inputs correspond to some properties of an image, and you have a " hidden node" whose input is the average pixel value. During training, you can see whether adding this node lowers your training error, and if so, add it. One can claim that the net magically realized that it needs to use the average pixel value, but this is merely a direct result of your learning algorithm definition.


Languages such that DFA requires $\Omega(c^k)$ states but NFA needs only $O(k)$ states? Given an alphabet $\Sigma$, let $c=|\Sigma|$.  Can a set of languages $\{L_k\}$ be created, such that any DFA for $L_k$ has $\Omega(c^k)$ states and a NFA for $L_k$ exists with $O(k)$ states?

I'm having trouble creating an $L_k$ such that any DFA for it has $\Omega(c^k)$ states.  There are constructions that require $\Theta(2^k)$ states, but here $c$ is an arbitrary constant, so if $c>2$ those constructions do not suffice.

Is the language of strings with a suffix of $s_k, |s_k|=k$ such a language? Following is a draft proof of that.

Proof by contradiction: let a DFA $\langle Q, \Sigma, \delta, q_0, F\rangle$ have $|Q|<c^{k-1}$. Let $a, b$ be strings of length $k$ and $a_k=(s_k)_1\not=b_k$

Let $q_a$ and $q_b$ denote $\delta(q_0, a)$ and $\delta(q_0, b)$, respectively.

There are two cases:

I. there are no $a,b$ such that $q_a=q_b$. Then each string corresponds to a different state, but there are $c^{k-1}$ such strings, therefore $|Q|\geq c^{k-1}$, which is not possilbe.

II. There are $a,b$ such that $q_a=q_b$. Then $\delta(q_a, s_2s_3\ldots s_k)=\delta(q_b, s_2s_3\ldots s_k)=q_c$. $as_2s_3\ldots s_k$ should be accepted and $bs_2s_3\ldots s_k$ shouldn't, therefore $q_c$ is both an accepting state and not an accepting state, which is not possible.

This seems to prove that any DFA for $L_k$ has at least $c^{k-1}$ nodes, which is sufficient for $\Omega(c^k)$. If my proof is correct, the only task left is to prove that a NFA containing $O(k)$ nodes exists for $L_k$.

The simplest way to do this is to create such a NFA, however I'm not sure how to do that. $O(k)$ suggests that $i$-th node should correspond to the state of "prefix of $s$ of length $i$ matches the suffix of the input string", however I do not follow how such a NFA can be created.

The language $L_k$ that you list doesn't work.

There is a straightforward NFA for the language $L_k$ you list, with $k+1$ states.  It guesses where the suffix starts, then checks that the suffix is equal to $s_k$.

In particular, the NFA has states $0,1,\dots,k$, with transitions $0 \to 0$ on each symbol, transitions $i-1 \to i$ on the symbol that matches the $i$th character of $s_k$, and $k$ being an accepting state.

It follows, using the subset construction, that there exists a DFA with $2^{k+1}$ states.

Consequently, that language does not meet your requirements, if $c>2$.


Which class of neural network problem is this? I have managed to describe a problem in quantum computing as the optimization of a function f(graph,vector), over graphs and real vectors.
For a given graph, I can optimize the vector with standard methods (say, gradient descent), but the search over graphs has to be a brute force random search, because I don't know what makes a graph 'good' for this application.

In any case, computing the value of f for a given graph and a given vector takes a time of the order of seconds, so even if I already knew good graphs the optimization of the vector would be feasible yet time consuming.

What I would love to try is to train a NN to find good pairs of graphs and vectors. Where do I start from? What kind of NN problem is this?

If I understand the question correctly,
you want to find the optimum of the function $F(G) := \min_{v\in V} f(G,v)$*, where $V$ is your vector space, over all valid graphs $G$. Additionally, you can compute $F(G)$ for any given graph.

First of all, I doubt only neural networks are going to be very helpful. The main strength of neural networks is to classify given training data. Judging from your question, I doubt training data is abundant.

The general problem of heuristically** optimizing an arbitrary function (here: $F$) over a discrete solution space (here: all valid graphs $G$) is usually solved by applying metaheuristics, such as local search methods (e.g. Hill climbing, simulated annealing, tabu search) or evolutionary algorithms.

These methods require you specify some structure of your solution space.

For local search, you need to define a neighbour relation between solutions to provide structure, such that

The neighbour relation is symmetric
Any two solutions are 'reachable' from another by
The difference in $F$ between neighbours is usually (hopefully?) low.

For this problem, we could consider two graphs neigbours if we can reach the other by removing or adding an edge. This is clearly symmetric and all solutions are reachable if we assume all graphs have the same vertices. Then, all that's left is to hope that the network performance $F(G)$ usually doesn't change much if we remove/swap two edges.

Most likely, this neighbour relation does not suffice, as this is very problem-specific. If you have such a neighbour relation, you can apply some local search method and get a hopefully good answer.

*: (You may want the maximum instead, but that doesn't really change anything, of course)

**: In other words, we 'attempt' to find a good answer without any optimality guarantees. Note that this is even 'weaker' than approximation. These methods are often justified, as many optimisation problems over discrete domains cannot even be approximated efficiently. I think this is acceptable, as neural networks usually cannot guarantee any optimality either.


What programming languages always learned in computer science B.Sc.? Even if programming by itself is not an integral part of computer science,
I would bet any B.Sc. student learns fundamentals of binary code, fundamentals of assembly code and at least one high programming language (above assembly).

What programming languages always learned in computer science B.Sc.?

I define programming as: writing source code in one or more computer languages, of the programming language type.

There is no programming language that is taught in every computer science B.A. program. There is a lot of variation in what languages are used to teach material, in different programs.  For instance, when I took computer science classes, I learned only C and Standard ML.  There are other other programs where you might learn (for example) Python and Java.  If you choose any one programming language, I would imagine you can find some B.A. programs that teach that language and others that don't.

Learning a specific programming language is usually not the main point of a computer science education. The goal is to learn concepts and skills, and teaching any one programming language is just a way to support that goal.


Does there exist any work on creating a Real Number/Probability Theory Framework in COQ? COQ is an interactive theorem prover that uses the calculus of inductive constructions, i.e. it relies heavily on inductive types. Using those, discrete structures like natural numbers, rational numbers, graphs, grammars, semantics etc. are very concisely represented.

However, since I grew to like the proof assistant, I was wondering whether there are libraries for uncountable structures, like real numbers, complex numbers, probability bounds and such. I am of course aware that one cannot define these structures inductively (at least not as far as I know), but they can be defined axiomatically, using for instance the axiomatic approach.

Is there any work that provides basic properties, or even probabilistic bounds like Chernoff bound or union bound as a library?

The standard library of Coq has a section about real numbers. These are the classical real numbers, using the Dedekind completion. There are also results about complex numbers, I suppose there are several libraries, I happen to know this one. Note that there is also a lot of results for constructive real and complex numbers, C-CoRN is the reference.

Side note: you could also define (computable) real numbers inductively with some of the constructive axiomatics, for example using rational numbers from the Cauchy sequences or some constructive version of the least-upper-bound property. I am not sure how much inductive that this.

I know there are some people working on probabilities with Coq. Unfortunately I am not sure how advanced their works are. My guess is that there is likely no such specific result about Chernoff bound or union bound. (But it's just a guess)


Strategy to create a testbed and gold standard I need to create a correct evaluation of the method I'm proposing. The problem is that in the field I'm working on there is no benchmark that I can use for this purpose. On the other hand, my method has to run, as much as possible, on top of "real documents", but these documents are mostly private and created by industry.

The documents are based on the AutomationML language, which is XML-based, and I do have some "real" ones. Until now, I have created the documents manually, and have also automatically generated them based on a given seed document and the AutomationML XML-Schema to ensure that the generated documents are syntactically correct. Also, they are generated following a uniform distribution.

I would like to extend the automatic generation but for this, I don't know how to automatically create the gold standard. I would appreciate any hints regarding this.

You can't.  You can't squeeze blood out of a stone.  If you want to evaluate how well your method will work on real documents, you need real documents.  With synthetically/artificially generated documents, you'll never know if they have the same characteristics as real documents.

You don't necessarily need a standard benchmark that others have used -- but you do need to assemble a representative set of real documents to evaluate on.  Basically, if there is no standard benchmark in your field, you'll have to assemble one yourself.

Yes, this is difficult to do.  This is one of the less-well-known and less-glamorous aspects of working on machine learning: in practical projects, often we spend 80% of our time (or more!) just assembling data sets, and only 20% on the actual learning algorithms themselves.


Reducing a problem to Halt I'm reviewing for a computability test, and my professor has not provided solutions to his practice questions. I came up with a "solution" to this problem, but it really seems like my answer is wrong (since I call upon $\mathsf{Halt}$ twice)...

We are given this initial language for some machine $M$:

$\mathsf{2Strings} = \left\{ \left<M\right>\ |\ L(M)\text{ contains at least 2 distinct strings }\land M\text{ is a }TM \right\}$

And we are told to "[s]how that [the language] is recursive-enumerable." The problem title is Reduction, so I assume we are supposed to use that.

My solution is as follows:

Pass $\left<M\right>$ to the following reduction:
Create $w_1 \in L(M), w_2 \in L(M)$, so that $w_1 \not= w_2$, and let $M' = M$.
Pass $\left<M', w_1\right>$ to $\mathsf{Halt}$. If the answer is Yes, proceed to step 4. Otherwise, return No.
Pass $\left<M', w_2\right>$ to $\mathsf{Halt}$. If the answer is Yes, return Yes. Otherwise, return No.

Basically, this is my logic: We pass each of two distinct strings from $L(M)$ to $\mathsf{Halt}$ separately; if either one says No, our answer is No. If both say Yes, the answer is Yes.

Is my answer valid? More importantly, is it correct? If not, what should I do to fix it?

First of all I find it rather artificial to argue with reductions, since a more direct argument is applicable here. However, you can of course do it.

I think your approach follows basically the right direction. But it is not a clean reduction. Here is how I would phrase it.

We want to show that ${\sf 2Strings}$ is recognizable by showing ${\sf 2Strings}\le_m {\sf Halt}$. The reduction  goes as follows: Assume we have  a TM $M$ and based om $M$ we define a different TM $M'$. Let us first define a NTM $N$:

 0. Delete the input
 1. Guess two words u and w
 2. If u=w cycle
 3. Simulate u on M
 4. Simulate w on M
 5. Accept if both simulation accepted, otherwise cycle

Now let $M'$ be the deterministic version of $N$. The reduction maps $\langle M \rangle $ to $\langle M',\varepsilon \rangle$. By construction,
$$
\begin{align}
\langle M \rangle \in {\sf 2String} & \iff N \text{ accepts every input}\\
 & \iff M' \text{stops on every input}\\
 & \iff M' \text{stops on }\varepsilon \\
 & \iff \langle M',\varepsilon\rangle \in {\sf Halt} \\
\end{align}
$$


Find a weighted median for unsorted array in linear time For days, I'm trying to figure out, whether it is possible to find an item in array which would be kind of weighted median in linear time.
It is very simple to do that in exponential time.
So let's say that we have an array, each item $x$ of this array has two attributes - price $c(x)$ and weight $w(x)$. The goal is to find an item $x$ such that
$$
\sum_{y\colon c(y) < c(x)} w(y) \leq \frac{1}{2} \sum_y w(y) \text{ and }
\sum_{y\colon c(y) > c(x)} w(y) \leq \frac{1}{2} \sum_y w(y).
$$
If the array was sorted by price, it would be simple:
Go from the first item one by one, count sum and if the sum becomes greater that half the total weight, then you found the desired item.
Could you give me some hint how to find such an item in linear time?

Let $A$ be an input array containing $n$ elements, $a_i$ the $i$-th element and $w_i$ its corresponding weight. You can determine the weighted median in worst case linear time as follows. If the array length is $\leq 2$, find the weighted median by exhaustive search. Otherwise, find the (lower) median element $a_x$ using the worst case $O(n)$ selection algorithm and then partition the array around it (using the worst case $O(n)$ partition algorithm from QuickSort). Now determine the weight of each partition. If weight of the left partition is $< \frac{1}{2}$ and weight of the right partition is $\leq \frac{1}{2}$ then the weighted (lower) median is $a_x$. If not, then the weighted (lower) median must necessarily lie in the partition with the larger weight. So, you add the weight of the "lighter" partition to the weight of $a_x$ and recursively continue searching into the "heavier" partition. Here is the algorithm's pseudocode (written in Latex).

FIND-WEIGHTED_LOWER_MEDIAN(A)
    if $n$ == 1
       return $a_1$
    elseif $n$ == 2
       if $w_1 \geq w_2$
          return $a_1$
       else
          return $a_2$
    else
       determine $a_x$, the (lower) median of A
       partition A around $a_x$
       $W_{low}$ = $\sum\limits_{{a_i} < {a_x}} {{w_i}}$
       $W_{high}$ = $\sum\limits_{{a_i} > {a_x}} {{w_i}}$
       if $W_{low} < \frac{1}{2}$ AND $W_{high} \leq \frac{1}{2}$
          return $a_x$
       else if $W_{low} \geq \frac{1}{2}$
               $w_x = w_x + W_{high}$
               B = \{ a_i \in A: a_i \leq a_x \}
               FIND-WEIGHTED_LOWER_MEDIAN(B)
            else
               $w_x = w_x + W_{low}$
               B = \{ a_i \in A: a_i \geq a_x \}
               FIND-WEIGHTED_LOWER_MEDIAN(B)

Now let's analyze the algorithm and derive its complexity in the worst-case. The recurrence of this recursive algorithm is $T(n) = T(\frac{n}{2} + 1) + \Theta(n)$. Indeed, we have no more than a recursive call on half the elements plus the (lower) median. The initial exhaustive search on up to 2 elements costs $O(1)$, determining the (lower) median using the select algorithm requires $O(n)$, and partitioning around the (lower) median requires $O(n)$ as well. Computing $W_{low}$ or $W_{high}$ is again $O(n)$. Solving the recurrence, we get the complexity of the algorithm in the worst case, which is $O(n)$.

Of course, a real implementation should not use the worst case $O(n)$ selection algorithm, since it is well known that the algorithm is not practical (it is of theoretical interest only). However, the randomized $O(n)$ selection algorithm works pretty well in practice and can be used since it's really fast.


Adding Big-O and little-o notation to get a little-o Lets suppose that there exists a comparison-based algorithm that turns an arbitrary array to a state $A$ in $o(n\log k)$, and there is another comparison-based algorithm that turns an array in state $A$ to completely sorted in $O(n\log (n/k))$. $n$ is the size of the array, while $k$ is another non-constant parameter given. I want to get a contradiction. Here is my reasoning:

Running the first algorithm followed by the second completely sorts the array, and takes

$$o(n\log k)\ +\ O(n\log(n/k)) = o(n\log k\ +\ n\log(n/k)) =$$
$$o(n(\log k\ +\ \log(n/k))) = o(n\log (k \times n/k)) = o(n\log n)$$

which is a contradiction to the known lower bound to comparison-based sorting algorithms.

My question is: Is my reasoning correct? Why or why not? I've tried to prove it using the definitions, but I'm stuck.

Thanks.

No. You are misusing Landau notation.

$o(f) + O(g) \not\subseteq o(f + g)$ even if $f \in O(g)$. The best you can get is $O(f + g)$. If $g \in o(f)$, you get $o(f)$.
$\log k$ and $\log n$ are incomparable as long as you can not put $k$ and $n$ in some kind of relation.

Assuming that $k \in \omega(1) \cap O(n)$, you can show that both $o(n \log k) \subseteq o(n \log n)$ and $O(n \log (n/k)) \subseteq o(n \log n)$. Then, we would indeed deduce that the proposed algorithm would take $o(n \log n)$ comparisons, contradicting the known lower bound.


What machine learning algorithm to use and how to implement it? I have a virtual world with a grid filled with squares (x by y). There are entities that can do:
1. move 1 step in the four cardinal directions
2. eat food
3. fight another entity of a different type
4. mate with the same type of entity to reproduce (create one more of that type of entity)

The objective is to obtain the highest score possible.
The score is calculated by:
+1 per food eaten
+1 per enemy killed
+1 per entity of that type

The inputs (neurons) are as follows:
1. position (x, y) on board
2. board size
3. types of entities in adjacent squares (including food, and null if empty)

I would like to create a program that will create hidden neurons that give rise to a sophisticated moving and attacking pattern that will allow it to obtain the highest score.

Which algorithm should I use?

I would suggest that you try to apply reinforcement learning, maybe deep Q-learning or some other form of RL.

I don't know if those are going to be the best set of features (the best way to represent the input).


Is there a way to determine whether a list of integers can be a prefix function? Say you had
(0,0,0,1,2,3,4,5,6,7,8,9,10)
or
(0,1,0,1,0,1,2,3,0,1,0,0,1)
Could you use, for example, the KMP algorithm to deduce the validity of the above lists as prefix functions? I know there is a way to find whether a substring exists in a string using KMP, but is there a way to do it the other way around, starting at the apparent prefix function and ascertaining that it is indeed a possible prefix function, without knowing the string/substring itself at the start?

Denote by $p$ the input prefix function. Refer to the characters of a word having $p$ as prefix function by their indexes $V=\{0,1,2,...,\operatorname{length}(p)-1\}$. We will keep a set of pairs $D$ of elements of $V$ to represent the characters that must be different. Finally, $V$ will be partitioned into equivalence classes according to the characters of the word that must be equal. I assume that to answer this question it is also given which is the alphabet $\Sigma$ of allowed letters to use. A possible variant of the question would give also a dictionary $L$ of allowed words.

Algorithm

A non-zero as first entry tells you right away that the sequence is not a prefix function.

Each positive value in $p$ tells you equality between certain pairs of characters of the potential word having that (presumptive) prefix function. Keep track of the equivalence classes that these equalities define, maybe with a disjoint set union data structure.

If you ever find an increase by more than $1$ ($p[k+1]>p[k]+1$) you can return immediately that it isn't a prefix function.

Whenever, the sequence doesn't increase it will also tell you one pair of characters that must be different. Collect these pairs in $D$.

Run by the pairs $D$ of vertices that must be different. If any belong to the same class return false.

Finally, consider the graph $G$ with vertices given by the equivalence classes obtained above and where the edges are the elements of $D$. If only the alphabet $\Sigma$ is given, then we compute if the vertices of $G$ can be colored with the elements of $\Sigma$ such that adjacent vertices don't get the same color. In the variant in which the dictionary $L$ is given, then we check if any word in $L$ has the length of $p$ and its characters that are in positions being in the same equivalence classes are equal, and the characters forming a pair in $D$ are different. If these conditions are satisfied we output true. Otherwise we output false.

Let's do your examples.
Example 1: Given $p=(0,0,0,1,2,3,4,5,6,7,8,9,10)$, then $V=\{0,1,2,...,12\}$. That $p[0]=0$ tells us that we don't return false right from the beginning. That $p[1]=0$ tells us that characters $0$ and $1$ must be different. So, we insert $\{(0,1)\}$ in $D$. That $p[2]=0$ makes us insert $(0,2)$ in $D$. The rest of the entries of $p$ increase by $1$. So, we never return with a false caused by an increase larger than $1$. Moreover, there are no new insertions in $D$, but we do get the equivalence classes $\{0,3,6,9,12\},\{1,4,7,10\},\{2,5,8,11\}$. Since the two pairs in $D$, $(0,1)$ and $(0,2)$ don't consist of elements belonging the same equivalence class then we output true. Well, conditional of the variants of the problem in which the alphabet is small and the variant in which the dictionary of all words are given.
For example, the word $1231231231231$ has $p$ as prefix function. Well, if the alphabet has less than $2$ letters then we could give the example $1221221221221$. If the alphabet has only $1$ letter, we would need to output false.
Example 2: Given $p=(0,1,0,1,0,1,2,3,0,1,0,0,1)$, then $V=\{0,1,2,...,12\}$. That $p[0]=0$ makes us not return false from the beginning. That $p[1]=1$ tells use that $0$ and $1$ are in the same equivalence class. That $p[2]=0$ makes us insert $(0,2)$ in $D$. That $p[3]=1$ tells us that $0,1,3$ are in the same equivalence class. That $p[4]=0$ makes us insert $(0,4)$ in $D$. that $[5]=1$, tells us that $\{0,1,3,5\}$ are in a equivalence class. I guess you can continue. At the end the only equivalence class with more than $1$ element is $\{0,1,3,5,6,9,12\}$. The rest of the characters are on their own equivalence classes. In $D$ we have the pairs $(0,2),(0,4),(0,7),(0,8),(0,10),(0,11)$. None of these consist of characters from the same equivalence class. So, we return true.
For example, the word $0010200130450$ has $p$ as prefix function.
Let me add an example that returns false to have an example of that case.
Example 3: Given $p=(0,0,1,2,3,4,2,0)$, then $V=\{0,1,2,...,6\}$. Since $p[0]=0$ we don't return false from the beginning. That $p[1]=0$ makes us insert $(0,1)$ in $D$. That $p[2]=1$ tells us that $0,2$ are in the same equivalence class. That $p[3]=2$, tell us that $1,3$ are in the same equivalence class and that $0,2$, which we already knew are also equivalent. That $p[4]=3$ tells that $0,4$ are equivalent, $1,3$, which we knew, and $2,4$, which by now we knew too. That $p[5]=4$ tells that $1,3,5$ are equivalent. Now, that $p[6]=2$ tells us that $6$ and $1$ are equivalent. That's okay so far. But it also tells us that $0$ and $5$ are equivalent. Now, the problem with that is that that makes $1$ (which is equivalent to $5$) in the same equivalence class as $0$, but $(0,1)$ is a pair in $D$. So, we will have to return false.


Network Flow with multiple connected subsets Given a set of buyers, houses, agents with the following constraints:

Agents only know a subset of buyers
Agents only know a subset of houses
Agents can only do some amount of transactions

Construct a flow network to model the problem.
Disclaimer this is homework

I have put together some thoughts on a solution to this problem.  First I realized that agents should be right before the sink node with a max flow equal to the number of possible transactions.  This would then limit the number of transactions that can flow through an agent since the max flow can't be exceeded.

I was then thinking that it would be possible to put an edge between each person and house that an agent knows (example if agent knows person A, B and house 1, 2 there are edges (A,1), (A,2), (B,1), (B,2)). Finally, connect each house that an agent knows to an agent with max flow of 1. Then by running a Ford-Fulkerson algorithm across it the inflow of the sink node would indicate max number of transactions.

However, I am concerned that there is no limit of stopping a house from being purchased more than once. I have tried building the network with various configurations (swapping houses and clients, building nodes of client/house pairs) and nothing seems to solve this specific problem.

I am mostly looking for hints to solve this problem.

Hint: think about your source node and what it is connected to.


What is an example of complex random string, in the Kolmogorov-Chatin sense? Any string generated from a PRNG clearly has a very short description.  You need the code for the random number generator, the seed, and then the number of times to iterate.  So, it seems that all such strings have low KC complexity.

If the above it true, then what is an example of a "complex" string, in the Kolmogorov-Chatin sense?

It is impossible to give a specific example of a string with high Kolmogorov complexity. If I was to give an example in this answer, then the following piece of code would retrieve it:

wget http://cs.stackexchange.com/q/9721

(plus some O(1) post-processing).

A string of high Kolmogorov complexity is as elusive as a random number:

There is in fact a connection between randomness and Kolmogorov complexity: a random string has maximal complexity for its length. (At least for one definition of randomness, appropriately called Kolmogorov randomness.)

This observation that it is impossible to exhibit a string of high Kolmogorov complexity can be put into a mathematical form and proved: it is called Chaitin's theorem.

The high-complexity strings are all the ones that you cannot describe.


What is µ A below ~ x in the Fuzzy Logic I am reading the book "Fuzzy Logic with Engineering" written by Timothy J. Ross and there is a phrase in the book at page 90, he mentions about the "Features of the Membership Function". He says:

  The support of a membership function for some fuzzy set A under ~ is
  defined as that region of the universe that is characterized by
  nonzero membership in the set A under ~. That is, the support
  comprises  those elements x of the universe such that μ A under ~
  (x)>0.

He denotes it as a graphical representation:

what is μ A under ~ (x) in this context?  Thanks in advance.

Edit Post
The μ A under ~ (x) in this context is membership function. https://www.tutorialspoint.com/fuzzy_logic/fuzzy_logic_membership_function.htm

Here μ A˜(∙) μA~(∙) membership function of A˜ this assumes values in the range from 0 to 1, i.e.,  μ A ˜ (∙)∈[0,1] μA~(∙)∈[0,1] . The membership function  μ A ˜
(∙)  μA~(∙) maps   U to the membership space M . The dot  (∙) in the membership function described above, represents the element in a fuzzy set; whether it is discrete or continuous.

In classical set theory, it is either 1 or 0.

source:

https://www.tutorialspoint.com/fuzzy_logic/fuzzy_logic_membership_function.htm


A question about halt (or stop) of Turing machine I try to understand something:
At Turing machine we have two stats: $q_{accept}$ and $q_{reject}$.

Now, if machine $M$ runs on word $w$ (I hope I write it right...) and the final configuration is: $C(w,q_t,\varepsilon )$,
 and $q_t =Q-\{q_{accept},q_{reject}\}$.

Of course $M$ don't accept $w$ and don't reject $w$, but my question is:
We can say that $M$ Stops on $w$?

I try to look for an answer but I didn't found...

Thank you!

No, Turing machine are defined in a different way than finite-automata: they don't "stop" at the end of the input, they stop whenever they reach a final state $q\in F$. Usually, there are two final states, $q_{acc},q_{rej}$ – if the machine transitions to one of these final states it stops; but until then, it keeps running.

Therefore, $\delta(q,\cdot)$ must be defined for any $q\in Q\setminus F$ and and letter the head points on. This will tell us how the machine behaves when in the state $q_t$ (using your symbol, assuming it is not a final state; see below if it is).

regarding halting without accepting/rejecting: the answer is yes. If, say, $F=\{q_{acc},q_{rej}, q_{inconclusive}\}$, and the machine reached the third final state, we can say it neither accepted nor rejected, but it halts indeed since it reached a final state in $F$. Of course, $F$ can be as large as $Q$. It may make sense for computing other task than yes/no decision problems.


Example Turing Machine for a time-constructible function I am currently reading "Computation Complexity: A Modern Approach" by Arora and Barak and have a question about time-constructible functions. In particular, I can't construct a turing machine for a simple function $f(n)=n$ using the definitions in the book.

The authors start by introducing $k$-tape turing machines: $1$ read-only input tape and $k-1$ read/write work tapes with the last one being the output tape. The tapes are one-directional and they are initialized in the leftmost cell via a special start symbol $\triangleright$. The input tape also contains the input $x$ after the $\triangleright$ symbol, in binary notation. All remaining cells contain the blank symbol $\square$. The tape-heads start on the $\triangleright$ symbol.

  A TM $M$ computes a function $f$ in $T(n)$-time if for every $x$, after $M$ is initialized in start configuration on input $x$, using at most $T(|x|)$ steps, $M$ halts with $f(x)$ written on its output tape.

They then define time-constructible functions

  A function $T \colon \Bbb N \to \Bbb N$ is time-constructible if $T(n) \geq n$ and there is a TM $M$ that computes the function $x \mapsto \llcorner T(|x|)\lrcorner$ ($\llcorner T(|x|)\lrcorner$ denotes the binary representation of $T(|x|)$) in time $T(n)$.

I have a problem constructing TMs $M$ for the functions $F(n)=n$ and $G(n)=n^2$. Let's say $x = 3$, so $|x|=2$. The machine for $F$ will have to halt after $F(|x|)=|x|=2$ steps and output $\llcorner x \lrcorner$. How is this possible if the machine heads start on the $\triangleright$ symbols?

In $2$ steps, the machine can't even read the input, since the first step is wasted by moving right from the $\triangleright$ symbol.

Shouldn't the definition make use of asymptotic notation?

I think you're right, we should use asymptotic notation, for the reason you mention, but maybe somebody more knowledeable than me can weigh in if that's wrong. Here are my thoughts: A function $T$ works as a function of the number of bits on the tape, with $|x|=\lfloor\log(x)\rfloor$. Consider the function $T(n)=n$. This function maps $x\mapsto T(|x|) = T(\lfloor\log(x)\rfloor)=\lfloor\log(x)\rfloor$. This means is must count the number of bits on the tape, erase the input, and write the number, but it has only exactly enough time to read the input, and then it must halt. But since $\log(x)<x$ for some $x$, this means the machine must, on most inputs, also move back on the tape, at least to the beginning. With a multitape Turing Machine, I can think of a $(3n+\log(n))$-time machine which computes $T(n)=n$, so I think it makes more sense to use asymptotic notation.

Note that in order to make a Turing Machine, if you have trouble when $n$ is small because $T$ doesn't grow fast enough for you, you can just hardcode the first billion values into your TM, and run an honest algorithm on the remaining numbers. This is how you overcome the problem of computing, for example, $n\cdot \log(\log(\sqrt{n}))$, which requires a lot of computation but grows very slowly.

A machine which computes $x\mapsto 2^{|x|}$: read the first $1$ on the tape, then replace all subsequent numbers by $0$ and add one $0$ to the end. And you did it in $n+1$ steps exactly! That is exponentially faster than the available time.

According to this question (link), there is an alternative source of Arora and Barak which does use asymptotic notation and one by Sipser, although it doesn't provide any explicit references. As far as I know, all other definitions (like $\text{TIME}(n)$ and $\text{SPACE}(n)$) are built around asymptotic notation anyway, so it should be perfectly legal to use asymptotic notation here.


Is the following Subset Sum variant NP-complete? Is the following problem NP-hard:

Input: $A\subset\mathbb Z, k\in\mathbb N$
Question: is there a multiset of indices $I$, such that $|I|=k$ and $\sum_{i\in I} a_i=0$?

For example, on the input $A=\{-1,2\}, k=3$ we can take $I=\{1,1,2\}$ and thus we get $|I|=3$ and $a_1+a_1+a_2=(-1)+(-1)+2=0$, as desired.

It is NP-hard.

Consider the following two variants:

Variant 1:

Input: $A\subset\mathbb N$, $s\in\mathbb N$.
Question: is there a set of indices $I$, $\sum_{i\in I} a_i=s$?

Variant 2:

Input: $A\subset\mathbb N$, $k\in\mathbb N$, $s\in\mathbb N$.
Question: is there a multiset of indices $I$, such that $|I|=k$ and $\sum_{i\in I} a_i=s$?

It is easy to see variant 1 is NP-hard. It is also easy to reduce variant 2 to your variant in polynomial time by transforming each element $e$ in an instance of variant 2 to $ke-s$. So if we can prove there is a polynomial-time reduction from variant 1 to variant 2, the proof is completed.

The reduction from variant 1 to variant 2 is exactly the same as the one posted by Kristoffer Arnsfelt Hansen in this answer. I rewrite it here for consistency of symbols.

Given an instance of variant 1, assume that $a_i < B$ for all $i$. We will have two new elements for each old element, simulating whether the element is used 0 or 1 times. For element $a_i$ we get two new elements $a^1_i = (2^{n+1} + 2^i)nB + a_i$ and $a^0_i = (2^{n+1} + 2^i)nB$. The new target sum is defined as $s' = (n2^{n+1} + 2^n + \dots + 2^1)nB + s$. The number of elements required in a solution is set to be $n$.

Note in a valid solution of the new instance, for each $i$, the number of $a_i^1$ and that of $a_i^0$ must be exactly $1$ in total, so there is exactly $n$ elements in a valid solution. This is indeed a polynomial-time reduction from variant 1 to variant 2.


P class definition in Garey and Johnson's Computers and Intractability I'm reading right now Computers and Intractability by Garey and Johnson. I've found the definition of PTIME complexity class a little strange. This is how it looks:

Let $\Sigma = \{ 0,1\}$. By $\Sigma^{*}$ we denote the set of all finite strings created from symbols from $\Sigma$. If a computation on a Deterministic Turing Machine with input $x \in \Sigma^{*}$ ends in $q_{y}$ (yes-state), it means that TM accepts this input. Language $L_{M}$ recognised by the machine $M$ is given by:

$L_{M} = \{ x \in \Sigma^{*} :$ $M$ accepts $x \}$.

Time complexity function is given by:

$T_{M} = max\{ m : $ there is an $x \in \Sigma^{*}$, with $|x| = n$, such that the computation of $M$ on input $x$ takes time $m$$\}$.

We call program $M$ a polynomial time DTM program if there exists a polynomial $p$ such that, for all $n \in \mathbb{Z}^{+}$, $T_{M}(n) \leq p(n)$.

Then they give such $P$ class definition:

$P = \{ L :$ there is a polynomial time DTM program $M$ for which $L=L_{M} \}$

Does this mean that their P complexity class contains only languages that are composed of yes-instances, i.e. languages recognised by $M$, consisted of $x$ strings such that $M$ always halts in accepting state for every of them as an input? What about input that also causes halting, but in rejecting state $q_{n}$? Shouldn't these be also in PTIME?

Do I understand this correctly? If yes, why they decided to define P class in such way?

P.S. Maybe that matters, I have the first edition of the book (1979).

The definition given is the standard one.  Before reading the rest of this answer, I recommend that you carefully go over the definition again. A lot of what you're asking is "What does the definition say?" and you'll probably understand it better if you figure it out yourself. The rest of your question is, "Why did we choose that definition?"

The definition is equivalent to the following. A Turing machine $M$ "runs in polynomial time" if there is some polynomial $p$ such that $M$ halts in at most $p(n)$ steps for all inputs of length $n$. A language is in P if it is the set of strings accepted by some Turing machine that runs in polynomial time.

  Does this mean that their P complexity class contains only languages that are composed of yes-instances, i.e. languages recognised by $M$, consisted of $x$ strings such that $M$ always halts in accepting state for every of them as an input?

Yes, that's what the definition says. It also says a little more: the language recognised by $M$ doesn't include any of the "no" instances.

  What about input that also causes halting, but in rejecting state $q_{n}$?

If a machine runs in polynomial time, it halts for all inputs. Thus, for any given input, the machine either accepts or rejects. The whole point is that the Turing machine tells you exactly which inputs are in the language and exactly which inputs are not.  If the machine rejects an input, that input isn't in the language.

  Shouldn't these be also in PTIME?

This is a category error. P is a class of languages, not inputs.

However, you might be thinking of the following. We could also define a language that is the set of strings rejected by some Turing machine that runs in polynomial time. Perhaps you're wondering why that language isn't in P? Well, it is, because it's also the set of strings accepted by some polynomial-time Turing machine. Just take the machine that defines the language by rejecting and modify it so that every instruction "go to the accepting state" becomes "go to the rejecting state" and vice-versa.  Now you have a Turing machine that defines the language you're interested in, but defines it by acceptance.


Can we easily check if we can place two not-intersecting circles inside a convex polygon We have given convex polygon of $N$ vertices, and two circles of radius $r$. Is it possible to check if we can place those two circles completely inside the polygon, such that they don't intersect, but they might have one point in common.

For example if we have given square with sides of length $1$, and $r = 0.25$. Then the answer should be yes, as we can place those two circles.

Let $P$ be the given polygon. Let $Q$ be the set of points inside $P$ whose distance to the boundary of $P$ is at least $r$. Your requirement can be met iff the diameter of $Q$ is at least $2r$. Indeed a radius $r$ circle lies inside $P$ iff its center is in $Q$, and two such circles are disjoint iff the distance between their centers is at least $2r$.

The problem of finding $Q$ is called inward polygon offsetting. That link has a lot of discussion about the general case, but it should be much simpler when $P$ is convex.

Suppose the vertices of $P$ are $p_1,\ldots,p_n$ in counterclockwise order. Let $R$ denote rotation counterclockwise by $90^\circ$. Let $n_i$ be the outward unit normal vector to edge $p_ip_{i+1}$, namely $n_i=R(p_i-p_{i+1})/|R(p_i-p_{i+1})|$. Let $e_i$ denote this edge shifted by $r$, namely the line from $p_i-rn_i$ to $p_{i+1}-rn_i$. Now we can iteratively construct a path $q$ which will become the boundary of $q$. In iteration $1$, let $q=e_1$. In iteration $i$, find the intersection of $q$ with $e_i$, discard the part of $q$ after the intersection and append the part of $e_i$ after the intersection (we should look for the intersection starting from the end of $q$; the more segments we have to check, the more vertices we can discard, so the algorithm will still be $O(n)$). After $n$ iterations, find where $q$ intersects itself and discard excess vertices to obtain a closed path; this is the boundary of $Q$.

Once we have $Q$, we can find its diameter using the Rotating calipers algorithm.


Confused by proof of correctness of Majority I have been studying a streaming algorithm to determine if there is a majority element in a stream. But am confused by a proof for it.
The algorithm works as follows. You keep one counter $c$ and a store for one item called $a^*$. When a new item arrives, first you check if $c == 0$. If so you set $c=1$ and $a^*$ stores the arriving item. Otherwise, if $c>0$ and the arriving item is the same as $a^*$ you increment $c$ or decrement $c$ if not.
If there is a majority element then it will be stored in $a^*$ at the end.
In the notes from http://www.cs.toronto.edu/~bor/2420f17/L11.pdf there is a proof of this fact (called simpler proof).

I can see that if there is a majority item then $c'$ will be positive at the end of the stream.  But:

How do we know that $a^*$ will hold the majority item at the end?
Does $c'$ being positive imply that $c$ will be positive too?

At each step,

if $c == 0$, set $c=1$.
Otherwise, if $c>0$, either increment $c$ or decrement $c$.

Since $c$ is 0 initially, it is always true that $c\ge0$. That means, $-c\le0$ all the time.

Suppose, at some moment, $c'$ is positive. The definition of $c'$ says $c'=c$ when $a^*=v$ and $c'=-c$ otherwise. Since $-c\le0$, $c'\not=-c$. So, the situation cannot be "otherwise". The situation must be other than "otherwise", i.e, $a^*=v$ and, hence, $c'=c$.
We just proved that for any moment, if $c'$ is positive, then $a^*=v$ and $c=c'$ is also positive.
Now just apply the above conclusion to the very last moment.


What is the abstract idea of a semaphore and how can we use it to implement mutual exclusion? So I've got this so far to try and wrap my head around the abstract idea of a semaphore:

  A semaphore is a variable or abstract datatype (commonly an integer),
  used to control access to a common resource by multiple processes in a
  concurrent system.

I'm not sure that this definition fully encompasses the full idea of semaphores.

As well as this, I'm not sure how we could use them to implement mutual exclusion.

Any notes to help me understand this concept is appreciated!

A semaphore is a counter, that counts the number of processes that have access to a resource. If a resource can service n processes, n is decremented each time a process accesses the resource, and increments it when the process no longer needs the resource. When n reaches zero, the access of the resource is denied.

A real life example will make things clear: imagine a public toilet with 5 toilets (n=5). At the entrance there is a guard (the semaphore). If some one wants to enter the guard looks at n. if n > 0 the guard let the visitor in and decrements n. If someone comes out n is incremented. Only if n=0 the guard will block the entrance until someone leaves.

Consider a binary semaphore, where n = 1. This semaphore works as a flag which is activated when the resource is in use or not, and can be used to protect a critical section. When a process wants to enter the critical section, it first looks at the ‘flag’ to find out if the critical section is being used by another process. If not, the process enters and raises the flag, preventing the other processes to enter. The flag is unset when the process leaves, and therefore ensures mutual exclusion.


What's the difference between a rule based system and an artificial neural network? I'm currently doing some reading into AI and up to this point couldn't find a satisfying answer to this question: what's the difference between a rule based system and an artificial neural network?

From my understanding both are trying to do inference based on a variety of different inputs.

The difference is vast, although as Dave wrote, the resulting black box might look the same from outside. Rule-based systems are examples of "old style" AI, which uses rules prepared by humans. Neural networks are examples of "new style" AI, whose mechanism is "learned" by the computer using sophisticated algorithms, and as a result, we humans don't really understand why it works. While in some cases rule-based systems could be effective, the general trend in AI has been to switch to machine-learning algorithms such as neural networks, due to their much better performance.


Black-box combinatorial optimization problem over permutations I am solving general black-box optimization problems like:
x*: f(x) -> min, where x are permutations of length N (N = 50 for example, so brute force search is not possible). Objective function f(x) is represented by stand-alone computer code and x represents configuration of complex system with the response simulated by f(x).

I learned, that in this case I can use many heuristic methods. But, most of these methods use always some kind of local search, which require suitable distance metric at search space (space of permutations x in my case). Under suitable distance metric I mean the metric which fulfill the "locality" property, e.g. small change of permutation x produce small change of objective function f(x). In my case is not known any suitable distance metric with this property, so any kind of local search is nearly the random search.

I have a few questions:

Are there available any heuristic black-box combinatorial optimization methods, which does not use local search and/or any distance metric at search space? I need to overcome the low "locality" of the problem or simply the fact, that any suitable distance metric at search space is unknown.
Is the "locality" property really so restricted at combinatorial optimization in general? May be I miss something..., but the most of real-world black-box combinatorial problem has low or very low "locality" due to the fact, that the common permutation distance metrics (Hamming, Kendal, etc.) are not suitable metrics in general.
Is there any general method how to find suitable distance metric at search space to satisfy at least approximately the "locality"?

Additional remarks:

In real, the black-box function f(x) is realized by stand-alone deterministic simulation code, where x plays a role of discrete configuration of the simulated physical system. So, function f(x) has definitely well defined properties, but this properties are so difficult, that is not possible to simple exploit it.
Because of above mentioned complicated internal properties of function f(x) is not possible to find proper distance metric d(x,x') in search space which fulfill "locality" (similar x and x' in a sense of any distance metric produce similar responses f(x) and f(x'))
So, finally, I am looking for any optimization heuristics, which are able to find any suitable sub-optimal solutions only by informations available by properties of f(x) at fitness space. Like EDA's (Estimation of Distribution Algorithms) for example.

The main reason of this question is, what types of optimization heuristics are suitable to solve this kind of problems.

In general if you know nothing about f and it can be totally arbitrary, then there is nothing you can do: you cannot do better than brute-force.  If f has no structure, no properties, no regularities, and is just totally random, then it is easy to see that any algorithm has to compute f on all $N!$ possible permutations to find the minimum.

In practice it is common to deal with functions f that do have some degree of structure.  For instance, if x,x' are similar (for some notion of similarity), then f(x),f(x') might have a good chance of being similar.  In those cases you can use techniques like local search.  But if you don't have that property, then you can't use local search, and you may be back to a situation where you cannot do any better than brute force.

There are other approaches in other situations: e.g., if we know the symbolic expression for f, we might be able to use a SAT solver, especially if that symbolic expression is not too large.  But again this requires f to have some structure and not be totally arbitrary.

There are no silver bullets.  You need to know something about f to have a hope of doing anything.


Mergesort and some claims on comparison suppose for $n$ elements we using mergesort.
each number compared at most $O(\log n)$ = False
in average each element compared with $O(\log n)$ elements = True
there exist an element compared with $\Omega (\log n)$ elements = True
is there anyone can share idea about these facts (i.e: why first is false and others is true).

For the first fact, consider the array $1,\ldots,n,n+1,\ldots,2n$. Sorting its two halves doesn't alter the array. When the two halves are merged, the element $n+1$ would be compared against all elements in the left half.
The second fact is true for every $O(n\log n)$ sorting algorithm: such an algorithm performs $O(n\log n)$ comparisons overall, and so $O(\log n)$ comparisons per element on average.
The third fact is true for every comparison-based algorithm: any such algorithm must perform $\Omega(n\log n)$ comparisons, and so $\Omega(\log n)$ comparisons per element on average; in particular, some element is compared $\Omega(\log n)$ times.
Finally, let us note that the AKS sorting network corresponds to a sorting algorithm which performs $O(\log n)$ comparisons per element (since its depth is $O(\log n)$, and each element can only be compared once in each layer).


Computing binomial coefficients and factorials modulo a composite number Does anyone know of a fast algorithm to compute factorials and/or binomial coefficients in general or modulo a composite number in particular (for composite moduli I am interested in the case where the factorization is not necessarily known)  I know that for primes and factorials we can apply Wilson's Theorem but I was wondering if there is also a fast method for composite numbers.  For binomial coefficients I was thinking of using recursion and the addition rule: $$\binom{n}{x} + \binom{n}{x+1} = \binom{n+1}{x+1}$$ somehow but I'm not sure really how to go about it.  Any suggessions?  Thanks.

If $p$ is prime and $n = n_\ell \ldots n_0$, $x = x_\ell \ldots x_0$ in base $p$, then (Lucas' theorem)
$$ \binom{n}{x} \equiv \binom{n_\ell}{x_\ell} \cdots \binom{n_0}{x_0} \pmod{p}. $$

For a product of distinct primes, you can apply the Chinese remainder theorem. So it remains to deal with prime powers. Such a method is described in this paper of Andrew Granville, though it's not as nice as the formula above.


graph theory conventions, difference between a PATH and a GRAPH? Consider this example, I did my pseudocode in python

findCycle(G):
    for each edge e in E(G):
        if isThereCycle(G-e):
            G = G - e
    return G

assume isthereCycle returns whether the graph $G$ has a cycle.

Input is a graph $G$ that contains a cycle, and the function should return a path of that cycle.

We go through each edge then remove it and see if a cycle still exists without that edge, until we are left with a graph with a single path that is a cycle. (Assume removing the edge (G - e) doesn't mutate the graph unless we do G = G - e).

I want to return a path. Is what I'm returning a path?

Your algorithm returns a cycle rather than a path.

Here is a cycle:

Here is a path:

(Both images taken from Wikipedia.)

To get a path from the cycle, simply remove one edge (this is my best guess for what return a path of that cycle means).

Let me also mention that your algorithm is very inefficient. A much better choice is to use BFS/DFS.


Natural deduction: understanding bottom elimination (¬e) I am new to natural deduction and upon reading about various methods online, I came across the rule of bottom-elimination in the following example.

I do not understand the step in line 10.

Upon inspection, my initial thought would be that the assumption of ¬p and p both being true is absurd, hence anything can be inferred ( in this case 'p'). However, if this were the case where would you stop (this seems to be an overly powerful tool)? So I assume that this idea is wrong.

Could someone help me understand the rule?

NOTE: I came to StackExchange due to the lack of resources and specific information online.

Usually in practice we weld the two steps together and just say that from $p$ and $\lnot p$ anything follows, but in formal logic this is a combination of two rules of inference:

$p$ and $\lnot p$ both together entail falsehood $\bot$,
from $\bot$ anything follows.

These are precisely lines 9 and 10 in your proof.

We often take $\lnot p$ to be an abbreviation for $p \Rightarrow \bot$, in which case the rule "from $p$ and $\lnot p$ follows $\bot$" is just a special case of modus ponens "from $p$ and $p \Rightarrow r$ follows $r$".


Iteration vs Recursion question in Lisp method I am curious if the following method would be called iterative or recursive:

(define (deep-reverse items)
  (define (iter things answer)
    (cond ((null? things) answer)
          ((pair? (car things))
            (iter (cdr things) (cons (deep-reverse (car things)) answer)))
          (else (iter (cdr things) (cons (car things) answer)))))
  (iter items ()))

I am confused because iter only calls itself with the state variables things and answer as arguments, and modifies those each run, so that I think it is iterative. It is defined in a method deep-reverse that does recursively call itself... This is confusing to me because there are elements both of iteration and recursion in this method, so that I don't know in the end how I would classify it... Is deep-reverse recursive? Is iter iterative?

Thank you.

Since deep-reverse and iter call each other, they are (mutually) recursive.
Their combination is not tail recursive however, so deep-reverse is not iterative in the scheme parlance (IOW, does not admit tail call optimization).

PS. A proverbial sufficiently smart compiler (and, in fact, many real ones) can compile this function into an iteration (i.e., not using the function call stack).


How did MacLisp's garbage collector "run in the register set"? Olin Shivers, ‘History of T’:

  Maclisp on the [PDP]-10 had used a mark&sweep GC (one version of which famously "ran in the register set," though that is another story)

This implies, in my interpretation, that the garbage collector used no storage other than the registers of the machine. Is my understanding of this correct, and if so, how did it achieve this efficiently? Was a paper ever published on its implementation?

The 16 high-speed registers of the PDP-10 ISA were addressible as locations 0-15 of physical memory, so that the code literally could run in the registers if it was short enough and you could devote a block of registers to it.  Not only could it use registers for temporary storage, it could use them as a code cache as well.


CIRCUITSAT ∈ DTIME(2^n/n^c) ⟹ NP ≠ EXP? $\mathsf{EXP}\not\subseteq \mathsf{DTIME}(2^{n})$ and $\mathrm{CIRCUITSAT}\in \mathsf{DTIME}({2^{n}})$ holds and so why does $\mathsf{NP}\neq \mathsf{EXP}$ not hold while we know $\mathsf{NP}\subseteq \mathsf{DTIME}({2^{n}})\implies \mathsf{NP}\neq \mathsf{EXP}$?

Does $\mathrm{CIRCUITSAT}$ in any of $\mathsf{DTIME}(\frac{2^{n}}{n^c})$, $\mathsf{DTIME}({2^{\sqrt n}})$ or $\mathsf{DTIME}({2^{(\log n)^2}})$ $\implies \mathsf{NP}\neq \mathsf{EXP}$?

$\mathsf{CircuitSat\in DTIME(2^n)}$ does not imply $\mathsf{NP\subseteq DTIME(2^n)}$ since the reduction might increase the input's size. Suppose for example that $L\in NP$ and the reduction from $L$ to $\mathsf{CircuitSat}$ maps strings of length $n$ to strings of length $n^c$ (for all $n\in\mathbb{N}$), then applying the reduction and using a naive exponential time algorithm for circuit sat yields a $2^{n^c}$ time algorithm for $L$.

If however you can place an NP-complete problem in a subexponential time class, e.g. $n^{\log n}$, then $NP\neq EXP$, since $n^{O(\log n)}$ is closed under polynomial transformations, i.e. $n\mapsto n^c$.


Show that every definite language is accepted by a finite automaton A language $L$ is definite if there is some $k> 0$ such that for any string $w$, whether $w \in L$ depends on the last $k$ symbols of $w$. How can I prove that every definite language is accepted by a finite automaton?

This is true as a consequence of the Myhill Nerode theorem. For any fixed $k\gt 0$, the number of possible combinations of the last $k$ symbols of any string $w\in L$ is $|\Sigma|^k$, where $\Sigma$ is the alphabet.

Any two strings that have the last $k$ symbols identical will always be both accepted or both rejected by $L$, for any string appended to them, i.e., no string in $\Sigma^*$ will distinguish such strings. Thus, such strings lie in the same equivalence class of $L$.

Strings with differences in their last $k$ symbols will either lie in different equivalence classes or will cause the classes demarcated in the previous step to collapse together into a single class.

Thus, the equivalence classes of $L$ are determined by the last $k$ symbols of $L$.

As the possible combinations of the last $k$ symbols is finite, the number of equivalence classes is finite. Thus, by the Myhill Nerode theorem, the language $L$ is regular. Hence, there exists a DFA that accepts $L$.


DBMS: MINIMUM NUMBER OF TABLES REQUIRED TO REALIZE THIS ER MODEL I was following a discussion on a forum where they have posted a question like this-->

Some people are saying that we can merge A,B,C in a single table and m:n relation of A and C in another table having foreign key. Thus 2 tables are required. Where as another person is saying that A,B,C cannot be merged as if we merge A,B,C then it means that the A and C sharing the same row must have relation. So we need at-least 3 tables, one for AB another for BC and another one for AC. So which is correct? 2 tables or 3 tables. I am pretty much confused with this.

The issue is that it cannot really be answered unless you give more constraints.

It can be implemented using only one table. Ugly but doable. Each record would be the union o fields needed plus one “type” field. There will be very little of help from the database in keeping referential integritet.


What is an upright rectangle? What is an upright rectangle?

I came across the phrase in my homework -

"The bounding box of a set of S points is the smallest upright rectangle containing S. Describe and analyze an algorithm to compute the bounding box of n points in the plane using fewer than 3n comparisons."

Can anyone explain to me what is meant by an upright rectangle?

Most likely it means an axis-aligned rectangle, i.e., a rectangle whose bottom edge is horizontal (parallel to the $x$-axis) and whose left edge is vertical (parallel to the $y$-axis).  This is the standard meaning of "bounding box".  For future reference, before asking it is useful to check Wikipedia and search thoroughly.  In this case you would have found lots of information on the phrase "bounding box": see, e.g. https://en.wikipedia.org/wiki/Minimum_bounding_box and https://en.wikipedia.org/wiki/Minimum_bounding_rectangle


Clustering a set of point by affine transform We are given a set of $n$ points on the plane $a_i = \{x^a_i, y^a_i\}$ and $b_i = \{x^b_i, y^b_i\}$.
Assume that the points b are an affine transform of the points a, we can find a matrix $M$ and vector $t$ such that $\sum_{i=0}^{n-1} ||M a_i + t - b_i ||^2$ is minimized, in fact, we can even do so analytically.
Assume however that the points a_i are composed of different subsets to which a different affine transform was applied.
Let $\epsilon$ be a small, tolerance value. A partition $\cup_{j=0}^m P_j = [1\ldots n] \wedge \forall j, k, P_j \cap P_k = \emptyset$ is said to be admissible iff
$$\forall j,~ \exists M_j, t_j,~ \forall i \in P_j,~ ||M_j a_i + t_j - b_i||^2 < \epsilon$$
Simply speaking, we partition the points into different subsets each of which is sent to $b$ with its own affine transform.
An admissible partition always exists because it's always possible to sent a to b exactly if each point is given its own affine transform (in fact, every 3 points can be sent to any other 3 points).
We want to cut up the points in as few pieces as possible: an admissible partition is minimal when it has fewer or equal subsets than any other admissible partitions.
How would one go about finding an admissible partition? Heuristics and approximate solutions are welcome. One approach would be to consider the transformation defined by every triplet of points and try to cluster those together, but this requires looking at $O(n^3)$ transforms.

I would suggest you try using RANSAC.  Randomly pick a triplet of $a$ points and $b$ points, find an affine transformation that maps the former to the latter, find all other points that it maps well, and create that as a candidate cluster those.  Repeat many times, and keep the best cluster.  Remove the points in that cluster, and then repeat.
This might perform better than your $O(n^3)$ time solution if you expect to have a few large clusters (but probably it is not better if you expect to have many small clusters).


Are nearly all natural numbers compressible? A simple counting argument shows most strings can't be compressed to shorter strings. But, compression is usually defined using Kolmogorov complexity. A string is compressible if its Kolmogorov complexity is less than its length, $K(s) < |s|$. The Kolmogorov complexity of a string is defined as the size of the smallest Turing machine (TM) that writes the string and halts when given a blank tape. I want to define the size of a TM as the number of states the machine has. I want to use a simple type of TM known as a Busy Beaver. BB's use two symbols, 0 and 1. A BB blank tape is initialized to all 0's and is unbounded in both directions.

Let the Kolmogorov complexity of natural number $n$, $K(n)$, be the number of states in the smallest BB that writes $n$ 1's and halts when given a blank tape. I use this definition so I can use known results about busy beavers, particularly Rado's sigma function, $\sum(n)$. $\sum(n)$ is defined as the maximum number of 1's an n-state BB can write and halt when given a blank tape. It is known $\sum(n)$ grows faster than any recursive function. This shows there is no recursive limit on how much a natural number can be compressed.

$\sum(2)=4$ so $K(4)=2$. This means 4 is a compressible number. This is the definition of the BB:

A0: 1RB / B0: 1LA

A1: 1LB / B1: 1RHalt

"A0: 1RB" means in state A on input 0 write 1, move one position right, and switch to state B. We can "extend" this machine to create new machines that compress natural numbers. To extend this machine replace the halt state with a new state. On input 0 this state writes 1 and halts. On input 1 it writes 1, moves one position right, and stays in the same state.

A0: 1RB / B0: 1LA / C0: 1RHalt

A1: 1LB / B1: 1RC / C1: 1RC

This 3 state machine writes 5 1's and halts. This proves $K(5) \leq 3$ and 5 is a compressible number. In fact, all numbers greater than 3 are compressible by at least 2 because we can write the first 4 1's using only 2 states. $\forall n(n>3 \rightarrow K(n) \leq n-2)$

We know natural number $n$ can be represented as a binary number with $log_2(n)+1$ bits. Let a number be super compressible if $K(n) < log_2(n)+1$. We see 4 is super compressible because $K(4)=2 < log_2(4)+1 = 3$. It is known $\sum(5) \ge 4098$. This means $K(4098) = 5$ and 4098 is super compressible. By extending this 5-state machine we can show 4099 through 4107 are also super compressible. In general, the range $\sum(n)$ through $\sum(n)+log_2(\sum(n))-n$ will be super compressible. For example, it is known $\sum(6) \ge 3.515 * 10^{18267}$. This proves the range $3.515 * 10^{18267}$ through $3.515 * 10^{18267} + log_2(10^{18267})$ is super compressible.

Are all large enough natural numbers super compressible? If not, why not?

Note there are lots of machines besides the ones defined by $\sum(n)$. There are probably lots of halting 5-state machines that write more that $2^5$ 1's and less than 4098 1's. All such machines define ranges of super compressible numbers. I previously asked a similar question without getting an adequate answer.

For every $n$ there is a "busy beaver" machine (i.e., a Turing machine on the tape alphabet $\{0,1\}$ run on the empty tape) which outputs $1^n$ using $O(\log n/\log\log n)$ states, which is asymptotically optimal (up to constants).

Here is how this machine works. For every $C$, we will construct such a machine having $O(\log n/C) + O(C2^C)$ states. The machine will first write the binary representation of $n$, and then use $O(1)$ states to convert it to its unary representation (that is, $1^n$); we will only describe the first phase.

The machine runs in $\log n/C$ rounds, maintaining a unary counter whose value at round $r$ is $1^r$ (after all the rounds finish, we erase the counter). At each round, we write $C$ bits of the binary representation of $n$. This is accomplished using $O(C2^C)$ states which implement adding $C$ bits (for which choice of $C$ bits), and $O(\log n/C)$ states for control (we use the unary counter to switch control to the correct state). This completes the description of the machine.

A machine with $S$ states on the binary tape alphabet has description size $O(S\log S)$. Hence we expect that the optimal answer be $O(\log n/\log\log n)$. Indeed, if we choose $C$ very carefully to be $\log (\log n/(\log\log n)^2)$, then the construction above gives a "busy beaver" machine with $O(\log n/\log\log n)$ states, which is optimal up to constants.

If the tape alphabet is allowed to grow with $n$, then $O(1)$ states suffice to output $1^n$: the alphabet will be of size $n + O(1)$, and we will use a certain cell as a counter. This construction shows that it is important to limit the tape alphabet.


Minimum words in a string given a dictionary The question is: Given a dictionary consisting of a set of words and a string: find the minimum number of words the string can be split into. If the string can not be decomposed into a list of words return -1.

I tried finding the longest prefix and proceeding but that doesn't seem to work. I searched this question online and found a similar stack exchange question but I believe that the solution provided is wrong. It looks like this person is finding the longest suffix and proceeding but this approach doesn't work. Link to similar question

The reason this doesn't work is because: Suppose the dictionary is:{i,iiiiface,facebook,book} and input instance is 'iiiiifacebook'. The given solution would select 'facebook' and then continue to select 5 'i's' making a total of 6 words when infact the optimal solution is: (book,iiiiface,i) which is just 3 words. Please correct me if I'm wrong.

Please help me find the optimal (DP) solution to this problem.

One possible approach to solve this problem is as follows:-

(1) Create a trie of the dictionary for fast matching.

(2) Create a recursive function that does the following:-

(a) Finds all possible prefixes of the current string that are present in the dictionary.

(b) Calls itself recursively with those prefixes removed

Example:-

Word:- keyboardrocks
Dictionary:- {key,keyboard,keyboardrock,s,board}

f(keyboardrocks)->f(boardrocks)
                ->f(rocks)
                ->f(s)

(c) Recurse until the string is reduced to an empty string.

(d) The minimum recursion depth will be the required answer.

What can be done to better the runtime complexity?

You can use memoization to remember the minimum number of words that were needed to construct a prefix of length m of the string in an array.

So now, MinWord[1,n]=MinWord[1,x]+findMinWord[x,n]


Non recursively enumerable language proof by reduction to non-HP I am trying to understand how the reduction proof for non r.e. languages works by following the examples from this website. In most cases to prove that a language is not r.e., you can reduce the language to the non halting problem which is not r.e.

For example, if I have

$$L_2 = \{\langle M\rangle\mid M \text{ is a TM and }|L(M)|\leq 3\}\,.$$

I construct $\tau(\langle M, x\rangle) = \langle M'\rangle$ such that $M'$ on input $w$: it
erases its input, copies $M$ and $x$ to its tape, and runs $M$ on $x$; it accepts if $M$ halts on $x$. Then I prove the reduction is valid (see website)

But then if I have the language

$$L_4 = \{\langle M\rangle\mid M\text{ is a TM that accepts all even numbers}\}\,,$$

I construct $\tau (\langle M, x\rangle) = \langle M'\rangle$ such that
$M'$ on input $w$: it
runs $M$ on $x$ for $|w|$ steps; it rejects if $M$ halts on $x$ within $|w|$ steps, and accepts otherwise.

I know this may sound like a stupid question but beginnings are always hard until you understand the main logic behind it but why does $M'$ need to reject when $M$ halts? Why not accept when $M$ halts like in the first case?

From a programming perspective, a reduction argument is often like this: "If you have a subroutine that can effectively solve problem A, here's how you can use it to solve problem B. But problem B is unsolvable, therefore no such effective subroutine exists."

In your case, the non-halting problem (Is my input $\langle M, w\rangle$ a Turing machine and a word that makes it loop forever?) is not recursively enumerable. If we can make it recursively enumerable by adding an effective subroutine for problem B, then no such subroutine for problem B exists.

The language $L_2$ of Turing machines that accept three or fewer strings is not r.e. If it were, then there's a subroutine B which recognizes whether a TM accepts three or fewer strings.  So: imagine a program that takes in a machine $M$ and a word $w$. The program makes a new machine $M^\prime$ which ignores its input and simulates $M$ on $w$. If the simulation finishes, $M^\prime$ accepts; otherwise it loops forever.  So, $M^\prime$ accepts all inputs if $M$ halts on input $w$. $M^\prime$ doesn't accept any strings if $M$ loops forever on input $w$.

Our program makes $M^\prime$, then asks B whether $M^\prime$ accepts 3 or fewer strings. If it does, $M$ must loop forever on input $w$. We should accept ("LOOPS FOREVER"). Otherwise, we don't ("DOESN'T LOOP FOREVER").

Because our program solves an unsolvable problem with help from B, such a subroutine B cannot exist.

The language $L_4$ of Turing machines that accept all even numbers is not r.e. If it were, then there's a subroutine C which recognizes whether a TM accepts all even numbers.  So, imagine we have a program that takes in a machine $M$ and a word $w$. The program makes a new machine $M^\prime$. On input $x$, the machine simulates $M$ on $w$ for $|x|$ steps, then rejects if $M$ has finished by then; otherwise it accepts. So, $M^\prime$ uses its input as a timer: it rejects all strings that are longer than the number of steps $M$ takes to halt on $w$. (If $M$ never halts, $M^\prime$ accepts all strings. If $M$ halts, $M^\prime$ accepts all short strings and rejects all long strings.)  So if $M$ never halts, $M^\prime$ accepts all strings, specifically including all even numbers. If $M$ halts, $M^\prime$ rejects all long strings, specifically including all large even numbers.

So, our program constructs $M^\prime$ and asks C whether it accepts all even numbers. If C says yes, it means that $M^\prime$ accepts all strings because $M$ loops forever on $w$. We accept ("LOOPS FOREVER").  If C says no, it means that $M$ eventually halts on input $w$. We reject ("DOESN'T LOOP FOREVER").

In both cases, $M^\prime$ uses "accept" to mean "LOOPS FOREVER", and "reject" to mean "DOESN'T LOOP FOREVER". In the first case, we made $M^\prime$ accept all strings when $M$ doesn't loop forever. In the second case, we made $M^\prime$ accept all strings when $M$ does loop forever. Those differences contributed to the discrepancy.