title: Average-case complexity for coNP

text:
# Question
Title: Average-case complexity for coNP
I have been unable to find any literature on average-case complexity for coNP, other than a folklore conjecture that most tautologies are hard for any given propositional proof systems and some analysis of random k-SAT refutation. Am I missing something?

Is the following not a simple characterization: no paddable coNP-complete language is easy on average (in AvgP) if one such language has a stronger property invariant under p-isomorphism: for any Turing machine M accepting the language, P-uniform input families requiring superpolynomial time exist and appear with positive upper density in an enumeration of input families.

# Answer
> 1 votes
Every problem that can be solved in polynomial time is both in NP and coNP, so many problems in coNP can be solved in polynomial time.

Even if you look at coNP-complete, I can easily design a problem where the number of hard instances grows so slowly that the average time to solve an instance is polynomial or even linear.

---
Tags: average-case
---


# Question
Title: Can there be an infinite number of different cycles in a directed graph?
If not, then what is the maximum number of cycles in any graph?

# Answer
> 0 votes
If the graph has finite vertices then the no. of cycles are finite but for an infinite graph there can be infinite cycles.

---
Tags: graphs
---


# Question
Title: Clarification regarding linear boolean functions!
I am a little confused when it comes to linear boolean functions. According to this post:

What is a simple way of explaining what a linear boolean function means in boolean algebra and relating it to the standard definition of linearity?

We have that a function is linear if: $$f(x \oplus y) = f(x) \oplus f(y)$$

which (again according to the comments in the previously mentioned post) is equivalent to:

$$f(x\_1, x\_2, ... x\_n) = c\_0 \oplus c\_1x\_1 \oplus ... \oplus c\_nx\_n $$

where multiplication is defined as the logical AND (since wie operate mod 2). Now assume I define the function f as addition with 1, thus:

$$ f(x) = 1 \oplus x $$

This can easily be written in the above mentioned way, namely having $$c\_0 = c\_1 = 1$$, and thus:

$$ f(x) = 1 \oplus (1 \wedge x\_1)$$

Quick double-check: If x = 1:

$$ f(1) = 1 \oplus (1 \wedge 1) = 1 \oplus 1 = 0$$

and if x = 0:

$$ f(0) = 1 \oplus (1 \wedge 0) = 1 \oplus 0 = 1$$

However, if we try to apply the above mentioned definition of linearity, and we set x to 1 and y to 1, we have: $$f(x \oplus y) = f(1 \oplus 1) = f(0) = 1$$ which is NOT the same as: $$f(x) \oplus f(y) = f(1) \oplus f(1) = 0 \oplus 0 = 0$$

Can someone clarify or explain where I am wrong in my thinking?

Thanks :)

# Answer
> 4 votes
A function satisfies $f(x \oplus y) = f(x) \oplus f(y)$ for all $x,y$ iff it is of the form $$ f(x) = c\_1 x\_1 \oplus \cdots \oplus c\_n x\_n. $$ Indeed, all functions of this form satisfy the identity. Conversely, suppose that $f(x \oplus y) = f(x) \oplus f(y)$. Then $f(0) = f(0 \oplus 0) = f(0) \oplus f(0)$. Now let $e\_i$ be the vector $(0,\ldots,0,1,0,\ldots,0)$, where the unique $1$ is in the $i$'th position. Then $$ f(x) = f(x\_1 e\_1 \oplus \cdots \oplus x\_n e\_n) = f(x\_1 e\_1) \oplus \cdots \oplus f(x\_n e\_n) = x\_1 f(e\_1) \oplus \cdots \oplus x\_n f(e\_n), $$ where $f(x\_i e\_i) = x\_i f(e\_i)$ holds since if $x\_i = 0$ then $f(x\_i e\_i) = f(0) = 0 = 0 f(e\_i)$, and if $x\_i = 1$ then $f(x\_1 e\_i) = f(e\_i) = x\_i f(e\_i)$.

---

A function satisfies $f(x \oplus y \oplus z) = f(x) \oplus f(y) \oplus f(z)$ for all $x,y,z$ iff it is of the form $$ f(x) = c\_0 \oplus c\_1 x\_1 \oplus \cdots \oplus c\_n x\_n. $$ Indeed, all functions of this form satisfy the identity. Conversely, let $g(x) = f(x) \oplus f(0)$. Then $$ g(x \oplus y) = f(x \oplus y \oplus 0) \oplus f(0) = f(x) \oplus f(y) \oplus f(0) \oplus f(0) = g(x) \oplus g(y). $$ Thus $g(x) = c\_1 x\_1 \oplus \cdots \oplus c\_n x\_n$, and so $f(x)$ is of the required form, with $c\_0 = f(0)$.

---

More generally, if a function satisfies $f(x^{(1)} \oplus \cdots \oplus x^{(m)}) = f(x^{(1)}) \oplus \cdots \oplus f(x^{(m)})$ for even $m \geq 1$, then $f$ is linear; if $m \geq 1$ is odd then $f$ is affine. You can see this by taking $x^{(2)} = \cdots = x^{(m)}$ when $m$ is even, and $x^{(3)} = \cdots = x^{(m)}$ when $m$ is odd.

# Answer
> 3 votes
From the definition, for any univariate linear function $$f(0)=f(0\oplus 0)=f(0)\oplus f(0)=0.$$

Hence the function $1\oplus a$ is not linear. (In fact, it is *affine*.)

---
Tags: boolean-algebra, linear-algebra
---


title: Reducing to an NP-complete problem

text:
# Question
Title: Reducing to an NP-complete problem
If $R$ is an arbitrary decision problem that is reducible to $S$, which is an NP-complete problem, what can be said about $R$?

I think we should be able to say that $R$ is in NP since an instance of $S$ can have a certificate verified in polynomial time and from the reduction $R \le S$, we could say the same about $R$. Is this reasoning valid? Would it also work if $S$ was only supposed to be in NP rather than NP-complete?

Thanks in advance.

# Answer
Yep - your reasoning regarding your NP is correct. But not regarding NP-complete. The crux of the matter is that NP is inclusive, P is in NP and your problem R could be in P (and thus in NP).

NP-complete is not inclusive. It refers to the hardest problems in NP and a problem is in NP is there is no "simpler solution" (assuming P!=NP). In your case since R \< S it may be (temporarily) true that R is in NP-complete, but then you will have to show that there is no simpler solution to R. What you have shown is that there is a solution to R going through S - this is a solution, but for NP-complete, you must show also there there is no simpler solution. (Caveat - all this language of simpler solution, hardest problem, and so on assumes that P!=NP.
> 2 votes

---
Tags: np-complete, reductions, np, decision-problem, polynomial-time-reductions
---


# Question
Title: Universal quantification and the number of solutions
How would one count the amount of solutions to quantified formulas that have universal quantifiers? For example, for a boolean formula $\Phi(X)$ with a number of solutions $\\#\Phi(X)$ let's construct a quantified boolean formula $\forall y \ \exists X: y \lor \Phi(X)$. In this case $X$ represents $n$ boolean variables. What would be the number of solutions to it? Either $0$ or $1$? If so, can we conlude $\mathsf{NP}\in\oplus \mathsf P$?

Or would it be a real number with a number of solutions between $0$ and $1$, like $\frac{\\#\Phi(X)}{2^{n+1}}$?

# Answer
There seem to be many misconceptions and confusions built into this question, so let me try to help you think about these topics more carefully. I encourage you to read about fundamental materials on these topics before asking another question in this line, so that you're able to formula your question using standard terminology and are able to clearly express what you're trying to ask.

First, please familiarize yourself with the definition of a formula and free variables. If $\Phi(X)$ is a formula with free variables $X$, then an assignment maps each variable in $X$ to true or false. We can then check whether $\Phi(X)$ evaluates to true or false under this assignment. A satisfying assignment is an assignment for $X$ where $\Phi(X)$ evaluates to true. Please read each of those links and familiarize yourself with this basic terminology.

Note that we normally only talk about satisfying assignments for formulas with free variables. It is not terribly useful to talk about satisfying assignments for a formula like $\exists X \> \Phi(X)$ or $\forall y \exists X : \Psi(X,y)$, as those have no free variables. More pedantically, if $\zeta$ is a formula with no free variables, then there is only a single assignment (since there are no free variables, there is only one way to map every free variable to true or false), and it is a satisfying assignment if $\zeta$ evaluates to true and otherwise is not a satisfying assignment.

So, with that foundation, we can then try to interpret your question in a sensible way in one of multiple different ways:

* Perhaps you mean to ask: given a formula $\Phi(X)$ with free variables, count how many satisfying assignments to $X$ it has. If $\Phi$ has no quantifiers, this is exactly the #SAT problem. #SAT is #P-complete. If it has quantifiers, the problem might be very hard (I don't know exactly how hard).
* Or perhaps you mean to ask: given a formula $\zeta$ with no free variables, count how many satisfying assignments it has. The answer to this question will be either 0 or 1: it is 0 if $\zeta$ evaluates to false, or 1 if $\zeta$ evaluates to true. If $\zeta$ is a Boolean formula with quantifiers, then determining whether $\zeta$ evaluates to true is the TQBF problem. TQBF is PSPACE-complete.
* Or perhaps you mean to ask: given a formula $\Phi(X)$ with free variables $X$ and no quantifiers, count the number of satisfying assignments of $\forall y . \exists X . y \lor \Phi(X)$ specifically. This is an instance of TQBF, but it is easier than general TQBF. Note that $\forall y . \exists X . y \lor \Phi(X)$ is a formula with no free variables, so the number of satisfying assignments will be 0 or 1, according to whether it evaluates to true or not. Moreover this formula evaluates to true iff $\exists X . \Phi(X)$ does. So, if $\Phi(X)$ is in CNF form (or is any Boolean formula with no quantifiers), this can be tested with a SAT solver. Thus, this problem is NP-complete.

I don't know where you got $NP \in \oplus P$ from or why you think that has any relationship to this matter. It's actually not a well-formed statement: both $NP$ and $\oplus P$ are classes of problems, so we can't have $NP \in \oplus P$. At best you could ask whether $NP \subseteq \oplus P$, but that doesn't appear to have any relationship to the rest of your question. Please learn about the $\oplus P$ complexity class as I suspect you may have some misunderstandings about it.
> 2 votes

---
Tags: logic, counting
---


# Question
Title: Sorted degrees and maximal degree in dynamic graphs
Consider a sequence of vertex and edge additions and removals to an initially empty (undirected, simple) graph.

Is it possible to update the *ordered* list of vertex degrees in constant time (and space), for each addition or removal? How?

Is it easier to update only the maximal degree (lower time or space complexity)? How?

# Answer
This is a special case of sorted counters, for which a constant-time solution is given there.

For degrees, a counter is needed for each vertex, and its value is bounded by the number $n$ of (present) vertices. If $n$ is known beforehand, and if vertices are numbers from $0$ to $n-1$, then the generic solution may be optimized: hash tables and dynamic arrays may be replaced by static arrays, which gives a constant worst case time complexity.
> 0 votes

# Answer
I would assume here that adding/removing edges/vertices will be done one at a time. Please take note, the term node is used for a node in a linked list and I tried my best not to use it interchangeably with the term vertex.

### The structures for storing vertices and edges

Let `A` be your adjacency list for the graph.

Let `V` be an array (ordinary/associative depending on your actual vertex representation) of pointers. An entry in `V` points to a vertex stored in the structure `D` given below.

Let `D` be a doubly linked list. A node `n` of this list holds two data: `d` an integer that represents the degree and a doubly linked list `l` containing all vertices with degree `d`. We shall maintain that the nodes of `D` are ordered in increasing value of `d`. You can think of nodes in `D` like a bucket containing all vertices with the same degrees. `D` will have a tail pointer that points to the end (bucket containing vertices with maximal degree).

Initially, `D` only has a node `n0` such that `n0.d = 0`, which will contain all newly added vertex (assuming that newly added vertex has no edge yet).

The entries of list `l` are vertices with degree `d`. Each vertex `v` in `l` has a pointer `b` that points back to the node in `D` where `l` belongs.

### Adding a new vertex

When you add a new vertex `v`, create an entry in `A` and add it to `n0.l` and finally add an entry in `V` that will point to `v` in `D`. Set `v.b` to `n0`.

### Adding and removing edges

When a new edge `(u,v)` is added, add the nodes (using the procedure above) if they do not exist yet. Update the entries of `A`. Then, follow the pointer of `u` in `V`. At this point, the degree of `u` will increase by 1. Follow `u.b` pointer to get the node `n` in `D` containing `u`. Let `n'` be the node following `n` in `D`. If `n'.d` = `n.d + 1`, transfer `u` to `n'.l`. If `n'` does not exists or `n'.d > n.d + 1`, insert a new node `m` after `n` such that `m.d = n.d + 1` and transfer `u` to this node. Update `u.b`. If after this `n.l` becomes empty , delete it, except when `n = n0`. Do the same update to vertex `v`. Finally, update the tail pointer of `D` in case the the last node in `D` changes.

When you remove an edge, you can simply reverse the process of adding (I will leave this one for you to think about).

### Removing a vertex

Removing a vertex `v` can be implemented by first removing all its edges one at a time using the edge removal procedure above, then finally removing `v` from `D`, `V`, and `A`.

### Analysis

Updating the edges of a vertex and maintaining the order of `D` after adding a vertex and updating edges takes $O(1)$ time (ignoring the cost of adding a new entry in `A` and `V` which is dependent on how you implement them). This is because we only need to follow and update constant number of pointers and create/remove constant number of nodes in the linked lists.

As for the removal of a vertex `v`, the time is $O(deg(v))$, which I think is optimal since you have to update that many vertices too since you have to update the neighbors of the removed vertex.

Each entire representation requires $O(n)$ extra space for the pointers and linked list nodes for each vertex. This is $O(1)$ additional space per vertex.
> 2 votes

---
Tags: algorithms, graphs, online-algorithms, streaming-algorithm, dynamic-graphs
---


# Question
Title: what are all the domains of computer sciences?
Im trying to build my own learning track

Currently I am working on becoming a unity developer to make game or whatever is needed. I use C# within the system.

I don't feel satisfied just working within the engine and want to make my skills more broad and flexible to be able to solve a wide number of problems.

if someone could help me break down the comp sci world so I can learn about each domain one at a time and potentially learn to combine them all.

Why? because I get extremely nervous when I see any feature that I can't deconstruct quickly.

A better way of phrasing it.. Im looking for a hierarchy of computer science ideas from the broadest to the smallest... so I can understand them properly and sort them. put the ideas together.

or perhaps I should just calm down

# Answer
> 4 votes
You'll be able to better understand all the branches and subfields of Computer Science if you take a look at the ACM Computing Classification System. This system is normally used by scientists to assign commonly agreed keywords to their papers. This site can show you a "big picture" (13 categories), then you can choose a category, click on it and see what it consists of, and so on.

An alternative way is to use the American Mathematical Society subject classification system - the `68 Computer Science` category is much more coarse than the ACM classification, however it still shows a "look and feel" of the Computer Science.

Looking at these subject classification systems might be useful if you want to **choose** a subject to dig deeper into it - however learning **all** these subjects one by one will be beyond any human capabilities.

# Answer
> 3 votes
Broadly speaking, computer science can be divided into Theoretical Computer Science, Artificial Intelligence, and Computer Systems. Each of these categories has many subcategories, and each subcategory has many subcategories and concepts after that, and there are also some domains that don't perfectly fit into any of the categories. The wikipedia page provides a good overview of all the areas of computer science in the introduction, and goes into more detail in the body of the article.

*Theoretical computer science* studies what can and cannot be computed efficiently. *Artificial intelligence* (including *machine learning*) is about making computers perform well on difficult conceptual tasks, especially processing images, text, and video data. *Computer systems* is about building computers and networks of computers, including all the software and hardware infrastructure (or "nuts and bolts") that makes everything fit together.

For computer science research, there's a website CSRankings.org that lists all the most prominent and active research areas in these categories. For example, within theoretical computer science, there is algorithms and complexity theory, logic, and cryptography. Within artificial intelligence, there is machine learning, computer vision, and natural language processing. Within computer systems, there are fields such as networks, operating systems, software engineering, programming languages, databases, and computer security.

**However,** it's important to note this sort of "big picture" view is not really a good way to learn computer science! For such a vast field, looking at the big picture you will encounter many concepts and areas that aren't relevant to what *you* are doing, and you will lose interest quickly. A much better way is to focus on only the subareas you find interesting, and read a little bit more about those. In the long run, you will develop an understanding of one or two areas, while dabbling in one or two more, and eventually have a deep understanding of some areas and a shallow understanding of all the others.

---
Tags: software-engineering
---


# Question
Title: An α-good tree with n nodes has height O(log n)
Let $α \in \[0, 1)$ be a constant. For a rooted binary tree $T$ and a node $x$ in $T$, we denote by $|x|$ the number of nodes in the subtree of $T$ rooted at $x$ (if $x$ = $NIL$ then $|x|$ = $0$). We say that $T$ is $α$-good if, for every node $x$ in the tree with children $y$ and $z$, it holds that $|y|$$|z|$$α|x|$. Show that an $α$-good tree with n nodes has height $O(\log n)$.

I tried using induction for this but made no progress.

Some other observations I made:

$|x| = |y| + |z| + 1$
$\le 2|z| - (|z| - |y|) + 1 $ (WLOG assume $|y|\le|z|$)
$\le 2|z| - ||z| - |y||+1$
$\le 2|z| - \alpha |x| + 1$
$ = 2|z| - \alpha |y| - \alpha |z| + (1 - \alpha)$

I'm not sure if it helps.

# Answer
> 6 votes
$$2|y| = (|y|-|z|) + (|y|+|z|)\le \alpha |x| + |x| - 1.$$ So, $|x| \ge \frac2{1+\alpha}|y|$.

Since $y$ is an arbitrary child of $x$, if node $x$ is of height $k$, $|x| \ge \left(\frac2{1+\alpha}\right)^k$.

If an $α$-good tree with $n$ nodes has height $h$, then $$n\ge \left(\frac2{1+\alpha}\right)^h$$

That is, $h\le\log\_{\frac2{1+\alpha}}n$, which means $h=O(\log n)$ since $\frac2{1+\alpha}\gt1$.

# Answer
> 5 votes
First, note that if $T$ is an $\alpha$-good tree, then for any node $x$ with children $y$ and $z$, without loss of generality, $|y| \leqslant |z| \<\frac{1+\alpha}2 |x|$.

Now consider $h\_n$ the maximal height of an $\alpha$-good tree of size $\leqslant n$. It is clear that $h\_1 = 0$ (or $1$, depending on your definition of height). The property above shows that for $n\geqslant 2$, $h\_n \leqslant 1 + h\_{\left\lfloor\frac{1+\alpha}2n\right\rfloor}$.

An induction can now show that $h\_n \leqslant \log\_{\beta}(n)$, with $\beta = \frac2{1+\alpha}$. Since $\alpha \< 1$, this is clearly in $\mathcal{O}(\log n)$.

---
Tags: asymptotics, trees, binary-trees
---


# Question
Title: Time complexity analysis for dynamic programming using memoization
I am trying to figure out the time complexity for "Regular Expression Matching" problem. Problem statement is simple, only meta characters allowed are '.' and '\*'. Actual problem statement can be found in Link

The solution is in java and I have solved it using memoization, but having difficulty to compute the time complexity. Can anyone help me with the explanation, and any reference documents or link to study further on this subject.

```
 1    public boolean isMatch(String s, String p) {
 2        return backTrack(s, 0, p, 0, new Boolean[s.length() + 1][p.length() + 1]);
 3    }

 4    boolean backTrack (String s, int si, String p, int pi, Boolean[][] dp) {
 5        if (pi >= p.length()) return si >= s.length();
 6        if (dp[si][pi] != null) return dp[si][pi];
 7        if (pi < p.length() - 1 && p.charAt(pi + 1) == '*') {
 8            if (si < s.length() && (s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '.')) {
 9                if (backTrack(s, si + 1, p, pi + 2, dp)) return dp[si][pi] = true;
10                if (backTrack(s, si + 1, p, pi, dp)) return dp[si][pi] = true;
11            }
12            if (backTrack(s, si, p, pi + 2, dp)) return dp[si][pi] = true;
13        }
14        if (si < s.length() && (s.charAt(si) == p.charAt(pi) || p.charAt(pi) == '.')) {
15            if (backTrack(s, si + 1, p, pi + 1, dp)) return dp[si][pi] = true;
16       }
17        return dp[si][pi] = false;
18    }

```

# Answer
***The time-complexity of dynamic-programming with memoization***

Here is the simple principle. Suppose an algorithm

* applies dynamic programming to solve a problem,
* with the majority of running time spent on computing $O(s)$ subproblems for some expression $s$,
* where each subproblem is computed/solved only once thanks to memoization,
* and it takes $O(u)$ time for some expression $u$ to compute/solve each subproblem, assuming it takes $O(1)$ time to access the result of any other subproblems that are needed during that computation,

then the time-complexity of the algorithm is $O(su)$, in general.

***Analysis of the algorithm in the question***

Let us estimate how many line-executions are done if the algorithm is run upon an input of a string of length $m$ and a pattern of length $n$.

There are $(m+1)(n+1)$ entries in the table `dp` (which represent $O(mn)$ subproblems). The code that actually computes and updates the entries are the code block from line $7$ to line $17$. Because of memoization, these lines will be executed at most once for each entry. So these $17-7+1$ lines will be executed at most $(m+1)(n+1)$ times, i.e., these lines correspond to at most $(17-7+1)(m+1)(n+1)$ line-executions.

How many times will line $4$ (for building and quitting calling stack frames), line $5$ and $6$ be executed? Except the first time that is triggered by line $2$, the execution of them is triggered by the execution of any one of $4$ lines, line $9$, $10$, $12$, or $15$, which happens during the execution of the code block mentioned above. So line $4$, $5$ and $6$ are executed at most $1 + 4(m+1)(n+1)$ times, i.e., these $3$ lines correspond to at most $3(1 + 4(m+1)(n+1))$ line-executions.

So, the total number of line-executions is at most $$(17-7+1)(m+1)(n+1) + 3(1 + 4(m+1)(n+1)) + 2,$$ where the last number $2$ is for the one-time execution of line $1$ and $2$ at the start of running the algorithm. We can check that it takes $O(1)$ time to execute each line, except for possibly line $2$, which is executed once that costs up to $O(mn)$ time. Hence, the time-complexity of the algorithm is $O(mn)$.

---

The analysis above serves as an example to illustrate and validate the principle.

Or we can apply the principle directly. There are $O(mn)$ subproblems. It takes $O(1)$ time to solve each subproblem, considering all recursive calls as taking $O(1)$ time. Hence the time-complexity of the total algorithm is $O(mn\times 1) = O(mn)$.
> 0 votes

---
Tags: time-complexity, dynamic-programming, memoization
---


# Question
Title: Understanding the application of the pumping lemma to show that $L=\{0^{2^p}, p \geq 0\}$ is not regular
I want to understand how is this proof working.

What I know:

**Pumping lemma for regular language-:**

Let $L$ be regular language. Then there exists a constant $n$ which depends on $L$ such that for every string $w \in L$ with $|w|\geq n$ and $w=xyz$ such that-:

1. $y\neq \epsilon$
2. $|xy| \leq n$
3. For all $i \geq 0$, $xy^iz \in L$

**The proof that I am trying to understand:** prove that $L=\\{0^{2^p}, p \geq 0\\}$ is not regular.

Solution:

1. Assume $L$ is regular. (I understand this).
2. $w=0^{2^n}=xyz$
3. $|y|$ can be from $1$ to $n$ (let) assuming $x=\epsilon$
4. Here we want to prove $xy^iz \not\in L$

So what the author has done is that:

|$xy^2z|=|xyz|+|y|$

The length of $xy^2z$ ranges from $2^n$ and $2^{n+1}$ But for $xy^2z$ $\in L$, we need its length in the multiple of $2^n$. This is what I understand. But I want to understand this better so that I can use this same problem solving ability to solve as many problems. Please review me.

What is the pumping length here? $i$ or $n$?

# Answer
The pumping length here is what you refer to with the variable $n$. (Usually but not always, the letter $p$ is used, but the name is not important as long as it is clear to you and your audience.)

The meaning of the pumping length $n$ is that for a language to have the pumping property, we only require that strings of at least $n$ characters have the necessary $xyz$ partition. This is because it's always possible to construct an automaton that accepts arbitrarily complex string patterns but only up to any fixed length. We want to say *sufficiently long* strings of a regular language must have some repeatable segment.

(Note: since we don't care if strings shorter than the pumping length can be "pumped" or not, and the pumping length does only specifies the minimum length of strings we require to have a legal $xyz$ partition, there actually exists an *infinite* number of pumping lengths for each regular language)

For this proof in particular, we've picked the string $w = 0^{2^n}$: that is, $w$ consists of $2^n$ repetitions of the symbol $0$. Since $|w| \geq n$, the string is clearly long enough. Then you correctly note that following the rules of the $xyz$ partition, $y$ must consist of at least $1$, at most $n$ repetitions of $0$. The next-longest string in $L$ after $w$ is $0^{2^{n+1}}$, but as $|y| \leq n$, we can reach at most $0^{2^{n}+n}$. Therefore $xy^2z$ is, no matter the choice of $y$ not in $L$ and therefore we've disproved $L$ having the pumping property. Since all regular languages have the property, $L$ is not regular.
> 1 votes

# Answer
We want to show the language $L = \\{0^{2^n}: n \ge 0\\}$ is nonregular.

By way of contradiction, suppose $L$ is regular. Then, there exists an integer $p$, called the pumping length, such that all strings in $L$ of length at least $p$ can be pumped. Let $w=0^{2^p}$. Because $|w| \ge p$, by the pumping lemma, there exists a partition $w=xyz$ such that $|xy| \le p, 1 \le |y| \le p$ and $xy^iz \in L, \forall i \ge 0$. The length of $xyyz$ is at least $2^p +1$ and at most $2^p + p \< 2^p + 2^p = 2^{p+1}$, whence $xyyz \notin L$, a contradiction.
> 0 votes

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Why rectangle packing is NP-hard but maybe not in NP?
Recently I studied a MIT open course.

In lecture2, it is stated that Rectangle Packing is NP-hard.

I can understand this because the problem can be reduced to 3-partition problem

**But I don't know why it's an open problem whether it's in NP.**

In lecture2 it is stated that:

> it is complicated to encode rotations efficiently.

**My question:** How to understand the last sentence?

# Answer
In order for a language $L$ to be in NP, there needs to be a way to certify that instance $x$ belongs to $L$. This "way" is a polynomial size witness which can be verified in polynomial time.

In this case, the obvious witness is a packing of the rectangles. Given such a packing, it is easy to check that it is indeed a packing. What is less clear is whether the witness has polynomial size, since it is not clear how to encode the rotations succinctly (or at all).
> 17 votes

---
Tags: np-hard, np, decision-problem
---


# Question
Title: Find largest set of players that never played against eachother
I have an interesting problem I need to solve. I have a list of about 200k two player matches containing about 22k unique players. I need to find the largest set of players that never played against each other.

The first approach I did:

1. pair each player with a set of players he played against
2. sort them by number of players played against (from min to max)
3. for each player, remove players played against from set of all players until the set is valid.

This approach got me a valid set of about 3000 players. How could I improve this? Thanks!

# Answer
You are essentially asking to find a maximum independent set of the graph in which each vertex is a player and there is an edge between two players that played against each other.

Unfortunately, without additional restrictions, the maximum independent set problem cannot be approximated in polynomial time within any constant factor unless P=NP. In fact, it cannot even be approximated in polynomial time within a factor $n^{1-\varepsilon}$ for any constant $\varepsilon\>0$ of choice (where $n$ is the number of vertices) unless ZPP=NP. See here.

Since you seem to be interested in one specific instance of the problem, you might try to use any readily available solver for max independent set/max clique and see how they perform. You could even write the problem as an integer linear program and use an ILP solver (although I would expect specialized tools to perform better).
> 4 votes

# Answer
Consider the players as a graph $G = (V, E)$ with $V$ being the set of all players and $(p\_1, p\_2) \in E$ if $p\_1, p\_2 \in V$ have not played against each other. Sets of players that have never played against each other are cliques of this graph, and you are looking for a maximum clique (a clique with the greatest number of member vertices). Alternatively, you can think of the edge representing that two players *have* played against each other and find a maximum independent set in the complement graph of $G$.

The best algorithms for finding maximum cliques or maximum independent sets in arbitrary graphs perform in exponential time with fairly small bases: Wikipedia lists a few approaches in their article on Clique problems. The asymptotically fastest algorithm currently known is described as follows:

> Robson's algorithm combines a similar backtracking scheme \[to Bron–Kerbosch algorithm\] (with a more complicated case analysis) and a dynamic programming technique in which the optimal solution is precomputed for all small connected subgraphs of the complement graph. These partial solutions are used to shortcut the backtracking recursion. The fastest algorithm known today is a refined version of this method by Robson (2001) which runs in time $O(2^{0.249n})$ = $O(1.1888^n)$.

The Robson 2001 paper is available here. However, due to the large dataset, even these best algorithms may prove to inefficient due to the general difficulty of finding cliques or maximum independent sets.
> 4 votes

---
Tags: algorithms
---


# Question
Title: Proving that the number of leaves in a tree >= number of unmatched vertices
Consider a rooted tree $T$. A matching in $T$ is said to be proper if for every unmatched vertex $v$ it holds that the parent of $v$ is matched to one of the siblings of $v$. It is known that every tree admits a maximum-size matching that is proper.

Consider a rooted tree $T$ over a set of vertices $V$ and a proper matching $M$ in $T$; we can think of $M$ as a collection of edges. Let $L(T)$ be the set of leaves of $T$, and let $U(M)$ be the set of vertices not matched by $M$ (i.e., $U(M) = \\{v ∈ V | v \notin e \space \forall e ∈ M\\}$). Prove that $|L(T)| ≥ |U(M)|$.

My attempt:

The set of internal nodes in $T$ form a valid vertex cover. The size of any vertex cover \>= the size of any matching.

$=\> |V| - |internal \space nodes| \<= |V| - |M|$

$=\> |L(T)| \<= |V| - |M|$

I can prove that $|M| \<=$ number of nodes being matched in the matching, and I guess I've to relate that to being less than $L(T)$ but I haven't figured out a way to do this.

# Answer
Prove it **by induction**. It is true for trees with |V|\<=3. Suppose that it is true for trees with |V|=n-1 and we want to prove it for a tree T with |V|=n.

**If** there exist a leaf v which is unmatched then by removing v, we have a tree T' and a proper matching M' where L(T')=L(T)-1, U(M')=U(M)-1 and L(T')\>=U(M'). Then, L(T)\>=U(M).

**Else**, all of vertices in F={v| v is a leaf} are matched by matching M. This means that all of leaves have no sibling which be a leaf. Hence, by removing a leaf v and its parent, we have a Tree T\_v on a subset of V-{v, Parent of v, all subtrees on siblings of v} and some trees T'\_v on siblings of v.

If we remove all of vertices in F and their parents, we have: V = Union of the removed vertices and the trees T\_v for all vertices v in F. Note that, it is possible that T\_v be equal to T\_u for u and v in F. Then, by deleting similar trees, suppose that we have different trees T\_v.

Then, let M\_v be the matching on T\_v. Based on induction, we have L(T\_v) \>= U(M\_v). Moreover,

we have L(T) \>= SUM(L(T\_v)) (for each leaf in T\_v we have at least a leaf in T)

and we have SUM(U(M\_v)) = U(M)

and this concludes that L(T)\>=U(M).
> 3 votes

---
Tags: trees, matching, vertex-cover
---


# Question
Title: A language that is either fully accepted by synchronised DFAs or not at all
I am trying to understand the concept of synchronised DFAs. I have a question where all the states in the DFA after reading that particular word from the alphabet will reach a particular state with the alphabet (A to Z). And I should prove that a language which accepts any random number of alphabet combinations followed by that particular word is either fully accepted by that synchronised DFA or it is not accepted at all.

I know my question might be confusing but maybe someone can explain to me like a idea how should I start because I'm not really sure and confused about how to go about here.

# Answer
A synchronizing word $w$ has the property that there is a single state $q$ of the DFA, such that for every state $s$ it holds that $\delta(s,w)=q$. That is, after reading $w$ you end up in $q$, regardless of where you started.

Now, suppose you read a bunch of letters. You know nothing about them. But you know that after reading them you are going to read a synchornizing word. Where will the automaton be after reading the entire sequence?

Can you take it from there?
> 1 votes

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


# Question
Title: Construction of a Turing Machine that accepts the language of (a^nb^nc^md^m for) m,n >= 1
i recently have been practicing constructing Turing Machines for languages. But i can't seem to figure this one out. I've seen a few videos on constructing 3 equal length strings (a^nb^nc^n) But i can't figure out this one. Can anyone help out how i can do this. Please don't give the answer outright, i want to actually know how it works.

Thank you.

# Answer
> 1 votes
Really, you have two identical tasks concatenated. Read the $a$'s and $b$'s and see if they're in the right form. Then, more or less reset and do the same things for the $c$'s and $d$'s. BTW, Welcome to the site!

---
Tags: turing-machines, context-free
---


# Question
Title: Sorted list of counters in constant time
**Summary.**

A data structure maintains in constant time a sorted list of counter values, for a dynamic set of counters. I am interested in references using this structure, and in possible improvements.

---

**Problem and motivation.**

Consider a set of counters that may be increased (by 1), decreased (by 1), deleted (when at 0), or created (with value 0). We want to efficiently update the sorted list of counter values when these operations are performed.

This is helpful for many counting tasks in dynamic contexts where we want to have the maximal value or the median value at any time. Typical examples include counting item occurrences within a bounded time window in any stream (one counter per item), the degrees in dynamic graphs (one counter per vertex/node), etc.

---

**Data structure.**

`values` is the array of counter values sorted in *decreasing* order: it has one cell per counter, `values[0]` is the largest counter value, `values[1]` the second largest (that may be equal to the first one), and so on.

`c2pos` is the dictionary giving the index of counters in `values`: `c2pos[c]` gives the index of the value of `c`, *i.e.* `values[c2pos[c]]`.

`pos2c` is the array that gives the counter corresponding to index `i` in `values`.

`val2pos` is the dictionary giving the smallest index `val2pos[v]` of a counter with value `v` in `values`.

`distrib` is the dictionary giving the number of counters of value `v`, for any `v`

All structures above are initialized to `empty`.

All counters are created with initial value `0`, and deleted only when their value is `0`.

---

**Algorithm.**

Addition of counter `c`:

> if `distrib[0]` does not exist then set it to `0`
> if `val2pos[0]` does not exist then set it to the length of `values`
> increase `distrib[0]`
> set `c2pos[c]` to the length of `values`
> append `c` to `pos2c`
> append `0` to `values`

Removal of counter `c`:

> decrease `distrib[0]`
> if it becomes `0` then remove entry `0` from `distrib` and `val2pos`
> swap `c` and the last counter in `values`
> remove entry `c` from `c2pos`
> remove the last cell of `pos2c`
> remove the last cell of `values`

Increase counter `c`:

> let `v` be the value of `c`
> swap `c` and the first counter in `values` with value `v`
> if `distrib[v+1]` does not exist, then set it to `0`
> if `val2pos[v+1]` does not exist, then set it to `val2pos[v]`
> increase `distrib[v+1]`
> decrease `distrib[v]`
> increase `val2pos[v]`
> if `distrib[v]` equals `0` remove entry `v` from `distrib` and `val2pos`
> increase `values[c2pos[c]]`

Decrease counter `c`:

> let `v` be the value of `c`
> swap `c` and the last counter in `values` with value `v`
> if `distrib[v-1]` does not exist, then set it to `0`
> if `val2pos[v-1]` does not exist, then set it to `val2pos[v]+distrib[v]`
> increase `distrib[v-1]`
> decrease `distrib[v]`
> increase `val2pos[v]`
> decrease `val2pos[v-1]`
> if `distrib[v]` equals `0` remove entry `v` from `distrib` and `val2pos`
> decrease `values[self.c2pos[c]]`

---

**Complexity.**

If dictionaries are implemented as hash tables, then the expected time of dictionary operations is $O(1)$. If counters are never deleted and if their values are bounded, then one may use arrays instead of hash tables, leading to a $O(1)$ worst case cost for dictionary operations.

If we use dynamic arrays, then array operations are in $O(1)$ amortized time. If we know the total number of counters in advance (or a bound), then the worst case complexity is $O(1)$.

Space complexity is linear with the number of counters, as the arrays and dictionaries contain one entry per counter, or one entry per counter value at most.

---

**Questions.**

Is this a well known method (maybe folklore?)? Where does it appear in the literature?

Is it possible to *significantly* improve it? For instance, are all the mentionned arrays and dictionaries mandatory? I wanted to avoid `distrib` but something of this kind seems necessary to avoid memory cost to grow with the maximal counter value.

# Answer
> 3 votes
I've implemented this data structure, or something very similar to it, various times, without using hash tables (or associative mappings) at all. As far as I know, it's a folklore algorithm, although I suppose it must exist somewhere in the literature, and hash tables weren't the first choice in languages which don't have them as a primitive data structure.

(When I say that it doesn't use hash tables, I mean that it doesn't use them internally. It's often convenient to use a hash table to find a counter given some identifier for it, but that's not always necessary. Here's a StackOverflow answer from 2016 and an even older one where I present this data structure; these do assume the use of a hash table to find the counters.)

I usually call it a "comb table" because it consists of tines, all with the same count, hanging off of a backbone of count objects. Each count object holds a count and an indication of the first and last counter which currently has that count. The counters themselves are either stored in an array (in which case they move around as the algorithm progresses, which needs to be tracked in some way), or they're stored in a double-linked list. If they're stored in an array, they will be in descending order so that new counters are born at the end of the array. Each counter has a reference to the count object; they don't hold their current count directly. They might also contain other information, of course.

Since the count has a reference to the first and last counter, and each counter has a reference to its count object as well as a mechanism for finding its predecessor and successor counter, it's not necessary to link the count objects. From a count object you can reach the next larger count by getting the count object of the successor of the last counter in the count object's list, and similarly for the next smaller count. By the same token, the application can find the zero-count object by following the reference from the first counter in the linked list of counters (or the counter at the top of the counter array).

The increment and decrement count operations are slightly more complicated than in your arrangement, but are clearly O(1) and follow basically the same steps. There are two paths, one of which applies when the count object is singular (has only a single counter) or multiple. Singular count objects are easy to recognise since their first and last counter references are the same.

To increment or decrement a counter whose count object is singular, we first increment or decrement the count object's count. We then check whether the new count is the same as the next count object (or the previous one, for decrement). If that's the case, the count object is deleted; the counter is repointed at the successor count object, whose first (or last) counter references is updated.

For a counter whose count object is multiple, we first move the counter to the appropriate end of the chain of counters with the same count object; if we're using a linked list, that involves four link modifications; if we're using an array, it's a simple swap, although we might also have to update whatever data structure is being used to find the counter. We then remove it from the chain for its current count object by modifying the last (first) counter reference of that count object. Finally, we check whether the next (previous) counter's count object has the consecutive count. If so, we only need to modify the first (last) counter reference that count object. Otherwise, we need to create a new count object and set both of its counter references to the counter whose value is being modified.

Count objects only exist for counts which have at least one counter, and there is only one count object per count value. So there are never more count objects than counters (and usually a lot fewer). It's possible to allocate counters and count objects together, even as a single memory allocation (although there's no relationship between the two parts of the allocation); since, there are usually fewer count objects in use, that means we'll need to thread a free-list through the unused count objects.

None of this is really limited to the case where increment and decrement are always by one. It's possible to handle problem domains with bounded increment and decrement, by just tracking through the successive counts until you find the right one, or the right place to insert one. That's still O(1), although you'd probably want the bound to be small. I've done this for increment bounds of two or three, and it's still competitive.

I don't know if that answers any question you had, but it's maybe interesting.

---
Tags: algorithms, algorithm-analysis, sorting, counting, constant-time
---


# Question
Title: Optimizing an arbitrary function of 10 variables
Let us be given a function $f(x\_1,\dots,x\_{10})$ of multiple variables $x\_1,\dots,x\_{10}$ given that $\sum\_{i=1}^{10} x\_i \leq 7$. How do we solve the following problem?

$$ \begin{equation} \begin{aligned} \max\_{\\{x\_i\\}, i=1,\dots,10} \quad & f(x\_1,\dots,x\_{10})\\ \textrm{s.t.} \quad & \sum\_{i=1}^{10} x\_i \leq 7\\ & x\_i \in X\_i, X\_i = \[0,10\] \\ \end{aligned} \end{equation} $$

I with my professor are trying to work on building a neural network in such a way that we have multiple output from each layer. For example there are $n$ neurons in the $i^{th}$ layer, there will be, let us say $k$ outputs of each size $n$. Similarly, the next layer will also have same number of output and we will look at all the possible ways to connect $k$ outputs of the $i^{th}$ layer and $k$ outputs of the $(i+1)^{st}$ layer. And we take the max of the output in each layer while updating the loss function. My professor told me that this boils down to finally become a DP problem.

# Answer
> 1 votes
There are only 19448 combinations of $x$'s that meet the constraints. If $f$ is arbitrary, the best you can do is enumerate all 19448 combinations and see which leads to the largest value of $f$. There is no faster algorithm. Dynamic programming does not seem relevant.

If you know something about the structure of $f$ (e.g., it is a separable function), then it might be possible to do better.

# Answer
> 0 votes
I do not see a dynamic programming solution. I highly doubt there is one (especially, a polynomial time).

---
Tags: algorithms, optimization, dynamic-programming
---


# Question
Title: Does every thread store its context in a separate PCB?
Is a thread's context stored in the process's PCB, or is a new PCB created for the thread?

# Answer
A thread is the unit of execution of a process. The latter can have one or more threads. Each thread, shares the common process info (global variables, files, address space), but it has its own computation and therefore stores independently PC, stack pointer, IP, and other registers. All this information is stored in the **TCB** (thread control block), whereas the process stores the information in the **PCB** (process control block). The way you link them together is by saving inside the thread's TCB, a reference to the process that spawned the thread.

For example, this is the implementation of the TCB for the Pintos operating system, written in C:

```
 struct thread {
    /* Owned by thread.c. */
    tid_t tid;                 /* Thread identifier. */
    enum thread_status status; /* Thread state. */
    char name[16];             /* Name (for debugging purposes). */
    uint8_t *stack;            /* Saved stack pointer. */
    int priority;              /* Priority. */
    struct list_elem allelem;  /* List element for all threads list. */

    /* Shared between thread.c and synch.c. */
    struct list_elem elem; /* List element. */

    /* Advanced scheduler fields. */
    int recent_cpu; /* In fixed point format.  */
    int nice;
    bool update_priority_needed;

    /* Donated priorities */
    struct donated_priorities donated_priorities;

    /* Lock this thread is trying to acquire */
    struct lock *lock_sought;

#ifdef USERPROG
    /* Owned by userprog/process.c. */
    uint32_t *pagedir; /* Page directory. */
    spt spt;
#endif

    struct process* process;
    /* Owned by thread.c. */
    unsigned magic; /* Detects stack overflow. */
};

```

Note the process pointer, right at the end of the struct.
> 2 votes

---
Tags: operating-systems
---


title: Examples of time complexity $O(n^k)$

text:
# Question
Title: Examples of time complexity $O(n^k)$
I am looking for some algorithms(examples) whose time complexity is given by $O(n^k)$. It could be any problems that you have come across. Please reply. Thanks!

# Answer
**Nesting for-loops climbs the asymptotic ladder by one power per nesting typically** (typically only, as it depends on the body and loop-parameters).

This is a good to keep in mind when nesting loops while coding.

**Consider the algorithms $P\_{k}$ which have $k$ nested for-loops. Each $P\_k$ is $O(n^{k})$:**

$P\_1$

```
For i = 1 to n do i := i + 1

```

$P\_2$

```
For i = 1 to n do

     For j = 1 to i do j := j + 1

```

...

$P\_k$

```
For i_1 = 1 to n do

      For i_2 = 1 to i_1 do

          For i_3 = 1 to i_2 do

            ...

              For i_k = 1 to i_{k-1} do i_k := i_k + 1

```

$P\_1$ is clearly linear-time $O(n)$

$P\_2$ is $O(n^2)$.

**Write out the $i$ and $j$ values for $P\_2$ corresponding to the program's execution:**

**i = 1:** j = 1

**i = 2:** j = 1, j = 2

**i = 3:** j = 1, j = 2, j = 3

...

**i = n:** j = 1, j = 2, j = 3, ... , j = n

This typical triangle shape occurs for $O(n^2)$ algorithms.

Recall that $1 + ... + n = \frac{n(n+1)}{2}$, the proof of which is based on doubling the triangle, making a rectangular shape, then halving the result to get the outcome.

In general, deepening the nesting of for-loops by 1 (typically) raises the power in the asymptotic classification by 1.

**You can also simply let the variables $i\_j$ run from $1$ to $n$** (rather than $i\_{j-1}$). This creates a more \`\`artificial" example which is obviously $O(n^{k})$ for $k$ loop nestings.

The code given for $P\_k$ is a little closer to practical nested for-loop cases. The example is still artificial, but it illustrates a principle behind many cases of $O(n^k)$ behaviour.

Algorithms in the literature for which the time analysis is $O(n^k)$ tend to fit the above pattern of loop-nestings tied to asymptotic behaviour. Bubble-sort is an obvious examples of $O(n^2)$ algorithms fitting this pattern. Insertion-sort also, be it that one of the loops is a while-loop rather than a for-loop. The same type of principle (typically) applies.
> 2 votes

# Answer
This is very broad. For the purposes of this discussion, I will assume k is a constant s.t. $k\neq k(n)$. One example of an algorithm that is $O(n^k)$ would be finding the maximum value of a k-dimensional array of size $n^k$. Another would be summing the values of a k-dimensional array of size $n^k$.
> 0 votes

# Answer
In parameterized complexity, the class XP contains all problems that can be solved in time $O(n^{f(k)})$ where $k$ is the size of the parameter, and $f$ is some computable function.

Note that ${n \choose k} = O(n^k)$, so any algorithm that tries to find a solution of size $k$ in a set of $n$ elements have a similar running time. For example brute force algorithm for many well-known NP-hard problems has such a running time where $k$ is the solution size.

Some examples are:

* Independence number, clique number, vertex cover number: Try all subsets of size $k$ and test if the chosen set is a solution.
* Hitting set: Try all subsets of size $k$ of the ground set.
* Set packing: Try all subfamilies of size $k$ of the given family of sets.
> 0 votes

---
Tags: time-complexity, polynomial-time
---


# Question
Title: Delete consecutive characters and add zeros at the end with a restriction
Given an array of characters, I need to delete all the characters that got repeated 3 or more times (consecutively) and add '0' at the end of the array for every deleted character,

The restrictions:

* $O(n)$ time
* $O(1)$ memory
* Can't overwrite a cell in the array more than once

Examples: "aacccbbddde" --\> "aabbe000000"

I managed to find the following solution without the restriction of $O(1)$ memory / overwrite (I can do only one at a time)

Any ideas?

# Answer
While waiting for your updated post that includes your solution, I have posted mine:

### Solution

A substring is **deletable** if all its characters will be deleted based on your requirement. This substring may have several groups of repeated characters. For example, if the string is "accccbbbdddagggde" then "cccc" and "bbb" are deletables. A deletable substring is **maximal** if it is not adjacent to any deletable substring.The examples earlier are not maximal deletable substring, but "ccccbbbddd" and "ggg" are maximal. An **undeletable** substring is a substring that will remain in the string. A **maximal undeletable** substring follows the same idea as maximal deletable.

Your problem is essentially to remove all maximal deletable substring in a string, and then append the resulting string with as many 0 as the removed characters. Below is a solution:

1. Let $cur = -1$ be the starting index in the array that can be overwritten. Initially, there is no index to overwrite. Let $count$ be the number of characters that will be removed.
2. Scan the array until you find the left-most maximal deletable substring $d$. Let $d\_{start}$ and $d\_{end}$ be the start and end index of this string, and $d\_{len} = |d|$ be $d$'s length.
3. Continue the scanning to find the maximal undeletable substring $u$ adjacent to $d$. Let $u\_{start}$ and $u\_{end}$ be its start and end indices and $u\_{len} = |u|$ be $u$'s length.
4. If both $d$ and $u$ exist, do the following:

* If $cur$ is still -1, set $cur = d\_{start}$.
    * Set $count = count + d\_{len}$.
    * Copy substring $u$ at position $cur$ all the way to $cur + u\_{len} - 1$. This essentially moves substring $u$ to the left, overwriting $d$, entirely or partially, depending on whether $|u| \ge |d|$.
    * Move $cur$ passed the copied substring, that is let $cur = cur + u\_{len}$.
    * Go back to step 2, but the scanning will start at $u\_{end} + 1$.
5. If either $u$ or $d$ does not exist, write as many 0 $count$ to the array starting at position $cur$, and we are done.

### Analysis

* This solution uses only $O(1)$ extra variables, hence it uses $O(1)$ extra space.
* It overwrites an index of the array once. Either at step 4, when moving an undeletable string to the left or when writing 0's at step 5.
* This solution runs in $O(n)$ time. Observe that an index is visited at most twice, once when it is considered in the search for deletable/undeletable substring and the other when it is overwritten. Finding a deletable and undeletable takes time $O(|d|)$ and $O(|u|)$ resp., while moving an undeletable takes $O(|d|)$ time. In the worst-case, all substrings in the string will be classified as is either deletable or undeletable. Since indices are written at most once, the total time of finding and moving all such substrings is $O(n)$.
> 1 votes

# Answer
Have a write index. Then go through the array, identify and measure each streak of equal characters. Streaks shorter than 3 get written. At the end, write zeros at the remaining indices.

Python implementation:

```
from itertools import groupby

array  = list("aacccbbddde")
expect = list("aabbe000000")

write = 0
for char, streak in groupby(array):
    length = sum(1 for _ in streak)
    if length < 3:
        for _ in range(length):
            array[write] = char
            write += 1
for write in range(write, len(array)):
    array[write] = '0'

print(array)
print(array == expect)

```

Output (Try it online!):

```
['a', 'a', 'b', 'b', 'e', '0', '0', '0', '0', '0', '0']
True

```
> 1 votes

---
Tags: algorithms, time-complexity, space-complexity, strings
---


# Question
Title: Pair points between to sets minimizing the global distance
I have two set of points in the plane or space, which could be for instance radar contacts over two successive scans. I'd like to pair them so that the sum of squared distances is minimal.

One difficult case, if for instance there is a serie of aligned and equidistant points in the first set, can be found in the second one shifted by one interval (they all moved together). The sum of squared distances does promote the desired solution, but if for every point we look for the closest match in the second set, we go in the wrong way.

I somewhat suspect that the problem can't be solved for the absolute minimum without checking all possible sets of pairs. But maybe there is a heuristic for finding a local minimum that would be the absolute one in most cases?

# Answer
> 1 votes
If you're looking for an algorithm to pair the points in a way that minimizes the sum of squared distances, this is an instance of the bipartite matching problem (or assignment problem). You have an edge between each point from the first set and each point from the second set, whose length is equal to the square distance between those two points. There are standard algorithms for solving the bipartite matching/assignment problem, which you could apply here.

These algorithms do not take advantage of the geometric structure here, so it is possible there might be even more efficient algorithms possible.

I recommend also learning about https://en.wikipedia.org/wiki/Correspondence\_problem and https://en.wikipedia.org/wiki/Point-set\_registration.

---
Tags: optimization, sets
---


title: Complexity of a restricted SAT problem

text:
# Question
Title: Complexity of a restricted SAT problem
I am wondering about the complexity of the following SAT related problem:

Given a CNF with $n$ clauses containing exactly $k$ literals with the following properties:

* The intersection of any pair of different clauses only contains 1 variable.
* Every variable is only contained in one intersection. So every variable appears at most in two different clauses.

For example for $k=3$ : $(x \vee y \vee z)\wedge(y \vee u \vee w)\wedge (x \vee w \vee v)$ is a valid formula.

Is checking the satisfiability of this problem still NP-complete like 3-SAT? My gut tells me that the heavy restriction on the form may made it easier to solve this problem, but I'm not sure.

# Answer
> 2 votes
Repeatedly perform the following simplification procedures:

* If a variable appears only once, we can satisfy the unique clause containing it by setting the variable accordingly. Therefore we can remove the clause.
* If a variable appears twice but with the same polarity, we can satisfy both clauses containing it by setting the variable accordingly. Therefore we can remove both clauses.
* If a variable appears twice, with opposite polarity, at the same clause, then the clause is always satisfied, and so can be removed.
* If a variable appears twice, in a clause $C \lor x$ and in a clause $D \lor \lnot x$, replace both with their resolvent $C \lor D$, which is logically equivalent to them.

Eventually no variables will be left. Either no more clauses are left, in which case the formula is satisfiable, or some empty clauses are left, in which case the formula is unsatisfiable.

---
Tags: complexity-theory, time-complexity, 3-sat, constraint-satisfaction
---


# Question
Title: Time Complexity of Exponentiation Operation as per RAM Model of Computation
Now, **$\color{blue}{\text{Exponentiation}}$** is defined as

> Exponentiation is a mathematical operation, written as $b^n$, involving two numbers, the base $b$ and the exponent or power $n$, and pronounced as "$b$ raised to the power of $n$".
> $$b^n = \underbrace{b\times b\times\cdot \cdots \times b}\_{n\text{ times}}$$

---

Now, my primary question is that **What is the Time Complexity of Exponentiation Operation as per RAM Model of Computation?**

* As per this, RAM Model assumes a computer can do Exponentiation in a single unit-cost instruction. $(\mathcal{O}(1))$
* Intuitively, it appears to be of $\mathcal{O}(n)$
* Now, **What is the time complexity of in-built `pow` functions in many programming languages? One comment claims it be of $\mathcal{O}(\log n)$. And does `**` operator in Python has the same complexity as that of `pow`?**

---

Adding to this, the $n^{th}$ Fibonacci Number can be computed in atleast four ways

* Using $F(n)=F(n-1)+F(n-2)$, Time Complexity of this is essentially $\mathcal{O}(2^n)$ \[using Master's Theorem\]
* Using Memoization, Time Complexity of this is essentially $\mathcal{O}(n)$
* Using Matrix Exponentiation, this they claim is $\mathcal{O}(\log n)$
* Solving Recurrence to get a Formula \[often called as Binet's Formula\]. $$F\_n=\frac{1}{\sqrt{5}}\bigg\[{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n}\bigg\]$$
**Now, will the Time Complexity using this formula be $\mathcal{O}(1)$?**

---

**TL;DR:** The three inter-related question are formatted using **Bold**. Since, the question is more of a convention, all relevant links are attached.

# Answer
> 1 votes
I just want to say first that I'm not an expert, but I find this question interesting. I will focus on integer exponentiation.

Like the OP says, intuitively, exponentiation of integers should cost $O(n)$, since each multiplication should add a constant number of bits to the result. For example, $8 \cdot 8$ in binary is $1000 \cdot 1000 = 1000000$ and any further multiplication by $8$ adds another 3 bits to the result.

If we use a *unit-cost* RAM model, we essentially assume that we can access any number in constant time, or $O(1)$. Many scientists believe this model is unreasonable, because in this model it's easy to create giant numbers, and solve problems like multiplication in linear time or $O(n)$. If you're curious about this, see Martin Fürer's paper "How Fast Can We Multiply Large Integers on an Actual Computer?". In this paper, however, Dr. Fürer talks about other possible models, such as the log-cost RAM. This model basically assumes it takes $O(\log{n})$ time to do an operation on an integer of size $n$. This model seems to predict real life much better than the unit-cost RAM. But remember, these are times for *multiplication*, not *exponentiation*.

---

So to make life easier, we can say multiplying a number $x$ takes time $M(x)$, where we replace the function $M(x)$ with either $O(1)$ or $O(\log{x})$, depending on the model.

Now we can focus more on exponentiation. The simplest method that is better than naïve multiplication is modular exponentiation. The idea is to break the exponent into powers of 2. The reason we do this is because it's easy to find $x^{2y}$ after we have found $x^y$. Just square $x^y$ and you get $x^{2y}$. This allows us to go through each power of 2 in the number $y$. This will take time $\Theta(\log{y})$, and if we want to include the time to multiply, we'd write $O(M(x^y)\log{y})$.

---

**EDIT 8/7/2022**

I made a mistake in the time to multiply. At each step, the time to multiply the $y^\text{th}$ Fibonacci number is $ M \left(x^{2^y} \right)$. The time for all other algebraic activities is less than this, asymptotically. It should be noted that the total time of modular exponentiation is

$$\begin{align} \tag{1} \sum\_{y=1}^n{ M(x^{2^y}) } &= M(x) + M(x^{2^1}) + M(x^{2^2}) + \dots + M(x^{2^n}) \\ \tag{2} &= \underbrace{M(x) + M(x^{2^1})}\_{\le 2 M(x^{2^1})} + M(x^{2^2}) + \dots + M(x^{2^n}) \\ \tag{3} &\le \underbrace{2 M(x^{2^1}) + M(x^{2^2})}\_{\le 2 M(x^{2^2})} + \dots + M(x^{2^n}) \\ \tag{4} &\le 2 M(x^{2^n}) \\ \end{align}$$

So, to summarize, the total time to calculate the $n^\text{th}$ Fibonacci number is proportional to the time it takes to multiply a single number the size of the $n^\text{th}$ Fibonacci number, or $O \left( M(x^{2^n}) \right)$.

---
Tags: complexity-theory, time-complexity, algorithm-analysis, runtime-analysis, computation-models
---


title: Chain rule for mutual information

text:
# Question
Title: Chain rule for mutual information
I am a bit confused in the following definition:

what does comma mean. I know I(X;Y) is the mutual information between X and Y but I am not sure how to interpret the I(X\_1,X\_2;Y)).

# Answer
> 1 votes
$I(X\_1,X\_2;Y)$ is $I(X;Y)$, where $X = (X\_1,X\_2)$.

For example, suppose that $X\_1,Y$ are two independent uniformly random bits, and $X\_2 = X\_1 \oplus Y$. Then $I(X\_1;Y) = 0$ while $I(X\_1,X\_2;Y) = 1$.

In more detail, the joint distribution of $(X\_1,X\_2,Y)$ is the uniform distribution over the vectors $(0,0,0),(0,1,1),(1,0,1),(1,1,0)$. The variables $X\_1$ and $Y$ are independent, and so $I(X\_1;Y) = 0$. In contrast, the variable $(X\_1,X\_2)$ (which ranges over $\\{0,1\\}^2$) determines $Y$, and so $H(Y|X\_1,X\_2) = 0$. Consequently, $$I(X\_1,X\_2;Y) = H(Y) - H(Y|X\_1,X\_2) = H(Y) = 1.$$

---
Tags: information-theory
---


# Question
Title: Is the problem of "DFA-TM-INCLUSION" recursively enumerable?
Consider the following problem:

> * Input: A Turing Machine M and a DFA D.
> * Question: Is $L(D) \subseteq L(M)$?

Of course, this problem is not decidable. Because it is known that judging whether a word belong to a Turing Machine is not decidable. If this problem is decidable, then we can write the word as regular expression and construct DFA from this regular expression, and then check the inclusion relationship between DFA and Turing Machine. So this is not decidable.

However, I feel difficult to prove or disprove whether it is recursively enumerable.

Any ideas are welcome.

# Answer
> 2 votes
No, $\\{\langle D,M\rangle\mid D\text{ is a DFA }\land M\text{ is a Turing Machine }\land L(D)\subseteq L(M)\\}$ is not recursively enumerable.

---

Let $Z=\\{0^{n}\mid n\ge0\\}$. Call a Turing Machine (TM) $M$ a $Z$-TM if $Z\subseteq L(M)$.

**Claim**. $\\{\langle M\rangle\mid M\text{ is a } Z\text{-TM}\\}$ is not recursively enumerable.
**Proof** (by diagonalization): Towards a contradiction suppose $\\{\langle M\rangle\mid M\text{ is a } Z\text{-TM}\\}$ is recursively enumerable. That implies there is Turing machine $A$ that enumerates all $Z$-TMs, i.e., given a natural number $n$ as input, $A$ will output (the encoding of ) a $Z$-TM, which is denoted by $C\_n$ such that the set of all $C\_n$ is the set of all $Z$-TMs.

Let us construct TM $B$ so that on input $w$, $B$ will check first whether $w$ contains only $0$s.

* If not, $B$ accepts. (The behavior of $B$ here does not matter.)
* If yes, $B$ computes $n$, the number of $0$s in $w$. Then $B$ will use $A$ to obtain $C\_n$. Then $B$ will simulate $C\_n$ on input $0^n$, until $C\_n$ accepts. Then $B$ will run one more step and accepts.

$B$ is different from each $C\_n$ for all $n$, but $Z\subseteq L(B)$. This means $A$ misses $B$ in its enumeration of all $Z$-TMs. $\quad\checkmark$

---

If we can enumerate all pairs of $D$ and $M$ such that $L(D)\subseteq L(M)$, we can further select the pairs such that $L(D)=Z$, since it is decidable whether $L(D)=Z$. Then we can enumerate $Z$-TMs. This contradicts the claim above.

# Answer
> 2 votes
TOTAL is the problem of deciding whether a given Turing machine halts on all inputs. This problem is $\Sigma\_2$-complete, and in particular, it is neither r.e. nor co-r.e.

Your problem is also $\Sigma\_2$-complete. There is a simple reduction from TOTAL to your problem. In the other direction, given a pair $(M,D)$, you can construct a new Turing machine $M'$ which on input $x$ checks whether $x \in L(D)$. If so, it runs $M$ on $x$, and otherwise, it immediately halts. The new Turing machine $M'$ is total iff $L(D) \subseteq L(M)$.

---
Tags: turing-machines, computability, finite-automata, reductions, recursively-enumerable
---


# Question
Title: When would it be optimal to use an Edge List as opposed to an Adjacency List / Matrix when representing a graph?
This seems to be my first ever question :)

Given that adjacency lists store all the necessary information with regards to the endpoints of an edge, we could even store a weight alongside that.

I don't understand why we would ever want to use an Edge List in a way that would be more useful than the above mentioned Adjacency List.

I had read on another that it may have to do with the **sorting of Edges by weight**. Is that something we can't accomplish with some other representation?

Thanks.

# Answer
> 1 votes
Any primitive operation that can be done with edge list, also can be done in adjacency list, but the main difference between them is time complexity of the primitive operations, for example, when you want find all adjacent vertices to some vertex $v$ the time complexity is $\Theta(|E|)$ but the same operation on adjacency list is $\Theta(deg(v))$ where $deg(v)$ is number of vertices that adjacent to vertex $v$ that in the worst case, if we have $n$ vertices it's equal to $\mathcal{O}(n)$, but doing that operation in edge list data structure in the worst case can be $\Theta(n^2)$ time.

On the other hand the space complexity of edge list is $\Theta(|E|)$, and adjacency list need the space $\Theta (|E|+|V|)$ and hence an edge list is more efficient in space complexity in some cases.

# Answer
> 2 votes
> Is that something we can't accomplish with some other representation?

Edge list and adjacency list represent the same thing so if you can do something with one, you can do it with the other. In the worst case, you will have to convert one to the other.

## Storage

When it comes to space, storing edge lists takes up less space than adjacency lists in most cases. For example, the adjacency list will take up less space for an undirected graph with high degree vertices.

A word about space complexity. We say that the space complexity is O(V+E) for the adjacency list and O(E) for the edge list. However, this is misleading. The edge list isn't asymptotically more space-efficient. The adjacency list's space complexity is O(V+E) because it can contain vertices with no edges which is something the edge list cannot do. To make the comparison fair, we should only consider graphs with no 0-degree vertices which can have at most 2E vertices, therefore, the space complexity of the adjacency list becomes O(E) as well.

## Speed

In my experience, adjacency list is much faster than edge list in most cases. Of course, there will always be exceptions.

The operations where edge list is superior to the adjacency list are typically the ones that directly involve computing something about the edge list itself or straight up returning one. Here is a non-complete list of operations where the edge list is better:

* Getting the list of edges
* Getting the number of edges
* ...

For some operations, edge list will be faster but not asymptotically faster.

* Getting the sum of edge weights
* Getting sorted edge weights
* ...

In some cases, operations with the edge list are so slow that it is worth converting it into an adjacency list just for that operation. For example, bfs search is O(V+E) time with adjacency list but O(V\*E) for edge list because finding the neighbors of a vertex takes considerable time. This case is a tradeoff with space. The space complexity will increase from O(V) to O(E) (or O(V+E) which is the same thing as I discussed earlier.) which is very little next to the time gains.

# Answer
> 0 votes
Krystal’s algorithm for constructing minimum spanning trees first sorts an array of edges in increasing order of weight, so that edges with the smallest weight can be considered first for selection.

---
Tags: algorithms, graphs, data-structures, graph-traversal
---


# Question
Title: What does "index up to $n^c$" mean in this question about CLRS "word size $c \lg n$"?
I don't know where else to ask this. And I don't know when or if I'll get reply at all if I comment on that answer. I was reading this answer on a text of CLRS and in the last line got confused. I understand with $c \lg n$ we can represent decimal numbers up to $n^c$. Does "index up to $n^c$" mean being able to store or represent up to $n^c$? Thanks in advance.

# Answer
RAM machines typically allow access to an array using an index, which in many programming languages is done using the syntax `A[i]`, where `A` is the array and `i` is the index. If your word size is $w$, then you can directly index this way $2^w$ words of memory (in the RAM machine, memory consists of machine words, whose size depends on the model; usually $O(\log n)$, where $n$ is the input size).
> 1 votes

# Answer
If $b$ bits of storage are allocated to an integer variable $i$ that represents an index variable in your program, then the number of different values that $i$ can take is $2^b$. For example, if $8$ bits of storage space are allocated to a variable, then the variable can take values $0,1,2,\ldots,255$. Note that $\lfloor \log 255 \rfloor + 1 = 8$, where log’s are to base $2$. In general, representing the index $n$ will take $\lfloor \log n \rfloor + 1$ bits of storage space.

Thus, if the range of indices goes from $1$ to $n^c$, then roughly $\log n^c = c \log n$ bits of storage space are needed, and conversely, if $c \log n$ bits of storage space are allocated to an index variable then the index variable can take values up to $n^c$.
> 1 votes

---
Tags: algorithms
---


title: Is $m \log^2 n$ complexity too much?

text:
# Question
Title: Is $m \log^2 n$ complexity too much?
I have been struggling for a few hours in terms of finding the right solution for the following problem:

> Suppose we have a file that contains integers where each represents a user of a service. By reading that file we want to find how many times the service was accessed and by how many different users. My code should print something like "The service was accessed 500 times by 132 different users". Options to implement this might differ, use an ADT of your choice. Try to find a fast way to do this.

My initial thought after reading the material was to use the ADT Sorted Map and then use an AVL tree to store the different users based on their respective integer as key. I could change the value to how many times they accessed, but we don't need that, so I decided to skip the effort.

My thought was that for every integer in the file I'd check if the key exists in the AVL tree and then if it does just continue, if it doesn't add a node for it with the respective key.

At the end of it I'd request for the algorithm to print the number m (counter for each iteration) and use size() of the tree to get the amount of users.

If I did the calculations correctly then that would give me a complexity of $O(m \log^2n)$, where $m$ is the total amount of accesses and $n$ is the amount of users. In class we usually work with $O(\log n)$ or $O(n\log n)$ or $O(m\log n)$ and others, but I've never come across $O(m\log^2n)$ before, so I don't really understand if it's fast, if it's time consuming, and it's causing me doubt about my choice of method.

My questions for the community are:

1. Can you give me an idea of how good or bad this type of complexity is?
2. According to how I describe it, am I right in my complexity calculations? If not what can I change?
3. Do you think my idea is bad, average or good? Do you have any suggestions on something I could think differently?

PS. I found one source that said $O(\log^2n)$ is still fast, but that $m$ changes everything. Also, this is the first time I'm properly working with algorithms and complexity and it's a new concept for me that's why I'm looking to understand them better here. Thanks for your help!

# Answer
> 1 votes
Suppose there are $m$ elements in a sequence containing $n$ distinct elements, and the distinct elements are stored in an AVL tree. Then, each of the $m$ Lookups will take $O(\log n)$ time. Each of the $n$ inserts will take $O(\log n)$ time, for a total cost of $O(m \log n + n \log n) = O(m \log n)$.

However, since this problem requires a lot of lookups (to check whether an existing element has already been seen in the sequence), hash tables would be a good data structure to use. Then, each lookup would take $O(1)$ expected time, and each insert would take $O(1)$ time. The total cost would be $O(m)$ expected time, which is blazingly fast.

---
Tags: algorithms, time-complexity, algorithm-analysis
---


title: Advantages of linked lists over arrays?

text:
# Question
Title: Advantages of linked lists over arrays?
Are there other advantages to linked lists over arrays other than constant time removals of the first element?

# Answer
> 19 votes
Linked lists can work well even if memory is fragmented. Arrays usually require a continuous piece of memory. For large piece of data finding this large continuous piece of memory might be hard.

Most of benefits of linked lists requires to remember more links than just the head. For example. If you are doing some sequential checks and deletions or insertions, you can keep this link of the last checked element. Then all of this insertions or deletions are O(1), you have all the data needed, and memory required for insert is small. In other words linked lists are good for local operations. Like text. If you would try to implement a text editor and rewrite the whole array when user adds another letter in the middle, it will be slower than with a linked list, if linked list remembers last edit points and most edits are a bit further than it. Upgrade to this idea are skip list and rope.

Another useful feature of links is atomicity of small edits. With an array you could achieve atomicity by replacing the link to the array itself, but only after making a whole new copy. But with linked list you can build another subchain, and then replace the link to it, changing the small portion of the linked list this way, keeping all the data consistent and not spending lots of memory on another copy.

# Answer
> 9 votes
This isn't really about "advantages", but appropriateness. Sometimes it's more appropriate to use an array, and sometimes to use a linked list.

If it helps, take a look at this large table of the complexity of various operations of a bunch of data structures from the C++ standard library so you can compare them. If you're not familiar with C++, `vector` is a growable array, `deque` is a double-ended queue (essentially a chunked array), and `list` is a linked list. What you can see is that the main tradeoff is:

* Dereferencing an element of an array, from a position index, is $O(1)$ operation, and linked lists don't really support that.
* Insertion and deletion of an *arbitrary* element of a linked list is $O(1)$, and $O(n)$ for an array.

# Answer
> 5 votes
If you make the elements stored in the list already contain the next/prev pointers (called an intrinsic or intrusive linked list) than the list doesn't need to do allocations and risk fragmenting memory further just to store 3-pointer sized structs or an array of pointer that needs reshuffling every time you pull out an element.

This is very handy if you expect the elements to move lists frequently and/or a possibly failing allocation means a panic. Like for example the thread descriptor object moving between various wait queues in the kernel depending on why the thread was interrupted.

With an intrinsic list which is doubly linked then if you can acquire a pointer to the object directly then you can pull the object out of the list without needing to find it in the list or array.

# Answer
> 5 votes
An important consideration missing from the other answers: It's easier and more performant to use immutable linked lists than immutable arrays, which is especially important in functional programming languages.

For example, to add an element to an array in an immutable language, you actually create a new array with the extra element added to it, which entails copying the entire array. The compiler might be able to optimize this out (it might detect that the original array is never read again, and just append in-place), but not in general.

Adding an element to an immutable linked list is easy, as long as you're willing to add to the front: Create the new head node, and link it to the old head. The old head still represents the old list, and the new head represents the new list!

This implies another benefit of linked lists: Two lists that differ only in the first few elements can share most of their memory.

# Answer
> 2 votes
A linked list is *appropriate* for many use cases *independent of performance considerations*. In addition to examples given by other answers here, consider that a given object (an instance) can be in more than one linked list (internally linked as well as externally linked) but can only be in one array (it can be pointed to by multiple arrays, but that's not the same, for many use cases).

Consider these diagrams from the book *The Design Of An Optimizing Compiler* (Wulf, Johnsson, Weinstock, Hobbs) (1973) - first is the multiply-internally-linked symbol table, second is the multiply-internally-linked "graph table" used for recognizing common subexpressions - the "threads" are multiple semantically different, semantically important traversals of the same data structure implemented by separate linked lists into the same objects each representing a symbol or a syntax tree node.

BTW, *IMO* it is a design mistake to consider performance of a data structure *before* considering appropriateness. But I can see that it frequently happens, probably because of the way CS/programming is taught, in many cases by teachers and textbooks, in which performance characteristics are prioritized over appropriateness, and in fact, appropriateness is given short shrift. See for example many industry "interview questions" which are considered properly answered by discussions of O-bounded performance, where the data structure to use is just assumed to be "obvious". Or in many many examples in textbooks, websites, and *language libraries* that have good support for *external* data structures (linked lists, arrays, dictionaries, hash tables) and never mention at all much less support *internally* linked data structures as used above. (Note that as in the diagrams above hash tables and trees can be represented using *internal* links if that is appropriate - it's just never done anymore not because it is wrong by mainly because there's no language or library support.)

# Answer
> 2 votes
Donald Knuth’s “dancing links” algorithm is a well-known one that uses the constant-time insertion and deletion of items in a linked list for performance. You can hear him discuss it, twenty-four years later, here.

An important optimization for linked lists, in a lazy functional language with immutable linked lists, is to treat them just as a sequence and avoid ever actually creating the list itself, compiling to something much like `yield return` in C#.

# Answer
> 1 votes
I don't have an exhaustive list (pun intended), but off the top of my head:

* You can also perform constant time operation at the tail (*for a circular doubly linked list*).
* You can implement the move-to-front heuristic (MTF) efficiently.
* No need to perform costly expansion/contraction (*there is a way to prevent this in an array but requires extra memory*)

# Answer
> 0 votes
If you mean fixed arrays (whose lengths are fixed in advance) versus linked lists, then linked lists have the advantage that they use up memory only on an as needed basis - a new cell is allocated each time a new insert operation is done. Whereas, arrays would require you to specify the maximum length of the list in advance, and any unused space is wasted, and you can’t insert more elements than this maximum length even if you encounter more data. So, if you don’t know in advance how many elements will be inserted into the list, a linked list would be a better data structure to use.

---
Tags: linked-lists
---


# Question
Title: Formal Proof on why Greedy isn't working on one Particular Problem
## Problem

You are given two integer arrays `nums` and `multipliers` of size `n` and `m` respectively, where `n≥m`. The arrays are **1-indexed.**

You begin with a score of `0`. You want to perform **exactly** `m` operations. On the `iᵗʰ` operation **(1-indexed)**, you will:

* Choose one integer `x` from **either the start or the end** of the array `nums`.
* Add `multipliers[i] * x` to your score.
* Remove `x` from the array `nums`.

Return the **maximum** score after performing `m` operations.

---

## Example 1

> **Input**: `nums = [1,2,3]`, `multipliers = [3,2,1]`
> **Output**: `14`
>
> **Explanation**: An optimal solution is as follows:
>
> * Choose from the end, \[1,2,**3**\], adding `3*3 = 9` to the score.
> * Choose from the end, \[1,**2**\], adding `2*2 = 4` to the score.
> * Choose from the end, \[**1**\], adding `1*1 = 1` to the score.
>
> The total score is `9+4+1 = 14`

## Example 2

> **Input**: `nums = [-5,-3,-3,-2,7,1]`, `multipliers = [-10,-5,3,4,6]`
> **Output**: `102`
>
> **Explanation**: An optimal solution is as follows:
>
> * Choose from the start, \[**-5**,-3,-3,-2,7,1\], adding `-5 * -10 = 50` to the score.
> * Choose from the start, \[**-3**,-3,-2,7,1\], adding `-3 * -5 = 15` to the score.
> * Choose from the start, \[**-3**,-2,7,1\], adding `-3 * 3 = -9` to the score.
> * Choose from the end , \[-2,7,**1**\], adding `1 * 4 = 4` to the score.
> * Choose from the end , \[-2,**7**\], adding `7 * 6 = 42` to the score.
>
> The total score is `50 + 15 - 9 + 4 + 42 = 102`.

---

## My Approach

I tried to solve it using **Dynamic Programming** and formed following Bellman Equation.

> $X\[i\]\[j\]$ stores the **maximum possible score** after we have done $i$ total operations and used $j$ numbers from the *left/start* side. The index of the *rightmost* element can be calculated from $n-1-(i-j)$. For purpose of formulation `multipliers` has been renamed to $M$ while `nums` to $N$ $$ X\[i\]\[j\] = \begin{cases} \text{max}\bigg((M\[i\]\cdot N\[j\]) + X\[i+1\]\[j+1\],\\\quad\quad\quad(M\[i\]\cdot N\[n-1-(i-j)\]) + X\[i+1\]\[j\]\bigg), & \text{if $i \neq m$ } \\\\[2ex\] 0, & \text{if $i=m$} \end{cases} $$

We essentially choose the **maximum** on choosing from *left* or *right*. If we choose left, next operation will occur at $\[i+1\]\[j+1\]$, else next operation will occur at $\[i+1\]\[j\]$.

On writing code for the same, the approach worked fine.

---

## Question

Why Greedy Approach is failing here? On Going Greedy in **Example 2**,

> * \[-5,-3,-3,-2,7,1\], from `50 vs -10`, choose `50`, hence `left`
> * \[-3,-3,-2,7,1\], from `15 vs -5`, choose `15`, hence `left`
> * \[-3,-2,7,1\], from `-9 vs 3`, choose `3`, hence `right`
> * \[-3,-2,7\], from `-12 vs 28`, choose `28`, hence `right`
> * \[-3,-2\], from `-18 vs -12`, choose `-12`, hence `right`
>
> The total score is `50 + 15 + 3 + 28 - 12 = 84`, which **isn't** optimal.

Is there a **formal proof** using eXchange Argument \[*Although the link suggests that To show that an algorithm A does not solve a problem it is sufficient to exhibit one input on which A does not produce an acceptable output*\] **or** Greedy Stays Ahead Approach$\color{red}{?}$

Any hint would be of great help. Thanks!

---

# Answer
> 3 votes
To prove that the greedy algorithm is not optimal, it suffices to give one counterexample, i.e. one problem instance $nums$ and $mult$ such that it is possible to obtain a value that is larger than the output computed by the greedy algorithm. You have already shown this. In fact, you showed more than that - you computed the optimal value for this problem instance, which is not necessary - it would have sufficed to show that the greedy algorithm’s output is $84$ and that there exists a sequence of decisions that gives a value larger than $84$, such as $90$, say. It’s not necessary to compute the optimal value $102$ to prove suboptimality of the greedy algorithm.

If you want to understand why the greedy algorithm is not optimal, it helps to find the smallest possible counterexamples. Suppose $nums=\[5,4\]$ and $mult=\[1,2\]$. Then, the greedy algorithm would choose to multiply the $1$ by a $5$ rather than $4$, giving an output of $1 \cdot 5+2 \cdot 4=13$. But the second multiplier $2$ is larger than the first multiplier and so should have been multiplied with the larger number $5$ to get the maximum output (which is $1 \cdot 4+2 \cdot5=14$). We can see why being greedy is suboptimal in general.

---
Tags: algorithms, dynamic-programming, greedy-algorithms, correctness-proof
---


title: Why can't $QBF$ be reduced to $SAT$

text:
# Question
Title: Why can't $QBF$ be reduced to $SAT$
Let $QBF\_k$ be the problem of determining the satisfiability of a formula of the form $Φ = Q\_1x\_1Q\_2x\_2 . . . Q\_kx\_k φ(x\_1, . . . , x\_n)$. where each $Q\_i$ is one of the quantifiers $∀$ or $∃$. So, $Φ$ contains $k$ quantified variables $x\_1, . . . , x\_k$ and free variables $x\_{k+1}, . . . , x\_n$. The problem $QBF\_k$ is to determine where $Φ$ evaluates to true for some value of the free variables $x\_{k+1}, . . . , x\_n$. φ is any propositional formula built up from the usual connectives and, or, not.

I know that $QBFk ≤\_p QBF\_{k−1}$

(Every $\exists$ quantifier can be made into 2 formulas connected with an or, while every $\forall$ quantifier can be made into a formula connected by an and)

What is wrong with the following argument: “Since $QBF\_k ≤\_p QBF\_{k−1}$ for any $k$, we can compose these reductions repeatedly to prove $QBF\_k ≤\_p SAT$, where $SAT$ is the problem of checking whether a standard quantifier-free propositional formula is satisfiable. Hence $QBF≤\_p SAT$, since any $QBF$ formula has some fixed number of quantified variables.” ?

While this definition of $SAT$ is a bit different from the original satisfiability problem (Which requires a CNF, and this may not necessarily be a CNF) I see nothing wrong with the argument? Where am I going wrong?

# Answer
The problem is that the resulting formula does not have a length that is polynomial in the original formula since you are doubling the size of the formula every time you remove a quantifier.

Even though $QBF\_k \le QBF\_{k-1}$, you cannot compose the reductions the way you are doing and still get a polynomial reduction, because you are composing a non-constant number of them.
> 6 votes

---
Tags: reductions, satisfiability
---


# Question
Title: Find an upper bound for T(n) = T(n/2) + T(n/2 + 1) using the Substitution Method base case fails
Given the algorithm

```
MYSTERY-ALG(n >= 0)
1 if n < 3 then
2     return 1
3 else
4     return MYSTERY-ALG(n/2) + MYSTERY-ALG((n/2) + 1)

```

I defined a recurrence $ T(n) = \begin{cases} 1 & 0 \leq n \< 3 \\ T(\frac{n}{2}) + T(\frac{n}{2} + 1) & \text{otherwise} \end{cases} $ which I guessed to be $O(n)$; I've managed to find suitable $c$ and $n\_0$, even an extra variable $b$, from which my bound holds *but* it fails certain base cases.

Here's my attempt:

Prove $T(n) = T(\frac{n}{2}) + T(\frac{n}{2} + 1) = O(n)$, where $T(\[0, 3)) = 1$.

*Try 1*

Assume $0 \leq ck$ for $k \< n$, $c \> 0$, must show $T(n) \leq cn$, $\forall n \geq n\_0$.

$T(n) = T(\frac{n}{2}) + T(\frac{n}{2} + 1)$, since $\frac{n}{2} \< n$ and $\frac{n}{2} + 1 \< n$ for $n \> 2 \implies n\_0 \> 2 \implies T(\frac{n}{2}) \leq \frac{cn}{2}$ and $T(\frac{n}{2} + 1) \leq \frac{cn}{2} + c \implies$

$T(n) \leq \frac{cn}{2} + \frac{cn}{2} + c = cn + c$

$\overset{?}{\leq} cn$ is not possible since $c \> 0$.

*Try 2*

Assume $0 \leq ck - b$ for $k \< n$, $c \> 0$, $b \> 0$ must show $T(n) \leq cn - b$, $\forall n \geq n\_0$.

$T(n) = T(\frac{n}{2}) + T(\frac{n}{2} + 1)$

$\leq \frac{cn}{2} - b + \frac{cn}{2} + c - b = cn - b - b + c = cn - b - (b - c)$

$\leq cn - b$, as long as $b - c \geq 0$

$\implies b \geq c$. From here, it's not clear how to find $b$ and $c$. Strangely, this expression is also independent of $n$.

If we take $c = b = 1$, $n\_0 = 3$ then the $T(3) = T(1.5) + T(2.5) = 2 \leq 3 - 1 = 2$ bound holds, but the base case, for example, $T(1) = 1 \leq 1 - 1$ fails.

Is there any way of making this work?

# Answer
The problem in the question is a good example for two related principles.

* Thanks to the substitution method in your try 2, you have found $c=b=1$ will enable the induction step for $T(n)\le cn-b$ to work. However, *if* the base case is $T(1)$, the inequality does not hold.

Instead of sticking to proving "$T(n)\le n-1$ for $n\ge0$", you can try proving "$T(n)\le n-1$ for $n\ge 3$" instead. Now the base case is "$T(n)\le n-1$ for $3\le n\lt 6$", which can be proved easily.

When we want to find some proposition that can be proven by mathematical induction, we can change the domain of the proposition so that the base case in a mathematical induction will be able to succeed. This useful freedom of choice can enable us to make progress. (We could also, of course, change the proposition so that the base case can succeed.)
* If we can prove $T(n)\le n-1$ for $n\ge n\_0$ from some $n\_0$, it means $T(n)\le n$ for $n\ge n\_0$, i.e., $T(n)=O(n)$. It does not matter whether $n\_0=1$, or $n\_0=3$, or $n\_0=2022$.

The big-$O$ notation is about asymptotic behavior. The behavior when $n$ is small can be ignored.

***Two easy exercises***
Exercise 1: Show by mathematical induction that $T(n)\le n-1$ for $n\ge3$, considering the base case as when $3\le n\lt 6$.

Exercise 2: Show by mathematical induction that $T(n)\begin{cases}=1,\quad\quad\text{ if }0\le n\lt 3\\\le n-1,\text{ otherwise} \end{cases}$, considering the base case as when $0\le n\lt 3$. This is another way to change the base case.
> 4 votes

# Answer
Your second idea is good, there is no need to start at $n = 1$:

You already proved that for $n\geqslant 3$, $T(n) \leqslant n - 1$.

You can now say that since $n-1 \leqslant n$ and since $T(1)\leqslant 1$ and $T(2)\leqslant 2$, then for all $n$, $T(n) \leqslant n$.

(You can consider $T(n) \leqslant n +1$ if you want to include $n = 0$).
> 3 votes

---
Tags: complexity-theory, asymptotics, runtime-analysis, recurrence-relation
---


title: Proof that 2-sat is P-hard?

text:
# Question
Title: Proof that 2-sat is P-hard?
i figured out this is what i want to know: in Cook's theorem it is shown that SAT is NP-hard. he shows it by showing that sat is at least as difficult like the word problem for nondet. Polynomial Time Machines. I want to know how i would proof that 2-sat is P-hard while showing that 2-sat is at least as difficult like the word problem for DET. Polynomial time machines

old question: i'm doing university work about the 2-sat problem and it is asked why 2-sat is p-hard. We discussed that 3-sat is np-hard and proved this by reduction from cnf-sat to 3cnf-sat. for my work the following is asked: "...what you can do is to look at the proof of NP-hardness for CNF-SAT(and ultimately 3-SAT) and see if there might not be 2-SAT formulas come out in the reduction if you use the word problem translated for a deterministic Turing machine. When that is so (or you can easily convert the resulting formulas into 2-CNF), then it has been shown that 2-SAT is at least as difficult like the word problem for det. Polynomial Time Machines. So is then complete for class P."

I understand the proof for 3-sat to be np-hard but i don't get the idea that is described for 2-sat to be p-hard. Could anyone help me out understanding the way of thinking to proof that 2-sat is p-hard? also excuse my bad english

any help is appreciated, thanks in advance

# Answer
2SAT is NL-complete (with respect to logspace reductions). Wikipedia outlines a proof:

1. We start by describing Krom's algorithm for 2SAT, using the *implication graph*. In this directed graph, the vertices are all literals, and each clause $\ell\_1 \lor \ell\_2$ corresponds to a pair of edges $\bar{\ell}\_1 \to \ell\_2$ and $\bar{\ell}\_2 \to \ell\_1$ (possibly self-loops, if $\ell\_1 = \ell\_2$). If there is a directed path from $x$ to $\bar{x}$ and from $\bar{x}$ to $x$ for some variable $x$, then the formula is unsatisfiable. It turns out that if there is no such directed path, then the formula is satisfiable. Roughly speaking, for every variable $x$, either there is no path from $x$ to $\bar{x}$ or there is no path from $\bar{x}$ to $x$ (or both), and we set the value of $x$ accordingly. This process should be done iteratively.
2. Implement this algorithm in coNL. That is, given an unsatisfiable 2CNF, we should give a logspace algorithm that verifies that using advice. The advice consists of two directed paths in the implication graph, from some variable $x$ to its negation $\bar{x}$ and from $\bar{x}$ to $x$. This advice can be verified in logarithmic space.
3. The Immerman–Slezepcsényi theorem states that NL=coNL. Consequently, 2SAT is in NL.
4. To show that 2SAT is NL-hard, we reduce from directed reachability, a well-known NL-complete problem. Directed reachability is the following problem: given a directed graph $G$ and two vertices $x,y$, determine whether there is a directed path from $x$ to $y$ (the undirected version is L-complete due to Reingold's theorem). Given an instance $(G,x,y)$ of directed reachability, we construct an instance of 2SAT as follows. The variables are the vertices of $G$. For each edge $(u,v)$, there is a clause $\lnot u \lor v$. In addition, there are clauses $x$ and $\lnot y$. This instance is unsatisfiable iff $y$ is reachable from $x$. (This is actually a reduction from directed reachability to co2SAT, but since NL=coNL, this is OK.)

If an NL-complete problem is P-hard, then P collapses to NL, which is considered unlikely. Since 2SAT is NL-complete, this suggests that it is not P-hard.
> 4 votes

---
Tags: np-hard, 3-sat, 2-sat
---


# Question
Title: reducing the word problem for dtm to sat / cnf-sat / 2-sat
word problem: given a language L through a deterministic turing machine, is the word w in the language L?

the problem should be decidable, since if there is a deterministic turing machine i can simply turn that into a dfa take the word w go through the dfa step by step and see if i end in an accepting state?

I now want to know if there is a way to reduce the word problem to sat / cnf-sat or 2-sat. can't think of a way that i could do that so i wanted to ask on here. my professor said i should take a look at the proof for cnf-sat / 3-sat in NP and then see what happens when i translate the word problem for dtm in the same way so i would guess i should check what happens when i search for a way where i try to translate the word problem into a sat/cnfsat/2-sat problem. thanks in advance

# Answer
> 1 votes
The answer is no because the problem seems undecidable.

You can reduce the halting problem to it.

---
Tags: reductions, satisfiability, 2-sat
---