# Question
Title: Can we solve $\mathrm{MFVS} \leq 1$ in linear (or subquadratic) time?
$\mathrm{MFVS} \leq 1$ is a concise way of writing the following decision problem:

> Let $G = (V, E)$ be a directed graph. Is there a $v \in V$ such that every cycle in $G$ passes through $v$?

(More generally, $\mathrm{MFVS}$ stands for *minimal feedback vertex set*, the problem of finding the smallest set of vertices such that every cycle passes through at least one of them. In general, MFVS is NP-complete.)

There is a trivial $\mathcal O(VE)$ algorithm: for every vertex $v$, use a $\mathcal O(E)$ cycle-finding algorithm, like a topological sort, to check if there is a cycle in $G$ that does not pass through $v$. I am wondering if we can do better: is it possible to solve this problem, either deterministically or probabilistically, in $\mathcal O(E^{2 - \epsilon})$, or even (ideally) in $\mathcal O(E)$?

There is a simple algorithm that seems promising: start with a set of candidate vertices $X = V$, and then alternate between:

1. picking a $v \in X$ and testing if it forms a feedback vertex set by itself; if not, remove it from $X$;
2. finding a random cycle in $G$, and removing all vertices from $X$ that are not on that cycle.

Unfortunately, it is possible for there to be a large set of vertices so that the vast majority of cycles contain the vast majority of those vertices, even if the answer to the decision problem is negative. So there is a class of graphs on which the above turns into a quadratic algorithm (with high probability) after all.

# Answer
A vertex $v$ such that $G-v$ is acyclic is called a feedback vertex, so your problem is equivalent to deciding whether there exists at least one feedback vertex in $G$.

The paper "A linear-time algorithm for finding all feedback vertices" by Garey and Tarjan describes an algorithm that can report the set of all feedback vertices of a directed graph in linear time.
> 5 votes

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


# Question
Title: Strategy of gradually integrating more complex distributed system into start up company
My 1st question ever on stackexchange, please be nice to me if it's too naive :)

I read the map reduce paper and i discover distributed system is expensive.

As an example in the paper, roughly speaking, approx. 1700 machines with 30000 mb/s throughput compares to non distributed single machine with 500mb/s ssd, it's 60 times through put increased with 1700 times machines! i understand achieving perfect linear scalability is impractical, since there's inherited overheads on **network latency** (prominent bottle neck in map reduce's case), data shuffling between machines, and synchronization issues.

But at the awe of this numbers gives me the scale feeling, I am wondering:

1. how do we decide for example : my business is doing well enough (ex: online gambling soccer game platform) to adopt this fancy distributed system,
2. what are some experiences of gradually integrating distributed systems in a startup company, bring in distributed system step by step, for different period of developing the business, we should design different distributed system that cost effective to that business phase, where can i find this material to read if there's ever such material? or this knowledge is mostly just in experienced people's head ?

# Answer
> 1 votes
The main reason to use a distributed system is because we have to. If you can meet the business need using a single server, typically that is more cost-effective. Distributed systems bring their own headaches and pain, so generally, we only enter into that if we have to. So the typical reason to use a distributed system is because we have no choice: that's the only way to build the service (or the only way to do so within a reasonable cost).

---

I have no experience with your second question. I'm not sure whether that question is the best fit for the Stack Exchange format. Generally, on this site we are looking for posts that contain a single, focused technical question. We ask folks to avoid asking multiple questions in one post (they can be asked separately), to avoid questions that call for opinions (see https://cs.stackexchange.com/help/dont-ask), and on this site, we focus on the technical aspects of computer science rather than the business aspects of software engineering.

---
Tags: distributed-systems
---


# Question
Title: Proving that the intersection of two languages is regular or not?
> Let $B$ and $C$ be two languages on $A = \\{a,b\\}$:
>
> $B = \\{ w \mid w \text{ has the same number of }a\text{ and }b\text{ symbols}\\}$
> $C = \\{ a^n b^m \mid n,m \ge 0\\}$
>
> Describe $B \cap C$ and determine whether $B$ is regular or not using *only* the closure property of regular languages.

I reasoned like this:

$B$ is not regular because a language is regular if there exists a DFA $M$ such that $L = L(M)$. But we know that DFAs cannot count so $B$ is not a regular language.

$$B \cap C = \\{a^n b^m \mid n=m \land n,m \ge 0\\}$$

which we know is not regular by the *pumping lemma*.

> Is there a different solution using only closure properties to prove that $B$ is not regular?

# Answer
> 1 votes
You are part of the way there.

You are expected to use the closure properties to show whether $B \cap C$ is regular depending on whether $B$ and $C$ are regular. You're not doing that. Closure properties are properties such as:

1. If $A$ is regular, then $\bar A$ (= $\Sigma^\* - A$) is regular.
2. If $A$ and $B$ are regular, then $A \cup B$ and $A \cap B$ are regular.

Your proof will depend on whether $C$ is regular, so you will need to determine that, too.

---
Tags: regular-languages, finite-automata
---


# Question
Title: What is the complexity of finding the predecessor of a node in a doubly linked list?
This is a question from Cormen 3rd edition(exercise 10.1). I am of the opinion that the complexity should be O(1), as we just have to look into the next pointer of the current node.

But the answers from the web suggest that it should be O(n). Where am I getting it wrong?

Can someone please help me out???

Thanks in advance!

# Answer
> 2 votes
Both answers look wrong. Time is indeed $O(1)$ because you can look into `prev` (not `next`) pointer of the node. The answers you found on the web are probably about single-linked lists.

# Answer
> 0 votes
I guess if you include the time it takes you to find a node X and its predecessor, then finding the node would be $O(n)$ and going back once will be $O(1)$, but this sounds unnecessary since we can directly find the predecessor.

# Answer
> 0 votes
I think I can clear this up:

Because you now have the predecessor prev, removal at the tail becomes faster because the time complexity is now 0(1). The logic behind it? The predecessor can now be renamed as the tail, which only needs to be done once for an individual removal. However, that does not mean removal in between the tail and the head is now 0(1). The time complexity for the algorithm for the middle part of the DLL is still 0(n) as you would still need to search for the item to remove.

Do correct me if any of this information is wrong. :)

# Answer
> 0 votes
Given a pointer to a node in a double linked list, getting a pointer to the previous node is constant time. That’s the whole purpose of double linked lists.

“Answers on the web” claiming O(n) will be answering some other question. Like the same question for a single linked list. Or finding a node.

---
Tags: algorithms, linked-lists
---


# Question
Title: If all problems in NP are polynomially reducible to SAT (Cook & Levin) can one also assume that all to SAT polynomially reducible problems are in NP?
From Cook & Levin's theorem we know that all Problems in NP are polynomially reducible to SAT: $ \forall\_{L\in NP}: L \leq\_{p}SAT$.

Is the opposite also true? That is if we know that a language L is reducible to SAT in polynomial time, can it be also stated that it must be in NP?

$L \leq\_{p}SAT \Rightarrow L \in NP$

I am struggling to understand if this holds true.

# Answer
> 1 votes
Yes, this is true. More generally, if $A \le\_p B$ and $B \in \mathbf{NP}$, then $A \in \mathbf{NP}$. (Most intro theory textbooks include a proof of this result.)

In fact, one way of defining what the class $\mathbf{NP}$ is is as “the class of all decision problems that polynomial-time reduce to $SAT$.”

# Answer
> 1 votes
Yes, it is true, and to get a feeling for why it is so, we can appreciate the fact that a reduction is just an algorithm (in this case, a poly-time algorithm) that transforms instances of one problem into instances of another.

So, given a string $x$, one way to check if $x \in L$ is to run the reduction to SAT (in polynomial time) on $x$ and check if the resulting formula is satisfiable (in non-deterministic polynomial time). This is clearly a non-deterministic poly-time algorithm to check membership in $L$; in other words, $L$ is in $NP$.

---
Tags: complexity-theory, computability
---


title: Max-min one-to-two matching

text:
# Question
Title: Max-min one-to-two matching
There are some $n$ people and $2 n$ items. Each person assigns a positive value to each item. The items should be allocated to the people, giving exactly 2 items to each person. The value of a person is the sum of values of the two allocated items. The goal is to maximize the minimum value of a person. For example, suppose $n=2$ and the values are:

* Alice: w=1, x=2, y=3, z=4
* Bob: w=5, x=6, y=7, z=8

Then the max-min partition is giving y,z to Alice and w,x to Bob, as the minimum value is 3+4=7, and this is the largest possible minimum value.

If there is only 1 item per person, then the problem can be solved in polynomial time by reduction to maximum matching.

In contrast, if there are 3 items per person, then the problem is NP-hard, by reduction from the 3-partition problem.

The case of 2 items per person is in between, so I do not know: is it NP-hard? Or is it solvable in polynomial time?

# Answer
The case of 2 items per person is also NP-hard, also by reduction from the 3-partition problem.

Consider the case where each person $i \in \[n\]$ has a "value score" $v\_i$, each item $j$ has a "value score" $w\_j \in \[2n\]$, and the value person $i$ has for items $j$ is $v\_i/2 + w\_j$. In particular, the total value person $i$ has for the pair of items $(j, k)$ is $v\_i + w\_j + w\_k$, and in any assignment of pairs of items to people, the total value among all people will be exactly $V = \sum\_{i \in \[n\]} v\_i + \sum\_{j \in \[2n\]} w\_j$.

Now, the maximal possible minimal value is at most $V/n$. It will equal $V/n$ iff the 3-partition problem with the set of weights $\\{v\_i\\} \cup \\{w\_j\\}$ is solvable (technically, this is a slight variant of the 3-partition problem where you must choose one element from the first set and two elements from the second set, but you can easily reduce this to the original 3-partition problem by simply adding a large constant $C$ to all $v\_i$). Since you can embed any 3-partition problem in this way, the original problem is also NP-hard.
> 3 votes

---
Tags: time-complexity, matching
---


# Question
Title: How to find the learned clause from a UIP cut
I would guess that this question is going to make some people wonder how I haven't already found a solution looking through papers -- but I do not see a clear algorithm.

In implementing CDCL, I read this site, which gives the following definition:

> Consider an implication graph $(V,E)$ obtained from a trail that falsifies at least one clause. A conflict cut of the graph is a partition $W=(A,B)$ of its vertex set such that
>
> * all the decision literal vertices belong to the set $A$, and
> * the conflict vertex $\bot$ belongs to the set $B$.
>
> Let $R = \\{l \in A \mid l' \in B : (l, l') \in E \\}$ be the reason set of the conflict cut consisting of the $A$ vertices having an edge to the $B$ set.
>
> The learned clause corresponding to the cut is ${\huge \lor}\_{l \in R} \lnot l$.

I have a trail -- a list of assigned literals (such as -5, or 4, etc.), each one annotated with whether it's a decision literal, or pointing to the clause it was implied by in unit propagation. Each one is also annotated with a decision level, effectively giving me an implication graph.

I am unsure of a generalised algorithm to get this reason set $R$ using this trail. I have a function that gives me a UIP literal in the trail, but I don't know if this helps here.

Say we decided on the UIP cut below:

What kind of algorithm or process would lead me to get $\lnot x\_2, x\_5, \lnot x\_6$ in my reason set, given I start from a conflict clause?

# Answer
First, some observations:

* Setting all literals in a reason set to true leads to a conflict through unit propagation.
* One can replace a non-decision literal from a reason set with its in-neighbors in the implication graph without disturbing the above property.
* The falsified clause $l\_1 \lor \ldots \lor l\_n$ that lead to the conflict immediately gives you a reason set $\\{ \lnot l\_1, \ldots, \lnot l\_n \\}$. Similarly, any reason set $R$ has a corresponding learned clause $\bigvee\_{l \in R} \lnot l$.

Clause learning consists of forming a reason set that contains exactly one literal from the current decision level, because backtracking before the current decision level then makes its corresponding learned clause a unit clause, which can immediately be used for unit propagation. The one remaining literal from the current decision level is known as a unique implication point (UIP), because from the current decision level it is solely responsible for the conflict.

All one needs to do now is to take the initial reason set and repeatedly replace one of the contained non-decision literals with its in-neighbors in the implication graph. This process is guaranteed to yield a desired reason set at some point because doing all possible replacements would result in a reason set containing only decision literals, which has the desired property.

Replacing literals at random is not particularly useful, though, because you might end up replacing a UIP without having detected it due other literals that are implied by this UIP still being in the reason set. Therefore, in order to not miss any UIPs, literals should be replaced in reverse order that they appear in the trail.

All UIPs will be detected in this procedure, though modern SAT solvers tend to stop once the first UIP (i.e. appearing the most recently in the trail) is found and use its corresponding learned clause for backtracking. The simple reason for this is that you can backtrack at most up to the decision level of the second most recently assigned literal in the reason set, since before that point the learned clause is no longer unit, and the first UIP minimizes this level.

To implement this, start out with the reason corresponding to the falsified clause, and iterate the trail in reverse to ensure that literals are processed in the correct order. Process each literal that you come across that is in the reason set by removing it from the reason set and inserting its in-neighbors in the implication graph. Keeping track of how many literals in the current reason set are from the current decision level lets you efficiently detect whether the current literal is a UIP.

Finally, it's worth noting that these replacement operations are nothing more than resolution using the clauses in the formula. In your example, the falsified clause $\neg x\_{11} \lor x\_{12}$ corresponds to the reason set $\\{x\_{11}, \neg x\_{12}\\}$ and replacing $\neg x\_{12}$ with $x\_{10}$ boils down to obtaining $\neg x\_{10} \lor \neg x\_{11}$ by resolving $\neg x\_{11} \lor x\_{12}$ (the learned clause associated with the current reason set) with $\neg x\_{10} \lor \neg x\_{12}$ ($x\_{12}$'s antecedent).
> 1 votes

---
Tags: satisfiability, dag, sat-solvers
---


# Question
Title: Transform OTM for Problem π to DTM ∈ DSPACE(n)
Given an Oracle Turing machine ($OTM$) that solves Problem π in max. 2n space, so $O(n)$ space and $O(n^2)$ time. Is there a DTM that can solve $π$ in $O(n)$ space if time doesn't matter? (The length of an instance $I$ of $π$ is n)

I would say the answer is yes. Construction: We already have a DTM M', which can verify a suggested solution given by the Oracle module for $I$ in $O(n)$ space. So basically, we just need to feed M' all possible suggestions for a solution to an Instance I deterministically.

How should I go on to formally prove this?

# Answer
It depends on the oracle. If $\pi$ is solved by the OTM using an oracle for a non-computable problem (non-decidable language), then there might not be a DTM that can solve $\pi$ without an oracle. There is no guarantee that you can verify the response from the oracle.
> 1 votes

---
Tags: turing-machines, decision-problem, space-complexity, oracle-machines, proof-assistants
---


# Question
Title: How far out can one determine a program is halting?
Suppose we have a finite set of programs, say, something like every Turing machine with 2 states and 7 symbols. After running all of them for a very long time, we've narrowed it down to a small subset thereof. Of those remaining, let's suppose that at least one will run forever and at least one will eventually halt, and that they fall into that category where it is impossible to tell which without running them for arbitrarily many more steps.

As I understand it, if we're determined enough and ignore physical considerations of time and memory, we'll theoretically reach the halting points for all those which are going to halt, although we'll never know that for sure. But before we reach that point, e.g., one step before the longest-running program halts, it will be obvious that that program is about to halt; we'll be able to look at its current symbol, state, and transform table, and it will be clear what's next.

Arguably, that's effectively computing that final step. But in reality, I have a very hard time imagining a scenario in which it isn't obvious that it's winding down 2, 3, or many steps earlier. In particular, if it's one of those recursion-based algorithms typical of BB-champions, or something like a Collatz sequence, various indicators that had been growing and growing for much of its run will suddenly be shrinking, or otherwise changing behavior.

There must be a limit to how far out such behavior can be detectable, or the halting problem wouldn't exist. On the other hand, it seems likely to me that there's probably also an upper bound on how obfuscated its behavior can be, or more concretely, how many steps out from a halt we could theoretically determine it will halt, without needing to directly compute all the remaining steps.

My question is whether this seems correct, and if so, whether anybody's figured out results along these lines already.

# Answer
What you are describing is indistinguishable from:

1. making a (free) copy of the Turing machine (in its current state)
2. running it for $n$ steps
3. seeing if it halted.

I fail to see how this gives you any new capabilities. An analogy to your logic would be: "I can determine, what's gonna happen 10 minutes into the future, if I just wait 10 minutes.".

So to answer your question in the header: You can determine, if your Turing machine is halting $n$ steps ahead, by running $n$ computations ahead on a copy of it.

Predicting the halting problem is only "obvious" for obvious cases, but can be incomprehensibly hard in other cases (see this answer).
> 4 votes

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


# Question
Title: If a problem A in NP is reducible in polyomial time to a problem B, can one say that B must also be in NP?
In other words:

If $A \leq\_{p} B$ and $A \in NP \Rightarrow B \in NP$

From my deduction this is has to be false. We know that if $A$ is NP Complete $\Rightarrow A$ NP-Hard and $A \in NP$, then $B$ is NP-Hard but we can't say for sure that $B \in NP$.

I struggle to understand why though.

# Answer
> 3 votes
Just to give you some kind of image you can use to build your intuition:

Think of the problems and the complexity classes, as boxes and shipping containers of different shapes and sizes. Translate $A \leq\_p B$ to "box $A$ fits into box $B$", and translate $A \in \mathrm{NP}$ to "box $A$ fits into shipping container $\mathrm{NP}$".

If you know that

* box $A$ fits into box $B$, and that
* box $A$ fits into shipping container $\mathrm{NP}$,

can you conclude that box $B$ fits into shipping container $\mathrm{NP}$? You can't, right? Box $B$ might be too big or weirdly shaped to fit in there.

# Answer
> 1 votes
One rough intuition that can help you is: if $A \leq\_p B$, then $A$ is "simpler than or equal to" $B$.

The fact that there exists a (polynomial) reduction $A \mapsto B$ tells you that $A$ is either the same problem as $B$ or a special case of it. In this sense, $A \leq\_p B$ does not tell you anything about $B$ in general.

In a case such as $SAT \leq B$, however, you know that $SAT$ is $\mathcal {NP}$-Hard, which means (using the intuition above) that every problem in $\mathcal{NP}$ is "simpler" than $SAT$. By the transitive property of $\leq$, it is immediate that every $\mathcal {NP}$ problem is also "simpler" than $B$, which means that $B$ is $\mathcal{NP}$-Hard as well.

If, additionally, we knew that $B$ is in $\mathcal{NP}$, we could conclude that it is $\mathcal{NP}$-complete.

# Answer
> 1 votes
Any $B$ such that $B$ is $\text{NP}$-hard but not $\text{NP}$-complete suffices as a counterexample. By definition, any $A\in\text{NP}$ can be reduced to such a $B$ in polynomial time.

One choice for $B$ would be the Halting-Problem $H$. Clearly $H\not\in\text{NP}$, though $H$ is $\text{NP}$-hard.

# Answer
> 1 votes
If you can reduce A in polynomial time to B then B might be much more difficult than A, including being much harder. “Polynomial reduction” means if you can solve the B instance then you get a solution for the A instance, so the harder B is, the easier it will be to reduce A to B.

It may be possible that the instances of B that you create by reducing instances of A are all in NP, but that might not be helpful.

---
Tags: complexity-theory, computability
---


# Question
Title: strip packing problem with fixed x-coordinate
Similar to the classic 2D strip packing problem, we want to put N blocks into a 2d strip and minimize the height of the strip. Each block has to be put at the **fixed x-coordinate**. **The width and height of all blocks are integer**.

Below is an example of 4 blocks:

you can only move every block **up and down** to reduce the overrall height. And a possible solution can be:

This problem originated from a memory allocation problem. For a computer, there are N known processes. Their start time and memory usage are different. We need to allocate memory properly to minimize the **peak** memory usage.

Does anyone have any clue to solve this problem?

# Answer
> 1 votes
I think this is the same as the register allocation problem, so I would guess that you might be able to use the same techniques.

# Answer
> 0 votes
This is equivalent to the problem of finding the chromatic number of an interval graph. This can be done by a greedy algorithm: sort the blocks in ascending order (after left endpoint) and, for each block, put it on the lowest level where there is room for it.

---
Tags: optimization, packing, memory-allocation
---


# Question
Title: Find shortest path between two vertices that uses at most one negative edge
Given a directed graph $G = \langle V,E \rangle$ with $n$ vertices and $m$ edges and a weight function $w:E \rightarrow \mathbb{R}$, together with two vertices $s$ and $t$ in $V$:

> Describe an efficient algorithm that finds the "cheapest" (in terms of $w$) path from $s$ to $t$ that uses at most one negative edge, or returns that there is no such path.

I was thinking about building a new graph $G'$ which will be equal to $G$ after we removed all of the negative edges from it.

$G'$ contains only non-negative edges, hence we can run *Dijkstra* on it. Let $s\_0$ be the weight of the path we found from $s$ to $t$, if we didn't find a path we will set $s\_0=\infty$.

Let $e\_1,...,e\_k$ be the negative value edges that we removed from $G$, $\forall i: 1\le i\le k:$

1. we can run a modified version of *Dijkstra* on $G' \cup \\{e\_i\\}$ (when there is only one negative valued edge in a graph we can modify *Dijkstra* and it will still work in $O(m+n \log n)$.
2. Let $s\_i$ be the weight of the path we found in the $i$-th *Dijkstra* run. (Again if there is no path we will set $s\_i=\infty$).
3. If $\min\\{s\_0,...,s\_k\\}\<\infty$ we return it, otherwise we retrun that there is no such path.

This algorithm runs in $O(m \cdot (m+n \log n))$ since in the worst case we will run *Dijkstra* $O(m)$ times.

Is there any way to optimize this algorithm, or is there a way to make the problem easier to solve with a better algorithm?

# Answer
You can use Dijkstra twice to find in your $G'$ the cost for each vertex $v \in V$, the cost of the optimal $s$-$v$-path and the cost of the optimal $v$-$t$-path. Store this in a table creatively called OPT.

Now, for each negative edge $e=(u,v)$ in $e\_1, e\_2, ..., e\_k$, the cost of the optimal $s$-$t$-path allowing $e$ is $$\text{OPT}^+(s,t,e) = \min \begin{cases} \text{dist}(s,t) \\ \text{OPT}(s,u) + w(e) + \text{OPT}(v,t) \end{cases}$$

Running time is that of Dijkstra's.

Output $\min\_{i \leq k}\text{OPT}^+(s,t,e\_i)$.

---

Ps, if by *path* you mean *simple path*, then the problem is NP-hard by a reduction from the classic 2-Disjoint Paths problem.
> 11 votes

# Answer
Another approach is to create a single graph $H$ as follows:

* each vertex in $G$ has two counterparts in $H$: vertex $s$ becomes $s\_A$ and $s\_B$, vertex $t$ becomes $t\_A$ and $t\_B$, and so on.
* each nonnegative-weight edge in $G$ has two counterparts in $H$, namely, edge $(u, v)$ becomes $(u\_A, v\_A)$ and $(u\_B, v\_B)$.
* but each negative-weight edge in $G$ has only one counterpart in $H$, namely, edge $(u, v)$ becomes $(u\_A, v\_B)$. Additionally, we increase the weights of these counterparts, all by the same amount, to make them all nonnegative (so that $H$ has only nonnegative-weight edges — necessary for Dijkstra).
* and there is one extra edge from $t\_A$ to $t\_B$, whose weight is the amount by which we increased the weights of the negative-weight edges. (That is: we add a zero-weight edge from $t\_A$ to $t\_B$, then increase its weight the same as we did the negative-weight edges.)

So $H$ essentially has two copies of $G$, where nonnegative-weight edges are within a copy and negative-weight edges carry from copy $A$ to copy $B$ — but never back — plus one extra "free" edge from copy $A$ to $B$. As a result, any path within $H$ corresponds to a path within $G$ that uses at most one negative-weight edge.

You can then run Dijkstra's algorithm on $H$ to find the cheapest path from $s\_A$ to $t\_B$. (Note: to obtain its cost, subtract the extra weight that we added to each of the negative-weight edges.)

This has the same asymptotic complexity as the approach that Pål GD describes. It can also easily be extended to a problem where we want a path with at most *two* negative-weight edges (using three copies of $G$), at most *three* (using four copies), etc., with the caveat that this will allow the *same* negative-weight edge to be reused each time.
> 11 votes

# Answer
This is a more general algorithm that computes the distance that uses at most one negative edge for all vertices.

```
def LikeBellmanFord(s):
    dpos[s] = 0
    dneg[s] = float('inf')

    for v in vertices:
        if v != s:
            dpos[v] = float('inf')
            dneg[v] = float('inf')

    for i in range(1, len(vertices)):
        for (x, y) in edges:
            if w(x, y) > 0:
                dpos[y] = min(dpos[y], dpos[x] + w(x, y))
                dneg[y] = min(dneg[y], dneg[x] + w(x, y))
            elif w(x, y) < 0:
                dpos[y] = dpos[y]
                dneg[y] = min(dneg[y], dpos[x] + w(x, y))

    # Check for negative cycles
    for (u, v) in edges:
        if d[v] > d[u] + w(u, v):
            print("Negative Circle")

    # Calculate final distances
    for v in vertices:
        if v != s:
            d[v] = min(dpos[v], dneg[v])

```
> 0 votes

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Natural combinatorial property in Natural Proofs
From Natual Proofs

> Specifically, natural proofs prove lower bounds on the circuit complexity of boolean functions. A natural proof shows, either directly or indirectly, that a boolean function has a certain ***natural combinatorial property***.

I haven't read the mentioned paper. Can somebody explain what is meant by "natural combinatorial property"? What ***is*** that property, and what is *natural* about it?

# Answer
From the paper \[\]:

> We start by defining what we mean by a "natural combinatorial property"; natural proofs will be those that use a natural combinatorial property.
>
> Formally, by a combinatorial property of Boolean functions we will mean a set of Boolean functions $\\{ C\_n \subseteq F\_n | n\in \omega\\}$. Thus, a Boolean function $f\_n$ will possess property $C\_n$ if and only if $f\_n \in C\_n$. (Alternatively, we will sometimes find it convenient to use function notation: $C\_n(f\_n)= 1$ if $f\_n \in C\_n$; and $C\_n(f\_n) = 0$ if $f\_n \notin C\_n$.) The combinatorial property $C\_n$ is *natural* if it contains a subset $C^\*\_n$ with the following two conditions:
>
> *Constructivity*. The predicate $f\_n \stackrel{?}{\in} C^\*\_n$ is in $P$. Thus $C^\*\_n$ is computable in time which is polynomial in the truth table of $f\_n$;
>
> *Largeness*. $|C^\*\_n| \geq 2^{-O(n)} \cdot |F\_n|$.

Further discussion continues later:

> The definitions of natural property and natural proof can be explained much less formally. First, a proof that some explicit function $\\{ g\_n \\}$ does not have polynomial-sized circuits must plainly identify some combinatorial property $C\_n$ of $g\_n$ that is *used* in the proof. That is, the proof will show that all functions $f\_n$ that have this property, including $g\_n$ itself, are hard to compute. In other words, $C\_n$ is *useful*. If $\\{ g\_n \\} \in NP$; then the proof concludes $P\neq NP$. Our main contention, backed by evidence in the next section, is that current proof techniques would strongly tend to make this $C\_n$ *large* and *constructive* as defined above. (Or at least these two conditions would hold for some subproperty $C^\*\_n$ of $C\_n$.)
>
> In order to understand the definition of *large* more intuitively, let $N=2^n$. Largeness requires that $|C^\*\_n|/|F\_n | \geq 1/{N^k}$ for some fixed $k\>0$; i.e., $f\_n$ has a nonnegligible chance of having property $C\_n$.
>
> *Constructively* is a more subtle notion to understand and justify. We take as our basic benchmark of "constructive" that $f\_n \in C\_n$ be decidable in time $2^{O(n)}$ , i.e., polynomial as a function of $2^n$. Now, this is exponential in the number $n$ of variables in $f\_n$ , and this makes our concept somewhat mysterious, especially since we are going to employ it for studying computations which are polynomial in $n$! The best justification we have is empirical: the vast majority of properties of Boolean functions or $n$-vertex graphs (etc.) that one encounters in combinatorics are at worst exponential-time decidable, and, as a matter of fact, known lower bounds proofs operate only with such properties. It also should be noted that, even with this loose notion of constructivity, we manage to prove in Section 4 strong negative results on the nonexistence of natural proofs.

1. Razborov, Alexander A., and Steven Rudich. "Natural proofs." Proceedings of the twenty-sixth annual ACM symposium on Theory of computing. 1994.
> 2 votes

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


# Question
Title: Mathematical benefit to use CPU/memory that increases by powers of 2 as 8-bit, 16-bit, 32-bit, 64-bit, etc?
Historically, processors often increase in bit-size by powers of 2, such as 8-bit, then 16-bit, 32-bit, 64-bit. Although this has not always been the case, it is a well known trend. One benefit is backwards compatibility. Another is that components can be scaled by combining two 8-bit components into a 16-bit, and so on, such as two 8-bit shift registers. I have also heard that some types of mathematical algorithms benefit from using powers of 2 bit sizes, but I cannot find anything about it, nor think of any. Is anyone here aware of any such algorithms, or such an argument for "powers of 2 bit sizes" in general?

# Answer
Multiplying and dividing binary integers by powers of 2 is *very* cheap, like multiplying and dividing by 10 for decimal numbers.

It's qualitatively different from other factors because the other bits don't change, you just move digits left or right (shifting). In hardware for fixed shift counts, it's literally just wiring.

As I mentioned below, array indexing like `arr[i]` with an index that counts in elements will involve (in hardware or software) scaling by the element size, if memory is byte addressable. (If it's not in a loop, it can't be optimized to a pointer increment). IDK if you'd call this an "algorithm", though.

---

https://superuser.com/questions/1735122/why-are-most-of-the-common-processors-bit-counts-powers-of-2/1735399#1735399 and other answers discuss some of the engineering problems you'd have with e.g. 24-bit words on a byte-addressable machine. (24-bit DSPs use word-addressable memory) - some 3-byte words will span wider boundaries, differing in higher bits of the address. But CPU caches and memory systems really want to group binary addresses by ignoring some low bits, not by doing a full division.

In algorithm terms, this is optimization of `i / sizeof(int)` into a right shift for unsigned `i`, and `i * sizeof(int)` into a left shift.

Another algorithm where this is relevant is a bit-array: given an integer bit-index, you need to break that up into a byte index or word index, and a bit number within the byte (to use as a shift count).

```
#include <limits>
int get_bit(unsigned int *bit_array, size_t n)
{
    size_t element_idx = n / std::numeric_limits<unsigned int>::digits;
    int bit_idx = n % std::numeric_limits<unsigned int>::digits;
    unsigned chunk = bit_array[element_idx];
    return  (chunk >> bit_idx) & 1;
}

```

When `numeric_limits<unsigned int>::digits` is a power of 2, like 32 on typical C++ implementations, this unsigned division and remainder become simple right-shift and bitwise AND, like `n >> 5` and `n & 31`.

This wouldn't be the case for 24-bit `unsigned int`, for example, unless you choose to only use 16 of the 24 bits per `unsigned int`. Division by a constant `24` or `3` is not *very* expensive if you have a fast multiplier, but it's non-trivial.

In hardware it's even more significant: splitting a value into multiple fields is literally just wiring. But for `n%24`, the remainder depends on all 24 bits, not just the low 5 bits, as well as requiring some significant computation.

---

### `std::vector`'s `.size()` member function, and indexing

Another more widely used data structure that benefits from it being very cheap to convert between element index and addresses is **C++'s `std::vector<T>`, a dynamic array that knows its size and can reallocate when push\_back exceeds the current capacity.** Typical implementations have 3 pointer members, perhaps named `T *m_begin`, `m_end`, and `m_capacity`.

The API includes `.begin()` and `.data()` which are trivial, just return the the start pointer. Similarly `.end()` can just return the end pointer. (C++ library functions that loop over a range take a start and end pointer, rather than a pointer + length). `.push_back` can increment `m_end += sizeof(T)` and check `m_end < m_capacity` is still true. (The size in bytes to pass to allocator functions can be obtained by casting to `char*` before subtracting.) None of that benefits from `sizeof(T)` being a power of 2, which is good for use-cases with T = an odd sized struct.

But `std::vector` also has a `.size()` API, typically implemented as `return end - begin;`. In C++, subtracting pointers returns the distance in elements, not bytes, so in asm it typically looks like `sub r0, r1` / `sra r0, 2` or something to arithmetic right shift the subtraction result to scale by `sizeof(T)`. If `sizeof(T)` isn't a power of 2, a right shift won't work for this division. (It is at least a compile-time constant so a multiply and shift can do the trick.)

It's not rare for code to do `for (size_t i = 0 ; i < vec.size() ; i++) do stuff with vec[i]`, or to use `.size()` for other things. Compilers might transform this loop into a pointer increment, avoiding the division by `sizeof(vec[0])`, but some uses of `.size()` won't optimize away.

A non-power-of-2 `sizeof(T)` for common primitive types like `int` and `int *` would make some uses of vectors of those types less efficient. (But implementations would probably keep the 3-pointer design, rather than needing to multiply by `sizeof(T)` more often with one pointer and size\_t length, capacity.

It would also mean `alignof(int)` had to be `1`, unless an implementation padded 3-byte `int` to a larger size. Unless you redefine alignment to mean multiple-of-3 instead of multiple-of-2.

Also, **array indexing** by an integer is normally just a left-shift to multiply by `sizeof(T)` to get a byte offset.

Perhaps such a machine would include scaled-index addressing modes so asm that could scale by 3 and 6, with a shift+add like `i + (i<<1)` instead of just a shift. For example current x86-64 can do `mov eax, [rdi + rcx*4]`. (The asm syntax is a multiply, but the only valid multipliers are 1, 2, 4, and 8; the machine code uses a 2-bit shift count.) So a 24-bit machine might allow `[rx + ry * 3]` or `*6` or `*12`. Otherwise software would need to do more operations to generate addresses.

Many RISCs like MIPS and RISC-V only have 1-register addressing modes so scaling needs software, but maybe they'd provide a single instruction scale-by-3 for address-generation. (Maybe also including a shift count to scale by 6 or 12 or whatever.) `3` only has two set bits, so a fixed shift (trivial in hardware) and an adder will do the trick.

Dividing by 3 is expensive, though.

If the caches on a byte-addressable machine with odd-sized words was still sized to a power-of-2 number of bytes, it could work a lot like a modern x86 which allows efficient unaligned loads/stores, with fairly efficient handling of cases where a load spans the boundary between two cache lines or even pages. Addresses break into offset-within-cache-line vs. index vs. tag by treating the binary address as separate fields.

If cache line sizes were a multiple of 3, like 48 bytes, none of the `int` in an array will span a cache-line boundary. (As long as the start of the array is "aligned" to a multiple-of-3 address!) But if addresses are still binary numbers, cache indexing is no longer simple. `index = (address / 48) % num_sets`, and `tag = (address / 48) / num_sets`. (Assuming for simplicity physical index and tagging.) Paging has a similar problem, power of 2 page size vs. multiple of 3.

(This is the same problem as for a bit-array where the `unsigned int` chunks aren't a power-of-2 size.)
> 11 votes

# Answer
On top of what everyone else has said, bit shift circuits are easier to design if the "shift amount" is a whole number of bits in size.
> 4 votes

# Answer
The fast Fourier transform and its relatives, such as the discrete Fourier transform used in JPEG compression, work best with data sizes that are powers of two. So, if you were to implement the FFT on, say, a DEC PDP-10, with its 9-bit bytes and 36-bit words, you'd have to "waste" 11% of the bits available (and you might also run into some difficulties with masking the unused bits, etc.--it's been a *very* long time since I programmed a PDP-10, so I don't remember the specifics).
> 4 votes

# Answer
It’s beneficial if you can combine smaller units into a larger unit. Imagine you had 12 bit and 20 bit numbers. 20 bits could hold one 12 bit number and waste 8 bit. 24 bits could hold one twenty bit number and waste four bit. You’d need to go up to 60 bits to hold 5x12 or 3x20 bits.

You wouldn’t have that problem with 8, 24, 48 and 96 bit numbers. But then calculating the address of item #n is slightly more complicated.

Having 12 bit bytes and 12, 24, 48 and 96 bits would actually be quite good. UTF-12 would store all characters in two units. 48 bit floating point would very often be enough, and 96 bit would have lots of extra precision.

The only slight disadvantage is storing bit arrays because you often divide a bit number by the byte size or word size in bits, and typical hardware can divide by a constant power of two faster. On the other hand I would expect this hardware to have a fast “divide by 96 / modulo 96” instruction.
> 3 votes

# Answer
On the level of assembly code, having $2^k$ bits in a word is convenient for bit operations. The result is that if you have an assembly command like "set bit $i$ of register $r$", then $k$ bits of the opcode will be devoted to specifying $i$. If the number of bits is not a power of $2$, then either some opcodes are wasted, or else the processor has a slightly harder time interpreting the opcodes.

If I wanted to make a case $2^n$-bit words based on mathematical algorithms, though, I'd bring up Hadamard codes. For all $k$, this is an error-correcting code that takes a $k$-bit input and encodes it as a $2^k$-bit codeword, with the property that any two codewords differ in at least $2^{k-1}$ bits. So, for example, we could take $6$-bit inputs and encode them as $64$-bit outputs; we get a rather inefficient but *very* error-resilient code in this way. The dual of a Hadamard code is a Hamming code, which also benefits from numbering the bits in a codeword in binary.

Finally, here's a very niche benefit: chess engines use bitboards to represent game state, which encodes a binary property like "which squares of the chessboard contain white pawns?" in a $64$-bit vector.
> 3 votes

# Answer
I think the story may be more complicated than some other answers suggest, even if they contain a lot of good arguments.

I add some observations:

* systems with 12,18,24,36 and other bit sizes exist
* Nibbles are the minimum needed for BCD arithmetic. it may sound like a distant memory from the past, but doing BCD arithmetic really simplifies building calculators and other hardware constrained machines, so using a multiple of a nibble was an efficient choice
* Many processor series first (or as a cheaper version -\> 8088) had an ALU being able to operate on the double size internally, and then got an external bus later (68000 was 16 bit data bus and had some 32 bit registers/arithmetic, 6809 hast 16 bit arithmetic with an 8 bit data bus, Z80 had some 16 bit registers/operations, 8088 was 8 bit data bus but had 16 bit registers)

The latter point is IMHO mainly responsible related to economics of designing computers:

* Having internal register sizes multiples the data bus means that you can use these registers as fast internal memory for applications requiring the lower bit number and not waste transfers.
* having these at a low multiple means that your processing is not out-pacing your RAM access (it does not make sense to waste space for an ALU processing the data faster than you can fetch them)
* having versions of your processor data bus at the register and half the size is good - it doesn't make sense to have a 1.5 times wide version

All in all this means that if you run 8 bit SW on a 16 bit data bus, you may have some wasted space, but not as mus as if you had 24 bits.

So i think doubling the bus/register width is the cheapest upgrade path for compatible designs.
> 3 votes

# Answer
## General Situation

Since computers use a binary system to represent data, a heavy use of powers of 2 results in easier optimizations in general.

The key reason for this is that when you multiply by 2 (`0b10`\[1\] in binary), all you need to do is shift the bits in the number. For example, `3` is `0b011` and `6` is `0b110`. Multiplication in binary is a vastly more complex operation, where-as shifting is a simpler one.

## Word-Size in Hardware

As you mentioned, there are many answers describing the hardware reasons. I'd like to call out specifically that the hardware reasons are mostly about alignment to known data-type sizes.

Word-size specifically benefits from having **all data sizes as factors**. This means all of the following need to divide into word size:

* 1-bit (`bool`)
* 8-bit (`char`/`byte`)
* 32-bit (`float`/`int`), and
* 64-bit (`double`/`long`)

So, in general **all of today's chips will use multiples of 64**. There have been several pieces of hardware that deviate from powers of 2. As you mentioned, this comes with costs for hardware design every time you choose a new bit-size. So, going from one bit size to another will require all new circuits for many operations unless you always align to data-type sizes.

## Word-Size in Software

All algorithms are using optimization that depend on hardware configurations. Hardware is the "reality of compute". So, we'll look at some reasons that span the hardware/software boundary. In these situations, there's a hardware design issue that makes either the software more complicated to optimize OR requires more customized hardware to equal the performance of a similar system that uses a power-of-2 bit size.

#### Data Spanning Words is costly

Now, imagine you're storing bytes (8-bits) in a CPU that uses a non-power-of-2 word-size. In this case, you would have to pack your bytes such that they span across multiple words. In a 36 bit system, you'd span 9 bytes over 2 words, with the 5th byte split over the last for bits of word 1 and the first 4 bits of word 2.

For the visually inclined:

```
   WORD 1    |   WORD 2
vvvvvvvvvvvvv|vvvvvvvvvvvvv
11 22 33 44 5|5 66 77 88 99
            ^ ^
           BYTE 5

```

This means that to get the 5th byte, you need to retrieve from both words and combine the data to create a byte. This results in less optimal access to any data that spans multiple words in memory. This results in loading more data into all caches and then into CPU registers, reducing the performance of all programs that use arrays like this one.

#### SIMD is more costly

CPUs also provide instructions that operate on multiple data in a single register. Consider a CPU today that has a 128 bit architecture. It supports instructions that allow you to operate on multiple data being stuffed into these bits. In this case, it can operate on 4 32-bit ints or floats simultaneously.

Now, if we had non-power-of-2 bits, this would be an inefficient use of the word.

Instead of using the word inefficiently, if we decided to pack as described in the previous point, the hardware would require further complexity to perform SIMD operations with different configurations. For example, with the setup described above (36-bit system), we'd need to have a circuit that supports both word configurations. With other bit-counts, it could be even more complex. 2 word configurations is the best we can do when we deviate from powers of 2.

#### Counting Data and Pointers

When data neatly packs into words, counting data and pointer-math become easy. It also means that you can (without knowing the index of data), have the same unpack logic for packed data. The reason why this is important is having a for loop like this would make branch prediction harder. Based on the 36-bit example above:

```
for (i in indices) {
  if (i % 2 == 0) {
    // unpack logic
  } else {
    // different unpack logic
  }
}

```

## Conclusion

It's all about the hardware. Optimizing software is about learning your hardware and writing your software accordingly.

\[1\] `0bxx` is a notation used in some languages to represent binary numbers. So, `0b01 == 1`, `0b10 == 2`, and so on. I am often trimming the leading 0s so that I don't have to write a full byte/word/etc of bits.

\[2\] CPUs don't execute exactly 1 instruction per clock cycle. Modern CPUs execute instructions in phases. The phases enable higher instruction throughput. CPU features like branch prediction can speculatively execute later instructions assuming your branch will take a particular path.
> 0 votes

---
Tags: cpu, history
---


# Question
Title: Alternative to show intersection of two languages is empty
Consider our alphabet set is $\Sigma$. Suppose $L\subseteq\Sigma^\*$. I want to show $L \cap L\Sigma^+=\emptyset$ as one of the bellow options:

1. $x,xy\in L\implies y=\lambda$
2. $x,xy^2\in L\implies y=\lambda$

I think the first is true but I have no idea to show that the second is false.

# Answer
> 3 votes
Take $\Sigma = \\{a\\}$ and $L = \\{\lambda, a\\}$. Then $L$ satisfies (2) but not (1).

---
Tags: formal-languages
---


# Question
Title: Restore the original array after merge Sort based on it's steps
i'm trying to write an algorithm to reconstruct the original array from the sorted one. considering input value is a string of 1s and 2s which 1 means in merging part of merge sort, element from left subarray is chosen and 2 means element from right subarray is chosen. how can i do it? specially i have problem on that part that merge sort appends what ever is left from a subarray to final list. for example: it's given 12212 as input string on an array of numbers \[1,2,3,4\]. it means that there is a permutation of numbers 1 to 4 that if you give it to merge sort, it will give you 12212. that permutation is 2 4 3 1 .

# Answer
> 1 votes
For simplicity I will assume that the number $n$ of elements is a power of $2$. The same idea works in general (by suitably rounding the sub-array sizes according to the implementation of Mergesort at hand).

Let's pretend that, whenever two arrays of size $x$ are merged in the mergesort algorithm, they contribute exactly $2x$ digits to your input "merge string" $m$.

In the last call of the mergesort algorithm the final sorted array $S$ was constructed my merging two sub-arrays $A$ and $B$ with $n/2$ elements each. These sub-arrays $A$ and $B$ can be recovered by looking at the last $n$ digits of your input "merge string" $m$ and proceeding backwards.

In details, you can start with two empty arrays $A$, $B$ and a string $m\_S$ containing the last n digits of $m$ and repeat the following step $n$ times:

* Let $x$ be the last digit of $m\_S$.
* If $s=1$, add the last element $S$ to the beginning of $A$.
* Otherwise (if $s=2$), add the last element of $S$ to the beginning of $B$.
* Delete the last element of $S$ and the last digit of $m\_S$.

Moreover, the remaining digits in $m$ (all but the last $n$ digits) can be (evenly) split into $2$ sub-strings $m\_A, m\_B$, where $m\_A$ (resp. $m\_B$) is the "merge string" resulting by using mergesort from sorting the first (resp. second) half of the elements into $A$ (resp. $B$).

Then you can apply the above strategy recursively on the sorted array $A$ with "merge string" $m\_A$ and on the sorted array $B$ with "merge string" $m\_B$. Eventually you'll reach a call in which the sorted array is just a single element, which must coincide with the input of the corresponding call of Mergesort.

A high level pseudocode could be the following:

```
// Returns the original order of the elements in S
Recover-Array(S, m):
  if |S| == 1:
    Return S

  Decompose m into three parts m_A, m_B, m_S such that |m_A| = |m_B| and |m_S|=|S|
  Split S into A, B according to the digits in m_S (as described above)

  A' = Recover-Array(A, m_A)
  B' = Recover-Array(B, m_B)

  return the concatenation of A' and B'

```

Let's now consider the case in which the merge operation of mergesort stops contributing digits to the merge string as soon as all the elements from one of the two input arrays are merged (since the leftover elements in the other array can simply be appended to the output).

Once all complete merge strings for all the recursive calls of Mergesort are known then you can also recover the original array using an approach similar to the previous one.

In order to recover the complete merge strings imagine visiting the recursion tree of mergesort in postorder (i.e., you start with the leftmost leaf, then visit its sibling, then their parent, etc). This is exactly the order in which merges are performed. Whenever you visit a generic internal node $u$ whose subtree has height $h$, the corresponding merge procedure of Mergesort merged two arrays $A$ and $B$ of size $2^{h-1}$ into an array $S$ of size $2^{h}$ and appended a contiguous sequence of bits, which we will call a trace, to the our input merge string. (Leafs have empty traces). The idea is that, when $u$ is visited, we will have already recovered the complete merge strings for all its proper descendants and we will also have removed the bits corresponding to their traces from the input merge string. In this way the current fist digit of the merge string corresponds to the first decision taken by the merge procedure for $u$'s call.

To recover the complete merge string $m\_u$ for an internal node $u$ find the shortest prefix $m\_S$ of the current merge string that has either $2^{h-1}$ ones, or $2^{h-1}$ twos. This corresponds to the comparisons performed to merge all elements from one of $A$ and $B$ into $S$, i.e., $m'\_u$ is exactly the trace for $u$'s call. To complete it into $m\_u$, it suffices to add the missing $2^h - |m'\_u|$ digits as a suffix (which corresponds to copying the leftover array). Then, we delete the trace $m'\_u$ of $u$ from the input merge string and continue with the postorder visit.

---
Tags: algorithms, recursion, divide-and-conquer, mergesort
---


# Question
Title: Which searching technique will cause lesser number of page fault?
Linear Search has O(n) T.C and Binary Search have O(logn) T.C. But how come Linear Search generates fewer page faults? Is there another searching technique that causes a lesser number of page faults than linear search?

# Answer
> 3 votes
Your assumption is wrong. If all data is in memory then there are no page faults. Now assume you have 100 pages, none in memory. Linear search will have on average 50 page faults. Binary search will have a fault for page 50, one for page 25 or 75, one for page 12, 37, 62 or 87, and a few more. The total will be the logarithm of the number of pages, that is 6 or 7.

Now if your data set is so huge that it doesn’t fit into RAM, say four times larger, and you search repeatedly. Linear search will have page faults for half the pages on average. For binary search, there is a huge number of pages that are read repeatedly. For example the middle page on every search, the first and last quarter page on every second search, and so on. Most of the pages visited will be in the least recently used list and cause no page fault, only the very last two or three pages will. So with 8GB of RAM available and 32 GB of data, you won’t have a million page faults per search but two or three.

# Answer
> 1 votes
One approach is Eytzinger layout, which is essentially a breadth-first traversal of the binary search "tree".

The idea is that the items that would be visited first in binary search are located next to each other in memory.

Another option is B-trees, which are designed with page efficiency in mind.

---
Tags: operating-systems, paging
---


# Question
Title: What are some complexity classes for neural networks?
Turing machines and neural networks are equivalent in their expressive powers, but as models of computation they are different. Turing machines come pre-configured with their transition functions while the neural networks configure weights to build learnable computable functions using input data.

Is the class of problems efficiently solvable by a neural network equivalent to the class P or NP... or some normal complexity class or do they have their own complexity classes that are not equivalent to normal ones.

# Answer
> 3 votes
Basically, no one has proven anything useful about which tasks a neural networks are able to efficiently learn to solve.

What we can say is: they're not magic pixie dust. They can't solve NP-complete problems in polynomial time, unless P = NP.

In practice, for most tasks that you'd find in a classical algorithms class, human-made algorithms vastly outperform neural networks. The situations where neural networks are better tends to be tasks that don't admit a crisp problem statement or specification of the desired behavior.

# Answer
> -2 votes
I think that this reply never consider a fact,which the classical alogorithms and the human thought are constantly evolving with the abstraction and resolve of problem. Basicaly,I think effectively corresponding relationship between the concept of computational complexity and the concept of human cognition will clear the problem. Then,will figure that the effective apparent comparison Angle is not so simple.

---
Tags: complexity-theory, neural-networks
---


# Question
Title: Buy two chocolates when want MAXIMUM nonegative spend
This is a self-study inspired by the trivial https://leetcode.com/problems/buy-two-chocolates/. Basically the question is as follows: if you have a value of money `m` and a list of `prices`, imagine you are a hungry child who wants to spend all of their money on two chocolates. Return the two prices that leave the least amount of (nonnegative) money left over. Is there an algorithm that solves this less than $O(n^2)$?

This problem is a form of constrained optimization, maybe somewhat similar to the problem of choosing a certain amount of coins to use up an amount of money. I am not aware broadly of what solutions fit these class of problems in the discrete case, however I do roughly know some of the tools for the non-discrete situations.

# Answer
> 1 votes
Yes. Sort all chocolates by price. For all possibilities for the choice of first chocolate, use \[...\] to find the best second chocolate to go with it. Keep the best pairing found.

Fill in the \[...\] with an appropriate algorithm, and you can beat $O(n^2)$.

To improve the running time even further, consider: as you increase the cost of the first chocolate, what effect must this have on the cost of the best second chocolate?

> In other words, How can you avoid the full cost of a binary search?

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


# Question
Title: Cycle-cancelling algorithm, Minimum cost flow
I am studying the cycle cancelling algorithm for the minimum cost flow problem, and I can not understand the proof of the following:

If there no negative cost cycles then you have a minimum cost flow. The other direction is easy but I am stuck with this one.

If you want to get a smaller cost with an augmentation on the residual graph then it's impossible because you don't have negative cycles

**But**

Wouldn't it be possible to choose a cycle in the residual graph augment the cycle's flow and create negative cycles again ? which are bigger than what cost you increased in the augmentation so the net result would be a smaller cost.

# Answer
It could have something to do with the amount of flow you redirect when you perform augmentation $\gamma$ along a positive cycle $\epsilon$.

Since you are assuming the creation of negative cycles, it means that you have created at least one new negative cost arc(the new negative arcs in residual graph $G(x')$ are the result of pushing flow on arcs in $G$ which had no flow assigned in flow $x$).

The residual capacity of those new negative arcs is equal to the flow redirected with $\gamma$.

This gives you an upperbound on the amount of flow you can redirect in any new negative cycle.

It can be shown too that the cost of any negative cycle, $\eta$, created with augmentation $\gamma$, is bound to be less or equal, in absolute value, to the cost of $\epsilon$. (Consider the subset of arcs in $\epsilon$ that created the negative cost arcs which are used in $\eta$).
> 1 votes

---
Tags: network-flow
---


title: Proving the set $R$ is finite

text:
# Question
Title: Proving the set $R$ is finite
Suppose $L$ is a regular language. Let $R\subseteq L$ be a language with maximal size such that for each $x,y\in R$ neither $x$ be a substring of $y$ after removing a substring from $y$ nor $y$ become a substring of $x$ after removing a substring from $x$. Could we conclude that $R$ is finite?

My thoughts are as follows:

We know our alphabet is finite, also each string on $\Sigma^\*$ is finite, I tried to use those facts to prove that $|R|$ is finite but I got stuck. Any hint will appreciated.

# Answer
There exists an infinite sequence of strings, such that no string is a substring of another. For example $a b^\* a$.

If one considers the subsequence ordering instead of the substring ordering, then every infinite set of strings has a pair such that one is a subsequence of the other. This is known as Higman's Lemma.
> 3 votes

---
Tags: formal-languages, regular-languages
---


# Question
Title: Do all computers use parity checking? When does it happen?
I know that parity checking is testing for accurate data transmission between nodes in a communication network.

1. When does this parity checking happen on a computer? Does it happen every time data is transmitted internally in a computer?
2. Do all computers use parity checking?

# Answer
> 1 votes
The problem with parity checking is: What do you do if it is wrong? Let’s say you stored a byte with value x, a parity bit is added, then you read the value and there is a parity error. You know that one of nine bits is wrong but not which one.

For data transmission there is a very simple rule: if there is any error then we behave as if the data had never been sent, and data transmission protocols are able to handle that.

For memory errors, you could have error correction which is quite expensive. Or you have parity errors, and then you need to decide what to do. If it’s in the software of a self driving car, what do you do? Stop the car (bad idea on a motorway) or continue and pray?

What you can do is check for defective memory when the computer is started. You write data to memory, read it back and check it is correct, using patterns to avoid getting the correct data by coincidence, and avoiding writes that go only to cache memory.

# Answer
> 0 votes
When Error-detection and Error-coorrection is performed depends on associated protocol and layers.

For example for Ethernet ,Error-detection and Error-coorrection performed in intermediate routers between sender and receiver at layer2(Data-link layer) for both header and data.

And at layer3(Network layer) for ipv4 Error-detection and Error-coorrection mechanism performed only for ipv4 header at intermediate routers between sender and receiver. For ipv6 header checksum option isn't not present.

Now most important work is happening at receiver side at layer4(transport layer). If you use TCP protocol then it's liable for checking Error-coorrection and detection for both data and header, TCP also restore the reliability for data packets. For ipv6 header, TCP is mandatory. But for UDP at transport layer checksum option is optional(but for ipv6 it is mandatory), then it depends on application layer as as well as layer2.

---
Tags: computer-architecture, computer-networks
---


# Question
Title: Find the largest possible number not larger than some integer N and is the product of K consecutive primes
Source: Hanoi student competition of unknown year (Kì thi học sinh giỏi thành phố)

Additional conditions:

N is a positive integer in range \[1, 2^64 - 1\]

K is a positive integer in range \[3, 10\]

Example: N = 106, K = 3 =\> res = 105 (3 * 5 * 7)

# Answer
> 2 votes
It can be checked easily whether the product of the first $K$ primes is larger than $N$. If yes, there is no such number that is not larger than $N$ and is the product of $K$ consecutive primes.

Otherwise, list consecutive primes nears $N^{1/K}$ as $p\_1, p\_2,\cdots,p\_K,p\_{K+1}, \cdots, p\_{2K-1}$ in increasing order, where $p\_K$ is the largest prime not larger than $N^{1/K}$. The wanted largest possible number must be the last product that is not larger than $N$ among the following $K$ products: $$p\_1p\_2\cdots p\_K,\ p\_2p\_3\cdots p\_{K+1},\cdots, p\_Kp\_{K+1}\cdots p\_{2K-1}.$$

In order to list the primes described above easily, we can find all prime numbers not larger than $N^{1/K}+ 340$. I select $340$ since there are more than $10$ primes between $N^{1/K}$ and $N^{1/K}+340$ when $N\lt 2^{64}$ and $K\ge3$. You can use a larger gap such as $2022$ or $152694$ instead; it does not slow down the computation noticeably. Using standard technique, we can find all primes not larger than $(2^{64})^{1/3} + 340$ in less than $0.1$ second.

A straightforward implementation of the approach above in Python could solve the problem within $0.1$ second.

Assume $K\ll N$, an estimate of the time-complexity of the approach above is $O(N^{1/K}\log\log(N^{1/K}))$. Check this Wikipedia article on the time-complexity of the sieve of Eratosthenes that lists all prime numbers up to a given limit.

# Answer
> 0 votes
Prefill a prime sieve with $2^{64/3}$ entries. This takes $330281$ bytes of storage.

Then for a given $K$, you can start a search from the largest prime below $\sqrt\[3\]N$, increasingly until you exceed $N$. The products can be computed directly or incrementally (next product from the previous).

# Answer
> 0 votes
(Should be read after John L’s answer so I upvoted it to make it come first).

You don’t need to restrict n to be less than $2^{64}$. The primes are around $n^{1/k}$. If this is small enough that you can find primes of that size easily enough, then you can find k+1 consecutive primes so that the product of the first k is not obviously greater than n and the product of the last k is not obviously less.

Calculating both products using floating-point arithmetic has a rounding error, but we can find bounds for that error, and we can often prove that the product of the first k is less than n, and the product of the last k is greater than n.

In other cases, we can prove that one product is less than or greater than n, but not the other one. For example, one product calculated with floating-point arithmetic might compare equal to n. In that case we can use multi-precision arithmetic to divide n by all the primes consecutively and decide.

If the primes are too large, then both products might be too large to decide; this will require some search for the solution.

As an example finding the 10,000 consecutive primes with the largest product less than $10^{100000}$ should find 10000 primes around $10^{10}$ easily.

---
Tags: algorithms, time-complexity, mathematical-programming, binary-search, primes
---


# Question
Title: Running time of modified BFS algorithm to find shortest path in weighted DAG
While the shortest path can be calculated with $O(V+E)$ time over a weighted directed acyclic graph using topological sort, I wonder about the running time of the following BFS type algorithm I thought of.

```
BFS_requeue(v):
Initialization()
push(s) //push the source node
while the queue contains at least one vertex:
    u = pull()
    for all edges u -> v
        w = edge_weight(u,v)
        if dist(v) > dist(u) + w
            dist(v) = dist(u) + w
            pred(v) = u
            push(v)

```

> Compare one of the standard BFS algorithms, this does not mark vertices, and one vertex can be pushed into the queue more than once. Although it seems that popping a vertex more than once can result in a slower running time in general, I am not sure with the exact running time of the algorithm on a **(possibly negative) weighted directed acyclic graph.**

Although I suspect in the worst case, this runs like Bellman-ford, in $O(VE)$ time, I cannot think of a concrete example. All the examples I thought of run in $O(V+E)$ time. So what is the running time of this algorithm on a weighted DAG?

I think regardless of the running time, this does identify the shortest path, essentially by relaxing all edges. However, I might be incorrect.

---

This algorithm is taken from page 7 of chapter 8 of Jeff Erickson's textbook on algorithms. I have only modified the algorithm so it applies to weighted graphs. Nonetheless, this problem is specifically about DAG, rather than weighted graphs in general

# Answer
The running time can be exponential, so it is much worse than $O(|V|+|E|)$ or $O(|V| \cdot |E|)$.

Here is an explicit counterexample. Suppose you have a dag with $n$ vertices, numbered $1,2,\dots,n$, and there is an edge $i \to j$ for each $i,j$ with $i \> j$, with weight $2^{i-j}-1$. Suppose that the for-loop traverses the neighbors from lowest-numbered vertex to highest-number vertex. The algorithm will start by visiting vertex $n$, then pushing $1,2,\dots,n-1$ onto the queue, visit vertex $1$, then $2,1$, and so forth. In particular, the condition `dist(v) > dist(u) + w` will always hold true, so the then-branch of the if-statement will always be executed.

What's the running time, on this graph, with this visit order? It satisfies the recurrence relation

$$T(n) = T(1) + T(2) + T(3) + \dots + T(n-1),$$

which solves to $T(n) = 2^n$.
> 1 votes

---
Tags: algorithms, graphs, algorithm-analysis, graph-traversal, weighted-graphs
---


# Question
Title: Proof that total computable functions are not enumerable
In an answer to this question, a sketch of the proof that total computable functions are not enumerable is made:

> Because of diagonalization. If $(f\_e:e \in N)$ was a computable enumeration of all total computable functions from N to N, such that every $f\_e$ was total, **then $g(i)=f\_i(i)+1$ would also be a total computable function**, but it would not be in the enumeration. That would contradict the assumptions about the sequence. Thus no computable enumeration of functions can consist of exactly the total computable functions.

I really don't understand why

> then $g(i)=f\_i(i)+1$ would also be a total computable function

Indeed if $g$ was a total computable function, then $\exists k, f\_k=g$, so that $g(k) = f\_k(k) + 1 = g(k) + 1$, which is impossible.

So it seems to me that building $g$ is impossible, so that we cannot reach a contradiction by saying that we have built another total computable function which is not in our enumeration.

I tried shifting the diagonal to avoid this effect, but other loops of the same kind can't be ruled out.

# Answer
> 5 votes
$g$ is total computable *by definition*.

* By assumption $f : \mathbb{N}^2 \to \mathbb{N}$ is total computable.
* $1$ certainly is.
* $+$ certainly is.
* The concatenation of $+$ and $f$ is computable by construction, and that's $g$.

The details depend on the exact definition of "computable" (i.e. the machine model) you use; see e.g. here.

So *under the assumption* that such $f$ existed, $g$ is computable; therefore, it *must* have an index in $f$, which is impossible (as you note); therefore, the assumption must be false.

# Answer
> 4 votes
The problem really is in how you're approaching the proof by contradiction. You're objecting to one conclusion ("$g$ is computable and total") by drawing a different conclusion ("$g$ isn't total computable, since it's not on the list" or "... since there is a way to interpret it as referring to itself") contradicting it. But this is exactly the point: that from our hypothesis we can conclude contradictory things, so our hypothesis must be wrong. That is, within a proof by contradiction you have to sort of give yourself "tunnel vision:" when trying to prove Thing A inside a proof by contradiction, don't let its clear falseness stop you!

It may be helpful in this case to rewrite the usual proof as a direct proof, and I've done this below. Incidentally, exactly the same thing can be done with Cantor's diagonal argument, and it might help to get comfortable with that first if this proof is still confusing.

---

First, convince yourself of the following:

> If $f$ is a total computable function of two variables, then the function $g\_f: x\mapsto f(x,x)+1$ is also total computable.

Exactly how you do this will depend on which definition of "computable" you're using, but they'll all make it fairly easy. For example, in $\lambda$-calculus this is immediate: $g\_f$ is just $\lambda x.S(f(x,x)).$ With Turing machines, this will take a bit more work but really only a bit.

We can now prove:

> If $f$ is a total computable function of two variables, then $g\_f$ is not any of the "rows" of $f$: for each $x$ we have $g\_f\not=f(x,-)$ (since in particular $g\_f(x)\not=f(x,x)$).

Now an effective enumeration of *(some, not necessarily all)* total computable functions of one variable is really just a single total computable function of two variables: "$(f\_e)\_{e\in\mathbb{N}}$" is really the same as the two-ary function $f: (x,y)\mapsto f\_x(y)$. So phrasing things differently, what we have is:

> If $(f\_e)\_{e\in\mathbb{N}}$ is an effective enumeration of total computable functions, then there is a total computable function $g$ which is not equal to any of the $f\_e$s.

Namely, let $g(x)=f\_x(x)+1$.

Note that **everything here is direct**: I haven't used a proof by contradiction anywhere. But now it should be obvious that there is no effective enumeration of all the total computable functions, since that would contradict the point above.

The basic flow of ideas in the proof-by-contradiction-version of this argument is:

* We start with a hypothetical object: an effective enumeration $E$ of all the total computable functions.
* Well, in particular it's an effective enumeration of *some* total computable functions (it just happens to hit them all) ...
* ... And for any effective enumeration of total computable functions, we have a total computable function not so enumerated.
* So in particular there is a total computable function not in $E$, and this contradicts the assumption on $E$, so we're done.

Note, though, that this is really just adding an unnecessary level of confusion: it's really better to proceed as above, where we prove directly a fact ("For every effective enumeration of total computable functions, we can find (in fact, effectively in an index for the enumeration!) a total computable function not so enumerated") which implies the thing we want ("No effective enumeration of total computable functions gets all of them").

# Answer
> 0 votes
I think the original question to be valid and Ciarán Taaffe's answer to be useful: Consider a diagonalisation on Turing machines, computing total computable functions from N to N. Then, G would be given a number, select the corresponding TM from the assumed enumeration, calculate the value and so on. But by assuming G was part of this list, there is a recursion (if G is given its own number in the enumeration) and therefore G does **not** terminate on that number and, in conclusion, does not compute a total function. With this contradiction, only the assumption that G was on that enumeration, is wrong (especially since it would not compute a total function if it were) and does not help proving more than that.

# Answer
> 0 votes
Suppose f\_k, k = 0,1,… is any enumeration of total functions on the natural numbers, n \>=0, that is, total functions whose domain and codomain are the natural numbers. Then g(n) = f\_n(n) + 1 is a total function which is not in the enumeration. For if it were, say the mth, then g(m) = f\_m(m) + 1 = g(m) + 1, a contradiction. We conclude that there is no enumeration of ALL the total functions on the natural numbers as the above argument applies to all the enumerations of total functions on the natural numbers.

# Answer
> -3 votes
The answer is that you have found a legitimate problem with these naive proofs by diagonalisation. In practice, diagonalisation cannot be applied to computational theory. Diagonalising is only possible in the fantastical land of actually infinite sets. There are no such things in the world of computation.

The problem is this: It is impossible to build a machine g case by case, because we would require an infinite number of cases, and the description of g would grow in length forever. However, to define g differently to any total computable function requires that g itself is not a total computable function, otherwise it would be different to itself! But we cannot begin by assuming what has to be proven.

$g(i)=f\_i(i)+1$ is not a definition. It is a property. It means "define g of i such that ..."

Unless a procedure can be legally described which computes g, then this property is meaningless in the world of computation. The reason that functions with such properties can be assumed to exist in the fantastical world of actually infinite sets is because the Axiom of Choice allows them to choose elements from every set in an infinite set all at once. Obviously in the finite world of computation, this is impossible.

Finally, I would like to point out that Turing, in his original 1936 paper does not give such a stupidly naive argument for the existence of uncomputable real numbers. His proof is much more complex, precisely because he was aware that direct self-reference such as this must be avoided.

---
Tags: computability, semi-decidability, enumeration
---


# Question
Title: Applied $\pi$-calculus: Name binding and if clauses
Assume in the applied pi-calculus we have the following process: $$(\nu n)\overline{c} \langle n \rangle.0 | (\nu n) (c(y).(\text{if n=y then P else Q}))$$ where $P$ and $Q$ are further processes.

I know that the following reduction semantic holds for the applied $\pi$-calculus (from wikipedia): $$\overline{x}\langle z \rangle.P | x(y).Q \rightarrow P | Q\[z/y\]$$ where $Q\[z/y\]$ denotes the process $Q$ in which the free name $z$ has been ''substituted'' for the free occurrences of $y$. If a free occurrence of $y$ occurs in a location where $z$ would not be free, alpha-conversion may be required.

Do I understand correctly, that in the above example, because $n$ is already used and thus not free, we would need to rename and thus the reduction would be like so: $$(\nu n') (\nu n) (c(y).(\text{if n=n' then P else Q}))$$

While on the other hand, in the following process: $$(\nu n)\overline{c} \langle n \rangle.0 | c(y).(\text{if n = y then P else Q}))$$ because $n$ is not bound, we can simply perform the transaction like so: $$(\nu n) (\text{if n = n then P else Q})$$ (and thus those two processes are also semantically different)?

# Answer
> 0 votes
yes, you're right about the processes being semantically different. There is a small mistake in your first reduction though, you forgot to remove the c(y) once you substitute y with n':

$(\nu n)\bar{c}\langle n \rangle.0|(\nu n)c(y).(if n=y \text{ then P else Q}) \rightarrow (\nu n')(\nu n)(if n=n' \text{ then P else Q}) $

---
Tags: process-algebras, pi-calculus
---


# Question
Title: what's the time complexity of finding all nullable symbols in context free grammar?
I'm reading Hopcroft's book about computation theory and wondering about how fast can u find all nullable symbols in CFG.

# Answer
> 1 votes
You can do it in linear time. For each nonterminal $A$, introduce a boolean variable $x\_A$ that identifies whether $A$ is nullable or not. Derive constraints on these boolean variables, following the relations described by Hopcroft and Ullman. Note that all of these constraints are Horn clauses. Now find the least solution to this system of Horn clauses. This can be done in linear time (see, e.g., https://en.wikipedia.org/wiki/Horn-satisfiability).

---

If you want a self-contained algorithm that runs in linear time, build a bipartite graph, with one left-vertex per rule in the grammar, and one right-vertex per nonterminal in the grammar. Add an edge between nonterminal $A$ and each rule where $A$ appears on the right-hand side. Now initialize a queue to be empty, repeat the following:

* For each rule $A \to \varepsilon$, mark $A$. Whenever you mark a nonterminal that wasn't previously marked, add it to the queue.
* While the queue is non-empty:

+ Pop some nonterminal, call it $A$, from the queue.
    + For each edge from $A$ to some rule, delete that edge. If the left-vertex for that rule now has no more edges out of it, mark the non-terminal on the left-hand side of that rule and add it to the queue if it wasn't already marked.

With an appropriate data structure for the graph, this runs in linear time.

---
Tags: context-free
---


title: Learning eigenvalue decomposition

text:
# Question
Title: Learning eigenvalue decomposition
How would you build a fully connected neural network that learns eigenvalue decomposition efficiently?

I wanted to build NNs that can predict certain properties about matrices which are NP-hard to compute but might require eigenvalue decomposition. However, I am not sure if hardcode-calculating eigenvalues at any specific layer would be a good idea, because I feel the need to find eigenvalues shouldn't be pre-determined at a certain layer and maybe yield issues in backpropagating errors.

Ofcourse, I may be wrong and hence, looking for some advice.

# Answer
This smells like an XY problem. A neural network is not a good tool to use for computing the eigenvalue decomposition. Machine learning is best for problems where you have examples of input-output pairs but you don't know of a classical algorithm to solve the problem. That doesn't apply here.

If you think that the eigenvalue decomposition of a matrix might help a neural network to learn the desired output, then compute the eigenvalue decomposition via a standard algorithm and feed it in as an additional input (additional features).

That said, I feel wary about the entire direction you are sketching. If you are trying to solve a NP-hard problem, I suspect there's a good likelihood that neural nets are probably not a helpful direction. Neural nets are not magic pixie dust that can solve every problem. See, e.g., Evolving artificial neural networks for solving NP problems and https://cs.stackexchange.com/a/128555/755 and https://cs.stackexchange.com/a/130272/755.
> 2 votes

---
Tags: machine-learning, neural-networks, matrices, decomposition
---


# Question
Title: Does exist an algorithm that decides whether a program halts or not as its timeout approaches to infinity?
By an algorithm $A(p, t)$ attempting to decide whether the program $p$ halts or not by running the program for $t$ seconds (the timeout) and trying to prove that it doesn't halt at the same time, can it decide more and more programs as the time gets bigger, so that any program would result in the algorithm in showing us "halts" or "doesn't halt" in *some* time as it really does? More precisely, by $H(t)$ representing the number of the programs being decided ($H(t) = |\\{p \in Programs: HALT(A(p, t))\\}|)$:

$\forall n \in N: \exists t \> 0: H(t) \> n$

and

$\forall p \in Programs: \exists t \> 0: HALT(A(p, t))$

Does such an algorithm $A$ exist?

# Answer
> 0 votes
By your definition such an algorithm does not exist.

In fact, the algorithm should give an answer in finite time. At whatever timestamp $t\>0$ the algorithm $A$ stops, there always exists a program $p$ which halts after $T\>t$ time, so that $A$ can not detect if $p$ halts or not.

The problem is that $A$, being al algorithm, can run for finite time, while the set $\\{t \in \mathbb{R} \ : \ \exists \ p \in P \ : \ p \text{ halts after } t \text{ seconds} \\}$ is superiorly unbounded.

Since I'm not sure on what you asked I provide also another answer:

If the program $p$ is fixed, either it halts at time $t$ or it does not halt. But also in this case, we can not know if it halts or not without knowing $t$ and this is the classic alting problem. You can find it on Wikipedia or on various books

# Answer
> 0 votes
Programs are enumerable, so you can organize rounds where you execute one elementary step of every program in turn and in the end add a new program.

The more time you spend, the more halting programs you will find.

# Answer
> 0 votes
You can write a program that detects that some programs halt with some inputs, and that some programs won't halt with some inputs (just not for all programs and all inputs).

I'm sure there are programs where you can prove "with input X, it will either halt within s seconds, or it will not halt at all". And then of course you can decide whether the program halts with input X by running it for s seconds. Take testing a number n for primality by dividing it by all integers other than 1 and n (so it halts when you find a non-trivial divisor, and if n is prime it never halts). That program will either halt within $\sqrt n$ steps or it will not halt at all.

And of course you can simulate any program with any input, and if that program with that input halts, then your simulation will detect that eventually. If you simulated all programs with all inputs, then you would be able to enumerate all halting program/input pairs. The problem is that after any finite amount of time, you don't know whether and which of the other problems will halt and which will not.

---
Tags: decision-problem, halting-problem
---


# Question
Title: Why does reducing the bit size by one of NP-hard instances imply P = NP?
I am reading some notes on parameterized complexity located here. Under the topic of "Kernalization" (section 3, page 4) they state:

> When faced with the task of solving an NP-Hard problem, almost every practical computer implementation performs preprocessing steps or data reduction steps. The goal of such a subroutine is to quickly solve the easy parts of a problem instance and reduce it to its difficult core structure that can then be solved by slower exact algorithm. The language of parameterized complexity helps us in formalizing this concept and analyzing the effectiveness of such preprocessing subroutines. **This cannot be done in the context of classical complexity since if the bit size of an instance of an NP-Hard problem could be reduced by even just one bit, then this would imply that P=NP.**

I am unable to see why this boldface portion is true. Why is it that being able to reduce NP-hard instance of a problem by a single bit implies P = NP?

# Answer
A formal statement of the text you are quoting could be:

> For any given NP-complete problem $P \subseteq \Sigma^\*$, if P $\neq$ NP, then there is no function $f\colon \Sigma^\* \to \Sigma^\*$ such that:
>
> 1. $|f(w)| \< |w|$ for all but finitely $w \in \Sigma^\*$,
> 2. $w \in P$ iff $f(w) \in P$, and
> 3. $f$ is computable in polynomial time.

Indeed, otherwise, given $w$, it would suffice to iterate $f$ exactly $|w|$ times on it, and then solve (using an NP algorithm) the small instance that you obtain. This algorithm would solve $P$ in polynomial time, and hence would imply that P = NP.
> 7 votes

---
Tags: complexity-theory
---


# Question
Title: Are Quantum algorithms probing the oracle?
Considering Deutsch–Jozsa algorithm

problem statement, of not being able to recognize "constant functions" from "balanced functions" on single call conventionally is clear to me...

Now quantum part, slightly modifies the "problem" function, from being a function (due to how quantum circuits work on gate based quantum computer)...

```
 |0>×N // N Input qbits, initialized to state 0 - so far good
 |1>  // single output qbit, initialized to state 1 - well, why not...

```

Now let's toy with some sample oracles

```
 Or1) always return 0, do not touch input qbits
 Or2) always return 1, do not touch input qbits
 Or3) balanced // just XOR some qbits together, via CNOT gate on those qbits with result one

```

Now the explanation/algorithm goes via

```
 0) - the function must be given as quantum oracle - i.e. built from the gates
 1) H gate on inputs and output
 2) pass qbits, now in H rotation, into oracle - thus exactly one invocation
 3) make H gate on inputs and outputs once again (is self inverse, so we are back in original rotation)
 4) Inspect INPUT qbits instead of output, and make decision

```

Like, wait a moment.... how does this differ from me modifying the original task into: instead of

```
bool F(bool[] inputs) // considered pass as value

```

I make it

```
void F(ref QBit result, ref QBit[] inputs)  // considered pass as value

```

and I require you to give me the function as definition via gates

where QBit would have "state" for normal perspective as well as state in H rotated perspective

and I define gates, in a way that they are reacting on both, inputs and outputs, i.e. CNOT would be in normal perspective, as expected (modifies target, reads control)

```
Control × Target => Control Target
 |00> to |00>
 |01> to |01>
 |10> to |11>
 |11> to |10>

```

whereas in H perspective, from point of action-reaction would also influence the other qbit

```
 |++> to |++>
 |+-> to |-->
 |-+> to |-+>
 |--> to |+->

```

or in other words.... apart from computing what to make result into, in H rotation I make it "mark" which qbits were used to actual decision making.... since function can only be constant or balanced, there are 3 cases

```
 Case1) is constant - so no qbit is touched in decision making
 Case2) something is used for decision making - thus (apart from Case3) must be a balanced
 Case3) decision making makes a tautology, so always decides the same - hence some XOR like marking - so reversed decision cancels out

```

as, now, I can also make the "quantum claimed superiority" by single call to the "oracle" function, by completely ignoring its output, rather using reference to the inputs as a probe to the function

So the question: why is this not considered "probing the oracle" in classical computing, or if make the comaprison somehow fairer, would be "Deutsch-Jozsa" algorithm still bringing any benefit over classical way (i.e. allowing probing on classical / disallowing probing on quantum)?

# Answer
> 1 votes
If you are given the combination of quantum gates that are used to implement the oracle, the problem is easier, even for classical algorithms.

But when we have an oracle, we don't get to see the quantum gates. We just have a black-box API. The quantum algorithm doesn't see the gates. Neither does the classical algorithm. The quantum algorithm can still distinguish even without seeing the gates. The classical algorithm can't.

So that's how it differs from your thought experiment.

---
Tags: quantum-computing
---


# Question
Title: Proving a language is recursively enumerable
Prove that the following language is recursively enumerable: L = {\<M,x\> | Turing machine M enters the same configuration twice on input x}

I have tried to construct a TM that maintains the current configuration which is of the form (u,q,v) where uv is the current tape content and the tape head is over the first symbol of v and q is the current state. However this would require infinite states to maintain the current tape content. I am not sure how to start this?

# Answer
Big Hint: You can simulate infinite, random access memory (RAM) using a turing machine (this would not require an infinite number of states).

As you mentioned, you can encode the current configuration when running $M$ on $x$, so if you can store configurations in your unlimited memory, do you see how you can detect when $M$ enters the same configuration?
> 0 votes

---
Tags: turing-machines, computation-models, decidability, turing-recognizable, recursively-enumerable
---


# Question
Title: Does a sorted sequence from in-order traversal imply a binary tree is a BST?
An in-order traversal of a binary search tree (BST) produces a sorted sequence. I wonder, if we perform an in-order traversal of a binary tree and obtain a sorted sequence, does that imply that the tree was a BST? (Is it a necessary and sufficient condition?)

I was looking for an algorithm to check if a given binary tree is a BST or not with the best time complexity. One of the solutions here suggested to do an in-order traversal and verify if the sequence is sorted. But I don't understand why this is a necessary and sufficient condition. I need a clear and rigorous proof.

I appreciate any help!

# Answer
> 2 votes
Indeed. A binary tree is a BST iff its inorder traversal is sorted.

First: when is a binary tree a binary search-tree (BST)? I for any node of the tree all nodes in its left subtree are less than the root, while all nodes in the right subtree are larger than the root.

The inorder traversal of a binary tree is recusively defined as LNR: visit left subtree, visit node, visit right subtree. Thus for any node, the inorder traversal visits all nodes in its left subtree before that node, followed by the right subtree. This holds for all nodes in the tree, even though in the final list we cannot recognize the subtrees anymore.

Hence, if the inorder traversal is sorted it implies that all nodes in a left subtree are smaller than the root of the tree, because all left nodes were listed before the root of that subtree. Symmetrically for the right subtree.

Rigorous enough for me, I hope it is clear for you.

---
Tags: data-structures, trees, binary-trees, search-trees, binary-search-trees
---


# Question
Title: How to prove $\{\langle M\rangle: L(M)=\emptyset\}$ is undecidable?
Consider the language $$E\_{T M}=\\{\langle M\rangle: L(M)=\emptyset\\}.$$ Prove that $E\_{T M} \in \text{coRE} \backslash\text{R}.$

I proved that $$E\_{T M} \in\text{coRE}$$ using Turing machine I built which recognizes the completement of the language. What left is to show that it is not in $$ R$$

Any suggestions how can I do that?

# Answer
One way to prove that is to reduce complement of A TM to E TM.

For Turing machine M and w as its input. We construct M' as follows:

For input w':

Run M on w:

If M rejected w, reject w'.

Otherwise, accept w'.

It is easy to see that M accepts w if and only if M' belongs to E TM.

From this reduction, we can deduct that E TM beings to coRE. And it doesn't belong to RE. If it does, Then E TM would be computable which contradicts the fact that A TM's complement is reducible to E TM.
> 1 votes

# Answer
$\overline{HALT}\_{TM} \leq\_m E\_{TM}$. Define a machine $H$ on input $\langle M, w \rangle$ as follows:

```
H(<M, w>):
    Construct a machine M' defined as follows:
    M'(x):
        Run M on w for |x| steps
          if (M halts on w after |x| steps)
             Accept x
          else
             Reject x
    Output <M'>

```

If $\langle M, w \rangle \in \overline{HALT}\_{TM}$, then $M$ never halts on $w$, which means $L(M') = \emptyset$ and $\langle M' \rangle \in E\_{TM}$. If $\langle M, w \rangle \notin \overline{HALT}\_{TM}$, then $M$ halts on $w$ after some finite number of steps, $k$, thus, on inputs string $x$ such that $|x| \geq k$, $M'$ accepts $x$, which means $L(M') \neq \emptyset$ and $\langle M' \rangle \notin E\_{TM}$.

Since we can reduce $\overline{HALT}\_{TM}$ to $E\_{TM}$, if $E\_{TM}$ is recognizable, then $\overline{HALT}\_{TM}$ is recognizable and the halting problem is decidable (since we know $HALT\_{TM}$ is recognizable), a contradiction. Thus, $E\_{TM} \notin RE$, which means $E\_{TM} \notin R$.
> 1 votes

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


# Question
Title: When does augmented indexing become easy?
Consider the following problem in 2-party communication complexity, where Alice sends a single message to Bob who must compute the output.

* Alice gets as input a bit vector $X=(x\_1,...,x\_N)$, for some integer N.
* Bob gets as input an index $i \in \[N\]$ and gets $x\_1,\dots,x\_{i-1},x\_{i+1},\dots,x\_N$.

Goal: Bob must output $x\_i$ after receiving a single message from Alice.

When Bob only knows $x\_1,\dots,x\_{i-1}$, this problem is known as **Agumented Indexing** and has a lower bound of $\Omega(N)$ bits, even for randomized protocols with constant error. However, I could not find any results about the variant where Bob knows everything except $x\_i$.

Questions:

1. Is there a randomized protocol that can do better than $O(n)$ bits?
2. If the answer to 1 is yes, is the lower bound for deterministic protocols still $\Omega(n)$?

# Answer
I can answer my own question: Alice just sends the parity of her input to Bob, and from this, Bob can compute the answer, so there is no nontrivial lower bound.
> 1 votes

---
Tags: randomized-algorithms, lower-bounds, communication-complexity
---


# Question
Title: Understanding Whether a Set is an Index Set
I'm struggling to grasp the intuition behind the concept of an index set. By definition, a set $I$ is called an index set if $\forall i,j: i \in I$, $\phi\_i = \phi\_j \implies j \in I$. This implies that if we have a program with indices $i \in I$ and a different program $j$, both computing the same function, then $j$ is also in $I$. Essentially, this set contains all possible program indices that compute the same function. This is clear for me.

There have been discussions regarding whether certain sets are index sets or not, as seen in these questions:

So my question is how to know if a set is index set or not, I still don't get it, even if I understand the idea of the index set. For example, let's take a simpler version of the halting problem where the halting is on its own encoding. This set is not index set why? can you give me the inution of why it's not index set and formal proof? or the sets $A=\\{x∣φ\_x(x)=x^2\\} ,B=B=\\{x∣φ\_x(x)=10\\}$ from the second link.

# Answer
> 1 votes
For your first question about how to prove that the following set is not an index set:

K = { e | e is the code of a machine which halts on e}

Let f be the following function:

f(n) = Code of a machine which halts only on n and gives 1 as output.

I think it is clear why f is a computable function.

We know, By Kleene's fixed point theorem((It is more known as Recursion theorem)) that there is some i which is the code of a machine that computes the same function as f(i)'s machine.

Now, According to f's definition, We know i appears in K. But since f(i) != i and f(i)'s machine halts only on i, f(i) won't appear in K.

In conclusion, we constructed a computable function which has two indices which one of them appears in K but the other one doesn't. So K is not an index set.

For sets A and B, Consider the following functions:

f(n) = Code of a machine which halts only on n and gives n^2 as output. g(n) = Code of a machine which halts only on n and gives 10 as output.

With the same argument which made for K, It can be proven that A and B are not index sets.

I hope my answer would be helpful for you.

---
Tags: computability
---