# Question
Title: What is the proper use case for count min sketch
Most of the sources about count min sketch say it usage is to give counts for several "items" stored "inside".

However in the following this question
What is the proper way to calculate dimensions of count min sketch
I made valid point if count min sketch is very saturated, it will always return wrong overestimated count, no matter what "item" it is queried about.

This is when the "items" are much more than the columns of the count min sketch, for example let suppose we have 272 columns and 1'000 items. Then no matter of the hash function, all counters will be equal to 1000 / 272 = 3.

Only exception will be frequent items (heavy hitters) which will have count bigger than 3.

What are the guarantees of the result?

* Obviously more frequent items will have higher count.
* Count seems to be proportional to the item frequency?
* anything else?

What count min sketch is good for?

* Obviously it is *NOT* good for keeping count of items.
* If is paired with heap - detecting heavy hitters / abnormalities? - I can see similarities with Misra - Gries algorithm, since it also can not give exact count, but paired with heap detects heavy hitters very well.
* anything else?

# Answer
You stated "Obviously it is NOT good for keeping count of items".

The sentence shows that you lack a clear understanding of both the problem that the Count-min sketch tries to solve (in particular how much difficult it is) and of the techniques it actually uses.

Let's start with the problem. Count-min is a frequency estimator. Why an estimator? Why not use exact counts? Let $\mathcal{U}$ be the universe set from which the items belonging to a stream $\sigma$ are drawn, and let $m$ be the cardinality of $\mathcal{U}$. The stream $\sigma$ may be even a continuous and unbounded sequence of items. Without loss of generality, we a priori set its length $n$ for convenience. In order to store exact counts you need $\Omega(m)$ space, i.e. space linear in the cardinality of the universe set. But, $m$ may be arbitrarily high so that in many situations exact counts are simply ruled out: at least, exact count are not practical.

This is why we use frequency estimators: we can't afford to use linear space, and frequency estimators can work with sub-linear space. This is the first key point you need to understand: if we use less than linear space, we must forget solving exactly the frequency estimation problem.

So, we have to settle for an approximate solution. Let $\[x\] = \\{1,2,\cdots,x\\}$. The frequency of an item is defined as follows.

Given a stream $\sigma$ of $n$ elements, the frequency of an item $s\in \mathcal{U}$ is the number of occurrences of $s$ in $\sigma$, that is $f\_\sigma(s) = \left\vert\\{i\in \[n\]: s\_i = s\\}\right\vert$.

A stream $\sigma$, whose items are drawn from the universe $\[m\]$, implicitly defines a frequency vector, $\mathbf{f}=(f\_1, f\_2, \ldots, f\_m)$, where $f\_i=f\_\sigma(i)$ is the frequency of item $i$. We can interpret $\sigma$ as a sequence of updates to $\mathbf{f}$: initially $\mathbf{f}$ is the null vector, then, for each item in the stream, the entry in $\mathbf{f}$ corresponding to the frequency of that item is incremented by one.

$\epsilon$-approximate frequency estimation problem:

Given a stream $\sigma$ of $n$ elements drawn from the universe $\[m\]$, the frequency vector $\mathbf{f}$ defined by $\sigma$, and a value ${0\<\epsilon\<1}$, the $\epsilon$-approximate frequency estimation problem consists in computing a vector $\mathbf{\hat{f}}=(\hat{f}\_1, \hat{f}\_2, \ldots, \hat{f}\_m)$, so that $\left\vert\hat{f}\_i-f\_i\right\vert \le \epsilon \lVert\mathbf{f}\rVert\_\ell$, for each $i\in\[m\]$ where $\ell$ can be either 1 or 2.

The quality of the output provided by a randomized algorithm (Count-min is a randomized algorithm) depends on the error committed estimating the quantity of interest. This is the second key point that you need to truly understand: we are interested only to randomized algorithms that may be wrong, but only with some small and controlled probability. In particular, we may require either an *additive* or a *multiplicative* approximation. Here, we define only what an additive approximation means, since Count-min relies on this type of approximation.

Let $A(\sigma)$ denote the output of a randomized streaming algorithm $A$ on input $\sigma$; it is worth noting here that $A(\sigma)$ is a random variable. Moreover, let $f(\sigma)$ be the function that $A$ is supposed to compute. The algorithm $A$ ($\epsilon$, $\delta$) additively approximates $f$ if $\Pr\[|A(\sigma) - f(\sigma)| \> \epsilon\] \leq \delta$. Here ${0\<\epsilon\<1}$ is an accuracy parameter, and ${0\<\delta\<1}$ is a probability of failure (our confidence in the result).

Let $w$ and $d$ be respectively the number of buckets (columns) and rows of the sketch. Count-min provides the following guarantees for an estimate $\hat{a}\_i$ of the item $a\_i$:

if $w=\left\lceil\frac{e}{\varepsilon}\right\rceil$ and $d=\left\lceil\ln \frac{1}{\delta}\right\rceil$, an estimate $\hat{a}\_i$ is such that $a\_i \leq \hat{a}\_i$ and $\hat{a}\_i \leq a\_i+\varepsilon\\|\mathbf{f}\\|\_1$ with probability at least 1 - $\delta$.

Note that the length of the stream is not relevant, and, indeed, the sketch dimensions are independent from the length of the stream.

The sketch provides this remarkably good additive approximation through a clever combination of the following techniques:

* it is designed to be extremely close (with regard to the previous additive bound) to exact on expectation (proved by using a sum of indicator variables and the linearity property of the expectation);
* how much does it drift from the expectation? Provably, not enough to provide bad estimates (again, with regard to the additive bound): a concentration of measure inequality (Markov inequality) can be used to prove this fact;
* the probability of getting good estimates is amplified by a well known trick for a randomized algorithm, i.e. the use of multiple repetitions of experiments: in the sketch case, you can think of one row as an experiment, the sketch is aptly sized so that the number of rows provides the required probability;
* it uses *pairwise independent* hash functions, which, informally stated, means that any pair of items is unlikely to collide. Of course, collisions happen for largely sized streams, but they are *exploited* by the algorithm, not suffered (you must be truly unlucky for collisions to be able to make the probabilistic bound invalid).
> 1 votes

---
Tags: algorithms, streaming-algorithm
---


# Question
Title: Prove that $o(g(n)) \cap \omega(g(n))$ is the empty set
This question is from CLRS (3rd Edition).

So, I know that this is true, but I can't seem to prove it. My approach was the following:

Let $f(n) = o(g(n)) \Rightarrow 0 \le f(n) \< c\_2g(n)$ for some $c\_2 \> 0$ and for all $n \ge n\_1 \ge 0$

Similarly, $f(n) = \omega(g(n)) \Rightarrow 0 \le c\_1g(n) \< f(n)$ for some $c\_1 \> 0$ and for all $n \ge n\_2 \ge 0 $

Therefore, $0 \le c\_1g(n) \< f(n) \< c\_2 g(n)$

But this can be true for $f(n) = 2n$ and $g(n) = n$ and $c\_1 = 1$, $c\_2 = 3$, and $n\_1 = n\_2 = 1$

So what exactly am I not picking up?

# Answer
> 1 votes
What is wrong is your definition of $o$ and $\omega$.

$f\in o(g)$ if and only if $f(n) = h(n)g(n)$ with $h(n) \underset{n\rightarrow +\infty}{\longrightarrow}0$.

$f\in \omega(g)$ if and only if $g\in o(f)$.

What you used as definition are $\mathcal{O}$ and $\Omega$ (which are different).

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


# Question
Title: Optimally partitioning the reciprocals of the first n integers
Do we know anything about the hardness of the optimization version of the multiway number partitioning problem when the set of numbers to partition consists of the reciprocals of the first $n$ integers? That is, for $n, k\in \mathbb{N}$, find sets $S\_1,\dots,S\_k$ such that

* $\bigcup\_{i=1}^k S\_i = \\{1, \frac{1}{2}, \frac{1}{3}, \ldots, \frac{1}{n}\\}$,
* $S\_i \cap S\_j = \emptyset$ for $i\neq j$

that minimizes the largest difference between two sets, i.e., that minimizes $\max\_{i,j}| \sum\_{x \in S\_i} x - \sum\_{y \in S\_j} y|$.

I am curious about other objective functions too. I am mainly interested about the effect of restricting the set of numbers to partition.

# Answer
The sum of all elements is H\_n (n-th harmonic number), approximately ln n + c where ln is the natural logarithm and c is quite small.

If k \> H\_n then the average size of a set is less than 1. So take {1} as the first set and you have H\_n - 1 and k-1 sets left. If the average is \> 1/2 then you take the set {1/2} etc until you have enough left for the sets. At that point it’s quite similar to bin packing, except the problem isn’t “how many bins of size s are needed” but “what is the smallest s so that k bins all contain more than s”.

Now if you were given n numbers then the problem size would be O(n) and the problem would be NP-complete. But the problem is given by two numbers, so the problem size is just log n + log k, so it’s much much harder relative to the problem size.
> 0 votes

---
Tags: algorithms, partitions
---


# Question
Title: Given a set of points $S$ which is a subset of a vector space $V$, find the smallest subspace which intersect $S$ in at least $k$ points
Given a set of points $S$ which is a subset of a vector space $V$ I want to want the smallest subspace of $A$ of $V$ such that $|A \cap S| \geq k $.

I suspect some variant of this problem would have already been studied but I have not been able to find it. Have anyone seen this or something similar before?

# Answer
In general, this problem is hard. For instance, if we have a vector space over $GF(2)$, then checking whether there is a one-dimensional subspace $A$ with the desired property is as hard as learning parity with noise (LPN). LPN is conjectured to be hard: I believe there are subexponential-time algorithms, but as far as I know, there are no known polynomial-time algorithms. The hardness will depend on the specific parameters, i.e., the dimension of $V$, the size of $S$, and the value of $k$.
> 1 votes

---
Tags: algorithms, linear-algebra
---


# Question
Title: How CPU uses wider address bus than register size?
i'm designing a CPU from scratch so i want it to be small. i decided to go with 4 bits registers. but 16 words of memory is a bit too small and i want more so i guess i need wider address bus (ie. 6). that raises a few questions:

1. how should i set address to memory address register?

* using multiple data registers at the same time?
    * by having a dedicated 'construction-site address register), setting that address using multiple instructions and only then do jump?
2. how to read an address from an instruction? in my program i want to have instruction `jump 0x2E`. but i read my program word by word. i can't fit opcode and 6-bit operand in a 4 bit instruction. i can't do it even if my address bus is the same as data bus. how this problem is solved in practice?

# Answer
> 0 votes
Look at early Intel processors designed under similar conditions, as 4004, 8008, 8051, 8080. In 8080, for example, 16-bit address is combined of register pairs like HL (so H+L), BC (B+C), DE (D+E), which also could be accessed separately (and there were few 16-bit operations, mainly for address handling).

In 8086, real address is combined of 16-bit segment shifted left by 4 bits plus 16-bit offset. Result is 20 bits.

In some successors of Mostek 6502, two special registers can specify high byte of address of "zero page" (memory operand for insrtructions with 1-byte address) and of stack.

To sum up, different designs from 1970s are all you need:)

---
Tags: computer-architecture, cpu, memory-hardware
---


# Question
Title: Is boolean formula equivalence problem for 2-CNFs $\mathsf{coNP}$-hard?
The problem:

> Given two boolean formulas in 2-CNF, decide if they are equivalent.

I know that the problem is $\mathsf{coNP}$-hard when at least one formula is in 3-CNF. However, the same proof of $\mathsf{coNP}$-hardness does not apply when both formulas are in 2-CNF.

Conversely, I don't see a straightforward way to show that this problem is in $\mathsf{NP}$.

What is the complexity of the problem? Can this somehow be reduced to (sub)graph isomorphism?

# Answer
I believe the problem is in $P$.

Let $\varphi,\psi$ be the two 2-CNF formulas. The plan of approach will be to test satisfiability of $\varphi \land \neg \psi$ and of $\psi \land \neg \varphi$. If either is satisfiable, then $\varphi,\psi$ are not equivalent; otherwise, they are equivalent.

How do we test satisfiability of $\varphi \land \neg \psi$? Write $\psi = C\_1 \land \dots \land C\_n$ where $C\_i$ are the 2-CNF clauses of $\psi$. $\varphi \land \neg \psi$ is satisfiable iff there exists $i$ such that $\varphi \land \neg C\_i$ is satisfiable. Note that $\neg C\_i$ is a 2-CNF formula (it is the conjunction of two literals), so $\varphi \land \neg C\_i$ is a 2-CNF formula. Therefore, for each $i$, we can test whether $\varphi \land \neg C\_i$ is satisfiable, using a standard algorithm to test satisfiability of 2-CNF formulas. If any of those are satisfiable, then so is $\varphi \land \neg \psi$; if not, then $\varphi \land \neg \psi$ is not satisfiable.

Do the same for $\psi \land \neg \varphi$.

The running time is quadratic.
> 2 votes

---
Tags: complexity-theory, satisfiability, boolean-algebra
---


# Question
Title: Can I speed up this multi-LCSS (Longest Common Substring) algorithm?
I'm creating a plagiarism detection algorithm in Python, which scores how much of document A has been plagiarised in document B, and returns all the copied sections in B that were plagiarised from A.

Here's my working version:

```
from textdistance import LCSStr

DEFAULT_MIN_SUBSTRING_LEN = 30

def get_doc_lcs_matches(
    doc1: str,
    doc2: str,
    min_substring_len: int = DEFAULT_MIN_SUBSTRING_LEN
):

    get_lcs = LCSStr()

    while True:

        # Find a satisfactory LCS:
        lcs = get_lcs(doc1, doc2)
        lcs_len = len(lcs)
        if lcs_len < min_substring_len:
            break
        yield lcs

        # Remove the found LCS substring from both strings:
        lcs_idx_1 = doc1.find(lcs)
        lcs_idx_2 = doc2.find(lcs)
        doc1 = doc1[:lcs_idx_1] + doc1[lcs_idx_1 + lcs_len:]
        doc2 = doc2[:lcs_idx_2] + doc2[lcs_idx_2 + lcs_len:]

def get_similarity(
    doc1: str,
    doc2: str,
    min_substring_len: int = DEFAULT_MIN_SUBSTRING_LEN,
    stop_score: float = None
):

    matches = []
    doc1_len = len(doc1)
    count = 0
    score = 0.0

    for match in get_doc_lcs_matches(doc1, doc2, min_substring_len):
        matches.append(match)
        count += len(match)
        score = count / doc1_len
        if stop_score and score >= stop_score:
            break

    return {
        "count": count,
        "score": score,
        "matches": matches
    }

```

I've added `stop_score` as a way to stop early if a certain plagiarism threshold has been reached, which helps speed this up considerably for my use case.

My problem is, however, this is still *extremely* slow for large documents (1 MB+), and I have to process quite a few!

I'm wondering if anyone can suggest anything that would improve efficiency? I'm also open to alternative solutions to my original problem.

**--- UPDATE ---**

@Pseudonym suggested tokenising. I considered this, but it won't suit my use case unfortunately:

* The documents are technical in nature and are about the same subject, so the vocabulary set is rather small.
* The kind of plagiarism I'm looking for is exclusively the copy & paste variety. I don't particular care to catch slight modifications, so don't need fuzzy or semantic matching.

Hence my current algorithm focuses on LCSS.

# Answer
Questions about specific programs or libraries are off-topic here, but let's talk about text similarity algorithms.

I have two suggestions that may help.

First off, consider tokenising the text into words first. It obviously depends on your goals, but I suspect that a score based on the number of matching words would be more informative than a score based on the number of matching characters, because it ignores whitespace. Case-folding is probably a good idea, and you could also consider stemming, if you want to catch near-similarities like changing the tense of a verb.

Second, if your goal is to find long runs of matches, LCSS is probably not the best way of doing this for a reason that you may not have considered: no matter how you compute it, a *longest* common substring may not be a *cleanest* common substring.

Consider two documents: Document A contains 10 'a' characters, and document B contains 20 'a' characters.

What you might hope is that a LCSS algorithm would match the 10 characters in document A with the first or last 10 characters in document B. But it's also a correct answer to match every second character in document B. That is, after all, still a common substring with the maximum possible length of 10 characters.

This specific simple case probably won't happen with most efficient LCSS algorithms, but it happens in practice on more complicated examples. The GNU diff program actually has a post-pass on its LCSS algorithm to make the diff "pretty".

A better approach would be to use suffix arrays. If you sort both documents into the same suffix array, which takes linear time and space, then substrings end up together in the sorted order, and finding long common substrings is straightforward.
> 1 votes

---
Tags: python, longest-common-substring
---


# Question
Title: Is there any reference materials on complexity analysis for lazy languages?
Is there any books, papers or articles on how to analyze the time complexity of programs written in lazy languages such as Haskell?

I know how laziness is implemented and how it can be expanded and thus analyzed, but is there any "intuitive" methods that does not go deep into the low level implementation principles of lazy evaluation?

# Answer
You could do worse than Chris Okasaki's *Purely Functional Data Structures*. It was published as a book, but here's the thesis version.

Another couple of theses that I haven't read, but may be worth trying to track down:

Meira, S.R.L., *On the efficiency of applicative algorithms.* PhD thesis, Computer Laboratory, University of Kent, p. 36. March 1985.

Stoye, W.,. *The implementation of functional languages using custom hardware.* PhD thesis, Computer Lab., University of Cambridge. May 1985.
> 1 votes

---
Tags: complexity-theory, programming-languages, functional-programming, haskell
---


title: Reference types

text:
# Question
Title: Reference types
Is a reference type (agnostic of PL) the object being pointed at, or the object doing the pointing?

I'm having a hard time wrapping my head around the concept fundamentally (of course, I have backgrounds in pointers, C, C++, Java, Prolog, Ocaml, etc. and am familiar with the implementations in all of them).

I mean fundamentally, from a programming languages sense, what exactly is a reference type?

You ask someone what a reference is:

* they might give you the C++ way (essentially a const ptr with implicit dereferences)
* the Java way (objects are references)

but for example, when I have `Dog x = new Dog()`, is the type of the object `Dog` or the type of `x` `Dog` (since fundamentally `x` is NOT the object itself, but a name for it -- which we call a reference to it)

I've tried giving some definitions:

* a reference type is one where there's a many to one mapping of names to objects (vs. one to one for primitives)
* a reference type can be addressed, a primitive cannot (in Java yes, C no)
* you can only gain access to the object types through references (again, doesn't generalize, and which is the `type`?)

I think it's essentially confusing because is the `value` of the type the value of the pointer, or the value of the thing pointed at? You can see how it doesn't quite generalize perfectly, because when you assign, you usually use the pointer's value, but otherwise, that's transparent and you treat it as the guy being pointed at.

It seems to mess up the semantics if you try to say it's a type in which multiple "values" are at play. Which is of that type, the reference or the object (considering the reference points to the object)?

# Answer
Neither. A type is not an object. An object has a type.

Objects don't do pointing. References do. A reference type refers to a value that is a reference to an object.

In Java, `int` is a value type. A `List` or (in your example) `Dog` is a value type. In `Dog x = new Dog();`, `x` gets assigned the type `Dog`, and the object created by `new Dog()` has type `Dog`.
> 0 votes

---
Tags: formal-languages, formal-grammars, terminology, programming-languages, type-theory
---


# Question
Title: Approximation algorithm with runtime complexity between poly(log(1/eps)) and poly(1/eps)?
Suppose we have an approximation algorithm to some maximization problem, that returns a solution with value $(1-\epsilon)\*OPT$.

* If the runtime of the algorithm is polynomial in the input size and $1/\epsilon$, then it is called an FPTAS.
* If the runtime is polynomial in the input size and $\log(1/\epsilon)$, then the algorithm is called polynomial, since $\log(1/\epsilon)$ is the size of the binary representation of $\epsilon$.

My question: are there any algorithms that are "in between" these cases? That is: is there an approximation algorithm with runtime complexity $f(1/\epsilon)$, where $f(x)$ is asymptotically larger than any polynomial of $\log(x)$, but smaller than $x^r$ for any $r\>0$?

EDIT: an example of such a function (mentioned in the comments by Discrete Lizard) is $f(x) := 2^{\sqrt{\log{x}}}$. Is there an approximation algorithm with runtime complexity $2^{\sqrt{\log{(1/ \epsilon)}}}$?

# Answer
$\sqrt(n)$. The smallest function polynomial in n is $c \cdot n$ for some $c \> 0$.
> -1 votes

---
Tags: time-complexity, approximation
---


# Question
Title: P=NP? A reduction of CNF boolean satisfiability to the circulation problem in an undirected graph
The picture below shows how to reduce the Boolean Satisfiability problem in CNF to the circulation problem in undirected graph (see here). As you can see, `a[i]` are the variables and `C[j]` are the clauses of a formula in the conjunctive normal form. If there is an edge between a variable (or negated variable) and a clause, it means that the variable participates in that clause with the respective sign.

The flows between variables and their negations are unconstrained. The direction of the resulting flow indicates whether the variable is `true` or `false`.

The flows between variables and clauses are unconstrained, as long as edges exist.

There is an additional vertex at the bottom connected to all the clauses, with the edges having the minimum flow of `1` and unconstrained max flow through that edge.

If a circulation doesn't exist, it means that the formula is unsatisfiable.

Do you see any flaws in this solution?

# Answer
Consider the CNF formula $a \wedge \neg a$. This has two clauses, $a$, and $\neg a$. If I understand your scheme correctly this maps to the following flow problem:

This clearly has a solution (1 flow going in a circle) while the formula itself is clearly unsatisfiable. So your algorithm gives *false positives*.

Now consider the CNF formula $a \wedge b$. This has two clauses, $a$ and $b$. If I understand your scheme correctly this maps to the following flow problem:

This has no solution (there doesn't exist a cycle in the graph), yet the formula is clearly satisfiable. So your algorithm also gives *false negatives*.
> 5 votes

---
Tags: graphs, logic, satisfiability, network-flow
---


# Question
Title: The formal proof that one Turing Machine recognizes one specific language
When given one *grammar*, we can formally prove that it can recognize one language using QA\_1

Since Kleene's Theorem gives the equivalence between the regular grammar and the NFA, we can also use QA\_1 to prove that one NFA can recognize one language by *transfroming the NFA to the grammar* firstly.

Then how to prove that one Turing Machine recognizes one specific language? This QA\_2 answer uses contradiction to prove. But it seems *informal* for me.

---

Take $\\{0^n 1^n:n\ge 1\\}$ for example. I followed this lecture.

Since there is no non-terminal/terminal symbols for the Turing Machine, it seems inconvenient to construct $M\_i$ when following QA\_1.

So I followed QA\_3 answer. It is trivial to prove the Turing Machine in p4 of the above lecture can accept $\\{0^n 1^n:n\ge 1\\}$, but how to prove that it *can't accept others*?

Both the reference QA\_3 answer and QA\_4 answer gives one strategy to construct states, but they didn't give one formal proof.

Q:

How to prove the Turing Machine in the above reference lecture recognizes $\\{0^n 1^n:n\ge 1\\}$? Is it impossible to give one formal proof since the halting problem is an unsolvable decision problem?

# Answer
> 1 votes
The halting problem doesn't really tell you anything about whether you can prove that a TM recognises a given language.

We can prove that the TM recognises $\\{0^n1^m : n \geq 1\\}$ using the definition of $L(M)$ and $\mapsto\_M$. One thing to note is that the machine is *deterministic*, so for each state and character there's at most one transition. Therefore for each input $w$ there's only one sequence of IDs (one *computation*) we need to consider to decide if $w \in L(M)$.

These proofs can get very long since there are a lot of cases to consider, so I'll just give a rough sketch.

---

For simplicity we'll write $\mapsto$ instead of $\mapsto\_M$, note the following:

> Lemma 1: $X^kq\_00^nY^k1^m \mapsto^\* X^{k + 1}q\_00^{n - 1}Y^{k + 1}1^{m - 1}$ for $k, n, m \in \mathbb{N}; n,m \geq 1$ using only states $q\_0, q\_1, q\_2 \notin F$.

This can be proven by applying the definitions of $\mapsto$ and $M$. A corollary of Lemma 1 is that for $n \geq m$

$$X^kq\_00^nY^k1^m \mapsto^\* X^{k + m}q\_00^{n - m}Y^{k + m}$$

and for $m \geq n$

$$X^kq\_00^nY^k1^m \mapsto^\* X^{k + n}q\_0Y^{k + n}1^{m - n}$$

using only transitions through $q\_0, q\_1$ and $q\_2$. From this it follows that for all $n \in \mathbb{N}; n \geq 1$

$$\underbrace{q\_00^n1^n}\_{=\ X^0q\_00^nY^01^n} \mapsto^\* X^nq\_0Y^n \mapsto X^nYq\_3Y^{n - 1} \mapsto^\* X^nY^nq\_3B \mapsto X^nY^nBq\_4B$$

with $q\_4 \in F$, so by definition $0^n1^n \in L(M)$.

Now assume that $w \in \Sigma^\*; w \notin \\{0^n1^n : n \geq 1\\}$, then one of the following cases must be true:

* $w = \varepsilon$ or $w = 1x$ for $x \in \Sigma^\*$, then $M$ on $w$ directly halts in $q\_0 \notin F \Rightarrow w \notin L(M)$.
* $w = 0^n$ for $n \in \mathbb{N}; n \geq 1$, then $$q\_0w \mapsto Xq\_10^{n - 1} \mapsto^\* X0^{n - 1}q\_1B$$ so the machine halts in $q\_1$ without ever entering a final state. Thus $w \notin L(M)$.
* $w = 0^n1^m$ for $n, m \geq 1; n \neq m$, if $n \> m$ then by the corollary of Lemma 1 $$q\_0w \mapsto^\* X^mq\_00^{n - m}Y^m \mapsto^\* X^{m + 1}0^{n - m - 1}Y^mq\_1B$$ so $M$ halts in $q\_1$ without having entered a final state. If $m \> n$ then again by Lemma 1 $$q\_0w \mapsto^\* X^nq\_0Y^n1^{m - n} \mapsto^\* X^nY^nq\_31^{m - n}$$ so $M$ halts in $q\_3$ without having entered a final state. Thus $w \notin L(M)$.
* $w = 0^n1^m0x$ for $n, m \geq 1$ and $x \in \Sigma^\*$, $w \notin L(M)$ can be proven similar to the cases above by considering $n = m$, $n \> m$ and $m \> n$.

So $w \in \\{0^n1^n : n \geq 1\\} \iff w \in L(M)$, thus $L(M) = \\{0^n1^n : n \geq 1\\}$.

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


# Question
Title: Should I be a good computer scientist to become a great software developer?
As I am headed into a Computer Science major wishing to eventually become a software developer, I wonder this: should I immerse myself in computer science theory and knowledge (data structures, algorithms, how computers work).

I think today many developers can just get by knowing their own tools and technologies depending on their jobs, perhaps without having to worry about theory or anything else.

But I don't want to be a mediocre programmer. I want to know, to understand what I am writing and what it is doing. Am I right in thinking I should take Comp Sci very seriously?

# Answer
> 1 votes
## Short answer

learning CS (computer science) won't make you a better programmer. ***But***, it will give you important theoretical tools, and more importantly - it will teach you *how to think*. There are other options, mostly from the engineering world, that can directly teach you coding instead - if this is what you want.

---

## Long answer

If your ultimate goal is practical code-writing software engineer, then probably learning software engineering from an engineering department - is the best go-to.

Computer science is purely theoretical. Yes, there are a lot of useful **practical** things you can learn in computer science, but I doubt that you *won't* learn them in an engineering major.

That being said, I'm majoring Computer science (and *only* computer science), so I don't know how accurate the above information is, as it is based on the basic knowledge that I have on the engineering faculty in my university, when I am in the exact sciences faculty.

In my opinion, there is a big benefit of to majoring computer science. I think it teaches well *how to think* and *how to solve problems* in ways that might seem very unintuitive at the start (also, it will actually teach you what we can't do. Its also important to know if the problem we want to solve actually has a solution, before we try to find it...). This generally allows you to construct better algorithms to solve problems, and also algorithms for seemingly really hard questions. For example, say you have a geometrical space and a polygon in it. How do you think we can know if a certain input point is in that polygon? This question has many practical usages, and is answered in a computational geometry course - that you can learn in a CS degree. That being said, there are a bunch of other problems you will probably never need to use, such as algorithms in NP that use an all-powerful prover.

Personally, I like to describe computer science as a special branch of mathematics that deals with "computational" problems. In this sense, CS is like Physics or Mathematics or even Chemistry. While coding, I would describe as some sort of combination, or weird mix between CS, and other less "exact" or less "science-ish" subjects.

If you strive for something that is more "high-level" than just writing programs, or maybe you just like theory in general, then CS is a very good choice for you. It will give you a wide range of tools that you can use pretty much everywhere.

Once again, this is only **my opinion**. It could be much different than other's opinions, so please ask more people. Maybe people you know that learned CS, maybe people you know from the industry. Ask a wide range of people, and try to understand for yourself what CS means and whether it suits you.

# Answer
> 1 votes
It seems like the really high end developers have a strong computer science background. They patent new algorithms and things like that. They make 7 figure salaries working for Silicon Valley companies.

I work with more normal developers and they are great but I think it would help them to know a little more computer science. It helps to understand b trees and hashing and in general how operating systems, compilers, graphics, etc. works.

I find that having a computer science background helps me in my database administrator job because it helps me solve difficult problems with either performance problems or weird behavior and bugs.

So, short answer is yes. Get all the comp. sci. you can afford and have aptitude for in my opinion.

Bobby

# Answer
> 0 votes
Should you be a good physicist to become a great aeronautical engineer? Should you be a good chemist to become a great chemical engineer?

The answer to all of these questions is "no", if by "good" you mean research-level. But ultimately, engineers build things out of the results of science, and you need to understand the science to a reasonable level to do the job well.

# Answer
> 0 votes
Actually, like some have said, CS teaches theories mainly and as a programmer with computer science background, it’ll help you think and write better structured algorithms.

---
Tags: programming-languages, theory
---


# Question
Title: Dynamic Programming as DAGs - Solution Always Shortest Path?
I've been trying to get a deeper understanding of how dynamic programming works and came across how it can be represented as directed acyclic graphs (DAGs). It's easy to see why, nodes represent the subproblems and directed edges represent which problem the subproblems help solve. Similar to a recursion tree but with repeated nodes removed and edges having a direction. However, many of the explanations for DAGs representing dynamic programming problems state that finding the shortest path of a DAG representing the problem also solves the dynamic programming version. Which to me does not make much sense.

I can see why this would be for a problem like Edit Distance. The edges simply represent the cost which we want to minimize hence the shortest path. But how would this work for the Longest Increasing Subsequence? The latter would require us to find the longest path to find the longest subsequence. My understanding is that we simply use the optimal substructure of the problem to follow edges from the nodes representing the base cases until reaching the desired solution. Which may or may not result in the shortest path on a DAG.

Here is an example (MIT lecture by Erik Demaine at 3:50) of the claim that the solution to dynamic programming problems is also the shortest path on a DAG. However, he does not explain why in that lecture or the previous one. And the other examples I've seen also make such claims without providing any proof. So is the solution for a dynamic programming problem always represented by the shortest path on a DAG or can it be represented by other paths as well?

# Answer
Dynamic programming can often be expressed as a shortest path problem on a DAG, but not always. It depends on the recurrence relation. If the recurrence relation has the form

$$A\[j\] = \min \\{A\[i\] + f(i,j) | i \< j\\}$$

then it can be expressed as a shortest-path problem on a DAG (with each edge $(i,j)$ having length $f(i,j)$). If the recurrence relation has other forms, then it cannot.

To see how a dynamic programming algorithm for longest increasing subsequence can be viewed as a shortest path in a dag, see Chapter 6.2 of Algorithms by Dasgupta, Papadimitriou, and Vazirani, which explains this in detail. (They explain how it is a longest-path problem, but by negating all edge weights, we obtain a shortest-path problem.)

Demaine does not say that dynamic programming can always be expressed as shortest path on a DAG. He writes on the board "DP $\approx$ shortest paths in some DAG": note that the $\approx$ is warning you that they are not *exactly* equivalent, but it's still a helpful intuition. Verbally, Demaine says "dynamic programming *in some sense* always is computng shortest paths on a DAG" (emphasis added). Note the "in some sense", which is letting you know that this statement is not 100% true but it's a helpful way to think about things.
> 2 votes

---
Tags: algorithms, dynamic-programming, shortest-path, dag
---


# Question
Title: Is "Length of Longest Increasing Subsequence" in L?
I can't find space complexity of this problem with search engines.

I think I have NL algorithm for it (just a basic "one by one non-deterministically accept values if possible"), but I wonder what other research was done on it.

Any references and/or ideas?

# Answer
> 0 votes
closest I could find so far:
https://arxiv.org/abs/2002.08498 provides an SC algoritgm (polylog space, poly time) for approximation of LIS

savitch seems to give smallest space so far

---
Tags: complexity-theory, reference-request, space-complexity, subsequences, longest-increasing-subsequence
---


# Question
Title: Wrapping one's head around priority arguments
One of my undergraduate math professors used to say "we'll always be drawing a picture, even when it is impossible", and I came to strongly sympathize with his witty point. Some recursion theory proof techniques are rather easy to visualize: diagonalization argument is easily pictured as filling out a table, and subsequently flipping ones and zeros on the diagonal. Priority arguments feel very different and seem hard to visualize. Realizing this may be more of a psychology than a math question, is there some suitable way to "picture" priority arguments? Is there (or need there be?) some sort of a visual way of dealing with complicated (priority) proofs for those proofs to be properly understood?

For example: The proof of Friedberg-Muchnik theorem, or, as a simpler example, Post's construction of a simple set.

# Answer
> 1 votes
Here is a picture for you: Your requirements are ordered as $0,1,2,\ldots$; each requirement equipped with a lamp that can be grey, green or red. Initially, all requirements are grey, as they are not active yet. If a requirement becomes active, the light turns red. Your construction provides a way to handle each individual requirement, doing so turns its light green. However, handling a requirement can mess with other requirements of higher numbers, turning them grey or red again, even if they were already green.

The overarching structure of a priority argument states that for any set of requirements that will eventually become active, the process ensures that in the limit, no lights are red.

---
Tags: proof-techniques
---


# Question
Title: Construct a regular expression for strings over the alphabet {a, b, c} that don’t contain the contiguous substring "baa"
I want to construct a **regular expression for strings over the alphabet {a, b, c} that don’t contain the contiguous substring "baa"**. I tried to follow the same procedure as in all the words that don't have both substring bba and abb, where the goal was to find a regular expression that matches **all words that do not contain both "bba" and "abb" as substrings**. However, I got stuck at some point and could not get the correct answer. Here are the steps I followed:

Here is how I tried to solve it

1. I constructed an NFA that accepts all words that contain contiguous substring "baa"
2. I constructed the **complement** of NFA by turning middle states into final states and final states into middle ones. Here it is.
3. I simplified the NFA by adding a new final state and eliminates some states.
4. I tried to write a regular expression for the simplified NFA, but I realized that it still accepts words that contain contiguous "baa" as a substring

Can someone tell me where I went wrong and how to fix it? Is there a better way to approach this problem? Thanks in advance.

# Answer
> -1 votes
I find it easier to build a DFA directly in this case.

---
Tags: finite-automata, regular-expressions
---


# Question
Title: Is the Turing machine the only framework to analyse limits of computation?
In Theory of Computation lessons, the limits of computation are usually analyzed within the framework of Turing machines, so if something isn't solvable with Turing Machine, then we consider this problem as undecidable.

I know computational models like Lambda Calculus are equivalent due to Turing-completeness, but why do we only consider the Turing machine as a model of general-purpose computation?

For example, in Physics, the Newtonian Framework has its own theory about light and about interaction time speed, but that framework fundamentally changed in 20th century which gave us new capabilities(or restrictions) theoretically. Is such a fundamental change viable in computer science, or we do consider Turing and early 20th century foundations similarly as quantum physics is to realm of physics.

Why do we work within the framework and don't try to change fundamentals such that things that may be undecidable become decidable within another framework?

# Answer
Turing machines are far from being the only model of computation considered by computer scientists. Among well-studied models of computation are:

However, we can prove that all these models of computation are equivalent, i.e., the functions they can compute are exactly the same (they're called Turing-computable functions, or just computable functions).

(Side note: Pure λ-calculus is Turing-complete, i.e., equivalent to Turing machines and all the others, but many typed λ-calculi are not. Also note that I'm speaking about equivalence in expressive power here, not in complexity. Some of these models allow to naturally define a notion of the time and memory used by an algorithm, and some do not; and among those which do, there can be large differences.)

Consequently, it is not useful to change your model of computation if you just want to study computability, because computability is the same in all these models.

There are also various commonly studied models that are more *restrictive* (e.g., finite automata, pushdown automata, various subclasses of grammars, primitive recursive functions, ...).

We *do* also occasionally study models which allow computing functions that aren't Turing-computable. For example, oracle machines with uncomputable oracles, when studying Turing degrees (degrees of uncomputability). Another example from complexity theory is the study of the P/poly class.

However, there is a simple but deep reason that we reserve the word "computable" for Turing computability: it is that *we do not know any physical device that could compute a function which is not Turing-computable*. This is called the Church-Turing thesis. It states that Turing-computable functions are exactly the functions which can actually be computed in real life, by a human or computer or any physical system. Because we have so many models of computation, which match our intuition of how computation works, and nobody so far (in the 90 years since λ-calculus and Turing machines were invented) came up with evidence of being able to compute something not Turing-computable, it is widely believed that Turing computability is "the right notion" for the world we live in. This doesn't mean that other notions aren't interesting, but Turing computability is particularly interesting for this reason.

Also, we can't exclude finding, someday, some physical effect in quantum mechanics/black holes/whatever that would disprove the Church-Turing thesis. But this doesn't mean the Church-Turing thesis is not useful, if only because it's what we have to live with on today's computers. (By the way, there is consensus among those studying quantum computing that it would not change the notion of computability, in the current state of knowledge.)
> 8 votes

---
Tags: turing-machines, undecidability, turing-completeness, decidability, philosophy
---


# Question
Title: What's the relationship between "semantic type soundness" and "functional correctness"?
In the Milner Award lecture "The Type Soundness Theorem That You Really Want to Prove (and now you can)" and related Sigplan blog post (with collaborators), Derek Dreyer argues that semantic soundness is an important thing worth proving.

In the questions section, Adam Chlipala asked how to trade off complexity between proving soundness of semantic types and functional correctness, and Dreyer unfortunately said "let's take this offline," so I don't know what the answer is.

Is the answer "semantic type soundness is something to prove about a programming language, but functional correctness something one proves of a program"?

I'm still a bit confused, though, because then someone asked a follow-up question about how semantic type soundness could fail to hold. Dreyer's answer was that if someone were to add a `covfefe` rule that flipped an arbitrary int to `0`, it could trigger someone's assertion that under certain conditions a given int is never `0`. So this makes it sound like soundness proofs for semantic types *do* involve the details of particular programs.

In addition to an answer to Adam Chlipala's question, it would be helpful to have some simple reference for what "semantic type soundness" means - the blog post doesn't really define it, and the closest paper I could find was the RustBelt paper which only discusses "semantic type soundness" in the context of a Rust MIR-like language and Iris, but I couldn't find a more general definition.

# Answer
> 2 votes
I'm not an expert, but can give at least a partial answer since I've been reading about this lately. The more recent preprint A Logical Approach to Type Soundness gives a good overview of what this is all about, outside the specific context of Rust.

The key distinction is between two relations: syntactic type checking ($\Gamma \vdash e : \tau$), which is the syntax-directed type checking we're usually familiar with, and semantic type checking ($\Gamma \vDash e : \tau$) . Roughly speaking, an expression $e$ *semantically* type checks as type $\tau$ if at run-time it eventually evaluates to a value with type $\tau$. Of course in general that reduces to the halting problem and is just as hard as any other kind of functional correctness proof.

I could be misinterpreting, but I think what Adam is asking is "The proof system you've shown here isn't powerful enough to prove all functional correctness properties, so how do you design a proof system that's 'good enough' to prove most of the stuff you need for semantic type checking, but not overly powerful/general?". I suspect the answer is along the lines of "it's a tradeoff, and there are many valid points you could select on the spectrum from very simple to very complex proof system", and so getting to the details of that question requires taking it offline.

Re: proving about a program or a language: Yes, semantic type *soundess* is something you would prove about a language as a whole. Semantic type soundness means that whenever a program semantically type checks, then it is always "safe" to run that program (for some definition of safe). However, whether an individual program semantically *type checks* is something you prove about a single program, and can sometimes require proving functional correctness of that program.

The first few sections of the "Logical Approach" paper above give a nice description of this, so I recommend checking it out if you'd like more details.

---
Tags: type-theory
---


# Question
Title: If an edge e doesn't belong to any mst, then what can we say about e?
I'm trying to prove a statement "given a graph G=(V,T) and that no cycle C exists that contains only edge "e" and other edges that their weight is smaller than that of "e", prove that "e" must be in some mst". I tried to proof by contradiction, but I'm not sure what I can say about "e" when it never belongs to any mst.

# Answer
Suppose that you run Kruskal's algorithm, which computes an MST by repeatedly adding the cheapest edge that does not create a cycle.

In any run of Kruskal, when we consider your edge $e = uv$, it turns out that $u$ and $v$ are already in the same connected component.

That means that there is a path from $u$ to $v$ where every edge is strictly cheaper than $e$.

Hence $e$ must be the heaviest edge in a cycle.
> 6 votes

---
Tags: minimum-spanning-tree
---


# Question
Title: Are they talking about virtual memory in this article?
I am reading this Wikipedia article:

https://en.wikipedia.org/wiki/Memory\_segmentation

And I am in this paragraph:

> **Segmentation with paging**
>
> Instead of a memory location, the segment information includes the address of a page table for the segment. When a program references a memory location the offset is translated to a memory address using the page table. A segment can be extended by allocating another memory page and adding it to the segment's page table.
>
> An implementation of virtual memory on a system using segmentation with paging usually only moves individual pages back and forth between main memory and secondary storage, similar to a paged non-segmented system. Pages of the segment can be located anywhere in main memory and need not be contiguous. This usually results in a reduced amount of input/output between primary and secondary storage and reduced memory fragmentation.

In the second paragraph they are clearly talking about virtual memory. But are they also talking about virtual memory in the first paragraph?

# Answer
Yes, the first paragraph is also talking about virtual memory concepts. It describes how to translate virtual addresses (used by programs) into physical addresses in the main memory. The page table holds the mappings between virtual pages and physical page frames. When a program references a virtual address, the page table is used to determine which physical page frame that virtual address is mapped to, and the offset within that page frame.
> 1 votes

---
Tags: memory-management, virtual-memory, paging
---


# Question
Title: Splitting a binomial heap into 3n/8 and 5n/8 binomial heap whereas 8 divides n with O(log(n)) time
I ran into this exercise that says:

> With a given binomial heap with n elements and n is divisible by 8, split the heap into 2 binomial heaps, one with 3n/8 elements and the other with 5n/8 elements.

I tried using another heap as a helping heap that saves the heaps I need to merge, but I didn't exactly know how to split. Then I tried to use a stack and a queue, and I didn't get anywhere either. Can someone please help with this?

# Answer
If $n$ is even, you can split the heap into two heaps of size $\dfrac{n}2$:

For each binomial tree in the heap, remove its first child; reconstruct a heap with all the children you removed.

Since a binomial heap has at most $\mathcal{O}(\log n)$ binomial trees, this operation is done in $\mathcal{O}(\log n)$.

Using the same idea several times, you can split the heap into:

* two heaps of size $\dfrac{n}8$
* one heap of size $\dfrac{n}4$
* one heap of size $\dfrac{n}2$

Now just merge (in $\mathcal{O}(\log n)$) two pairs of those and you get the result.
> 3 votes

---
Tags: algorithms, data-structures, heaps
---


# Question
Title: Understanding proof for Busy Beaver being uncomputable
I found this proof on http://jeremykun.com/2012/02/08/busy-beavers-and-the-quest-for-big-numbers/ and have highlighted the part I don't understand in bold.

(BB(n) is defined as the number of steps made by n-state Busy Beavers.)

> *Theorem:* BB(n) is uncomputable. That is, there is no Turing machine that can take as input n and computes BB(n).
>
> ---
>
> *Proof:* Suppose to the contrary that such a machine existed, and call it T. We will use T to construct a machine which solves the halting problem as follows:
>
> On input \< T, w \>, a description of a Turing machine and its associated input, we can determine in finite time the number of states that T has (it is encoded in the description of T).
>
> Now simply compute BB(n), where n is the number of states in T, and simulate T on input w, counting its steps as it proceeds. Eventually the simulation of T either halts, or makes more steps than BB(n).
>
> In the former case, we may stop the computation and declare that T halts. **In the latter, we know that BB(n) is the maximal number of steps that can occur for any Turing machine with n states that eventually halts. Therefore, if T had not halted on the input w, it must never halt.**
>
> We may stop our computation there, proclaim an infinite loop, and thereby solve the halting problem.
>
> This is a contradiction, so the sequence BB(n) cannot be computable.

If we assume that T can calculate BB(n) for any n, don't we also have to assume that it does halt, and therefore that it will not exceed the steps of BB(n)? (That would also mean that using T to solve the halting problem does not work)

# Answer
> 4 votes
**EDIT:** The proof seems to contain two errors:

1. The proof uses the same T to denote the Turing Machine that can solve BB(n) as well as for the input-TM for the halting-problem solver. So we have to rename the input-TM.
2. From http://mathworld.wolfram.com/BusyBeaver.html:

> \[...\] some authors define a busy beaver as a Turing machine that performs a maximum number S(n) of steps when started on an initially blank tape before halting

This proof obviously uses above definition which states that Busy Beavers do more steps than any Turing Machine with *zero-initialized tape*. That means, we can only test the halting-problem on Turing Machines with no input parameters. So we have to remove $\omega$ as input parameter.

---

The correct formulation would then be:

*Theorem:* BB(n) is uncomputable. That is, there is no Turing machine that can take as input n and computes BB(n).

*Proof:* Suppose to the contrary that such a machine existed, and call it T. We will use T to construct a machine which solves the halting problem as follows:

On input \< TM \>, a description of a Turing machine and its associated input, we can determine in finite time the number of states that TM has (it is encoded in the description of TM).

Now simply use T to compute BB(n), where n is the number of states in TM, and simulate TM, counting its steps as it proceeds. Eventually the simulation of TM either halts, or makes more steps than BB(n).

In the former case, we may stop the computation and declare that TM halts. In the latter, we know that BB(n) is the maximal number of steps that can occur for any Turing machine with n states that eventually halts. Therefore, if TM had not halted on the input w, it must never halt.

We may stop our computation there, proclaim an infinite loop, and thereby solve the halting problem.

This is a contradiction, so the sequence BB(n) cannot be computable.

Or as pseudocde:

```
T(n):
    return BB(n)

halting_problem_solver(TM):
    n := number of states in TM
    BB_n := T(n)
    steps := 0
    in each step of TM() simulation:
        steps = steps + 1
        if steps > BB_n:
            return T will not halt!
    return T halts

```

# Answer
> 4 votes
Just for the completeness, I will present my proof that shows uncomputability of BB function. The structure of a correct proof would look something like the following.

1. Construct a universal Turing machine U that simulates any other Turing machines but writes ‘1’ on the output tape for every step of the simulation.
2. For any Turing machine M, there is an encoding 〈M〉for U. We create a new Turing machine by adding new states in U which first writes〈M〉on its input tape and runs it on U. Call this new Turing machine UM.
3. Let n be the number of states in UM, and m be the number of states in M. We can see that BB(n) upper-bounds the number of 1’s outputted by UM and also upper-bounds the maximal number of steps run by the halting Turing machine with m states. Hence, S(m) \<= BB(n), where S(m) is the maximal number of steps run by a halting Turing machine with m states.
4. Given a Turing machine of size m, we can always determine corresponding value for n.
5. If there is any function that always upper bounds S, it is uncomputable as it will contradict with the result from the halting problem. (Run a Turing machine that many steps to determine whether it halts or not)

# Answer
> 3 votes
The reference blog has changed and it seems to have been corrected which includes the OP's correction. Although the waybackmachine archived this blog old uncorrected version (2013 version) but it can't render the formula images.

The corrected reference blog (it is similar to this lecture p9):

> Theorem: $ BB(n)$ is uncomputable. That is, there is no Turing machine that can takes as input $ n$ and computes $ BB(n)$.
>
> Proof. Suppose to the contrary that such a machine existed, and call it $ A$. We will use $ A$ to construct another machine, say $ M$ which solves the halting problem as follows. We will use the version of the halting problem where the input is assumed to be the empty string (i.e., there is no input); this problem is also undecidable.
>
> When $ M$ is given the input $ \left \langle T \right \rangle$, a description of a Turing machine, $ M$ determines in finite time the number of states that $ T$ has (it is encoded in the description of $ T$), and then uses $ A$ to compute $ BB(n)$, where $ n$ is the number of states in $ T$. The machine $ M$ then simulates $ T$ on the empty string input, counting its steps as it proceeds. Eventually the simulation of $ T$ either halts, or makes more steps than $ BB(n)$. In the former case, $ M$ may stop the computation and declare that $ T$ halts. In the latter, we know that $ BB(n)$ is the maximal number of steps that can occur for any Turing machine with $ n$ states that eventually halts. Therefore, if $ T$ had not halted, it must never halt. We may stop our computation there, proclaim an infinite loop, and thereby solve the halting problem.
>
> This is a contradiction, so the sequence $ BB(n)$ cannot be computable.

Here I give one summary for the corrected one with some more *description of the implementation* of $M$:

1. > We will use the version of the halting problem where *the input* is assumed to be *the empty string* (i.e., there is no input); this problem is *also undecidable.*

See this QA whose main idea is reduction from one specific problem to one specific problem where one of the 2 problems is already investigated.
2. > $ M$ determines in finite time the number of states that $ T$ has (it is encoded in the description of $ T$)

See this QA. The ending form of the tape depends on the implementation of $A$. Maybe we writes $n$ 1s on the tape and $A$ reads these specific number of 1s to compute $BB(n)$. (Anyone knowing one specific TM to compute the cardinality of a set can help improve this answer. Thanks in advance.)
3. > and then uses $ A$ to compute $ BB(n)$

Here $A$ is implemented implicitly inside $M$ like how we implement composition of multiple Turing Machines.
4. > The machine $ M$ then simulates $ T$ on the empty string input Since we may probably prints $BB(n)$ 1s on the tape, to ensure the *empty* string input and also *remembering $BB(n)$*, we can use the Multitape Turing machine.

More specifically, assume we have $$ \begin{align\*} 0: &\overbrace{11\cdots11}^{BB(n)\text{ times}}q\_{k}\\ 1: &00\cdots00\cdots \end{align\*} $$ Then we may proceed until $$ \begin{align\*} 0: &&q\_{k'}&00\cdots00\cdots\\ 1: &&\cdots00&\overbrace{11\cdots11}^{BB(n)\text{ times}}00\cdots \end{align\*} $$ Then we use tape-0 to simulate $T$. Meanwhile, we change 1 to 0 of the tape-1 for

> counting its steps as it proceeds

and compare the step number with $BB(n)$ where we may end up as the following when simulating $T$ (The detailed values of $10\cdots 010$ depends on the behavior of $T$): $$ \begin{align\*} 0: &&10\cdots 010&q\_{k''}\cdots\\ 1: &&\overbrace{00\cdots00}^{BB(n)\text{ times}}1&0\cdots \end{align\*} $$ Here we use $q\_{k''}$ to mean that $T$ won't halt by (more specifically, $T$ is one *2-symbol* n-state Turing machine)

> $ BB(n)$ is the *maximal* number of steps that can occur for any Turing machine with $ n$ states that *eventually halts*.

(Here I didn't give the behavior of the tape-1 before "The machine $ M$ then simulates $ T$". But we can probably use many states to ensure the tape-1 keeps all 0s before we doing the above process.)
5. > proclaim an infinite loop

i.e. non-halt.

# Answer
> 2 votes
This can't be right. E.g. I can build a 2-state Turing machine, which takes an input $\omega$ and just moves right and halts after overwriting the first blank with a $1$. If $\omega$ is long enough (longer than $\mathop{BB}(2)$ in our case), my TM will take more than $\mathop{BB}(2)$ steps and halt. Besides, $\mathop{B}$ is defined as writing on an initially blank tape, and is the number of $1$ written, not the number of steps.

---
Tags: computability, turing-machines, halting-problem, busy-beaver
---


title: Fizz Buzz and pseudo-polynomial time

text:
# Question
Title: Fizz Buzz and pseudo-polynomial time
I am currently taking a course on algorithms, and when reading about the 0/1 Knapsack Problem on Wikipedia I came across a technique which uses dynamic programming and supposedly runs in $O(nW)$ time, which makes sense to me after studying the algorithm. But to my understanding, the 0/1 Knapsack Problem is NP-complete, which means it cannot be solved in polynomial time (that would solve the infamous $N=NP$ problem). The explanation that I have seen for why $O(nW)$ does not run in polynomial time, is that when we're discussing time complexities that depend on numeric values, we're actually not concerned with the value of $W$ but rather the size of its representation. If $W$ is represented in binary, then adding bits would increase the *size* of $W$ linearly, but the value of $W$ would increase exponentially.

And assuming that I have understood everything correctly thus far, here is my question:

The Fizz Buzz problem can be solved in $O(n)$ time, and is described as a problem that can be solved in *linear* time according to (for instance) these articles which show up with a Google search: Medium, Jared Nielsen, San Tuon.

But $n$ in Fizz Buzz is simply a numeric value, just like $W$ in the Knapsack Problem. So how come Fizz Buzz is regarded as a problem which can be solved in polynomial time, but the Knapsack Problem is not?

# Answer
The running time of the algorithm is linear in terms of $n$, but yes, you're right the algorithm does have a pseudo-polynomial time complexity since the standard is for the running time to be in terms of the number of bits of the input.

The articles don't make this distinction since this they're written for beginners, for whom it'll be hard to grasp the concept of pseudo-polynomial time and the reasoning behind it if they're just getting familiarised with the notion of time complexity.
> 2 votes

# Answer
The runtime of $0/1$ knapsack problem using dynamic programming is $O(nW)$. Now assume that $W = 2^n$, then the runtime of the above algorithm is $O(n2^n)$, which is not a polynomial runtime in $n$. The runtime of the algorithm depends upon $n$ and $W$.
> 0 votes

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


# Question
Title: How are non-binary codes implemented in practice, i.e. codes over $\mathbb{F}_q^n$ for $q\neq 2$?
I am only familiar with binary implementations of information, though I am aware other implementations (ternary etc.) exist. I was wondering, if a code over $\mathbb{F}\_q^n$ is used in practice, where $q\neq 2$, how is this done really? Do we use chunks of bits to encode elements of $\mathbb{F}\_q$, for example $\\{00, 01, 10, 11\\} \in \mathbb{F}\_4$? Or is a different protocol used? I cannot image it's the former since this would be hard for $q\neq 2^s$ for integer $s$, and it requires block encoding which is less robust against errors.

# Answer
> 2 votes
For $\mathbb{F}\_2^n$ people store the bits consisting of the coefficients of the polynomial of some generator $x$. For $\mathbb{F}\_q$ the field is isomorphic to simple integers mod $q$, so they simply store the integer in binary. I don't know of anything that actually uses $\mathbb{F}\_q^n$ with $q \> 2, n \geq 2$, but again you could just store a vector of coefficients of some polynomial in generator $x$, where each coefficient is an integer $\<q$.

---
Tags: coding-theory, error-correcting-codes
---


# Question
Title: Regular branch and bound vs integer programming branch and bound
In the context of linear integer programming, we have a branch and bound algorithm described here. This involves solving the non-integer constrained linear program and successively introducing additional constraints, thus getting a bunch of integer solutions. Then picking the best among those.

And then there is also a branch and bound described in Wikipedia that is more broadly applicable and involves successively building solutions in the form of a tree where the leaves are the complete solutions. To avoid exploring the entirity of the prohibitively expensive tree, they prune it by bounding the partial solutions and eliminating branches when they are not likely to result in good solutions.

Are these two flavors of branch and bound connected? They seem to share a name, but I can't see how the first one is connected to the second one.

# Answer
The first two sentences of the document you linked says it all:

> The *branch and bound method* is not a solution technique specifically limited to integer programming problems. It is a *solution approach* that can be applied to a number of different types of problems.

In short, branch and bound, as utilized in solving ILP problems, is just a special case of branch and bound generally. The specific way of obtaining bounds by solving LP relaxations of the problem is specific to ILP, though.
> 2 votes

---
Tags: optimization, combinatorics, integer-programming
---


# Question
Title: A problem maybe related to pattern-matching
Let $\Sigma\_{1}=\\{a,b\\}$ and $\Sigma\_{2}=\\{t,f\\}$.

Define the function $f\_{w}:\Sigma\_{1}^{\*}\rightarrow\Sigma\_{2}^{\*}$ for every $w\in\Sigma\_{1}^{\*}$; $f\_{w}(w')\in\Sigma\_{2}^{\*}$ is the word obtained from $w'\in\Sigma\_{1}^{\*}$ by replacing the start position of each subword that matches $w$ with $t$ and any other position with $f$.

I meant;

$f\_{w}(w')=x\_{1}...x\_{|w'|}$;

here

$\exists(u,v)\in\Sigma\_{1}^{\*}\times\Sigma\_{1}^{\*}\[w'=uwv\wedge|u|=i-1\]\Rightarrow x\_{i}=t$ $\neg\exists (u,v)\in\Sigma\_{1}^{\*}\times\Sigma\_{1}^{\*}\[w'=uwv\wedge|u|=i-1\]\Rightarrow x\_{i}=f$

for every $i\in\\{1,...,|w|\\}$.

Also, define the function $f\_{w}^{\*}:P(\Sigma\_{1}^{\*})\rightarrow P(\Sigma\_{2}^{\*})$ for every $w\in\Sigma\_{1}^{\*}$; $f\_{w}^{\*}(L):=\\{f\_{w}(w')|w'\in L\\}$.

I want to know whether each of the assumptions below is true or not;

1. For every $w\in\Sigma\_{1}^{\*}$ satisfying $|w|\>0$; $L$ is a regular language $\Rightarrow$ $L'$ is a regular language.
2. For every $w\in\Sigma\_{1}^{\*}$; $L$ is a context-free language $\Rightarrow$ $L'$ is a context-free language.

# Answer
> 0 votes
Yes, both assumptions are true.

Your pattern matching operation can be performed by a finite state automaton with output, a finite state transducer. Keep the last $|w|$ read symbols in memory, and output $t,f$ accordingly. (And at the end affix some $f$'s.)

This closure property of the regular and context-free languages is not well known. It is equivalent to closure under (inverse) homomorphisms and under intersection with regular languages. Part of the theory abstract family of languages.

Transducers can be decomposed into inverse morphism, intersection with regular languages, and morphism. So if you are not familiar with the transducer instead you can apply those three closure properties.

Here we go. Starting with an alphabet $\Sigma$ and a string $w$ of length $n$, we make a large new alphabet $\Sigma^n$ consisting of all $n$-sequences of letters.

The morphism $g: \Sigma^n\to \Sigma$ maps a sequence to its first letter: $g(\[\sigma\_1\sigma\_2\dots\sigma\_n\]) =\sigma\_1$. The inverse morphism $g^{-1}$ nondeterministically assigns a sequence to every letter with matching first symbol.

The regular language $R$ over $\Sigma^n$ consists of all strings where the consecutive sequences overlap. Thus $\[\sigma\_1\sigma\_2\dots\sigma\_n\]\[\sigma\_2\dots\sigma\_n\sigma\_{n+1}\]$ must be consecutive.

The morphism $h:\Sigma^n\to \\{t,f\\}$ assigns $\[\sigma\_1\sigma\_2\dots\sigma\_n\]$ to $t$ if $\sigma\_1\sigma\_2\dots\sigma\_n = w$ and $f$ otherwise.

If you apply $g^{-1}$, intersection with $R$, and finally $h$ to the original language $L$, you will obtain your pattern language $L'$.

---
Tags: context-free, matching, substrings, pattern-recognition, string-matching
---


# Question
Title: O(m) time algorithm to check for a strongly connected graph
Given a directed graph G=(V,E) how can I check to see if it is strongly connected i.e. every vertex is reachable from every other vertex.

what's a good algorithm to check for this that runs in O(m) time? (the number of edges) where we assume that n \< m. (there are always more edges than vertices in the graph)

# Answer
> 2 votes
As mentioned by others, we can assume $n \le m$ otherwise the answer is NO. Perform a visit (say, a DFS) from node 1 along the digraph; and then, a visit from node 1 along the "reverse" digraph in which all the edges are reversed (after precomputing the reverse digraph in linear time). If both visits hit all nodes of the digraph, it is strongly connected. If not, it can't be.

# Answer
> 0 votes
The algorithms on the Wikipedia page linked by @idmean indeed run in $O(n + m)$ time, but this is only because they don't just test if a graph is strongly connected, but also find each strongly connected component. However, if we only want to test if the entire graph is strongly connected, such an algorithm can run in $O(m)$ time. The key observation is that if $m \< n$, we know the graph is not strongly connected: there simply aren't enough edges to do the job! Therefore, we can assume that $n \in O(m)$, and therefore the running time simplifies to $O(m)$ time.

# Answer
> 0 votes
Find the number of SCC of input graph $G$ in $\mathcal{O}(n+m)$, then check whether the number SCC is $1$ or not. If the number of SCC is $1$ then $G$ is strongly connected. Note that, according your observation $n\<m$ we can conclude that $\mathcal{O}(n+m)=\mathcal{O}(m).$

# Answer
> 0 votes
One efficient algorithm to check if a directed graph is strongly connected is Kosaraju's algorithm. It runs in O(m) time complexity, where m is the number of edges in the graph. This algorithm involves two depth-first searches (DFS) and can determine if every vertex is reachable from every other vertex.

---
Tags: graphs, time-complexity, connected-components
---


# Question
Title: compute the intersection of two polytopes and it's corner points
I am looking for a method in python/matlab to calculate the corner points of polytope which is an intersection of a polytope with half spaces.

I have a polytope P1 of the form

* -1\<= x0 \<= 1
* -1\<= x1 \<= 1
* -1\<= x2 \<= 1
* -1\<= x3 \<= 1

And half spaces defined by the equations as in the following format.

* -0.1 * x0 + 1.0 * x1 + 2.0 * x2 + 0.8 * x3 + 6.5 \> 0
* 1.5 * x0 + 0.5 * x1 + -3.5 * x2 + 0.4 * x3 + 6.0 \> 0
* 1.2 * x0 + 1.8 * x1 + 15.0 * x2 + 2.5 * x3 + 1.0 \> 0
* -1.5 * x0 + -0.5 * x1 + 3.0 * x2 + 1.5 * x3 + 6.2 \> 0

I wanted to compute a polytope P2 as the intersection of the polytope P1 with half spaces defined by the equations similar to the equations mentioned above. Then I need to compute the corner points of the intersected polytope P2.

I used python `script.linprog` for the computing the intersection of polytopes by using the vertical stacking method. But don't know how to calculate the corner points.

# Answer
An example Pyton script using the scipy.optimize.linprog function.

from scipy.optimize import linprog

```
import numpy as np

# Define coefficients of the half-space inequalities
A = np.array([
    [-0.1, 1.0, 2.0, 0.8],
    [1.5, 0.5, -3.5, 0.4],
    [1.2, 1.8, 15.0, 2.5],
    [-1.5, -0.5, 3.0, 1.5]
])

# Define right-hand side of the inequalities
b = np.array([6.5, 6.0, 1.0, 6.2])

# Define bounds for the variables (P1)
x_bounds = [(0, 1) for _ in range(4)]

# Use linprog to find the corner points of intersection
result = linprog(c=np.zeros(4), A_ub=A, b_ub=b, bounds=x_bounds, method='highs')

# Extract corner points
corner_points = result.x

print("Corner Points of the Intersection:")
print(corner_points)

```

Hopefully it’s self explanitary with the comments. Just ask if you need anything explained and I’ll edit the answer.
> 0 votes

# Answer
Representing the polyhedron of feasible solutions as the intersection of half spaces, defined by linear inqualities, is known as H-representation.

Representing that polyhedron by a list of its vertices (and its rays) is known as V-representation.

So, your problem amounts to converting from H-representation to V-representation. A search on those terms will turn up many algorithms and software libraries that you can use for this purpose.

Be prepared that it can take exponential time, as there can be exponentially many vertices.
> 0 votes

---
Tags: computational-geometry, linear-programming, python
---


# Question
Title: How synchronous and asynchronous signals are different?
A process can receive two kinds of signals classified based on the source and reason.

* Synchronous are the one that are generated by illegal memory access or division by zero.
* Asynchronous are the one that are generated by another process like SIGKILL and etc.

Quoting from the 9e OSC Book by Prof. Galvin, topic **Signal Handling (Section 4.6.2)**

> A signal may be received either synchronously or asynchronously, depending on the source of and the reason of the event being signaled
>
> ...
>
> Examples of synchronous signal incude illegal memory access or and division by zero $0$. ... delivered to the same process that performed the operation that caused the signal.
>
> When signal is generated by an event external to the running process, that process receives the signal asynchronously. Examples of such signal include terminating a process with specific keystrokes (such as CTRL-C) and timer expire (*`SIGALRM` from sleep*)

In the both cases, the signal must be handled either by custom or default handler. For the synchronous it is crashing the running process, and in asynchronous, it is using the default routine whatsoever is defined in the system.

Here is the list of questions I have in my mind right now:

1. What does exactly Synchronous and Asynchronous means here?
2. In the synchronous, who is waiting for the receiver process to respond?
3. If both of them are need to be handled, then in my opinion, only priority of the execution would be the difference between these two. Does that mean synchronous signals have more priority?
4. Can we call synchronous signals as exceptions (or *interrupts*)? For example we have `ZeroDivisionError` or `FileNotFoundError` and all.

# Answer
> 0 votes
Answering the questions in the same order:

1. If the source of the signal is within current process, then it is synchronous because it is handled immediately and the OS sends interrupt to the process. Asynchronous is when external tool sends signal to process, for example using `kill` tool or Ctrl+C and so on. ref
2. "Waiting for receiver" does not make sense, both the cases the receiver would be target process. The difference lies in the source.
3. There is no priority kind of thing here in the scene. But a good point to note, `SIGKILL` and `SIGSTOP` can't be handled within program, their default handle will be executed and attaching handler to it would return error (*check code and bonus section*).
4. Yes we can call it. But, that is related to particular programming. Signals are more general and OS specific keyword in this context.

The following code is generated from the ChatGPT, and it works fine. I have tested it.

```
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <unistd.h>
#include <string.h>

void signal_handler(int sig, siginfo_t *info, void *context) {
    (void)context; // Unused parameter

    switch (sig) {
        case SIGFPE:
            printf("Caught SIGFPE: Arithmetic error, such as divide by zero.\n");
            break;
        case SIGSEGV:
            printf("Caught SIGSEGV: Invalid memory reference.\n");
            if (info) {
                printf("Sent by process: %d\n", info->si_pid);
            }
            break;
        case SIGINT:
            printf("Caught SIGINT: Interrupt from keyboard (Ctrl+C).\n");
            if (info) {
                printf("Sent by process: %d\n", info->si_pid);
            }
            break;
        default:
            printf("Caught unhandled signal: %d\n", sig);
            break;
    }
}

int main() {
    struct sigaction act;
    memset(&act, 0, sizeof(act));

    // Set the handler to use the sa_sigaction field
    act.sa_sigaction = signal_handler;

    // Set the SA_SIGINFO flag to use the sa_sigaction field, not sa_handler
    act.sa_flags = SA_SIGINFO;

    // Register the signal handler for SIGFPE, SIGSEGV, and SIGINT
    sigaction(SIGFPE, &act, NULL);
    sigaction(SIGSEGV, &act, NULL);
    sigaction(SIGINT, &act, NULL);

    // A demonstration attempt to handle SIGKILL, which will not work
    if (sigaction(SIGKILL, &act, NULL) < 0) {
        perror("Cannot catch SIGKILL");
    }

    printf("PID: %d\n", getpid());
    printf("Try causing a divide by zero, segmentation fault, or press Ctrl+C\n");

    // Infinite loop to keep the program running until a signal is caught
    while (1) {
        sleep(1);
    }

    return 0;
}

```

> **Bonus:** As per the man pages, `SIGKILL` and `SIGSTOP` can't be blocked ref. This is because `SIGKILL` is meant to immediately terminate the process without giving it time to release the resources (in this case memory, cpu and etc will be reclaimed by the OS). `SIGSTOP` instructs the operating system to stop a process for later resumption. These two can be blocked by kernel, but not user-space processes.
>
> In this example you will see CTRL+C will not close the process, only `kill -9 PID` will terminate the process. Now imagine what if you were allowed to block it, you won't be able to terminate the process at all.

---
Tags: operating-systems
---


# Question
Title: If we prove that NP = EXP, does that automatically prove that P != NP?
If P = DTIME(n^c) and EXP = DTIME(2^n), and we prove that NP = EXP, then it means that NP = DTIME(2^n). According to the time hierarchy theorem, the set of languages decided in O(f(n)) is bigger than those decided in o(f(n)). So does that not imply P != NP?

# Answer
> 3 votes
Yes, that is correct.

It is currently considered unlikely that NP = EXP.

# Answer
> 3 votes
Yes. We know that $\mathsf{P}\subseteq\mathsf{NP}\subseteq \mathsf{EXP}$. However, by diagonalization we know that $\mathsf{P} \neq \mathsf{EXP}$, hence one of the inclusions must be strict. So it follows that showing $\mathsf{NP}=\mathsf{EXP}$, implies $\mathsf{P}\neq \mathsf{NP}$.

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Why finding the largest element in a min-heap using a comparison-based algorithm takes Ω(logn) time?
How we can prove that the largest element in a min-heap using a comparison-based algorithm takes Ω(logn) time?

Is this useful that worst running time for comparison based sorting is \>= longest path from root to leaf = height of the tree \>= log(n!) = Ω(logn)?

# Answer
> Is this useful that worst running time for comparison based sorting is \>= longest path from root to leaf = height of the tree \>= log(n!) = Ω(logn)?

It is useful if we interpret $\log n!$ as $n \log n$.

> How we can prove that the largest element in a min-heap using a comparison-based algorithm takes Ω(logn) time?

It is possible if we interpret the operation as extracting instead of returning.

Extracting $n$ elements is equivalent to sorting $n$ elements, if sorting $n$ elements runs in $n \log n$ then sorting an element runs in $\log n$.
> 0 votes

# Answer
Probably you meant to *extract* the element. Also we are using a min-heap, so I would suppose you wanted to extract the smallest element, but the argument works for both.

Suppose you can extract minimal element from a binary min-heap in time $o(\log n)$. I claim that you can sort in time $o(n\log n)$, which contradicts a well known fact that in comparison based model sorting cannot be done faster than $O(n\log n)$.

Take elements $x\_1,\ldots, x\_n$, build a min-heap from them in time $O(n)$, then call `extract_min` $n$ times and append the minima to an auxiliary array. Observe that the last step takes $o(n\log n)$ time and the elements $x\_i$ are sorted in the auxiliary array. Thus, you managed to sort in $o(n\log n)$ time which is impossible.
> 0 votes

---
Tags: data-structures
---


# Question
Title: Determining whether two special variants of knapsack have the same optimal value
Given two unbounded knapsack instances, $K\_1 = (W\_1, weights, values), K\_2 = (W\_2, weights, values)$, where $W\_1 \ne W\_2$, what is the complexity of determining $v(K\_1) = v(K\_2)$ where $v$ returns the optimal sum of values given a knapsack instance?

I know that the decision problem of knapsack -- i.e. asking whether or not a knapsack instance can achieve a value of at least $k$ is NP-hard, but am having trouble reducing that to this particular decision problem. I conjecture that this remains NP-hard though.

# Answer
> 0 votes
I have no proof, but I expect it's probably hard, because given a target value $t$, it is easy to construct a knapsack problem $K\_2$ whose optimal value is $t$. This means that your problem is at least as hard as testing, given $t$ and $K\_1$ whether the optimal value of $K\_1$ is equal to $t$. I don't know whether that problem is NP-hard, but the related problem of testing whether the optimal value of $K\_1$ is $\ge t$ is NP-hard.

---
Tags: complexity-theory, np-hard, decision-problem, knapsack-problems
---


# Question
Title: Advice for better performance neural network
As a beginner in neural networks, I'm currently working on a project for predicting winning fighters in MMA matches. I understand that this is a complex task due to the nature of the sport.

Currently, I'm achieving an accuracy of 64.2% on my test dataset. My goal is to increase this accuracy to 70%.

The method I'm using involves a fully connected neural network with the following layers to achieve this score:

```
self.fc = nn.Sequential(
   nn.Linear(70, 90),
   nn.Linear(90, 110),
   nn.Linear(110, 70),
   nn.Linear(70, 50),
   nn.ReLU(),
   nn.Linear(50, 1),
   nn.Sigmoid()
)

```

I'm only training for 5 epochs because I've noticed that if I train for more, the model starts overfitting.

One of my main challenges is the limited amount of data I have, which totals 7855 samples. I split this into 80% for training and 20% for testing.

It's worth mentioning that there are 70 inputs because each fighter has 35 statistics. Additionally, I'm uncertain whether it's better to have a single output where the network predicts the winning fighter, or two outputs where the network outputs the probabilities of each fighter winning.

I believe I'm facing a significant data scarcity issue.

I was wondering if there are techniques available for generating synthetic data (similar to using color filters or altering regions in image data) since I have such a small dataset.

I'm open to any ideas or advice!

# Answer
> 1 votes
You should consider putting RelU after every Linear layer (except the output layer). Chaining multiple linear layers without an activation like that is equivalent to a single linear layer, but you're restricting the rank of that layer.

---
Tags: machine-learning, neural-networks, data-sets
---


title: No Neighbor Vertex Cover

text:
# Question
Title: No Neighbor Vertex Cover
Let $G=(V,E)$ be an undirected connected graph with a set of vertices $|V|$ and a set of edges $|E|$. A set cover $D$ satisfies $D \subseteq V$ and $uv \in E \implies u \in D \lor v \in D$. A variant of the vertex cover requires that **exactly one vertex**, $u$ or $v$, not both, is in $D$. In this sense, no vertices in $D$ are neighboring. The maximization problem seeks to maximize $|D|$ and the minimization problem seeks to minimize $|D|$. Are both problems solvable in polynomial time?

# Answer
> 2 votes
We can see the following observations on the sets $D$ and $C = V\setminus D$:

Every edge in $E$ contains exactly one node in $D$

$\rightarrow$ Every edge in $E$ contains exactly one node in $C$

$\rightarrow$ Both $D$ and $C$ are vertex covers of $G$

$\rightarrow$ Both $D$ and $C$ are independent sets (the complement of a vertex cover is always an independent set)

$\rightarrow (D,C)$ is a 2-coloring of $V$, and as such, they only exist if $G$ is bipartite.

As Michal says in the other answer: If $G$ is connected, then the 2-coloring is unique and can be found in polynomial time.

Even if $G$ is not connected, maximizing the size of such a vertex cover is equal to taking the union of the biggest color class in each component, and can be found quickly as well.

# Answer
> 1 votes
This answers the problem only partially (in particular, for the minimization) Whether or not the set $D$ exists is equivalent to the fact that $G$ is bipartite. This can be tested in polynomial time.

To see the equivalence, note that $G$ is bipartite if and only if it does not contain an odd cycle. If $G$ is bipartite, each partition is a valid independent vertex cover. On the other hand, if $G$ is not bipartite, then consider the odd cycle $C$ of length $2n+1$ in $G$. Every independent set in $C$ is of size at most $n$, but every vertex cover is of size at least $n+1$, so no such set can exist for $G$.

Suppose that $G$ is conencted, otherwise do it per connected component.

We know that if $G$ is connected then the bipartition is, up to swapping the parts, unique and the minimum independent vertex cover is the smaller of the two parts.

---
Tags: complexity-theory, graphs, optimization, dynamic-programming, np-hard
---


# Question
Title: Is every problem which can be solved by an algorithm using polynomial space in PSPACE?
I recently learned about the definition of PSPACE problems, which are a subset of decision problems that can be solved by using polynomial space. However, one thing I don't understand is when I asked my instructor whether any problem, as long as it uses polynomial space to solve, is in PSPACE, and the instructor said yes! This makes me wonder if problems like the two-sum problem are in PSPACE, since you can solve two-sum using polynomial space?

# Answer
> 1 votes
As you said yourself: The definition of PSPACE is all problems that can be solved using polynomial space. Therefore, if a problem can be solved using polynomial space, then it is in PSPACE.

PSPACE is a very large class of problems, and it contains pretty much every problem you will ever come across.

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


# Question
Title: Are there problems in NP that would solve P vs NP, but are not NP complete
NP-complete problems are the "hardest problems" in NP. This means that all other problems in NP reduce (in polytime) to these problems. A consequence of this is *if* we were to find some polynomial time algorithm to solve one of these problems, we could prove $P = NP$. And if we could prove that no polynomial time algorithm could exist, this implies $P \neq NP$.

Are there other problems in $NP$ that have this property? That is,

Is it possible for a problem $X$ in $NP$ to not be NP-complete, but we could still solve $P$ vs. $NP$ by determining if it has polynomial time lower bounds.

Of course, proving that there is an exponential lower bound on any NP problem proves $P \neq NP$, but are there problems in NP where finding a polynomial time lower bound (besides NP complete problems) shows $P = NP$?

# Answer
> 4 votes
Yes.

Ladner's theorem shows that for any problem $X \in \mathrm{NP} \setminus \mathrm{P}$ there is a problem $Y \in \mathrm{NP} \setminus \mathrm{P}$ such that $Y$ is reducible to $X$ but not vice versa.

If we apply the construction from Ladner's theorem to e.g. $\mathrm{SAT}$ we obtain a problem $Z \in \mathrm{NP}$ such that either $Z$ is neither in $\mathrm{P}$ nor $\mathrm{NP}$-complete (in case that $\mathrm{P} \neq \mathrm{NP}$); or $Z$ is simulatenously in $\mathrm{P}$ and $\mathrm{NP}$-complete (if $\mathrm{P} = \mathrm{NP}$).

In other words $Z$ is not $\mathrm{NP}$-complete unless for trivial reasons, and proving that $Z$ belongs to $\mathrm{P}$ entails $\mathrm{P} = \mathrm{NP}$.

# Answer
> 0 votes
To extend the answer provided by @Arno, the problems sought by the OP are those belonging to the class of NP-intermediate problems: $N P I=N P \backslash(P \cup N P C)$. Despite the interest, we still do not know of any natural problem belonging to this class, all we have are natural candidates, e.g. graph isomorphism, discrete logarithm and factoring. A few years ago I have found, along with my coauthor, another possible candidate which has been useful for the construction of a cryptographic protocol:

**Exponentiating Polynomial Root Problem (EPRP)**

Let $p(x)$ be a polynomial with $deg(p) \geq 0$ with coefficients drawn from a finite field $GF(q)$, and $r$ a primitive element for that field. Then, the problem of finding roots of

$p(x) = r^x$

is believed to be NP–intermediate, i.e., it is in the complexity class NP but it is supposed not to be in P nor NP–complete.

This problem is at least as hard as the discrete logarithm, it can be regarded as a generalization of it since the discrete logarithm problem is a particular case of EPRP when $deg(p) = 0$. Additional details can be found here or here.

# Answer
> -1 votes
My original answer below takes "not $\mathsf{NP}$-complete" in the OP's title and text at face value. As far as I can tell it is correct, and not incompatible with Arno's answer, whose interpretation of "not $\mathsf{NP}$-complete" is less "strict" — though probably closer to what the OP wanted and yielding more interesting properties!

---

The answer is no.

Consider a problem $X$ in $\mathsf{NP}$ that is not $\mathsf{NP}$-complete. Suppose that finding out some bound on the complexity of $X$ would show $\mathsf{P}=\mathsf{NP}$.

The thing is that if $\mathsf{P}=\mathsf{NP}$, then all problems in $\mathsf{NP}$ are $\mathsf{NP}$-complete, except for the two trivial problems “always yes” and “always no”.

So $X$ would have to be either “always yes” or “always no”, whose complexity is well-known (they are constant time) and has no bearing on the $\mathsf{P}$ vs $\mathsf{NP}$ problem.

---
Tags: complexity-theory, np-complete, np, p-vs-np
---


# Question
Title: How to convert the following from NFA with ε-moves to DFA?
Can you provide the transition table along with the solution for better understanding?

# Answer
> 0 votes
It helps to begin by asking: What language does this NFA recognize? There are two distinct pathways, one that recognizes (10)\* (including the empty string) and one that recognizes 0\* (again, including the empty string).

To build a DFA for this language, it helps to try to describe what you know about the string seen so far, then add a state to the DFA for every piece of information. There is no single solution. For example, one key observation is that the first symbol (0 or 1) determines the type of acceptable string, 0\* or (10)\*. Therefore:

1. We need an initial state A, which should also be an accepting state since the empty string is valid.
2. On a 0, we go to a state B that consumes additional 0's.
3. On a 1, we alternate between two states C and D that consume 0's and 1's respectively.

For example, state C means „I have seen a 1 and I expect to see a 0”.

It is important to define every transition for every (state,symbol) combination. In our case, strings like 00001 or 10101011 should move to an error state E, which should be absorbing (no escape).

| state | accepting | on 0 go to | on 1 go to |
| --- | --- | --- | --- |
| A | yes | B | C |
| B | yes | B | E |
| C | no | D | E |
| D | yes | E | C |
| E | no | E | E |

---
Tags: finite-automata
---


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

Thank you all for your answers.

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

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

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

# Answer
Discrete Maths contains Sets, Relations, Trees, Graphs, Boolean Algebra etc. which are some conceptual Topics not Calculus. Discrete Math is very useful as view of Programming.
> 2 votes

# Answer
I think that answer depends slightly on the curriculum and the teaching method for the class (Discrete Math).

If this is an undergraduate class, thought from Kenneth Rosen's book it usually does not require much pre-requisite at all beyond standard math classes. I would say that the only pre-requisite is understanding of Math in general, basic (order of operations, etc).

If the class is somewhat more demanding and if it requires knowledge of basic proving techniques, concepts in number theory, I think the course in Abstract Algebra is a good pre-requisite.

I am currently reading a Dover book for fun - "Concepts of Modern Mathematics" by Ian Stewart which is a great self-study intro (and beyond).

In general, one should read up on sets, proofs, boolean algebra, state machines and general ide of algorithms to get a good start.
> 2 votes

# Answer
> Is calculus required or will precalculus do just fine?

No. Calculus deals with calculating the slope at any point on a *continuous* curve or calculating the area under a *continuous* curve. Since continuous ranges (uncountably infinite) and discrete ranges (finite or countably infinite) are opposites, calculus is largely inapplicable to discrete math.

Some concepts from basic math courses are useful

* algebra - treating quantities symbolically
* geometry - formal proof
* pre-calculus - specifying relations inductively based on (countably) infinite series

Formal logics are also valuable since formal logics stress induction and symbolic thinking. Some logics (Boolean) also deal with discrete truth values.
> 2 votes

# Answer
The answer depends on both your career choices and your university's program.

Do you think you'll need to process sounds and music? Then some knowledge of calculus, power series and, even more important, Taylor series, is a MUST.

Will you work on a 3D engine? Maybe something VR - related or some virtual simulation machine? Then abstract algebra (groups, fields etc.) is required, at least for the first - person camera movement (see the quaternion group and quaternion rotation). So is linear algebra.

Or maybe you wish to work in a more engineer - oriented company, such as Siemens? Calculus is again a requirement for such a job, and again, so is linear algebra.

All of the above are jobs that demand a certain skill when it comes to mathematics.

If you're more inclined towards developing web/ desktop/ mobile applications, then maybe you won't need so much math (in case it's not an app such as WolframAlpha).

You're going for a more theoretical - oriented career? Then you'll need a very good understanding of algorithms (complexities, optimization and such) and you'll also be asked to come up efficient solutions and make them even more optimal after deploying them.

Is it that you wish for an embedded programming job? If that's so, you'll also want to know quite a bit of electrical engineering (DOS and such) and, as you can already tell, some maths are needed to understand that.

As you can tell, mathematics is not a subject to be ignored when it comes to computer science and programming, but it shouldn't define your career. See what you want to do in in the tech world. List a couple of choices which you like best. After that, see what maths are required for a good job in the sector you chose to work in. Maybe you won't like them. Maybe they're not that interesting to you. If that is the case, move to the second choice and repeat the process. If the maths are more to your liking, than go for that job/ field/ sector and knock yourself out!

The most important thing in the "Hello World!" (pun) is to get you coding and algorithm skills on point. Tackle some fields: webdev, embedded, etc. (at least read about them). Then learn the maths that you'll need in you field of choice.

Hope this kinda answered you question and that it was helpful!
> 1 votes

# Answer
I think Maths is a very wide term these days. It could include algebra, calculus, geometry, trigonometry, statistics and so on. And generally, we refer to one or more domains when talk about any topic or concept in mathematics. Now, talking to your point whether you need a good knowledge of maths, so the answer is NO!. I think so because logical reasoning is not any branch of mathematics. Logic is defined as the theory of inference or, given one truth (or set of truths), how to infer another. It is NOT a branch of mathematics, is a study in its own right, but is also seen as a branch of or intersecting with philosophy.
> -1 votes

---
Tags: discrete-mathematics
---