# Question
Title: Struggling to disprove this flow network question
> Consider a flow network $G$. Let $(S, T)$ be a min-cut of $G$. Let $(u, v)$ be an edge that crosses the cut from $S$ to $T$. Claim: increasing the capacity of $(u, v)$ causes the value of the maximum flow in $G$ to increase.

I'm 99% sure this is false, but I'm struggling to disprove it. Can anyone give me some tips to find a counter-example?

I thought of making a graph with a cut and having two edges run through this cut such that one is the minimum and one is greater; increasing the greater one won't change the max-flow by the min-cut theorem.

# Answer
Since this is a homework question, I'll provide a hint.

Instead of having two edges in the cut, why not try with only one? What if your graph is only one long path?
> 0 votes

---
Tags: data-structures, network-flow
---


# Question
Title: Why isn't there a computational "Carpenter's Algorithm" for Planar Convex Hull?
Planar Convex Hull is a problem where you have $N$ points in a Cartesian plane, and you want to find the smallest convex polygon that encloses the points. QuickHull seems to be the best available algorithm for this, and it finds the hull in $O(N \log h)$ where $h$ is the size of the output.

Interestingly, Michael Shamos points out in his 78 PhD thesis that there's a much simpler physical algorithm (call it the Carpenter's algorithm) which solves Convex Hull in time complexity $O(N)$. Just take a wooden board, hammer a nail in for each point of the set, and wrap a rubber band around the points to determine the convex hull.

I'm totally bewildered by this apparent discrepancy. Why haven't we developed a computer program to solve Convex Hull in $O(N)$ time?

# Answer
> 3 votes
Carpenter's algorithm isn't implementable in a computer and makes assumptions that are not realistic in practice, such as that nature works with infinite-precision arithmetic and that you can choose the location of the nail with infinite precision in constant time and that the rubber band will find the global optimum in constant time and that you can measure in constant time whether a particular nail is touching the rubber band. As such Carpenter's algorithm is basically a cute idea that is most likely a distraction for purposes of understanding how fast you can solve very large problems in practice.

See also NP-complete Problems and Physical Reality, Scott Aaronson, SIGACT News, vol 36 no 1, March 2005.

# Answer
> 2 votes
Nail all $n$ points in time $O(n)$. Then sweep a vertical taut rope from far left until you hit the leftmost nail. Next you have two options:

* rotate the two ends until you hit other nails, and continue until you complete the hull "by wrapping". This takes $O(h)$ sweep operations, as you wind every nail once and unwind at most once.
* wind the rope to the next two nails (up and down) in angular order, and as long as the rope forms a reflex angle, unwind from the angle vertex. This takes at most $O(n)$ operations.

What we are missing is the operation "sweep to the next nail" in constant time. The best we have is a sweep in time $O(n)$, or a sweep in constant time $O(1)$ after preprocessing by sorting, $O(n\log n)$.

---

Should I add that none of this makes sense as long as you have not defined a real cost function ?

---
Tags: algorithms, optimization, computational-geometry, convex-hull
---


# Question
Title: Sorting a collection of tuples using merge rearrangements
Given a collection of tuples $X=\\{(x\_1,y\_1),\dots,(x\_n,y\_n)\\}$, where elements $x\_i, y\_i \in R\_{\geq 0}$ are non-negative real values. The collection $X$ is sorted if $x\_i \leq x\_{i+1}$ and $y\_i \leq y\_{i+1}$ for all $i \in \[n-1\]$. Sorting $X$ is not always possible for instance if the given input has two tuples $(x\_i,y\_i), (x\_j,y\_j)$ such that $x\_i \> x\_j $ and $y\_i \< y\_j$ for some $i \neq j$. So we want to merge tuples in $X$ so that the resulting collection is sorted and the merge operation $\phi(i,j,k)$ is defined as

$$\phi(i,j,k) := \Big\\{\text{delete}~(x\_i,y\_i), (x\_j,y\_j)~\text{from}~X~\text{and insert}~\big(\frac{x\_i+x\_j}{2}, \frac{y\_i+y\_j}{2}\big)~\text{at position}~k\big\\}$$

The problem always has an obvious solution with $(n-1)$ merge operations i.e, merging everything to a single tuple is always feasible. But we would like to find the **minimum number of merge operations** required to sort the collection.

Even though we suspect that finding the minimum number of merge operations is NP-hard, we do not have a hardness proof to support the claim. The problem looks like something which might have been already studied in the literature. If you are aware of any related or similar problems please guide us to relevant results. Any clues for hardness or algorithmic results are helpful.

**Example:** Given $X=\\{(1,4),(2,2),(3,2),(4,1)\\}$ with two merge operations i.e, $\phi(1,4,3)$ followed by $\phi(2,3,2)$ we can obtain $\\{(2.5,2),(2.5,2.5)\\}$, which is sorted.

$$\\{(1,4),(2,2),(3,2),(4,1)\\} \xrightarrow\[\]{\phi(1,4,3)} \\{(2,2),(3,2),(2.5,2.5)\\}$$ $$\\{(2,2),(3,2),(2.5,2.5)\\} \xrightarrow\[\]{\phi(2,3,2)} \\{(2,2),(2.5,2.25)\\}$$

**Note-1:** $\phi(i,i,k)$ is a valid operation.

**Note-2:** While inserting an element at some index $\ell$, the index of tuples at positions $\\{\ell,\dots,n\\}$ are incremented by $1$, i.e, no element in the collection is deleted while inserting.

**Note-3:** If the merge operation is restricted to operations of the form $\phi(i,i+1,i)$ and insert the resulting element at position $i$, then the minimum number of operations can be found in polynomial time using a dynamic programming algorithm.

Thanks in advance.

# Answer
A crude estimate is that the worst number of merges is greater or equal to $\frac{n-1}{4}$. For this, consider the set \begin{equation} X=\\{(0,1),\ldots,(0,m)\\}\cup\\{(1, 0),\ldots,(m, 0)\\} \end{equation} where $m = \lfloor n/2\rfloor$. None of the points of the first list is comparable to any of the points of the second list. It means that if one of the points is untouched by the merging operations, then all the points of the other list must be touched by at least one merge operation. As each merge operation involves two points, it means that there are at least $\lceil m/2 \rceil$ merge operations. But $\lceil \lfloor n/2\rfloor /2\rceil\ge \frac{n-1}{4}$.

One can even reach a lower bound of $\frac{n-1}{2}$ by considering a set \begin{equation} X = \\{(a\_1, -a\_1), \ldots, (a\_n, -a\_n)\\} \end{equation} where $a\_1,\ldots,a\_n$ are distinct real numbers. Pairs of points in $X$ are never comparable, which means that $n-1$ of them must take part in a merge operation. Hence there are at least $\frac{n-1}{2}$ merge operations.

If we add more conditions on the $a\_k$ s, for example assuming that they are independent over ${\mathbb Q}$, we have an exemple where $n-1$ merge operations are actually necessary because the points $(x, y)$ generated by the merge operations will always have the form $(x, -x)$ and they will always be distinct. They will never become comparable and the algorithm can stop only when the cardinality of $X$ is $1$, that is to say after $n-1$ operations.
> 0 votes

---
Tags: optimization, sorting, np-hard, combinatorics
---


# Question
Title: How would you prove that the Independent set is a complement of a vertex cover and vice versa
I am just wondering how you would write out a proof that the independent set is the complement of the vertex cover. I know how to explain it in common language, just wondering what a more official proof would look like.

# Answer
Let $C$ be a vertex cover and $I = V \setminus C$.

**Claim.** $I$ is an independent set.

**Proof.** Let $u$ and $v$ be two vertices in $I$. Then, since neither $u$ nor $v$ are in $C$, ...
> 2 votes

---
Tags: graphs, np-complete, np
---


title: Context Free Grammar Advantages

text:
# Question
Title: Context Free Grammar Advantages
I am currently learning about context-free grammar, however, I am confused as to why context-free grammar is used over regular languages(Regular expression) and what makes CFG more powerful. Even though the structure is more complex than regular expressions. Any suggestion would be highly appreciated.

# Answer
> 2 votes
While regular languages can allow some particular search (see Grep), where context-free languages shine is in compilation.

Regular languages can be used to do a lexical analysis, meaning it can recognize lexemes in code. For example, lexical analysis can tell you that `42hello` or `if<=>!` are illegal part of code in C. However, what regular languages lack is an advanced memory. They can't be used, for example, if there are the same number of opening and closing parentheses, or if thoses are in a correct order.

This can be done by syntax analysis, using context-free grammars. The syntax analysis is used to create a parse tree, most necessary for compilation.

On a more formal approach, as an example why context-free languages are more vast than regular languages, the language $L = \\{a^nb^n\mid n\geqslant 0\\}$ is a well-known non-regular language (this can be proven using the pumping lemma). However, the grammar $S\to aSb\mid \varepsilon$ generates $L$.

---
Tags: context-free, regular-expressions
---


# Question
Title: Maintaining an array under subarray reversals
Given a sequence of real numbers $\\{a\_1, a\_2, a\_3 \ldots a\_n\\}$, I wish to design a data structure that supports the following operations on it.

1. $\mathrm{REVERSE}(i,j):$ Reverse the contiguous subsequence $a\_i, a\_{i+1}\ldots a\_j$ i.e. swap $a\_i$ with $a\_j$, $a\_{i+1}$ with $a\_{j-1}$ so on and so forth.
2. $\mathrm{REPORT}(i):$ Report the $i$-th element of the sequence.

In my attempt so far I have tried to construct a binary tree each node of which maintains a composition of reversals of the underlying segment but it doesn't seem like this approach can work. Any help is appreciated.

# Answer
> 2 votes
You can get both operations in $O(\log n)$ time with a binary tree. The idea is to store a boolean at each node indicating whether or not the entire subtree underneath the node is logically (not physically) reversed. You can then reverse a node in $O(1)$, by toggling the boolean.

Logical reversal is pretty easy to handle: any time you would descend into a node, check if the node is marked as reversed; if so, then swap and logically reverse its children.

Using this approach, we can adapt standard split/join primitives. And then, using split/join, we can implement `REVERSE(i,j)` like this:

1. split at offsets `i` and `j` to produce three trees `left`, `middle`, and `right`,
2. logically reverse `middle` by toggling the boolean at its root, and
3. join the three trees.

This requires only $O(\log n)$ time on a balanced tree.

---

Here's some pseudocode. The implementation of `REPORT` should hopefully demonstrate how logical reversal is handled.

```
// elements of type T
type Tree<T> {
  elem: T,
  left: Tree<T>,
  right: Tree<T>,
  size: int,
  rev: bool
}

function TOGGLE(tree) {
  tree.rev = !(tree.rev);
  return tree;
}

// swap and toggle children, if necessary. O(1) time.
function NORMALIZE(tree) {
  if (tree.rev) {
    left = tree.left;
    right = tree.right;

    tree.left = TOGGLE(right);
    tree.right = TOGGLE(left);
    tree.rev = False;
  }
}

function REPORT(tree, i) {
  NORMALIZE(tree);

  if (i <= tree.left.size)
    return REPORT(tree.left, i);
  else if (i == tree.left.size + 1)
    return tree.elem;
  else
    return REPORT(tree.right, i - tree.left.size - 1);
}

function REVERSE(tree, i, j) {
  left, tmp = SPLIT(tree, i);
  middle, right = SPLIT(tmp, j-i+1);
  return JOIN(left, JOIN(TOGGLE(middle), right))
}

function SPLIT(tree, i) { /* omitted... */ }
function JOIN(tree1, tree2) { /* omitted... */ }

```

---
Tags: data-structures
---


# Question
Title: Is there a language that has a LL(1) grammar but not LALR(1) grammar?
I know that languages that have LL(1) grammar also will have LR(1) grammar as LL(1) grammar can be written only for a subset of DCFL whereas LR(1) grammar can be written for all DCFL, but I wanted to know where LL(1) will fall if I had it put it along with LR parsers.

L1 is defined as languages for which LL(1) grammar exists and L2 is defined as languages for which LALR(1) grammar exists, is L1 a subset of L2? so I was looking for a language that has LL(1) grammar but doesn't have LALR(1) grammar as a counter-example.

# Answer
> 1 votes
Every language which has an $LR(k)$ grammar for some $k$ has an $SLR(1)$ grammar (which is necessarily also $LALR(1)$ and $LR(1)$).

The proof is constructive: from the $LR(k)$ grammar, you can mechanically derive the $SLR(1)$ grammar.

So $LR(1)$ languages and $LALR(1)$ languages are the same set (which is the set of deterministic languages), and as you note $LL(1)$ languages are a proper subset.

---
Tags: formal-languages, lr-k
---


# Question
Title: if X is in NP but Y is not in NP then can X be reduced to Y?
I have been led to believe that the following statement

$X \in NP \land Y \not\in NP \implies X \not\le^m\_p Y$

Is True.

But I am having difficult proving it. And I'm not even sure it IS true anymore.

At first it seemed reasonable that it was true. Since X is in NP there must exist some NP-complete problem Z that it reduces to and my thinking is that any other problem that X reduces to must also reduce to this NP-complete problem Z, that is, since X is in NP both it and any problem it can be reduced to must also reduce to an NP-complete problem Z so it cannot be the case that X can be reduced to a problem Y that is NOT in NP. This is not my proof but simply my intuition for why the statement is True.

I was hoping initially to prove it by contradiction:

> suppose not, that is, suppose $X \in NP \land Y \not\in NP$ but $X \le^m\_p Y$
>
> since $X \in NP$ it must be that $\exists$ a poly-time verifier algorithm $B$ such that
> $\forall$ inputs $x \in X$ : $\exists$ certificate $t$ s.t. $B(x,t) = yes$
>
> and since $X \le^m\_p Y$ it must be that $\exists$ a poly-time reduction $f$ such that
> $\forall$ inputs $x$ $x \in X \iff f(x) \in Y$
>
> it follows then that $f(x) \in Y \iff x \in X \iff \exists t B(x,t) = yes$

Then at this point I was hoping to reverse engineer the verifier B to come up with a poly-time verifier for Y thus contradicting the supposition that $Y \not\in NP$ similar to what the answer to this question does:
If X is polynomial reduction to Y and Y is in NP, then X is in NP?
But that direction doesn't really work and I haven't found way to use the reasoning above to try and show that $X \not\in NP$ and achieve contradiction that way

And so this is where I am stuck. Am I missing something or am I wrong in my intuition that the statement is true?

# Answer
The time hierarchy theorem states that $\mathsf{NP}\subsetneq \mathsf{NEXP}$.

So if you consider a $\mathsf{NP}$-complete problem $A$ (for example $\texttt{SAT}$) and a $\mathsf{NEXP}$-complete problem $B$ (for example $\texttt{SUCCINCT HAMILTONIAN PATH}$), then $A\leqslant\_m^p B$, $A\in \mathsf{NP}$ and $B\notin \mathsf{NP}$.

Note that more simply, you can consider $A=\emptyset$ and $B$ any problem not in $\mathsf{NP}$ and the result still holds.
> 2 votes

---
Tags: complexity-theory, np-complete, np, decision-problem
---


# Question
Title: Regex for bit strings with at least two zeros but no consecutive zeros
This is what I have:

$$(1^\*011^\*011^\*)^\*\\,.$$

But I don't think this is accounting for an odd number of zeros, like "$10101010101111$". I think I have the right expression that satisfies no 2 consecutive zeros and even number of zeros. Can someone help? Thanks!

# Answer
What does it mean by "no consecutive zeros"? That means there is at least one 1 between any two zeros. You can express it as $01^\*1$, expecting there might be a 0 downstream.

If there are two non-consecutive zeros, you must have a substring like $011^\*0$. All other characters must be optional, which should be better expressed separately.

So a possible answer could be $$1^\*(01^\*1)^\*(011^\*0)(11^\*0)^\*1^\*$$ It reads as a string that

1. starts with zero or more 1's,
2. followed by zero or more strings each of whom starts with one 0 and ends with 1 with possible more 1's in between,
3. followed by two 0's that are separated by one or more 1's,
4. followed by zero or more strings each of whom starts with one 1 and ends with 0 with possible more 1's in between,
5. followed by zero or more 1's.

Notice the symmetry, which should help your understanding.

Motivated by oerpli's answer, we can actually remove one part of the expression. For example, we can let the two zeros occur at the end, i.e., no zero is after those two zeros. The shortened expression will be $$1^\*(01^\*1)^\*(011^\*0)1^\*$$
> 0 votes

# Answer
The shortest regex I came up with is: `1*01+0(1+0?)*`

1. Start with arbitrary amount of 1s (`1*`)
2. Exactly one 0 (`0`)
3. One or more 1s (`1+`)
4. Another 0: (`0`)
5. Arbitrarily often (`(...)*`):
    1. One or more 1s (`1+`)
    2. At most one 0 (`0?`)
> 1 votes

# Answer
You have the "no consecutive zeroes" part correct. However, your answer has two mistakes. As you've noticed, it only matches strings with an even number of zeros; but it also matches the empty string, which it shouldn't.

A string contains at least one zero if it contains a zero, and then maybe some more zeros. If we ignore the ones for a moment, that's $00^\*$. I think you already know how to modify that so the zeros can't be consecutive.
> 0 votes

# Answer
You start with any number of 1s. Then a zero, one or more 1s, and a zero. That’s the first string in your language. You can follow it by (at least one 1, followed by zero) any number of times, getting more than two zeroes, and then you can add more 1s

$1^\* 011^\*0 (11^\*0)^\* 1^\*$

If you use + as “once or more” then it becomes

$1^\* 0 (1^+ 0)^+ 1^\*$
> 0 votes

# Answer
My solution is `1*(01+){2,}0?`

1. `(01+){2,}` means there are at least two (01+), e.g. 0101, 01101, 011010111
2. Then we should allow any number of 1 at the begining so add `1*` at the begining.
3. We should allow 0 at the send, exactly one 0 or no 0. So add `0?`

Combine step 1, 2, 3, get the solution `1*(01+){2,}0?`

According to oerpli, `1*01+0(1+0?)*` is also a good answer.
> -1 votes

---
Tags: regular-expressions
---


title: Variation of 3-SAT

text:
# Question
Title: Variation of 3-SAT
I already know that SAT and 3-SAT are NP-complete. If in 3-SAT the Boolean expression should be divided to clauses,such that every clause contains at most (in the original problem it says exactly) three literals would it still be NP-complete?

I think the answer is yes but I'm not sure of my solution. I think the reduction will remain pretty much the same. We'll use SAT. For the clauses that contain 1,2 or literals we don't change anything. For the clauses that contain more that 3 literals we turn them into clauses with 3 literals like we did in the original 3-SAT.

Are my thoughts correct or am I missing something?

# Answer
Yes, it would.

To make this answer self-contained, here is a sketch of how the transformation works.

Take any SAT problem in CNF. Suppose you have a clause that is more than three literals in size. Let's say it's four.

$$x\_1 \vee \neg x\_2 \vee x\_3 \vee \neg x\_4$$

Introduce a fresh variable $y$. Then this clause is equivalent to the conjunction of two clauses:

$$\left(x\_1 \vee \neg x\_2 \vee y\right) \wedge \left(x\_3 \vee \neg x\_4 \vee \neg y\right)$$

The proof is simple, because this is just the resolution rule. Using this transformation and a lot of fresh variables, you can turn any clause into the conjunction of linearly-many three-variable clauses.

Since, *any* SAT problem can be turned into this 3SAT variant, it follows that this variant is NP-hard. It is also in NP since a valid variable assignment is a certificate checkable in polynomial time. Therefore it is NP-complete.
> 1 votes

---
Tags: np-complete, reductions, np, satisfiability, 3-sat
---


title: 4DM is NP-complete

text:
# Question
Title: 4DM is NP-complete
Is 4DM NP-complete?

An instance of 4DM consists of four disjoint sets X, Y, W and Z of size k, and a set Q of quadruples $Q = \\{ (x, y, w, z) \mid x ∈ X, y ∈ Y, w ∈ W, z ∈ Z \\}$

Question: Is there a subset $M ⊆ Q$ such that each of the elements of X, Y, W and Z is in exactly one quadruple in M?

The answer I found online: complete. To show 4 dimensional matching is NP complete, we want to reduce from 3 dimensional matching. The trick is to just pad each triple with an extra coordinate. We need to do this in a way that we don't really change the problem. One way to do this is to just repeat the last coordinate - so that the triple \[a, b, c\] is mapped to the quadruple \[a, b, c, c\].

But if we do that isn't W and Z equal? And we want them to be disjoint.

# Answer
> 2 votes
It is generaly not a problem to consider a set as a disjoint copy of another. If you consider a set of integers, just say that the first set are blue integers and the other are red integers.

If that is still a problem for you, you can create: $$Z=\\{(w, 0)|w\in W\\}$$ or $$Z = \\{\tilde{w}\mid w\in W\\}$$ Now $Z$ is kind of a copy of $W$, but not exactly.

---
Tags: np-complete, reductions, np-hard, np, check-my-answer
---


# Question
Title: Finding a solution vs Proving that a solution exists
In the context of $P$ vs $NP$, I was taught the following during my CS education:

* $P$ is the set of problems that can be solved in polynomial time
* $NP$ is the set of problems for which solutions can be verified in polynomial time
* Until $P$ vs $NP$ is solved, we only know that $P \subseteq NP$

However, I can also imagine a set of problems $X$, defined as the set of problems for **which we can prove that a solution exists in polynomial time, without necessarily finding the solution itself**. For example, assuming a problem instance that belongs to SAT:

* A solution to a SAT problem can be checked in polynomial time.
* A solution to a SAT problem be found in exponential time (if $P \neq NP$), or in polynomial time (if $P=NP$)
* However, the above does not answer how fast can we prove if a solution exists, without finding the solution itself.

Based on the above, I have the following question:

* What is the relation between $X$, $P$ and $NP$?
* Fundamentally, is finding a solution computationally equivalent to proving that a solution exists?

Personally, I find it reasonable that proving the existence of a solution should be fundamentally easier than constructing a specific solution. The former requires less information than the latter. However, this was rarely, if ever, discussed during my CS education.

EDIT: I corrected the definition of class X: "which we can prove that a solution exists in polynomial time, without **necessarily** finding the solution itself"

# Answer
> 2 votes
$\mathsf{P}$ and $\mathsf{NP}$ are classes of decision problems. It means that for an instance of such a problem, the question is **always** a Yes-No question.

Since you define $X$ as "the set of problems for which we can prove that a solution exists in polynomial time", there is a bit of ambiguity: are those problems decision problems? Optimisation problems? Search problems?

However, since the question you are asking is whether or not there exists a solution, there is a clear correspondance between $X$ and $\mathsf{P}$: given a problem $A\in X$ and $x$ an instance of $A$, what your polynomial algorithm do is solve the decision problem:

> Instance: $x$ an instance of $A$.
>
> Question: does there exist a solution to $A$ with instance $x$?

# Answer
> 0 votes
You are pretty much asking if there is a broader set of algorithms $X$ such that for some decision problem $p$, there is a non-constructive proof that $p\in P$.

This set would be separate from the classes $P, NP$ as those sets only care about the existence of solutions, whether or not they are actually constructable is not needed.

Its also pretty easy to show that $X\subset P$, as any member of $X$ is in $P$ by definition, but we know of problems in $P$ that have constructed solutions.

As for if there is a name for this set of problems, not that I am aware of, but research is pretty expansive to maybe in a paper I'm not familiar with

---
Tags: complexity-theory
---


# Question
Title: Help understanding the proof of the definition of Big-Theta based on limits
I was reading Kleinberg's and Tardo's book (especifically, this one) and, on page 38, these authors define the Big-Theta notation the following way:

> Let $f$ and $g$ be two functions that $\lim\_{n\to\infty}f(n)/g(n)$ exists and is equal to some number $c\>0$. Then $f=\Theta(g)$.

Then, they provide a proof that connects the classic defition based on sets of functions to this definition based on the limit of the ratio of two functions. This proof goes as:

> We will use the fact that the limit exists and is positive to show that $f=O(g)$ and $f=\Omega(g)$, as required by the definition of $\Theta(\cdot)$. Since $\lim\_{n\to\infty}f(n)/g(n)=c\>0$, it follows from the definition of a limit that there is some $n\_0$ beyond which the ratio is always between $c/2$ and $2c$. Thus, $f(n)\leq 2cg(n)$ for all $n\geq n\_0$, which implies that $f=O(g)$; and $f\geq c/2\cdot g(n)$ for all $n\geq n\_0$, which implies $f=\Omega(g)$. $\blacksquare$

However, I'm struggling to follow this proof; in particular, I fail to see how or why the authors chose the constants $c/2$ and $2c$ "from the definition of the limit" (as they say). I consulted Leithold's book on calculus (this one) and, on page 250, I found the following definition for infinite limits (translation is mine):

> Let $f$ be a function defined for all numbers within some open interval $(a,\infty)$. The limit of $f(x)$ when $x$ grows indefinitely is $L$, which is denoted as $\lim\_{x\to\infty}{f(x)}=L$, if, for any $\varepsilon \>0$ (no matter how small this number is), there exists a number $n\>0$ such that: if $x\>n$, then $|f(x)-L|\<\varepsilon$.

Applying this definition to Kleinberg's and Tardo's proof, I understand that $\lim\_{n\to\infty}f(n)/g(n)=c$ implies that, no matter what $\varepsilon$ I choose, there's always an $n\_0$ beyond which $|f(n)/g(n)-c|\<\varepsilon$ (in other words, the ratio $f(n)/g(n)$ differs from $c$ within any given margin $\varepsilon$). But then, I fail to see how this fact implies that "the ratio is always between $c/2$ and $2c$", as Kleinberg and Tardos claimed.

I think that the definition of infinite limits allows us to choose (at least in this particular case) any $\varepsilon$ that we find convenient, since $n\_0$ will always exist no matter what we choose. Following this idea, I would suspect that Kleinberg and Tardos simply chose a value for $\varepsilon$ for which $|f(n)/g(n)-c|\<\varepsilon$ would imply that $c/2\leq f(n)/g(n)\leq 2c$ is always true. However, I don't think such $\varepsilon$ can be chosen under these circumstances, since the distance from $c/2$ to $c$ is not the same as the distance from $c$ to $2c$.

Can somebody please help me understand what step I'm missing from this proof?

# Answer
> 0 votes
By the definition of the limit, for any $\epsilon$ we can always establish

$$c-\epsilon\<\frac{f(n)}{g(n)}\<c+\epsilon$$

by choosing $n$ sufficiently large.

In fact, the proof stops here, as this reads

$$c\_0 g(n)\le f(n)\le c\_1 g(n).$$

The author preferred to work with $\epsilon=\dfrac c2$ on the left and $\epsilon=c$ on the right (this is more "constructive"), but that does not make a big difference.

---

Technical note: $c\_0$ must be positive, so we must choose $\epsilon\<c$ on the left (hence the $\frac12$). There is no such constraint on the right, but the author might as well have kept the same $\epsilon$ for clarity.

---

The reciprocal is not true. As a counter-example, consider

$$f(n)=(2+\sin n)n.$$

We do have

$$n\le (2+\sin n)n\le 3n\implies f(n)=\Theta(n)$$ but the limit does not exist.

# Answer
> 0 votes
I'd like to add a few observations about Yves Daoust's answer. The relation $$ (1)\qquad c-\varepsilon\<\dfrac{f(n)}{g(n)}\<c+\varepsilon $$ can be esaily inferred by tracing $|f(n)/g(n)-c|\<\varepsilon$ on the number line like so:

That is, $f(n)/g(n)$ can be any value in the interval $(c-\varepsilon,c+\varepsilon)$. From there, as just explained in my question, we can choose a value for $\varepsilon$ that we find convenient.

My confusion was that the authors chose two different values for $\varepsilon$. This can be more esily seen by separating the relation (1) in two relations and working separately on them (this was explained by Yves Daoust in his/her answer), as so: $$ (2) \qquad\dfrac{f(n)}{g(n)}-c\<\varepsilon\\ (3) \qquad c-\dfrac{f(n)}{g(n)}\<\varepsilon $$

For (2), we can choose $\varepsilon=c$ and get the following: $$ \begin{aligned} \dfrac{f(n)}{g(n)}-c&\<c\\ \therefore f(n)&\<2c\cdot g(n) \end{aligned} $$ which satisfies the definition for $f=O(g)$ (remember that, no matter what value for $\varepsilon$ we choose, there always exists an $n\_0$ for which $f(n)\<2c\cdot g(n)$ is true for all $n\geq n\_0$; this is by the definition of the limit that I stated in my question).

Finally, for (3), we can choose $\varepsilon=c/2$ and get the following: $$ \begin{aligned} c-\dfrac{f(n)}{g(n)}&\<c/2\\ \therefore (c/2)g(n)&\<f(n) \end{aligned} $$ which satisfies the definition for $f=\Omega(g)$. Thus, since $f=O(g)$ and $f=\Omega(g)$, we conclude that $f=\Theta(g)$, finishing the proof.

# Answer
> -1 votes
*If* the limit exists then f/g will be between c-eps and c+eps for every eps \> 0 if n is large enough. The author chose eps=1/2 which is more than good enough to prove big-theta.

But big theta doesn’t require a limit. 2 + cos(n) is big-theta(1).

---
Tags: big-o-notation
---


# Question
Title: How can I compute the most general unifier for these two expressions?
I have the following first order logic expressions:

$f(g(a, h(b)), g(x, y)),~f(g(z,y), g(y, y))$

and I want to compute the most general unifier for them. If I follow the algorithm found on these slides then I get the following.

\begin{align\*} S\_0 &= \\{f(g(a, h(b)), g(x, y)), f(g(z,y), g(y, y))\\}\\ D\_0 &= \\{g(a, h(b)),g(z,y)\\} &\[\text{first disagreement set}\]\\ &\text{(need to unify these two functions)}\\ D\_0'&= \\{a,z\\} &\[\text{first sub-disagreement set}\]\\ \sigma &= \\{z=a\\}\\ D\_0''&=\\{h(b),y\\} &\[\text{second sub-disagreement set}\]\\ \sigma &= \\{z=a, y=h(b)\\}\\ S\_1 &= \\{f(g(a, h(b)), g(x, h(b))), f(g(a,h(b)), g(h(b), h(b)))\\}\\ D\_0 &= \\{x,h(b)\\} &\[\text{second disagreement set}\]\\ \sigma &= \\{z=a,y=h(b),x=h(b)\\}\\ S\_2 &= \\{f(g(a, h(b)), g(h(b), h(b))), f(g(a,h(b)), g(h(b), h(b)))\\} \end{align\*} No disagreement, unifier found! $\sigma = \\{z=a,y=h(b),x=h(b)\\}$.

However, this is not the most general unifier as we have $\\{y=h(b),x=h(b)\\}\in \sigma$, so i think the MGU should actually be $\sigma' = \\{z=a,y=h(b),x=y\\}$.

Is this correct? When I use Prolog to unify them, it gives $\sigma'$. What did I do wrong in my following of the algorithm, so that it gave me a unifier that wasn't the most general?

# Answer
> 1 votes
There seems to be a small confusion with the notation. Notice that $\sigma = \\{z = a, \ y = h(b), \ x = h(b) \\}$ and $\sigma' = \\{z = a, \ y = h(b), \ x = y \\}$ are the same unifier, written in a different way. It doesn't matter if we write $x = y$ or $x = h(b)$, since we also have $y = h(b)$. Hence, you did nothing wrong and you have computed the most general unifier.

---
Tags: first-order-logic, unification
---


# Question
Title: Storing N bits on the smallest possible space in a real computer
**Update.** Since my original question was misunderstood by many, and lead to a lot of debate about various issues, let me try to pose this modified and rephrased question:

> Assume that I have a computer with a giant disk that can store $2^{1000}$ bits. Is it possible for any $N\<2^{999}$ to write a code in Python for any $N$-long bit string $x$ that prints $x$, such that the code of the program uses at most $N+O(\log N)$ bits of space?

(I'm aware that such a disk cannot exist in our universe.)

**Original version.**

Because of Kolmogorov/Levin complexity considerations, most $N$-long bit strings require $N+\log N+o(\log N)$ bits to store, since we also need to specify where the sequence ends; see D.W.'s or Rainer's answer for the details.

I wonder what is the most efficient way something like this can be realized on a *real* computer. What is the optimal way of storing an $N$-long bit string? Can it be done in $N+o(N)$ space?

Please note that this question is about practical methods that can be implemented as a code, not theory! You can pick your favorite programming language, Python, C++, assembly etc.

# Answer
> 1 votes
I'll take a swing at answering your question about why a physical machine might use more memory than the theoretical optimum. The schemes described by Rainer P. and D.W. can be implemented exactly as then have described; however...

Your assertion that "I don't think it can be done on real hardware" is probably true, but not for theory vs reality reasons (ala a spherical cow in a vacuum) and more because efficiently packing bitstrings is just not the primary goal of actual hardware systems. Real systems care about memory correctness, bandwidth, latency, availability, etc. before they care about storage efficiency.

First, memory is only addressable down to the byte, and since bit twiddling to interact with non-byte-aligned data is probably not worth the performance hit, you'll have to lose some bits to byte alignment.

Next, consider that CPU architectures have a native word size, and so reads/writes and random access perform best when the data is aligned to the word size. Structs generated by C can include multiple bytes of padding even for small structures.

Data in the sense C structs is "records" composed of "fields", and those fields are likely to be fixed length for performance, so if the data in those fields doesn't fill the fields completely, that's wasted space.

Cache is largely invisible to programs, but it's still memory - since the CPU is traditionally orders of magnitude faster than main memory, several layers of cache are used to reduce the latency by "reading ahead", trying to predict what data the CPU might ask for in the near future and saving the eons of time the CPU would otherwise waste blocking for data retrieval - this would probably also count as wasted memory in some sense.

Following from cache into memory itself, consider virtual memory, paging and the Memory Management Unit. When processes interact with main memory, the addresses they use don't have a direct correspondence to where data is stored. Instead they are "virtual addresses" that are mapped by the system into "pages" of physical memory \- this is done for several different reasons and worth a read, but my point here is that the virtual memory system has an overhead cost for indexing the pages, similar to a filesystem, with potential additional costs of wasted padding.

Which brings up secondary storage and filesystems. Filesystems are all about tracking blocks of data across a physical drive that comprise files, and about indexing them for structured retrieval (like directory-based filesystems). The files aren't stored as single long blobs of bytes, but as chunks potentially strewn across the physical drive, and each file/chunk requires some indexing overhead. Filesystems often have a native block size that they allocate (e.g. 4096 bytes), so files which are smaller than the block size or not evenly divisible will waste some space.

Next, at a lower layer, physical drives are composed of sectors which use error correcting codes to detect/correct errors and even identify and "disable" bad sectors that no longer store data properly. In both cases, space is wasted to achieve these goals.

Certainly, everything above will waste some space versus the theoretical bitstring packing you asked about, but it's not all doom and gloom: consider that much of the time, data is actually stored MORE efficiently than you propose. Lossy compression for images/video/audio are well established, and generalized lossless compression file archive tools like zip/gzip are fantastic at identifying and exploiting patterns in real world data to achieve remarkable storage efficiency. Video games often achieve pretty insane space efficiency by utilizing procedural generation techniques - consider the 96kb shooter which would have taken 200-300MiB if stored conventionally.

Memory is cheap. Performance is king. I could probably get my hands on a microcontroller or some other simple system that doesn't include many of the bells and whistles above, and I could implement the algorithms mentioned in the other answers (though the bit twiddling to load/store a non-byte-aligned bitstring would be kind of a pain). However from my perspective, the "most efficient way to store data" is actually not to determine and implement the theoretically optimal way to pack bitstrings - it's to wait for hardware engineers invent denser storage.

# Answer
> 8 votes
Represent the string $x$ using the following encoding:

$$0, x\_k, \dots, 0, x\_2, 0, x\_1, 1, x\_0$$

where $x\_0 = x$, $x\_{i+1} = \text{len}(x\_i)$ is a binary representation of the length of $x\_i$ in bits (namely, $\text{len}(x\_i)=\lceil \lg x\_i \rceil$, for $i\ge 1$), and $k$ is the smallest $k\ge 1$ such that $x\_k \le 3$. In particular, you encode 0 or 1 with a single bit, encode $x\_k$ with 2 bits, and encode $x\_i$ with $x\_{i+1}$ bits.

This requires $N + \lg N + \lg \lg N + \cdots + \log^\* N = N + \lg N + o(\lg N)$ bits of space to encode a $N$-bit string $x$.

# Answer
> 4 votes
You can achieve N+2log2N with a simple algorithm:

1. Write down the binary string.
2. Prefix it with its length.
3. Prefix that with as many zeros as the length is long.

With this encoding, a 20 bit string is encoded as:

> 00000 10100 XXXXXXXXXXXXXXXXXXXX

Do decode it, count the number of leading zeros (5) and decode as many bits after them (10100 = 20). That's the payload length.

---
Tags: computation-models, data-compression, kolmogorov-complexity
---


# Question
Title: How are setup and hold and timing constraints handled when reading an address from memory?
When an operand encodes an address, and that address changes the "memory address register" and the word in memory being addressed, it seems like timing issues could be a problem. Examples, LDA instruction (load address from memory, load word from that address. )

Illustrated in timing diagram below.

How is this usually solved (could be different across different CPUs but there are probably trends. )

Is a temporary register used (the "memory address register" could load and output in two separate steps), or is the timing issue just not a problem and tends to work out regardless?

Example LDA with two step "memory address register",

```
      when LDA_1 =>           -- Load accumulator from operand
        addr_in <= dr;

        state := LDA_2;
      when LDA_2 =>
        addr_out <= addr_in;

        state := LDA_3;
      when LDA_3 =>
        accu <= dr;

        state := load_opcode;

```

Timing with temporary "address in" register illustrated below,

# Answer
Well, actually there are many different approaches that can be used, and the optimal solution depends on the specific requirements and constraints of the system.

While using a temporary register, the address is typically loaded into the MAR in a single clock cycle, and then used to access the word in memory in the next clock cycle. This ensures that there is sufficient time for the address to be stable before it is used to access memory.

Well another way is to use a dedicated memory controller, it is responsible for managing the timing of read and write operations to memory. The memory controller can be designed to ensure that the timing constraints of the memory are met, regardless of the speed of the CPU.

These approaches can help ensure that the read operation is successful and the timing constraints of the memory are met. However, as I already said the specific solution will depend on the design of the CPU and the memory system.
> 1 votes

---
Tags: cpu
---


# Question
Title: What is the complexity class of counting Yes/No instances of an NP problem?
Let's say that I have an NP-complete problem such as the Clique Problem. Let's also assume that I have a finte set of graphs. What is the complexity of counting Yes/No instances?

More specifically let's define a new decision problem that returns Yes on a finite set of graphs if the number of Yes instances is $\geq$ a constant $k$ and the number of No instances is $\leq$ a constant $l$ Equivalently $l' \leq \operatorname{count}(Yes) \leq k$. In what complexity class does this problem belong? I know it can be solved in polynomial time with an NP oracle but is it hard in this class or is there a lower bound?

In a more general setting if I need the set of graphs to satisfy a condition $c(\operatorname{count}(Yes), \operatorname{count}(No)) \leq k$, where $c$ is an arbitrary function, does the problem become harder?

# Answer
I think you are looking for $\\#\mathsf{P}$, a set of counting problems.

See this paper for some examples of $\\#\mathsf{P}$-complete problems.
> 2 votes

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


# Question
Title: Show that $\text{BOOL-VAL}$ and $\text{DNF-SAT}$ is decidable in linear time
A boolean expression is valid if it is true for every valuation. The problem $\text{BOOL-VAL}$ asks whether a given boolean expression is valid. As the question suggests I need to show that $\text{BOOL-VAL}$ is decidable in linear time. I have no idea how to go about proving this.

Is $\text{BOOL-VAL}$ the complement of $\text{BOOL-SAT}$?

Moreover, A boolean expression is Disjunctive Normal if it is the disjunction of conjunctive clauses, where a conjunctive clause is the conjunction of 1 or more literals. Such an expression is said to be a DNF (“disjunctive normal formula”). $\text{DNF-SAT}$ says given a DNF, is it satisfiable? The way I want to prove that it is decidable in linear time is like in $\text{CNF-SAT}$ we want atleast one literal per clause to be true and here we want atleast one clause to be true so that somehow intuitevely reduces the number of steps need to come to conclusion leading to lower time complexity but I'm not sure if I'm correct.

Source: This was asked as a brainteaser in my ToC class. There are two questions but I was told that they are basically the same so I asked both.

# Answer
No. What you are trying to show is not correct. As far as we know, there is no efficient algorithm to test whether an arbitrary boolean expression is valid.

If $\varphi$ is a boolean formula in CNF format, then $\neg \varphi$ is valid iff $\varphi$ is unsatisfiable. So if you had a linear-time algorithm to test for validity, you could apply it to $\neg \varphi$, and thereby learn in linear time whether $\varphi$ is satisfiable. That would constitute an algorithm proving that P=NP. That seems very unlikely, given our current state of knowledge.

Testing whether a CNF formula is valid can be done in linear time ($\varphi$ is valid iff every one of its clauses is valid, and a clause is valid iff \<you fill in this part\>), but testing whether a DNF formula is valid cannot be done in linear time (or even polynomial time) unless P=NP. Similarly, testing whether a DNF formula is satisfiable can be done in linear time, but testing whether a CNF formula is satisfiable cannot be done in linear time (or even polynomial time) unless P=NP.
> 0 votes

---
Tags: time-complexity, np, decision-problem, linear-complexity
---


# Question
Title: Given a definite program, how do I obtain its Herbrand base?
Given a definite program, how can I obtain its Herbrand base?

For instance, given the program $P$ below, what is its Herbrand base $B\_P$?

> $p(f(x)) \leftarrow p(x)$
> $q(a) \leftarrow p(x)$

I know the definition of Herbrand base for a first-order language $L$, which relies on the concept of a Herbrand universe for $L$ (I am putting them below), but I don't know the connection with a Herbrand base **of a program**.

> **Herbrand base**. Let $L$ be a first-order language. The Herbrand base $B\_L$ is the set of all ground atoms which can be formed by using predicate symbols from $L$ with ground terms from the Herbrand universe as arguments.
>
> **Herbrand universe**. The Herbrand universe $U\_L$ for $L$ is the set of all ground terms, which can be formed out of constants and function symbols appearing in $L$. (In the case that $L$ has no constants, we add some constant, say $a$ to form ground terms.)

# Answer
If $S$ is a set of formulas, by abuse of language, we can talk about the Herbrand base $B\_S$ of $S$ instead of the Herbrand base $B\_L$ of the underlying first-order language $L$ from which the formulas come. Now, recall that a program $P$ is a set of formulas, and you will know what he meant by $B\_P$.

In the particular example, the Herbrand universe is $$H\_P = \\{a, f(a), f(f(a)), \ldots \\} $$ and hence the Herbrand base is $$B\_P = \\{ p(a), q(a), p(f(a)), q(f(a)), p(f(f(a))), q(f(f(a))), \ldots \\} $$
> 0 votes

---
Tags: prolog
---


# Question
Title: Which architecture do modern computers use?
Is it one of:

* Harvard
* Modified Harvard
* von Neumann

Or are they antiquated models that modern computers are only loosely based on?

If you asked Intel or AMD what would they say?

# Answer
Modern general-purpose high-performance processors use separate instruction and data caches, and so could be classified as modified Harvard even though they use a unified address space. (Some microcontrollers—usually to provide extra memory or protection without a memory protection unit—use a Harvard architecture in which data and code use separate address spaces.)

x86 might be considered a little more nearly "pure" von Neumann than some other ISAs in that *self-modified* code is guaranteed to be handled properly if a jump is used. Many other ISAs require an instruction synchronization instruction and may require explicit invalidation of any modified memory from the instruction cache (i.e., the instruction cache is not necessarily coherent).

Cross-modified code is somewhat more complex; even x86 requires a synchronizing instruction.
> 12 votes

# Answer
Depends on how you see it, but the most common answer is Von Neumann, because there is no physical separation between data and program in modern CPU. However, in actuality modern machines are perhaps better described as modified Harvard Architecture, because for security reasons, modern machines do implement mechanisms to prevent data from being accidentally executed as code (this is the cause of many security issues in older systems), in the form of DEP (Data Execution Prevention) or NX bit (No eXecute bit), essentially making them more like Harvard architecture.
> 4 votes

# Answer
Because it store the data and program in a single memory space.As compare to other computer architecture it is cheaper because it has no physical sepration between the data and instruction.It execute the single instruction with a double clock cycle and it can access the instruction but can't read and write at a same time
> 0 votes

# Answer
I think Von Neumann is appealing answer but most processors implement a modified harvard architecture so they can load programs for disk storage as data and then execute it!..
> -1 votes

---
Tags: computer-architecture
---


# Question
Title: Protein folding, P vs. NP, and DeepMind with AlphaFold
"DeepMind has predicted the structure of almost every protein so far catalogued by science, cracking one of the grand challenges of biology in just 18 months thanks to an artificial intelligence called AlphaFold", reads newscientist.com.

If protein folding is supposedly an NP-complete problem, does DeepMind deserve a millennium prize? What am I missing?

# Answer
> 3 votes
The $\mathsf{P}$ vs. $\mathsf{NP}$ problem asks whether $\mathsf{P}=\mathsf{NP}$. To settle this problem one needs to either provide a *formal* proof that $\mathsf{P}=\mathsf{NP}$ or a *formal* proof that $\mathsf{P}\neq\mathsf{NP}$.

One possible proof for $\mathsf{P}=\mathsf{NP}$ consists in exhibiting a polynomial-time algorithm that solves a $\mathsf{NP}$-hard problem (along with proving its correctness and that the algorithm's time complexity is indeed polynomial in the input's size). For an algorithm to solve a problem, it must return the correct answer on *all* possible input instances.

AlphaFold **does not solve the protein folding problem** in the formal sense, i.e., there is no guarantee that the returned solution is the optimal one (I'm not even sure if it works for arbitrarily large instances). It is merely a *heuristic* that provides *good* solutions to *practical* instances *most of the time*.

---
Tags: algorithm-analysis, np-complete, artificial-intelligence
---


# Question
Title: Why Regular Grammar is Left/Right Linear?
From the definition I know that regular grammar should be Left/Right Linear (ie it should have variable on Left/Right side of each production rules)

But, my question is why it is mandatory? Can't we have "Grammar which has DFA(Determistic Finite Automata) or NFA be called Regular Grammar"?

S --\> SaS | e (e is epsilon/null/lambda) ; This is not a regular grammar as per its original definition, but the above grammar is generating only regular language.

The above grammar can also be written as, S --\> aS | e ; which is basically the same.

So why is there such rule for regular grammar?

# Answer
The boring answer is: The phrase "regular grammar" means what it means, because we have decided that it means that. Had we decided it should mean something else, it would mean something else.

That aside, it is of course legitimate to ask whether

> Definition A: "A *regular grammar* is a grammar that is either right-linear or left-linear."

is a better definition than

> Definition B: "A *regular grammar* is a grammar that describes a regular language (which we've already defined, eg via automata."

A very nice aspect of Definition A is we can very easily check whether a given grammar satisfies it or not. We just look at it, and we know. This goes horribly wrong if we were to adopt Definition B. There is no algorithm that takes in a general grammar and tells us whether or not it defines a regular language. The reason for this is that we can translate Turing machines into general grammars, and thus eg produce a grammar that defines a finite language if the given Turing machine halts only for finitely many inputs, and some definitely-not-regular language otherwise.

We also wouldn't get any of the other benefits that right-linear/left-linear grammars give us, such as easy parsing.
> 1 votes

---
Tags: regular-languages, finite-automata, formal-grammars, theory
---


# Question
Title: Subgraph Isomorphism Problem NP complete?
I found many solution online on how to reduce Subgraph Isomorphism problem to Clique, but how do I prove that it is NP complete by reduction from independent set?

I'm struggling to figure out this proof through independent set. Any hints?

# Answer
> 2 votes
The idea is exactly the same: an undirected graph $G = (V, E)$ has an independant set of size $k$ if and only if the graph $(\\{1,…,k\\}, \emptyset)$ (the graph with $k$ vertices and no edge) is isomorphic to a subgraph of $G$.

---
Tags: np-complete, np, graph-isomorphism, subgraphs
---


# Question
Title: How to make a recursive definition for a given predicate?
I have the following predicate: $empty(r)\Leftrightarrow L(r)=\emptyset.$ Now I am given the following regular expressions where $e, f$ are any regular expression:

* $r=\emptyset$
* $r=\varepsilon$
* $r=a:\forall\in\Sigma$
* $r=e+f$
* $r=ef$
* $r=e^\*$

Now I have to write a recursive definition for $empty(r)$. And this is the thing where I have some problems with. I know that we need at least one basecase and at least one case where the definition calls itself with a reduced problem. I understand the predicate as the following: *"If L is empty empty(r) is false, otherwise it's true"*. I started with the basecases:

$$empty(\emptyset)=true$$

$$empty(\varepsilon)=false$$

The first base case is pretty much self explained. My plan was to somehow reduce the regular expressions so much until they are only $\varepsilon$ and I thought that I could use the fact that every regular expression can be combined with $\varepsilon$ like this: $$r\Leftrightarrow\varepsilon r$$ But I still don't understand how I should build the definition for $empty(r)$. And maybe someone here can help me.

It would be nice as well if someone could give a hint on how I could proof the definition when I found one. I am grateful for every answer and comment!

# Answer
> 1 votes
Let $L, L\_1, L\_2$ be regular languages.

* if $L = L\_1\cup L\_2$, then $L$ is empty if and only if $L\_1$ is empty **AND** $L\_2$ is empty;
* if $L = L\_1L\_2$, then $L$ is empty if and only if $L\_1$ is empty **OR** $L\_2$ is empty;
* if $L = L\_1^\*$, then $L$ is not empty.

That should do it for induction.

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Is time complexity $O(n^{n/log(n)})$ considered subexponential time?
If there is an algorithm with time complexity $O(n^{n/log(n)})$, is that already exponential time or still subexponential time?

It shouldn't be considered quasi-polynomial since the exponent is also depending on $n$, right?

# Answer
> 1 votes
$$n^{\tfrac{n}{\log\_2 n}} = (2^{\log\_2 n})^{\tfrac{n}{\log\_2 n}} = 2^{\tfrac{n}{\log\_2 n}\times \log\_2 n} = 2^n$$

---
Tags: time-complexity, runtime-analysis
---


# Question
Title: Are empty-set languages recursively enumerable?
Are languages whose sets are empty recursively enumerable or recursive? For example, consider the language $L$ $\subseteq$ {0,1}\*:

> $L$ = { $w$ | $w$ consists of only 0's} $\cap$ { $w$ | $w$ consists of only 1's }

I believe this language creates an empty set. There are many different ways to design a Turing Machine that decides that whether word $w$ is in $L$. In that sense, $L$ seems recursive. Further, there are many different machines that can return the empty set. Any of these them would effectively "enumerate" the members of L, even though there are none.

My gut tells me to reject these conclusions. Could anyone steer me in the right direction? Any guidance would be much appreciated.

# Answer
> 2 votes
The empty language is recursive. The TM accepting this language just returns $0$/REJECT on any input. Similarly, the language $\Sigma^\*$ is also recursive. Just return $1$/ACCEPT on any input.

Basically, it does not matter how a language is defined. What makes them recursive/RE is the fact that we can effectively decide its membership. For a recursive language $L$ *there is* a TM that always accepts $x$ if $x \in L$ and rejects $x$ if $x \notin L$. For a recursively enumerable language $L$ *there is* a TM that always accepts $x$ if $x \in L$.

# Answer
> -5 votes
I strongly believe the answer from fade2black is wrong. The empty language is not recursive, in fact it is not even recursive enumerable. The question you have to ask yourself is given any encoding of a turing machine M, can we determine if its language is the empty language. The way you can formally prove this would be by showing that the complement of the empty language is recursive enumerable and then it follows directly, that the empty language is neither recursive (otherwise the complement must be recursive as well) nor recursive enumerable (if a Language L and its complement are both recursive enumerable you can proof by contradiction that L is recursive).

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


title: Weighted-Graph Datasets

text:
# Question
Title: Weighted-Graph Datasets
I am searching for datasets to evaluate an algorithm designed for tasks such as node-classification (edge-prediction, etc.) on *weighted* and potentially directed graphs.

The Stanford Network Analysis Project (SNAP) repository only contains datasets containing *temporal* weighted graphs.

Are there standard datasets for such tasks on non-temporal weighted (and directed) graphs?

# Answer
> 2 votes
I think these datasets meet your constraints, wn18rr and proteins. I found them by looking here.

---
Tags: graphs, machine-learning, reference-request, data-sets
---


# Question
Title: What's wrong here, or, is CNF to DNF conversion in o(exp(n))?
I've been thinking about conversion from CNF to DNF. Assume a "worst case" CNF formula with $k$ disjunctions, each containing exactly $l$ elements and no variable is used twice. Example with $k=3$ and $l=2$:

$(a \lor b) \land (c \lor d) \land (e \lor f)$

Obviously, this will result in a DNF of length $k^l$, as all possible conjunction combinations need to be listed and due to all variables being unique, nothing will vanish. Given that, computation time complexity will at least be exponential and lay in $o(k^l)$.

Now, two questions:

1. Can we say that time complexity will also be within $o(exp(n))$, where n denotes formula length?
2. If 1. is true, wouldn't that prove that this problem isn't part of $P$, and, given CNF -\> DNF is ~~NP-hard~~ NP-complete, that $P \neq NP$? *Edit:* I'm aware CNF -\> DNF is NP-hard, but is it NP-complete too?

# Answer
> 1. Can we say that time complexity will also be within $o(exp(n))$, where $n$ denotes formula length?

No, because no one has proven that distribution of terms is the only way to convert CNF to DNF. Obviously simple distribution of terms produces an exponential blowup in the formula size, but there may be other ways to compress the formula so that the same truth table is produced. We already known that given a truth table clever algorithms can produce smaller formulas than full disjunction over the distributed terms.

> 2. If 1. is true, wouldn't that prove that this problem isn't part of $P$, and, given CNF -\> DNF is ~~NP-hard~~ NP-complete, that $P \neq NP$?

No. If CNF to DNF conversion could be accomplished in polynomial time, its output would necessarily fit into polynomial space. Therefore you could scan this output in polynomial time and decide satisfiability. Thus P would be equivalent to NP. But if CNF to DNF conversion takes exponential time it says nothing about whether some other algorithm could efficiently solve SAT and bring P and NP together.
> 5 votes

# Answer
1. The conversion of CNF to DNF is exponential in the worst case. There are no tricks that avoid writing out an exponential number of clauses. It is not obvious to me that the little-o notation with *exp* is correct, but, yes, it is exponential.
2. No. The NP-complete satisfiability problem you are thinking of is a decision problem, a yes or no answer, for whether or not there is at least **one solution**, a satisfying assignment of truth values. In your example, each clause of the resulting DNF corresponds to a solution; thus, this conversion is equivalent to listing **all solutions**, a lot more work than just identifying one. So, you can't assume that CNF-to-DNF conversion is NP-complete.
> 2 votes

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: Does flipping the kernel in image processing only help maintain mathematical symmetry?
So I've been really confused about the act of flipping a kernel in image processing. Is there any intuitive way to think about it or does it only help computing efficiently and maintain the mathematical symmetry?
Do we necessarily flip a kernel in image processing? (say the kernel is not symmetrical). Do we only flip it because we'll put it in a convolution later? Thanks in advance!

# Answer
Flipping the kernel comes from the pure-math context of a convolution, where it is a natural thing to do. See this part of 3b1b's video on convolutions where he gives a great intuitive answer to your question.
> 1 votes

---
Tags: image-processing, kernel-functions
---


# Question
Title: Why is the Church-Turing thesis not accepted as fact?
I recognize that it has overwhelming consensus at this point, but from what I understand, it's still technically considered "probably true" instead of "definitely true".

If we go by their original definition, then it amounts to dealing with things that can be accomplished by "effective methods", meaning finite sets of instructions of specific steps that can be carried out (when applicable) in finite time. Basically, it sounds logically identical to our modern conception of an algorithm.

If that were the case, then by simply having a computer (with infinite memory, of course) enumerate every possible program and execute them in dovetail-succession so that all halting programs will eventually halt, you would be guaranteed to hit upon any more-powerful computational technique which could be carried out with an "effective method" sooner or later. However, this is clearly impossible since by definition any such method could not be carried out by a computer (or Turing machine, or whatever).

I am certain I am retreading old ground here but could not find it on search. Do I have the thrust of their thesis wrong, or is there a flaw in my find-it-with-enumeration approach?

I also realize that I have possibly oversimplified their thesis to "anything a computer can do, a computer can do", but I'm finding a hard time getting around that.

# Answer
Because what can be effectively carried out depends on what is possible within the physics of our universe. So if we have not correctly understood physics, it is possible that perhaps more might be possible than we can currently imagine. While that doesn't seem likely, it's not something we can absolutely definitively rule out, so there is no basis for treating the Church-Turing hypothesis as definitely proven.

Or, to put it another way, there is no proof of the Church-Turing hypothesis, so therefore there is no basis to consider it proven. In fact, there is not even an accepted precise, rigorous formulation of exactly what the CT is claiming.

See, e.g., the extended Church-Turing hypothesis, which might sound roughly as plausible as the Church-Turing hypothesis, which your line of argumentation seems just as valid for as for the normal Church-Turing hypothesis, and yet for which we have valid reasons to believe is false, given what it appears quantum computers can achieve.

As another example, if time travel is possible (specifically, closed timelike travel), then the computational power achievable is far greater than what our current computers can achieve. See https://cstheory.stackexchange.com/q/43920/5038.

Related reading:
> 2 votes

---
Tags: turing-completeness, church-turing-thesis
---


# Question
Title: Is there a known method for reducing the problem of prime factorization to the problem of determining if a hamiltonian path exists?
I hope this question is not out of place here, but I am currently attempting to implement the problem(a reduction algorithm) stated in the Title. I included the steps I am following as of now and an existing attempt at implementation. Are there better/simpler ways to go about this? Logic: Create a non-deterministic Turing machine that accepts if there exists a factor of n less than k, and rejects otherwise. This Turing machine could be implemented using a set of states, transition rules, and a way of storing and reading input and output. For example, the machine could have a start state, an accept state, and a reject state. It could also have a set of intermediate states for carrying out the binary search for a factor of n within the range 1 to k. The transition rules would specify how the machine moves from one state to another based on the current input and the state it is in. The input would be the values of n and k, and the output would be whether the machine accepts or rejects the input.

Use the Cook-Levin reduction to construct a boolean circuit that is satisfiable if and only if the Turing machine accepts the input (n,k). This would involve defining the circuit using logical gates and connections, and ensuring that it has the desired behavior. The Cook-Levin reduction is a method for constructing a boolean circuit that is satisfiable if and only if a given Turing machine accepts its input. This means that the circuit will have the same behavior as the Turing machine, in terms of whether it accepts or rejects a given input. To construct the circuit, we would need to specify the logical gates and connections that make up the circuit, and ensure that they are arranged in such a way that the circuit is satisfiable if and only if the Turing machine accepts the input.

Convert the boolean circuit into a formula using the reduction from Circuit-SAT to 3-SAT. This would involve expressing the circuit as a logical formula using variables and logical operators, in a way that is equivalent to the behavior of the original circuit. The reduction from Circuit-SAT to 3-SAT is a method for converting a boolean circuit into a logical formula that is satisfiable if and only if the original circuit is satisfiable. This means that the formula will have the same behavior as the original circuit, in terms of whether it is satisfiable for a given input. To convert the circuit into a formula, we would need to express the logical gates and connections of the circuit using logical operators and variables, and ensure that the resulting formula is equivalent to the behavior of the original circuit.

Convert the formula into a graph using the reduction from 3-SAT to Hamiltonian Path. This would involve representing the formula as a graph, with vertices and edges, in a way that is equivalent to the behavior of the original formula. The reduction from 3-SAT to Hamiltonian Path is a method for converting a logical formula into a graph that has a Hamiltonian path if and only if the original formula is satisfiable. This means that the graph will have the same behavior as the original formula, in terms of whether it has a Hamiltonian path for a given input. To convert the formula into a graph, we would need to represent the logical variables and operators of the formula as vertices and edges of the graph, and ensure that the resulting graph is equivalent to the behavior of the original formula.

(Last and easy part) Use a Hamiltonian Path oracle to determine whether the graph has a Hamiltonian path. This could be implemented using an algorithm or other tool that is able to determine whether a given graph has a Hamiltonian path.

class TuringMachine:
    # initialize the Turing machine with the values of n and k
    def __init__(self, n, k):
        self.n = n
        self.k = k
        self.initial_state = None
        self.accept_state = None
        self.reject_state = None
        self.transition_rules = {}

    # set the initial state of the Turing machine
    def set_initial_state(self, state):
        self.initial_state = state

    # set the accept state of the Turing machine
    def set_accept_state(self, state):
        self.accept_state = state

    # set the reject state of the Turing machine
    def set_reject_state(self, state):
        self.reject_state = state

    # add a transition rule to the Turing machine
    def add_transition_rule(self, state, input, next_state, output):
        # initialize the dictionary for the given state if it does not exist
        if state not in self.transition_rules:
            self.transition_rules[state] = {}

        # add the transition rule to the dictionary for the given state
        self.transition_rules[state][input] = (next_state, output)

    # execute the Turing machine on the given input and return the result
    def execute(self, input):
        # set the current state to the initial state
        current_state = self.initial_state

        # while the current state is not the accept or reject state,
        # execute the transition rules based on the current input
        while current_state != self.accept_state and current_state != self.reject_state:
            next_state, output = self.transition_rules[current_state][input]
            current_state = next_state
            input = output

        # return the result of the Turing machine execution
        if current_state == self.accept_state:
            return "accept"
        else:
            return "reject"

    # return a string representation of the Turing machine
    def __str__(self):
        # create a string representation of the Turing machine
        tm_str = "Turing Machine:\n"
        tm_str += "  Initial state: " + str(self.initial_state) + "\n"
        tm_str += "  Accept state: " + str(self.accept_state) + "\n"
        tm_str += "  Reject state: " + str(self.reject_state) + "\n"
        tm_str += "  Transition rules:\n"
        for state in self.transition_rules:
            for input in self.transition_rules[state]:
                next_state, output = self.transition_rules[state][input]
                tm_str += "    " + str(state) + " on " + str(input) + " => " + str(next_state) + " with output " + str(output) + "\n"
         # return the string representation of the Turing machine
        return tm_str

    # set the initial state of the Turing machine
    def set_initial_state(self, state):
        self.initial_state = state

    # set the accept state of the Turing machine
    def set_accept_state(self, state):
        self.accept_state = state

    # set the reject state of the Turing machine
    def set_reject_state(self, state):
        self.reject_state = state

    # add a transition rule to the Turing machine
    def add_transition_rule(self, state, input, next_state, output):
        self.transition_rules[state][input] = (next_state, output)

    # execute the Turing machine on the given input and return the result
    def execute(self, input):
        # set the current state to the initial state
        current_state = self.initial_state

        # while the current state is not the accept or reject state,
        # execute the transition rules based on the current input
        while current_state != self.accept_state and current_state != self.reject_state:
            next_state, output = self.transition_rules[current_state][input]
            current_state = next_state
            input = output

        # return the result of the Turing machine execution
        if current_state == self.accept_state:
            return "accept"
        else:
            return "reject"
# define the function for performing a depth-first search
def dfs(vertex, visited, vertices):
    # perform a depth-first search on the given vertex and return the result
    visited.add(vertex)
    if len(visited) == len(vertices):
        return True
    for neighbor in vertex.neighbors:
        if neighbor not in visited:
            has_path = dfs(neighbor, visited, vertices)
            if has_path:
                return True
    return False

# define the function for checking if a graph has a Hamiltonian path
def check_for_hamiltonian_path(graph):
    # check if the graph has a Hamiltonian path and return the result
    has_path = False
    for vertex in graph.vertices:
        visited = set()
        has_path = dfs(vertex, visited, graph.vertices)
        if has_path:
            break
    return has_path
# define the Graph class for representing a graph
class Graph:
    # initialize the graph with a list of vertices
    def __init__(self, vertices):
        self.vertices = vertices

    # add a vertex to the graph
    def add_vertex(self, vertex):
        self.vertices.append(vertex)

    # add an edge to the graph
    def add_edge(self, vertex1, vertex2):
        self.vertices[vertex1].add_neighbor(vertex2)
        self.vertices[vertex2].add_neighbor(vertex1)
    def has_hamiltonian_path(self):
        # check if the graph has a Hamiltonian path and return the result
        has_path = check_for_hamiltonian_path(self)
        return has_path

# define the states of the Turing machine
START = "Start"
ACCEPT = "Accept"
REJECT = "Reject"
# define the function for constructing a boolean circuit using the Cook-Levin reduction
def cook_levin_algorithm(clauses):
    # create an empty list to store the variables in the boolean circuit
    variables = []

    # for each clause in the list of clauses, add the variables in the clause to the list of variables
    for clause in clauses:
        for variable in clause:
            if variable != 0:
                variables.append(variable)

    # create the boolean circuit using the list of variables and clauses and return the result
    circuit = create_circuit(variables, clauses)
    return circuit
# define the function for constructing a boolean circuit using the Cook-Levin reduction
def cook_levin(n, k):
    # create an empty list to store the clauses in the boolean circuit
    clauses = []

    # for each value of i from 1 to n, create a clause that represents the value of x_i
    for i in range(1, n+1):
        clause = (i, i, 0)
        clauses.append(clause)

    # create a clause that represents the negation of the value of x_n+1 (the accept state)
    clause = (n+1, 0, 0)
    clauses.append(clause)

    # for each value of i from 1 to k, create a clause that represents the transition from state x_i
    # to state x_i+1
    for i in range(1, k+1):
        clause = (i, i+1, 0)
        clauses.append(clause)

    # create a clause that represents the transition from state x_k+1 (the reject state)
    # to state x_k+1 (the reject state)
    clause = (k+1, k+1, 0)
    clauses.append(clause)

    # create the boolean circuit using the clauses and return the result
    circuit = cook_levin_algorithm(clauses)
    return circuit
# define the function for creating a formula in conjunctive normal form (CNF)
def cnf(clauses):
    # create the formula in CNF using the list of clauses and return the result
    formula = "&".join(clauses)
    return formula

# define the function for creating a formula using the Circuit-SAT reduction
def create_formula(clauses):
    # create the formula using the list of clauses and return the result
    formula = cnf(clauses)
    return formula
# define the function for converting a boolean circuit into a formula using the Circuit-SAT reduction
def circuit_sat(circuit):
    # create an empty list to store the clauses in the formula
    clauses = []

    # for each gate in the boolean circuit, create a clause that represents the output of the gate
    # based on the inputs to the gate
    for gate in circuit:
        # get the inputs and output of the gate
        inputs = gate[0]
        output = gate[1]

        # create a clause that represents the output of the gate based on the inputs
        clause = (inputs[0], inputs[1], -output)
        clauses.append(clause)

    # create the formula using the clauses and return the result
    formula = create_formula(clauses)
    return formula

def create_circuit(n, k):
    # create the boolean circuit for the given input (n, k) using the Cook-Levin theorem
    circuit = cook_levin(n, k)
    return circuit

# define the function for converting a boolean circuit into a formula using the Circuit-SAT reduction
def convert_to_formula(circuit):
    # convert the given boolean circuit into a formula in conjunctive normal form (CNF)
    # using the Circuit-SAT reduction
    formula = circuit_sat(circuit)
    return formula

# define the function for creating a vertex that represents a clause in a formula
def clause_to_vertex(clause):
    # create the vertex that represents the clause and return the result
    vertex = ",".join(clause)
    return vertex

# define the function for creating a graph from a list of vertices
def create_graph_from_vertices(vertices):
    # create the graph using the list of vertices and return the result
    graph = Graph(vertices)
    return graph

# define the function for creating a vertex that represents a clause in a formula
def create_vertex(clause):
    # create the vertex that represents the clause and return the result
    vertex = clause_to_vertex(clause)
    return vertex

# define the function for creating a graph from a list of vertices
def create_graph(vertices):
    # create the graph using the list of vertices and return the result
    graph = create_graph_from_vertices(vertices)
    return graph
# define the function for converting a formula into a graph using the 3-SAT reduction
def three_sat(formula):
    # create an empty list to store the vertices in the graph
    vertices = []

    # for each clause in the formula, create a vertex that represents the clause
    for clause in formula:
        vertex = create_vertex(clause)
        vertices.append(vertex)

    # create the graph using the list of vertices and return the result
    graph = create_graph(vertices)
    return graph

# define the function for converting a formula into a graph using the 3-SAT reduction
def convert_to_graph(formula):
    # convert the given formula into a graph using the 3-SAT reduction
    graph = three_sat(formula)
    return graph

# define the function for checking if a graph has a Hamiltonian path
def hamiltonian_path(graph):
    # check if the graph has a Hamiltonian path and return the result
    has_path = graph.has_hamiltonian_path()
    return has_path
# define the function for using a Hamiltonian Path oracle to determine whether a graph has a Hamiltonian path
def oracle(graph):
    # use the Hamiltonian Path oracle to determine whether the given graph has a Hamiltonian path
    result = hamiltonian_path(graph)
    return result
# define the function for constructing a boolean circuit using the Cook/Levin reduction
def cook_levin_reduction(n, k):
    # create the boolean circuit for the given input (n, k)
    circuit = create_circuit(n, k)
    return circuit

# define the function for converting a boolean circuit into a formula using the Circuit-SAT reduction
def circuit_sat_reduction(circuit):
    # convert the given boolean circuit into a formula
    formula = convert_to_formula(circuit)
    return formula

# define the function for converting a formula into a graph using the 3-SAT reduction
def three_sat_reduction(formula):
    # convert the given formula into a graph
    graph = convert_to_graph(formula)
    return graph

# define the function for using a Hamiltonian Path oracle to determine whether a graph has a Hamiltonian path
def hamiltonian_path_oracle(graph):
    # use the Hamiltonian Path oracle to determine whether the given graph has a Hamiltonian path
    result = oracle(graph)
    return result

# define the function for creating a non-deterministic Turing machine
def create_turing_machine(n, k):
    # create the Turing machine using the values of n and k and return the result
    machine = TuringMachine(n, k)
    return machine

# define the function for finding the answer to the question of whether n has a non-trivial factor less than k
def has_nontrivial_factor(n, k):
    # create a non-deterministic Turing machine that accepts if there exists a factor of n less than k
    # and rejects otherwise
    turing_machine = create_turing_machine(n, k)

    # use the Cook/Levin reduction to construct a boolean circuit that is satisfiable iff
    # the Turing machine accepts (n, k)
    circuit = cook_levin_reduction(turing_machine)

    # use the Circuit-SAT reduction to convert the boolean circuit into a formula
    formula = circuit_sat_reduction(circuit)

    # use the 3-SAT reduction to convert the formula into a graph
    graph = three_sat_reduction(formula)

    # use the Hamiltonian Path oracle to determine whether the graph has a Hamiltonian path
    result = hamiltonian_path_oracle(graph)

    # since reductions are answer-preserving, the result given by the Hamiltonian Path oracle
    # is the same as the answer to the question of whether n has a non-trivial factor less than k
    return result

# define the main function that will be called to find the answer to the question of whether n has a non-trivial factor less than k
def main():
    # prompt the user for the values of n and k
    n = input("Enter the value of n: ")
    k = input("Enter the value of k: ")

    # find the answer to the question of whether n has a non-trivial factor less than k
    result = has_nontrivial_factor(n, k)

    # print the result to the user
    print("The answer to the question is:", result)

# call the main function to find the answer to the question of whether n has a non-trivial factor less than k
main()
```

# Answer
Yes, your reduction looks correct, as far as I can see. I only skimmed it and didn't check every detail carefully.

A computer scientist would probably give a shorter proof that such a reduction exists. First, they would show that the factoring problem is in NP: specifically, to test whether $n$ has a factor less than $k$, a simple witness/certificate for "yes" instances is to output that factor. Then, they would note that the Hamiltonian path problem is known to be NP-complete. Finally, they would note that the definition of NP-complete implies that there is a reduction from any problem in NP to Hamiltonian path, and thus from factoring to Hamiltonian path.

Notice how the computer scientist relies on theorems/facts that have been previously proven by others and are widely accepted, without having to re-iterate the details of those proofs. This provides a form of "abstraction" (in the same way that calling library functions, or decomposing your program into subroutines that you call, makes your code easier to understand) and makes the proof much easier for others to check.

Now, if you want to find an explicit reduction, you could expand the proof of each of those statements above, and you'd obtain such a proof. For instance, you'd find that a standard proof of NP-completeness for Hamiltonian path combines a proof of NP-completeness for SAT (using the Cook-Levin theorem) together with a reduction from SAT to Hamiltonian path. Expanding all of that out leads to exactly the construction you described in your post. This is kind of a tedious exercise that is straightforward to do once you understand the concepts and proofs but is tedious and lengthy to describe in full, so computer scientists normally wouldn't type it all out and instead rely on others to be able to carry out that exercise. It's good that you were able to do it, and it looks like you did it well. This is a good test of your understanding, and it looks like you do understand the subject well.
> 3 votes

---
Tags: algorithms, complexity-theory, graphs, turing-machines, np-complete
---


# Question
Title: What is wrong with this proof that shows every language over $\Sigma=\{0, 1\}$ is recognizable?
In the following let $\Sigma=\\{0, 1\\}$. I'll prove that *every* language over $\Sigma$ is recognizable.

Let $L\subseteq\Sigma^\*$. Let $w\_1,w\_2,\ldots$ be the list of words in $L$. For every $i=1,2,\ldots$, let $M\_i$ be the Turing machine that *decides* the language $\\{w\_i\\}$, which trivially exists. Consider a Turing machine $M$ that works as follows.

> On input $v$, run $M\_1, M\_2, \ldots$ in order, and if at any moment some $M\_i$ accepts $v$, $M$ accepts $v$.

I argue that $M$ precisely recognizes $L$. There are two cases.

* Case 1: $v\in L$. This means $v=w\_i$ for some $i$. Hence $M\_i$ will accept $v$, making $M$ accept $v$.
* Case 2: $v\notin L$. This means $v\ne w\_i$ for every $i$. Hence every $M\_i$ will reject $v$ and $M$ will never halt.

This completes my proof. However I am certain that there are some languages over $\Sigma$ that are unrecognizable. What is wrong with my proof?

# Answer
> 2 votes
The problem is that $M$ doesn't (in general) exist.

If $L$ is infinite, then there will be infinitely many $M\_i$. So you can't do something like building all the states of all the $M\_i$ into $M$ in some kind of sequence, as that would lead to infinitely many states.

Instead, you would have to try to build $M$ via something like a process that can enumerate all the $M\_i$, and simulate each of them on the given input. Now, your argument shows that this would allow (semi) recognizing $L$, which means that enumerating all the $M\_i$ must be at least as difficult as recognizing $L$. So, we should conclude that if $L$ cannot be recognized, then $\\{M\_i\\}$ can't be enumerated.

---
Tags: formal-languages, turing-machines, turing-recognizable
---


# Question
Title: Complexity of unbounded Gaussian convolution
What is the asymptotic complexity of doing a convolution of an unbounded Gaussian on an NxN input matrix $M$?

The naive approach is $O(n^4)$ ($R\_{ij} = \sum\_{k=1}^{n}\sum\_{l=1}^{n}M\_{kl}\*g(\sqrt{(k-i)^2 + (l-j)^2})$; $O(n^2)$ work on each of $O(n^2)$ elements); there is a fairly trivial lower bound of $O(n^2)$ (at least, assuming an arbitrary input and output matrix, at least one of which is explicitly represented).

I suspect the true asymptotic complexity here is far closer to $O(n^2)$ than $O(n^4)$; I am aware merely of the existence of methods of speeding up convolutions, but I am nowhere near familiar enough to know what said methods are or if they are applicable in this case.

# Answer
Gaussian kernel is separable, which means you can do 1D-convolutions on every row, and then on every column. This already gives you $O(N^3)$ almost for free. If you do 1D-convolutions using FFT, then it'll be just $O(N^2 \log N)$.
> 3 votes

# Answer
Using FFT the time complexity can be reduced to $O(n^2 log^2n)$ see this answer
> 1 votes

---
Tags: algorithms, asymptotics, matrices
---


# Question
Title: The meaning of Tautology and Contradiction in Complexity theory
I recently had this question answered on stack exchange:
if X is in NP but Y is not in NP then can X be reduced to Y?

The answer proposed a counter example using an element of complexity theory I had not given much thought to, specifically it was the problem

> $A = \emptyset$

that is, $A$ is the empty problem (or contradiction problem) where $\forall$ inputs $x$, $x \not\in A$

The role of $A = \emptyset$ in my answered question was that it served as problem in $NP$ that could be reduced to any other problem, including those not in $NP$, thereby giving a direct counter example to the statement: $X \in NP \land Y \not\in NP \implies X \not\le^m\_p Y$

What interests me was the implication that $A = \emptyset$ could be polynomial-time, many-one reduced to any other problem and that $A \in NP$.

This makes sense to me as these two implication seems vacuously true:

> Let $B$ be any other problem such that $B \neq \emptyset$. Now $A \le^m\_p B$ if $\exists$ some polynomial reduction $f$ such that $\forall$ inputs $x$, $x \in A \iff f(x) \in B$. But since $\not\exists x, x \in A$ by the definition of A then the reduction of $A$ to any $B$ would be a trivial one in that no matter what the given input $x$, the reduction $f(x)$ could simply produce a same input instance for $B$ such that $f(x) \not\in B$

> $A \in NP$ since it seems clear that verifying an input to a problem that always returns false can be trivially accomplished in polynomial time in that we don't really even need to verify anything since there is no input instance to $A$ that would evaluate to true

Using the same logic as above this leads me to reason that there is a tautology problem $C$ such that $\forall$ inputs $x$, $x \in C$ and that $C \in NP$ and $C$ can be polynomial-time, many-one reduced to any other problem just like $A$

Is this true? or have I made an erroneous assumption? And what other useful properties are possessed by the contradiction and tautology problems $A$ and $C$?

# Answer
You've actually missed an important prerequisite in your argument that $\emptyset \leq\_m^p B$: You need that $B \neq \Sigma^\*$ (the "tautology" problem $C$ you introduce later, where every instance is a "yes"-instance). But we do get that $\emptyset \leq\_m^p B$ iff $B \neq \Sigma^\*$, and with a very similar argument, that $\Sigma^\* \leq\_m^p B$ iff $B \neq \emptyset$.

I wouldn't really consider these useful examples. They are more annoying examples, i.e. require us to make exceptions in statements that would otherwise be true (eg, we would have liked to say "If $X \in \mathrm{P}$ and $Y$ arbitrary, then $X \leq\_m^p Y$" - but we need to exclude $Y = \emptyset$ and $Y = \Sigma^\*$ to make it true).
> 1 votes

---
Tags: complexity-theory, np, decision-problem
---


# Question
Title: How do I show language consisting prime number of 0s or prime number of 1s is not context-free?
The language is: `L1 = {w | n0(w) or n1(w) is prime}`

n0 means number of 0s and n1 means number of 1s I can show a^n (n is prime) is not context-free. But I can't find any solution for this one.

# Answer
> 0 votes
Suppose it is context-free and let $n$ be the pumping length.

Consider $u = 0^p$, where $p$ is any prime number greater than $n$. It is clear that $u \in L$. The pumping lemma for context-free languages states that there exists a decomposition $u = vwxyz$ such that:

1. $|wxy| \leqslant n$;
2. $|wy| \> 0$;
3. for any $k\geqslant 0$, $vw^kxy^kz\in L$.

But for $k = p + 1$, $|vw^kxy^kz| = p + p |wy| = p(|wy| + 1)$ is not a prime number. We conclude that $vw^kxy^kz\notin L$ and by contradiction that $L$ is not context-free.

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


# Question
Title: How do I create a circuit based on this truth table? The solution I implemented is not working as expected
I am trying to create a circuit based on this truth table below: can you describe how to make the circuit using only logic gates

```
In_1 In_2 In_3  Out
 0    0    0     0
 0    0    1     1
 0    1    0     1
 0    1    1     1
 1    0    0     1
 1    0    1     1
 1    1    0     1
 1    1    1     1

```

This is what I have done so far

However, this circuit is not working as expected. It is giving me this error:

Please let me know what I am doing wrong and how do I fix this? Thanks in Advance!

# Answer
I don't know this software but as you have a fan-in of at least three, a simple OR gate should suffice as your function is 1 if at least one input is set to 1.

The input $(1, 0, 0)$ is evaluated to $0$ as your AND gate will return $0$ and use this result together with the $0$s from $x\_2, x\_3$ in the OR gate but I don't see what is wrong with the input $(1, 1, 1)$. It might be that the expected output is wrongly specified there?
> 1 votes

---
Tags: algorithms, formal-languages, circuits
---


# Question
Title: Asymptotic calculation check for triple-nested for-loops
I have the following repetition structure:

```
sum = 0
for (i = 0; i < n; i++) {
   for (j = 0; j < i*i; j++) {
      for (k = 0; k < j; k++) {
         sum++
      }
   }
}

```

By the following, I have reasoned the runtime of this structure to be in $O(n^7)$ :

$\sum\_{i=1}^{n} (\sum\_{j=1}^{i^2}(\sum\_{k=1}^{j} k))$

$= \sum\_{i=1}^{n}(\sum\_{j=1}^{i^2}(\frac{j^2+j}{2}))$

$= \frac{1}{2} (\sum\_{i=1}^{n}(\sum\_{j=1}^{i^2}j^2 + \sum\_{j=1}^{i^2}j))$

$= \frac{1}{2} (\sum\_{i=1}^{n}(\frac{i^2(i^2+1)(2i^2+1)}{6} + \frac{i^2(i^2+1)}{2}))$

$= \frac{1}{2} (\sum\_{i=1}^{n} \frac{2i^6+3i^4+i^2}{6} + \sum\_{i=1}^{n} \frac{i^4+i^2}{2})$

$= \frac{1}{2} (\frac{1}{3} \sum\_{i=1}^{n} i^6 + \frac{1}{2} \sum\_{i=1}^{n} i^4 + \frac{1}{6} \sum\_{i=1}^{n} i^2 + \frac{1}{2} \sum\_{i=1}^{n} i^4 + \frac{1}{2} \sum\_{i=1}^{n} i^2)$

$=\frac{1}{6} \sum\_{i=1}^{n} i^6 + \frac{1}{2} \sum\_{i=1}^{n} i^4 +\frac{1}{3} \sum\_{i=1}^{n} i^2$

$\approx \frac{n^7}{42} + \frac{n^5}{10} + \frac{n^3}{9}$

$\therefore \text{runtime} \in O(n^7)$

The approximation at the end comes from the rule:

$\sum\_{i=1}^{n} i^k \approx \frac{n^{k+1}}{k+1}$

Is this correct? I'm fairly confident that it is but some of the results that I've gotten from running the structure in JMH (Java Micro-Benchmarking Harness) don't really reflect this result so I just want to confirm.

# Answer
> 1 votes
The inner loop always executes `sum++` $j$ times. The middle loop lets $j$ vary from $0$ to $i^2-1$, so the count equals $\dfrac{(i^2-1)\\,i^2}2$. The outer loop runs for $i$ from $0$ to $n-1$ hence

$$\sum\_{i=0}^{n-1}\dfrac{(i^2-1)\\,i^2}2\sim\frac{n^5}{10}.$$

---

There is no real need to give a more accurate expression, as you should account for the other statements anyway.

# Answer
> 0 votes
As Yuval Filmus and gnasher729 have pointed out my original equation for the repetition structure is indeed wrong. I believe this to be the true correct answer:

$\sum\_{i=1}^{n} (\sum\_{j=1}^{i^2} j)$

$= \sum\_{i=1}^{n} (\frac{i^4+i^2}{2})$

$= \frac{1}{2} \sum\_{i=1}^{n}i^4 + \frac{1}{2} \sum\_{i=1}^{n}i^2$

$\approx \frac{n^5}{10} + \frac{n^3}{6}$

$\therefore runtime \in O(n^5)$

---
Tags: asymptotics, check-my-answer
---


title: Two's complement using logic gates

text:
# Question
Title: Two's complement using logic gates
How can a 4-bit two's complement operation be implemented using boolean NOR gate? I search lots of 4-bit two's complement videos and articals, but most of them are using XOR gate.

# Answer
> 1 votes
A NOR can serve as an inverter, so 1's complement is easy. Now you need to implement two-bit adders to increment the result. A sum is a XOR ($a\oplus b=\overline{\overline{(\overline{(a+b)}+\overline{(\overline a+\overline b)})}}$, and the carry out an AND ($a\cdot b=\overline{\overline a+\overline b}$).

# Answer
> 0 votes
Boolean NOR is universal, so you can construct an XOR gate or any other gate from NOR gates, and then use the methods you've read about.

---
Tags: boolean-algebra
---


# Question
Title: Why do we care about termination analysis?
Why is it important to know if a program terminates or not? In particular, what are some consequences of a non-terminating program?

# Answer
First, the halting problem is the fundamental building block that enables us to prove that many, many problems we care about are undecidable. See https://en.wikipedia.org/wiki/List\_of\_undecidable\_problems.

Second, in some contexts, it is important to know that a program will terminate and in some bounded amount of time. For instance, in an airplane with fly-by-wire, it is important to know that when the pilot presses the left rudder pedal, then the rudder will turn left within a reasonable amount of time. This usually relies on worst-case execution time analysis, which is a bit different from the methods used for solving the halting problem, so I'm not sure whether it is what you are asking about or not. See https://en.wikipedia.org/wiki/Worst-case\_execution\_time, https://en.wikipedia.org/wiki/Termination\_analysis, https://en.wikipedia.org/wiki/Safety-critical\_system.
> 3 votes

# Answer
A lot of information processing problems can be modelled as search problems: find a solution within a set. For example, find a number with certain properties (e.g. in numerical analysis or cryptography), or find a point in space with certain properties (e.g. in image processing or robotics), or find a string with certain properties (e.g. in databases), etc.

It is desirable to know whether a solution exists. One way to prove that a solution exists is to write a program that finds a solution. This is an especially nice way to prove the existence of a solution because it's very practical: you can run the program, and you'll get a solution.

How do you know that the program finds a solution? Supposing that the program stops after it prints out a solution (which is what we want in practice, if the goal of the program is to search for a solution), it takes two things:

1. When the program outputs a value, this value is a solution.
2. The program actually does output a value. This means that the program terminates.

In this very common setting, termination distinguishes useful programs from boring ones. Programs that are only useful for their final output are only useful if they terminate. Programs that just do nothing forever are all indistinguishable (as long as you're just interested in their output) and not useful. (Sometimes we're interested in more than a program's final output. But cases where the final output is the only thing that matters are common enough that they're very widely studied.)

As an added benefit, a lot of other interesting properties of programs are equivalent to determining whether a certain modification of the program terminates. For example, “does the function `f` ever return the value 0?” is equivalent to “does the program `function x -> if f(x) = 0 then loop forever`”. Another example: “does the program `f(); g();` actually execute `g()`?” is equivalent to “does `f()` terminate?”, assuming `f` doesn't call `g`. Since a lot of questions of the form “does the program P have this property?” are equivalent to “does the program P' terminate”, having theories about program termination is a good basis for theories about all kinds of other useful properties of programs.
> 3 votes

# Answer
It's a fundamental property of any algorithm that it halts after some finite number of steps. Indeed, for many problems, it can be shown that such an algorithm does indeed exist, i.e., that no matter what (valid) input you give, it will always halt. That's a very desirable property just because such procedures are much more useful in practice.
> 1 votes

---
Tags: termination
---