title: Josephus Problem - A faster Solution

text:
# Question
Title: Josephus Problem - A faster Solution
I came through Josephus problem a little while ago. Problem is stated as follows :

> "People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and proceeds around the circle in a specified direction. After a specified number of people are skipped, the next person is executed. The procedure is repeated with the remaining people, starting with the next person, going in the same direction and skipping the same number of people, until only one person remains, and is freed. The problem — given the number of people, starting point, direction, and number to be skipped — is to choose the position in the initial circle to avoid execution."

*Though I was able to figure out O(n) (n being no. of people & k being specified no of people skipped) solution to this problem using DP.I came to know that a better solution for larger value of n exists O(k\*log(n)),but unable to figure it out.*

Please help me with O(k\*log(n)) solution.

# Answer
> 1 votes
You can find both the $O(n)$ and $O(k.log(n))$ solutions and time complexity analysis here

Here is the $O(k.log(n))$ algorithm:

> For relatively small $k$ we can come up with a better solution than the above recursive solution in $O(n)$. If $k$ is a lot smaller than $n$, then we can delete multiple numbers $(⌊\frac nk⌋)$ in one run without looping over. Afterwards we have $n−⌊\frac nk⌋$ numbers left, and we start with the $(⌊\frac nk⌋⋅n)$-th number. So we have to shift by that many. We can notice that $⌊\frac nk⌋⋅n$ is simply $n (mod \space k)$. And since we removed every $k$-th number, we have to add the number of numbers that we removed before the result index.
>
> Also, we need to handle the case when $n$ becomes less than $k$. In this case, the above optimization would cause an infinite loop.

```
int josephus(int n, int k) {
    if (n == 1)
        return 0;
    if (k == 1)
        return n-1;
    if (k > n)
        return (josephus(n-1, k) + k) % n;
    int cnt = n / k;
    int res = josephus(n - cnt, k);
    res -= n % k;
    if (res < 0)
        res += n;
    else
        res += res / (k - 1);
    return res;
}

```

And here is the time complexity analysis:

> Let us estimate the complexity of this algorithm. Immediately note that the case $n\<k$ is analyzed by the old solution, which will work in this case for $O(k)$. Now consider the algorithm itself. In fact, after every iteration, instead of n numbers, we are left with $n(1−\frac 1k)$ numbers, so the total number of iterations $x$
>
> of the algorithm can be found roughly from the following equation:
>
> $n(1−\frac 1k)x=1$,
>
> on taking logarithm on both sides, we obtain:
>
> $ln(n)+x.ln(1−\frac 1k)=0$, $x=\frac {−ln(n)} {ln(1−\frac1k)}$,
>
> using the decomposition of the logarithm into Taylor series, we obtain an approximate estimate:
>
> $x≈k.ln(n)$
>
> Thus, the complexity of the algorithm is actually $O(k.log(n))$ .

---
Tags: algorithms, dynamic-programming, algorithm-design
---


title: Why are all regular languages in P?

text:
# Question
Title: Why are all regular languages in P?
Just to be clear, I am aware that you can define an accepting DFA for every regular language. My problem is a bit deeper.

Let's say we have a language L which consists of a random half of all binary strings of length at most k. This language is finite, so it is regular. We can of course create a DFA for it, by representing every binary string of up to k length and marking the states corresponding to words in the language as accepting.

However, such a DFA has 2^(k+1) + 1 states - one for every input, one starting state (accepting if the empty word is in the language), and one garbage state for strings longer than k.

If I were to write a program to implement this DFA, it would require an exponential number of instructions (in regard to maximum input length k), since I need to at least allocate memory for every state and map transitions. So it looks like it shouldn't be in P.

Possibly, this DFA can be minimized to have fewer states. I am not aware of any theorem that it is always the case though and for a good reason - if you could minimize any DFA to say, polynomial number of states, then you could do it for all finite languages - like 3SAT over 100 boolean variables, with obvious consequences.

What am I missing here?

# Answer
> 6 votes
Such a DFA is a binary decision tree with depth k. While it does have O(2^k) nodes, in order to reach a leaf you need at most k steps, so deciding whether a word is in L takes O(k) steps. How big the program is is irrelevant for the runtime complexity.

# Answer
> 5 votes
There are two important things you should note:

1. the complexity (of a Turing Machine) is measured by *running time*, and not by the length of the "code", or the number of states.
2. Every DFA can be converted to a TM that just goes right on the tape.

Combine the two ideas, and you get that every DFA can be converted to a TM that accepts the same language and runs in exactly $n$ steps, where $n$ is the size of the input. Hence, every regular language is in $P$.

---
Tags: complexity-theory
---


# Question
Title: Decidability of $\{⟨G⟩ \mid \text{$G$ is CFG and $L(G) ⊈ \Sigma^+$}\}$
I want to prove that the following language is decidable:

$$\mathit{SEQ}\_{\mathit{CFG}} = \\{⟨G⟩ \mid \text{$G$ is CFG and $L(G) ⊈ L$}\\}, \text{ where } L = \Sigma^\* - \\{\epsilon\\}$$

So, I think about the relationship between equality and substrings.

for example, I saw in different questions that when we have $L(G) = L(H)$ we can perform that proof on the $L(G) ⊆ L(H)$.

So can I do that with $L(G) ⊈ L$?

So what is the benefit of saying $L = \Sigma^\* - {\epsilon}$ ? I'm a bit confused. Can anyone help me with this question?

# Answer
The idea is that $L(G) \not\subseteq \Sigma^\* \setminus \\{\epsilon\\}$ iff $\epsilon \in L(G)$.
> 1 votes

---
Tags: formal-languages, context-free, decidability
---


# Question
Title: Existence of good error correcting codes
I recently asked this question and got an answer from Yuval Filmus stating that we can build a solution using error-correcting codes.

More specifically, I'm looking for error correcting codes (for binary alphabet) with **constant** $R\>0$ non-zero **relative** rate, and as high as possible **relative** distance $\delta$.

I know that using this theorem, we can achieve any $\delta \< \frac{1}{2}$. As pointed out by Yuval Filmus's answer to my last question, this is the best $\delta$ we can hope for.

Where can I find a proof that states there is no binary error-correcting code with a relative distance bigger than $\frac{1}{2}$?

# Answer
> 2 votes
This is known as the Plotkin bound.

---
Tags: reference-request, error-correcting-codes
---


# Question
Title: Vector pathing via acceleration with velocity
I'm trying to solve a scenario where I need to find the smallest number of time steps to reach a location in 2d space, where I can manipulate the velocity with an acceleration at each time step where the acceleration has a maximum magnitude of $n$. This sounds vague, so let me clarify:

I have the following scenario:

Where the green ball is the start location, the arrow is its starting velocity, and the red ball is the target location. At any given point, I can change the green ball's velocity with an acceleration vector with *at most* a magnitude of $n$, that is applied at the end of the turn.

As in, the green ball is moved by the velocity vector using the following equation:

$$\text{Location}\_\text{new} = \text{Location}\_\text{old} + \text{Velocity}$$

*then* the velocity vector is updated with the acceleration, using the following equation:

$$\text{Velocity}\_\text{new} = \text{Velocity}\_\text{old} + \text{Acceleration}$$

Below is a more concrete example (where orange is the veolicty):

In this case the ball starts at $(1,3)$ and I want to get it to $(2,1)$. Each "turn" I can change the velocity by adding an acceleration vector that has a maximum magnitude of $1$ (in this case $n=1$). As you can see, this is a pretty simple case, simply remove the horizontal velocity when it's aligned with the target then the vertical when it's aligned again. Of course, it starts to become more complicated once the ball is traveling in a different direction to the target, and an optimized solution would take a diagonal path.

If anyone has any sources for related work, or suggestions it would be greatly appreciated!

Edited to clarify acceleration and explicitly define the movement mechanics

# Answer
> 2 votes
There is a theorem that can be used to characterize the optimal solution, which then makes algorithm design trivial. In particular, you can solve the problem in logarithmic time.

# Theorem

Suppose we are hoping for a solution that uses $k$ time steps. Let $v\_0$ denote the starting velocity vector, $s$ the starting position, and $t$ the target position. Let $d = t - (s + kv\_0)$. Then without loss of generality the solution can use acceleration vectors that all point in direction $d$ (i.e., if there exists a solution, there exists a solution that satisfies this condition). Moreover, there is a solution iff $\\|d\\| \le nk(k-1)/2$. If this condition holds, you can use an acceleration of $a=2d/k(k-1)$ in each time step (the same acceleration in each time step), i.e., an acceleration in direction $d$ with a magnitude chosen appropriately so that you reach the target.

# Proof of the theorem

Why does this solution work? Well, letting $p\_i,v\_i,a\_i$ denote the position, velocity vector, and acceleration at time step $i$, we have $$\begin{align\*} v\_i &= v\_0 + a\_0 + a\_1 + \dots + a\_{i-1}\\ p\_i &= p\_0 + v\_0 + v\_1 + \dots + v\_{i-1}\\ &= p\_0 + i v\_0 + (i-1) a\_0 + (i-2) a\_1 + \dots + a\_{i-2} \end{align\*}$$ Now if $a\_0=a\_1=a\_2=\cdots=a$, then we have $$\begin{align\*} p\_k &= p\_0 + k v\_0 + \[1 + 2 + \dots + (k-1)\] a\\ &= p\_0 + k v\_0 + \frac{1}{2} k(k-1) a \end{align\*}$$ Now note that $p\_0=s$, and our goal is to make $p\_k=t$, so solving this equation for $a$ yields the expression given above.

Why is this the optimal solution? If you look at $(k-1) a\_0 + (k-2) a\_1 + \dots + a\_{k-2}$, if we require $\\|a\_i\\| \le n$ for all $i$, then the magnitude of $(k-1) a\_0 + (k-2) a\_1 + \dots + a\_{k-2}$ is maximized when all $a\_i$ point in the same direction, and moreover, when all $a\_i$ have magnitude $n$.

# Algorithm

This suggests a straightforward algorithm: find the smallest integer $k$ such that

$$\\|t - (s+kv\_0)\\| \le n k(k-1)/2$$

and use the theorem above to output a solution for this $k$. You can use binary search to find the smallest such $k$. The correctness of the algorithm follows immediately from the theorem.

It might be possible to construct a constant time algorithm, as finding $k$ is closely related to solving a quadratic equation, and you might be able to use a closed-form solution for the quadratic equation, but I haven't tried to work out the details, as the difference between log-time vs constant-time might not be worth worrying about -- they will both be extremely fast in practice.

---
Tags: graphs, computational-geometry, shortest-path
---


# Question
Title: What is a guarenteed amount of colors, depending on the graph's arboricity
Let $G=(V,E)$ and denote $d=d(G)$ its maximal degree and $a=a(G)$ its arboricity. My question is: what is the smallest amount of colors $f(a)$, such that a $f(a)$-coloring is guarenteed to exist?

For example, $f(d)=d+1$, because a $d+1$-coloring always exists.

My assumption is that $f(a)=2a$. Because each forest can be colored by $2$ colors (Am I correct?), and by using unique color palleteus, we get a $2a$-coloring.

I would like to ask:

1. Is my explanation correct?
2. Is there a smaller function (depending only on $a$)?

# Answer
> 4 votes
Your explanation is correct.

And, you can not do better than $f(a) = 2a$. For example, take a complete graph on $4$ vertices: $a,b,c,d$. The Arboricity is $2$ since $(a,b), (b,c),$ and $(c,d)$ forms the first tree, and the remaining edges form the second tree. The graph is colorable with exactly four colors.

In fact, the Arboricity of a complete graph on $n$ vertices ($n = even$) is $n/2$ \[link\]. Therefore, the function $f(a) = 2a$ is the best possible you can get.

---
Tags: graphs, colorings
---


# Question
Title: $NTime(2^n) \subseteq NSpace(n^k)$ implies $EXP = PSPACE$?
Assume $NTime(2^n) \subseteq NSpace(n^k)$, for some fixed $k$. Is it possible to imply that $EXP = PSPACE$? and what about $NEXP = PSPACE$? It seems the answer might be YES, because this question seems to be equivalent to the open question $EXP=PSPACE$?
Can it be shown using some padding argument?

# Answer
$\let\c\mathrm$The assumption $$\c{NTIME}(2^n)\subseteq\c{NSPACE}(n^k)\tag1$$ indeed implies $$\c{PSPACE=EXP=NEXP}$$ by a simple padding argument. The inclusions $$\c{PSPACE\subseteq EXP\subseteq NEXP}$$ hold unconditionally. In order to show $\c{NEXP\subseteq PSPACE}$, take an arbitrary language $L\in\c{NEXP}$, and let $c$ be such that $L\in\c{NTIME}(2^{n^c})$. Then the language $$L'=\\{(w,1^n):w\in L,n\ge|w|^c\\}$$ is in $\c{NTIME}(2^n)$, hence $$L'\in\c{NSPACE}(n^k)\subseteq\c{DSPACE}(n^{2k})\subseteq\c{PSPACE}$$ by (1) and Savitch’s theorem. Since $L$ is polynomial-time reducible to $L'$ by means of the function $w\mapsto(w,1^{|w|^c})$, it follows that $L\in\c{PSPACE}$, too.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: All longest paths in a tree cross each other at a single vertex
How to prove that in any tree, all longest paths cross one another in one vertex?

# Answer
You can prove that any longest path contains the center vertices of the tree. It will then follow that all longest paths intersect not only at some vertex, but at the center.
> 2 votes

---
Tags: graphs
---


# Question
Title: Is there a $\Sigma^0_3$ variant of the halting problem?
In terms of the arithmetical hierarchy, the halting problem is known to be $\Sigma^0\_1$-complete, and the so-called *universal halting problem*, is the problem of determining whether a given computer program will halt for every input, is known to be $\Pi^0\_2$-complete.

Is there a natural $\Sigma^0\_3$-complete variant of the halting problem?

# Answer
Here are some natural problems which are complete for $\Sigma^0\_3$:

* Given $\langle M \rangle$, is $L(M)$ cofinite?
* Given $\langle M \rangle$, is $L(M)$ recursive?
* Given $\langle M \rangle$, is $L(M)$ regular?
* Given $\langle M \rangle$, is $L(M)$ context-free?

In all of these, $L(M)$ is the set of inputs on which $M$ halts.

See these lecture notes.
> 7 votes

---
Tags: computability, halting-problem
---


# Question
Title: How to prove the my greedy algorithm for placing guards?
> Given $n$ images placed in indexes $x\_1 \< x\_2 \< ... \< x\_n$ and an endless number of guards, where each guard if placed in index $y$ can protect $\[y-0.5,y+1\]$. I want to protect all images with **minimum** possible number of guards.

My suggestion for an algorithm:

Place a guard at $x\_1+0.5$ then loop from $i=2$ to $i=n$, if image $x\_i$ is protected by the previous guard then do nothing, else place a new guard at point $x\_i+0.5.$

---

I proved that my algorithm returns a valid solution, but am stuck on proving that it returns the minimum solution.

I am trying to prove this claim:

*Let $s\_i$ be the number of guards placed until and including the point $x\_i + 0.5$ Then for each i there is an optimal solution which used exactly $s\_i$ guards until and including the point $x\_i + 0.5.$*

I proved this in 3 pages in case the algorithm adds new guard in step $k$, and only now I discovered a HUGE problem in the induction. what if in step $k$ my algorithm didn't add a new guard?

How can I still prove that the optimal solution which is guaranteed for $k-1$ is still valid (I think in some cases it's not and we need to make some changes to it by moving some or all guards...)?

# Answer
> 2 votes
Here is a simple reasoning that shows your greedy algorithm is correct. No mathematical induction is required.

Call an image critical if the greedy algorithm places a guard $0.5$ after it.

The algorithm ensures that each critical image is more than $1.5$ away from the previous critical image (except the first image, before which there is no image). That means any two critical images are more than $1.5$ apart.

Since a guard covers an interval of length $1.5$, it can cover at most one critical image. So, any solution must place at least as many guards as critical images. The greedy algorithm places exactly one guard for each critical image. So, the greedy algorithm is optimal.$\quad\checkmark$

---
Tags: algorithms, algorithm-analysis, greedy-algorithms
---


title: Average Access time in caches

text:
# Question
Title: Average Access time in caches
I know that the average access time for systems with level 1 caches is:

Average Access Time = Hit time + (Miss Rate x Miss Penalty)

How can this be generalized for n level caches?

# Answer
> 0 votes
If I remember correctly, this is the formula:

Hit time +

(miss rate for cache 1 * (1 - miss rate for cache 2) * miss penalty for cache 1) +

(miss rate for cache 1 * miss rate for cache 2 * miss penalty for cache 2)

Essentially, we just split the case that cache 1 missed into the two cases: cache 2 hit, cache 2 missed.

I believe that if you understand this, it wont be hard to generalize for the $n$ cache levels.

---
Tags: computer-architecture, cache
---


# Question
Title: Find the largest rectangle inscribed in a region partitionable into rectangles
Given a rectilinear polygon, what is an run-time efficient algorithm that finds the largest inscribed rectangle the sides of which either parallel or perpendicular to the sides of the rectilinear polygon? A dumb algorithm to form all the rectangles formed from unordered 4-tuples of the edges, for each of the rectangle check to see if any edge or vertex lies inside it, then choose the one with the largest area. The run time is quintic.

# Answer
Daniels, Milenkovic and Roth \[1\] show how this can be done in $O(n\log^2 n)$ time ($n$ being the number of vertices) even for general polygons (possibly with holes). They also mention that the algorithm from Aggarwal and Suri \[2\] for largest empty rectangle can be adapted to your problem in the rectilinear case, but I haven't thought about how one would do that.

\[1\] Daniels, Milenkovic and Roth. Finding the largest area axis-parallel rectangle in a polygon. https://www.sciencedirect.com/science/article/pii/0925772195000410

\[2\] Aggarwal and Suri. Fast algorithms for computing the largest empty rectangle. https://dl.acm.org/doi/10.1145/41958.41988
> 3 votes

# Answer
After seeing @Tassle's answer, I did a bit Google search and found that the largest empty rectangle is a well researched subject.

In the following, I try to draft an algorithm on my own.

Suppose the polygon has $2n$ sides. There has to be $n$ horizontal and $n$ vertical sides. For simplicity sake, we assume no two horizontal sides of the rectilinear polygon have the same $y$ coordinates, and the same for the vertical sides. A candidate rectangle has to have all its sides coincide with the sides of the rectilinear polygon. Given the top and bottom sides of the candidate rectangle, the left and right sides are determined or the candidate rectangle does not exist. So we need to examine at most $\displaystyle n\choose 2$ candidate rectangles. The complexity of this algorithm is at least quadratic.
> 0 votes

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


title: What's an Instruction Set Architecture

text:
# Question
Title: What's an Instruction Set Architecture
I'm a beginner and I don't understand what an Instruction Set Architecture is (*I read the wikipedia page related to it*).
Can anyone explain it to me in a simple manner please?

# Answer
> 7 votes
It's a description of how a certain processor is designed, e.g. which commands it understands, how many registers it has, how it handles interrupts, etc. Any program you write (in assembly) or compile (e.g. from C) for a specific ISA can run on any processor that uses that ISA.

To run a program compiled for one ISA on a different ISA, you need an emulator that translates commands and potentially simulates registers, etc.

For example, desktop PCs use the x86 ISA family, which is why you can run Windows, Ubuntu, etc on any x86 processor.

Smartphones and Raspberry Pis have processors with the ARM ISA, which is why you can't run regular x86 Windows on a RaspPi, instead requiring one specially built for ARM.

# Answer
> 2 votes
Instruction Set Architecture is the broad concept of defining the nature of instructions in a computer. Classic differential architectures are CISC vs RISC. RISC is a reduced instruction set, and CISC, complex instruction set, is anything else.

A classic difference is an IBM S/360 being a CISC machine. Just look at the edit instructions and you will see what is meant by a complex instruction. An ARM architecture is considered RISC.

But there is more to instruction sets. For examples, are registers primarily used or is a stack primarily employed. How is I/O performed?

For example, a PDP-8, which has a 12 bit word, is considered a CISC processor because of how the instructions are constructed and grouped. So the size of the word is not the determining factor.

There has been an ongoing battle over whether large word instructions where operands are memory locations are more efficient than instructions which primarily address registers or stacks, with instructions that preload stacks.

The portability of code between processors is a function of the specific instruction set for the processors. It is possible to have very similar architectures, even though the instructions are different, and of course the code would not be portable.

On an aside, decades ago I earned my living by writing device drivers and peripheral diagnostics for various computers. About 40 of them. Oddly, the diagnostics were about the same number of bits in size regardless of the computer they ran on. I cannot say what the result of a similar informal analysis would be today, but it would be interesting.

# Answer
> 1 votes
Instruction Set or ***Instruction Set Architecture*** is the part of the computer that contains the commands for the processor to function. This usually would consist of addressing modes, instructions, native data types, registers, memory architecture, interrupt, and exception handling, and external I/O. An example is the x86 and x64 instruction sets which are popular on most computers of today.

---
Tags: cpu
---


title: Does this grammar accept this words?

text:
# Question
Title: Does this grammar accept this words?
I made this grammar:

$S \rightarrow ASa$

$S \rightarrow c$

$A \rightarrow a|b$

And I want to check that it accepts words like $aacaa$, $abcaa$, $babcaaa$, I formed the grammar by thinking about the typical $ a ^ nb ^ n $,but I added what is necessary for my interest.

# Answer
> 1 votes
It looks like the grammar indeed accepts all words of the form $\[b+a\]^nca^n$ (which means, all words that start with any sequence of $n$ $b$'s and $a$'s, and then a single $c$ and afterward exactly $n$ times the letter $a$).

To show why to try to show the two following things:

1. every word accepted by the grammar must be in such form
2. every word with such form has a derivation sequence in the grammar.

The first statement can be easily proved by induction (over sequence derivation length) if you notice that each derivation of $S$ adds only one element to both sides.

The second statement can be much more easily proved, try to think of what derivations are necessary to create such words.

---
Tags: context-free, formal-grammars
---


# Question
Title: Non-convex linear program optimisation with infinite number of OR constraints
I am aware that when we have a linear problem subject to OR constraints, the LP would be a non-convex optimisation problem. For example,

${x = 0}$ OR ${1\<=x\<=2}$.

**My question is in such a situation, is it possible to check if an LP is feasible/infeasible, bounded/unbounded or if it has an optimal value or not**

I could not find much explanation on the internet concerning a detailed explanation of this situation. I'd appreciate it if anyone could explain this in more detail.

Similar questions in other sites:

https://math.stackexchange.com/questions/4158912/infinite-number-of-or-constraints-in-linear-programming

https://stackoverflow.com/questions/50987517/expressing-an-or-constraint-in-linear-programming

# Answer
Yes, it's possible. Let $S$ be the original linear problem, i.e., a conjunction of inequalities. You can form two LPs. One LP has the form $S \land x=0$, which can be solved with a LP solver. The other LP has the form $S \land 1 \le x \le 2$. If either one has a feasible solution, your problem has a feasible solution. This procedure takes polynomial time.

This works if you have a *single* disjunction. If you have an unlimited number of disjunctions, it is still possible to find a solution, but such a naive strategy will take exponential time. You can convert the problem to an instance of integer linear programming (see Express boolean logic operations in zero-one integer linear programming (ILP)) and then use an ILP solver. ILP is of course NP-hard, so there is no method that will be efficient in general on all problem instances, so if you have many disjunctions, you might run into instances that are intractable to solve within your lifetime.
> 1 votes

---
Tags: optimization, linear-programming, constraint-satisfaction
---


# Question
Title: Time complexity of the triangle factoring problem
We define the triangle factoring problem as in Triangle Factors in Random Graphs, which is, given a simple undirected graph of $3n$ nodes, find if there's a subset of edges dividing vertices into $n$ vertex-disjoint triangles.

I've seen some papers discussing about the probability of such a factoring exists, but I'm unaware of any non-trivial algorithm solving this problem or any reductions. Is it NP-Complete? or, is it in P?

# Answer
> 3 votes
The triangle factor problem is NP-complete in general \[1\] (and even for graphs of clique number 3), but solvable in polynomial time for some restricted graph classes like chordal graphs \[2,3\]. These references will get you up to speed easily.

---

\[1\] Garey, Michael R., and David S. Johnson. "Computers and Intractability: A Guide to the Theory of NP-completeness" (1979).

\[2\] Guruswami, Venkatesan, C. Pandu Rangan, Maw-Shang Chang, Gerard J. Chang, and Chak-Kuen Wong. "The vertex-disjoint triangles problem." In International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 26-37. Springer, Berlin, Heidelberg, 1998.

\[3\] Dahlhaus, Elias, and Marek Karpinski. "Matching and multidimensional matching in chordal and strongly chordal graphs." Discrete Applied Mathematics 84, no. 1-3 (1998): 79-91.

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


# Question
Title: Does 1NF require that there can be no duplicate rows?
From Database System Concepts, by Silberschatz, Korth and Sudarshan :

> A domain is atomic if elements of the domain are considered to be indivisible units. We say that a relation schema `R` is **in ﬁrst normal form (1NF)** if the domains of all attributes of `R` are atomic.

From https://stackoverflow.com/a/724032/156458

> 1NF is the most basic of normal forms - each cell in a table must contain only one piece of information, and **there can be no duplicate rows**.

If I am correct, "there can be no duplicate rows" in the second definition means exactly that there must exist at least one candidate key in the relation schema.

I wonder if the two definitions of 1NF above are the same?

In particular, is it correct that "there can be no duplicate rows" can't be implied by "the domains of all attributes of `R` are atomic"?

Thanks.

---

**Updated:**

This book seems to say that having a primary key implies atomic and is it correct?

> In first normal form (INF), related attributes are organized into separate **tables, each with a primary key**. A primary key is an attribute or set of attributes that uniquely defines a tuple. Thus, **if a table is in INF, entities within the data model contain no attributes that repeat as groups.** W. Kent has explained that in INF, all occurrences of a record must contain the same number of fields. In INF, each data cell (defined by a specific tuple and attribute) in the table will contain only atomic values.

# Answer
> 4 votes
What was called 1NF in the past is considered nowadays part of the definition of the Relational Data Model itself: each attribute must be a single value, neither composed, nor repeated. When we talk about relations we assume implicitly this fact, since structures with non-flat attributes are not considered proper relations.

Note, however, that there exists alternative models, called non-1NF models or NRC which are based on the concept of relations with possibly other relations as values inside tuples (so it is a kind of Nested Relational Model). Such models, presented in the scientific literature but not implemented in commercial systems, are in some sense a sort of “bridge” towards the late object-oriented data model, that allow more complex kind of data (and that have a concept of association which differs from that of foreign key).

A different aspect is that relations are sets, and not multisets (that is they cannot contains duplicate rows). This is a basic principle of the Relational Data Model: we assume that a relation is just a set, stop. For more details, see this answer.

But you should keep in mind the these are mainly theorical aspects, useful when reasoning about relations, about languages to operate on them (for instance the Relational Algebra), and about theories developed on them (for instance the Normalization Theory).

In practice, however, things can be quite different: for instance in Relational Database Management Systems you can have “relations” without keys or unique attributes, so that they can have duplicate rows. Also, you can have composed data types for attributes of records, like arrays (or, worse, people sometimes put multiple values in an attribute maybe as a single string with commas separating the intended values).

# Answer
> 1 votes
With continuation to your previous question Does 2NF require 1NF?

Theoretically aspects say that each cell (value) in a table (relation) must contain only one piece of information, and there can be no duplicate rows.

From Wiki

> According to Date's definition, a table is in first normal form if and only if it is "isomorphic to some relation", which means, specifically, that it satisfies the following five conditions:
>
> 1\] There's no top-to-bottom ordering to the rows.
>
> 2\] There's no left-to-right ordering to the columns.
>
> 3\] There are no duplicate rows.
>
> 4\] Every row-and-column intersection contains exactly one value from the applicable domain (and nothing else).
>
> 5\] All columns are regular \[i.e. rows have no hidden components such as row IDs, object IDs, or hidden timestamps\].
>
> Violation of any of these conditions would mean that the table is not strictly relational, and therefore that it is not in first normal form.

```
You argument: "...is it correct that "there can be no duplicate rows"
can't be implied by "the domains of all attributes of R are atomic"?..."

```

Basic definition states that no cell in given attribute(s) should be multivalued and composite, or in other words they should be atomic. But being atomic doesn't mean that they are also in non-duplicate state. Duplicity can exist, but there are 5 explicit constraints and out of that one tells you to avoid duplicity. So, actually with basic definition of 1NF follows five other constraints.

# Answer
> 1 votes
The requirement for unique rows is not part of the definition of 1NF, rather it is a *prerequisite* for normalizing to 1NF.

There is a step before first normal form which is called *unnormalized relations* (described in Codd, E.F. "Further Normalisation of the Data Base Relational Model"). In this step the data is described as relations, which means rows have to be unique, per the definition of relation. But there is no constraint on the domains, so you can have attributes which themselves contain relations, in arbitrary depth.

First normal form means eliminating non-simple domains, which means an attribute should not have relations as values. Normalizing is the process of eliminating nested tables by turning nested tables into stand-alone tables, instead connected to the parent row through a foreign key. (described in Codd, E.F (1970). "A Relational Model of Data for Large Shared Data Banks".)

Note that SQL and hence most relational databases does not allow or support nested tables in the first place, so data have to be in 1NF before it can even be entered.

> is it correct that "there can be no duplicate rows" can't be implied by "the domains of all attributes of R are atomic"?

It is implied by the definition of relation. Since relations are sets of tuples it follows that tuples are distinct. So the rows are distinct *whether or not* the domains are atomic.

As for the three quotes:

The first quote is more or less correct, although "indivisible units" is somewhat misleading - it just means anything which is not a relation.

The second quote is just wrong. Codd specifically describes normalization to first normal form as requiring relations with primary keys as a starting point.

The third quote is ambiguous. It implies that for a table to be in 1NF it need have primary keys. This is technically correct, but it is not the definition of 1NF, it is a prerequisite. "No attributes that repeat as groups" is also rather ambiguous. A relation cannot have a *varying* number of attributes, that would be against the definition of relation, but I'm not sure what "repeat as groups" is supposed to mean.

---
Tags: database-theory
---


title: Does $NP^{SAT}=NP^{NP}$?

text:
# Question
Title: Does $NP^{SAT}=NP^{NP}$?
Does $NP^{SAT}=NP^{NP}$?
We can see easily that $NP^{SAT}\subseteq NP^{NP}$, because $SAT \in NP$.
But is the other side $NP^{NP}\subseteq NP^{SAT}$ also true? If yes, how can we prove it?

# Answer
> 5 votes
Yes, because $\mathsf{SAT}$ is $\mathsf{NP}$-complete.

Let $L\in\mathsf{NP}^\mathsf{NP}$. This means that there exists $A\in\mathsf{NP}$ such that $L\in\mathsf{NP}^A$. But you can replace any oracle query to the set $A$ with a polynomial-time deterministic computation that uses oracle queries to $\mathsf{SAT}$. Thus, $L\in\mathsf{NP}^\mathsf{SAT}$.

---
Tags: complexity-theory, turing-machines, np, oracles
---


# Question
Title: How to simplify the query qualification?
Given the following DB and query :

Now if we need to simplify the query qualification, here is the answer from the book (Principle of distributed database systems, third edition) :

My question is in the highlighted bracket, I think this should be (p1 OR (p2 AND (Not p2))) instead of the one written because we have the following rule :

Is that right ?

# Answer
> 2 votes
You are right, but it doesn't really matter — it still simplifies to $p\_1$.

---
Tags: databases, relational-algebra
---


# Question
Title: Proving $b_1! \cdots b_k! < (b_1 + \cdots + b_k+1)!$
I can't figure out how to solve this problem:

> Let $b\_1,b\_2,\ldots,b\_k$ be positive integers with sum less than $n$. Prove that $$b\_1!b\_2! \cdots b\_k! \< n!.$$

# Answer
> 4 votes
The number of ways to divide a set of $b\_1 + \cdots + b\_k$ items into $k$ sets of sizes $b\_1,\ldots,b\_k$ is $$ \frac{(b\_1 + \cdots + b\_k)!}{b\_1! \cdots b\_k!}. $$ You take it from here.

# Answer
> 1 votes
Show that if $0 \< n ≤ m$ then $n!m! \< (n-1)!(m+1)!$.

If $b\_1 + b\_2 + \dots + b\_k = s$, use this to show that $b\_1!b\_2! \cdots b\_k! \< s!$ if there are at least two non-zero $b\_i$. (Use induction over the sum of all but the largest element.)

Comparing to $(s+1)!$ makes the statement true even if there is only one non-zero $b\_i$. If all $b\_i$ are zero, it is false.

---
Tags: number-theory
---


# Question
Title: How do you have a type typed "Type" when implementing a programming language?
I am working on the *base* of a language model, and am wondering how to represent the base type, which is a type `Type`. I have heard of an "infinite chain of types", but (a) I can't seem to find it on the internet while searching anymore, and (b) I am not sure if that's what I need or what it really means in practice.

Basically, I have a system in the language like this:

```
type User
type String
type X
...

```

Internally these get compiled to something like this:

```
[
  {
    type: 'Type',
    name: 'User'
  },
  {
    type: 'Type',
    name: 'String'
  },
  ...
]

```

But actually, the `type: 'Type'` gets further compiled not pointing to the string `'Type'`, but to the actual `Type` object:

```
[
  {
    type: theTypeObject,
    name: 'User'
  },
  {
    type: theTypeObject,
    name: 'String'
  },
  ...
]

```

So then the problem is, I need to now define or specify the "type type" itself:

```
type Type

```

which I try represent in a similar way, so now we have:

```
[
  {
    type: 'Type',
    name: 'Type'
  },
  ...
]

```

which is:

```
let theTypeObject = { name: 'Type' }
typeTypeObject.type = theTypeObject

```

Is that correct? What is this really saying? It is a circular structure, does this even make sense conceptually?

What would be better to do in this situation? Or is this perfectly acceptable? Basically I would like to understand how to explain what this circular structure even means, because it just makes me confused.

> The type "Type" is typed "Type". It is an element of itself...

That doesn't seem logically possible. So what should I do?

# Answer
I think what you might have found in your previous researches might be a pure type system.

In a pure type system, to avoid having "Type" being a "Type" at the same level that "Int" is a "Type", you would define another layer of "Types" where you would define "Type" as the entire first layer (and you would define this layer in the next one, and so on)

In practice, you could define your base types as "types", and the next layer would be kinds. The type "type" would be a kind. You might also want to consider functions of types to types as another kind.
> 1 votes

# Answer
Take the Swift language as an example. In Swift, lots of things are defined in the standard library that would be built into other languages, like Int and Double, arrays etc.

Swift has five basic types: class, struct, enum, tuple, and closure. These are built into the compiler. None of them can be used directly, but every type must be based on one of these five basic types. To describe any other type, you would possibly have an indication that it is a type, then an indication of which of the five basic types the type is based on, and then more information depending on the basic type. (A Swift compiler written in Swift would like use an enum with five cases "class", "struct", "enum", "tuple" and "closure").

You don't describe these basic types at all, you just follow the specification of the language. Of course you are free to declare a sixth basic type and call it "basictype", and create six types manually which have a basic type of "basictype", but I don't see that as being too useful.
> 0 votes

# Answer
I suspect that part of the problem might be your choice of root type.

A root type typically is a type with very few properties, because (by definition) it's the union of properties of all types. Yet a `Type` type, which needs to handle the complexity of your type system will have quite a few properties.

Having said that, for a language *model* it does not really matter what that your `Type` has a type that is itself `Type`. That's just how you model it. Models are just descriptions. But you say "compile", and that means you're actually going to **do** things. And that means you're dealing with such practical matters as code and data.

In particular, type systems are generally used to represent object types, where objects are combinations of code and data. Sure, there's a data property `type name` which has itself type `String` and can have a value of `"Type"`. But that data is mostly meaningless without code.

Also, code doesn't live in its self-shaped world. Your code will not execute in an environment that already understood your type system, that's the whole point why you need code in the first place. It's your code and data which will need to materialize your type system in more primitive terms. Again, unlike a model, which can live in its own world.
> -1 votes

---
Tags: type-theory, modelling
---


# Question
Title: Shortest walk in a grid with turnstiles and waypoint
This video shows a grid maze with a type of tile that I'd call *turnstiles*.

The mechanics of those tiles are described below.

* A turnstile tile has two bars on adjacent sides of the tile.
* You cannot step into a turnstile tile if it would mean crossing a bar.
* You can exit a turnstile tile in any direction.
* If you exit the tile in a direction where there was one of the bars, then the pair of bars *rotate* by a 1/4 turn such that there's no more bar in the direction you exited the tile from (see video at 7:02).

Here's an example before and after exiting a turnstile tile:

Turns out, finding the shortest path from A to B in a maze containing this kind of tile is fairly easy. Long story short: even with turnstiles, the shortest path don't involve revisiting a node, therefore the usual algorithms work.

However, if we introduce a single waypoint, like fetching a key before going to the door, then we can no longer ignore the state in which we left the turnstiles. We might indeed revisit some tiles. Although taking the shortest path from A to K and then from K to B would produce a valid A-K-B walk, we can easily construct examples where this wouldn't produce the shortest walk overall, like this one:

I couldn't figure out a way to turn this problem into a regular shortest path without blowing up the graph size exponentially with the number of turnstiles.

So, if the problem of finding the shortest walk with a single waypoint in a grid maze with turnstiles is NP-hard, any idea of proof?

If it's not NP-hard, how do we find a solution efficiently?

# Answer
> 1 votes
I guess this is another non-answer.

---

### $k$ waypoints $\in \mathrm{NP\ hard}$

The generalization of this problem ($k$ waypoints) is NP-hard even without turnstiles.

The reduction can be seen in Amiri et al. \[\] from subset traveling salesman problem (TSP):

> In the subset TSP, the task is to find a shortest closed walk that visits a given subset of vertices \[38\]. As optimal routes for WRP \[Waypoint Routing Problem\] and subset TSP traverse every edge at most twice, optimal solutions for both are identical when $\forall e \in E : c(e) \geq 2$.

Note that this also holds for planar graphs such as ours.

### $1$ waypoint and $0$ turnstiles $\in \mathrm{P}$

That being said, when $k = 1$ and there are *no* turnstiles, we can solve this in polynomial time via a reduction to minimum cost integer flow (Amiri et al. \[\]).

> Indeed, the common endpoint $w$ can be leveraged to employ a reduction to an integer flow formulation: introduce a super-source $S^+$ and a super-destination $T^+$, connect $S^+$ to $s$ and $t$, and $T^+$ to $w$ with two links, all of unit capacity...

> Next, solve the minimum cost integer flow problem from $S^+$ to $T^+$ with a demand of $2$. By performing flow decomposition and removing $S^+$, $T^+$, we obtain an $s - w$ and a $w - t$ flow, whose combined length is minimum.

---

### $1$ waypoint and $k$ turnstiles and $c(e) = 1$ $\in \mathrm{NP\ hard}$, maybe?

If we restrict each edge to having capacity $1$, meaning it can only be included once in the shortest path, then we can make a reduction from the NP-complete $2$-link-disjoint paths problem. See section 2.3 of Amiri et al. \[2\] for the full proof. The idea is that with $c(e) = 1$ we can make our graph directed by using turnstiles to establish the direction of each edge.

However, this is only true for non-planar graphs. If we restrict it to planar graphs, the question appears to be open \[3\]. That being said, it is known to be in P under certain constraints \[4\], but still unclear for the general case.

### $1$ waypoint and $k$ turnstiles and $c(e) = 2$ $\in$ ???

I'm not quite sure where your problem lies, but the allowance of turnstiles imposes a certain directionality on the graph even in the presence of $c(e) = 2$ which would incline me to believe this is NP-hard. Though, the results on the edge-disjoint path problem with congestion make me think there may be a poly time solution for $1$ waypoint.

---

$^1$ https://arxiv.org/abs/1708.09827

$^2$ https://arxiv.org/abs/1705.00055

$^3$ https://www.sciencedirect.com/science/article/pii/0304397580900092

$^4$ https://dl.acm.org/doi/10.1145/1132516.1132621

# Answer
> 3 votes
This is not an answer, but also too many words for a comment and I didn't want to post a handful of comments.

I am not sure if this is NP-hard or not, but I have some ideas for a proof.

---

### Proving NP-hard

I would take an approach similar to the NP-hardness proof for Super Mario Bros. Please watch this lecture: https://youtu.be/7d73E1DiH0w?t=2851

First you would need to change your question to "Has Path" rather than "Shortest Path". That is, does there exist a path from start to finish at all? For example, the answer is clearly no for the following (where green is start and red is finish):

We can then try to reduce a given 3SAT instance to this problem. My idea is not complete, but the idea is to use turnstiles as boolean "switches" which will determine a literal true or false.

For example, let's say (A) means a literal is false and (B) means a literal is true:

We can construct variables in such a way that the given path from source to end only allows one of the literals to be true. For example, the following would be such a variable:

If the top path is taken then $x$ is true, if the bottom is taken then the $x$ is false. Notice that if the path were attempted $A \rightarrow \neg X \rightarrow X$ that $X$ would be blocked and could not be flipped unless we go back through $\neg X$ which would flip $\neg X$ back to false. So this is a valid gadget that says "$X$ can only be true or false and the path from $A$ to $B$ will determine that value."

Next we need to construct a clause gadget. My idea for this would be to essentially have a similar setup to the example above where every instance of $X$ can be "set" to true at the same time by flipping its turnstile OR every instance of $\neg X$ can be "set" to true at the same time by flipping its turnstile but NOT both.

We need to construct this clause gadget in such a way that the literal and its negation cannot be both true at the same time. My idea was the following.

Let's say we have a SAT formula: $(x \lor \ldots) \land (\neg x \lor \ldots)$. We could construct a clause like:

If we had $x$ in multiple clauses like: $(x \lor \ldots) \land (\neg x \lor \ldots) \land (x \lor \ldots)$. We could have the following:

The important thing to note here is that you can't flip the $x$ turnstiles while also flipping the $\neg x$ turnstiles.

Then if we have multiple variables like: $(x \lor y \ldots) \land (\neg x \lor y \ldots) \land (x \lor \neg y \ldots)$. We would first route the path through $x$ then through $y$:

Again note that if we tried to choose $x$, the $x$ and $\neg x$ paths reconnect when routing to $y$. However, going "back" one path you would still not be able to "set" the other turnstiles because they are blocking a backward entrance due to their positioning, so the only route forward after $x$ is determine is to continue on to $y$ if you want to make it from start to finish.

For example, a valid solution to our 3SAT formula would be $x$ is true and $y$ is true. This would correspond to the following path from start ($x$) to finish (red). The path is shown in green:

---

The last thing we would need to do is verify that all clauses have at least one turnstile "switched" on. You can see in my example we could also get a path from start to finish with $x$ is false and $y$ is false even though this does not satisfy the 3SAT formula.

In the Super Mario example, the clauses are verified by "unlocking" a super star which allows Mario to survive a flame walk to the end. We don't exactly have this luxury in our game. By flipping our turnstiles we can't "unlock" anything special, like a path to the end. You could attempt to accomplish this with waypoints, but the waypoints don't actually add much because a path could go to the waypoint, then go exactly back to start and continue on as normal and it has effectively "visited" the waypoint without having to change its solve path.

One idea I had for "unlocking" something by completing a clause was the following:

If $x$, $y$ or $z$ are "set" then they can (exactly one at a time) go into the bottom chamber and flip the turnstile blocking upward entry from `A`. The idea would be that if you put a waypoint below `A` for each clause and you hook up the end of the variable chain to the right most `A` then you hook up `B` to the `A` of the clause to the left and chain them together like that. Then the `B` of the leftmost clause would be the end. The issue is what I just mentioned, we could just go to the way points then go all the way back to the start, then just set a literal in the first clause an exit.

So these would be my main ideas for constructing a reduction, however its clearly incomplete. If we added in "one-way" blocks or waypoints that only allowed the path to go in one direction but not back then I think this may work because you could trap a regular waypoint behind a one-way block.

---

The other big issue I did not mention but you would realize if you watched the Super Mario reduction is that the graph I have been showing is non-planar whereas the game is played on a planar graph. We would also need someway to establish crossovers which I think is nontrivial. One idea would be to do something like this:

This is clearly an issue however because if the green path was the "exit" of setting $x$ and the red path was the "entry" of setting $\neg x$ in a clause then you could exit setting $x$ and turn right to effectively also set $\neg x$. This is not allowed.

So you would need to resolve these crossovers as well.

Hopefully someone can take some of these ideas and run with them. It has the vibes of an NP-hard problem since you can essentially encode the turnstiles as bits and *almost* encode a 3SAT equation into them, but I'm not convinced yet.

# Answer
> 0 votes
To decide if there is a path in $O(N)$ for a $N$ cells maze , you can simply run a BFS from start (As ryan already said, here, one should not talk of Dijkstra meaning priority queue...). So if you can reach both, the waypoint and the exit, it exists a solution.

**Proof**

You already proved that on a simple path, there is no need to consider the re-orientation of turnstiles. Indeed, you already reached this cell.

Another point is that you can always go back your path as turnstiles always get open to the leaving direction. So any cell reachable from start is reachable from any other reached cell, and in particular, the waypoint.

This of course does not guarantee you find the shortest path, your exemple shows it perfectly. But gives you an upper bound.

---
Tags: np-hard, shortest-path
---


title: What are the limits of Boolean Algebra?

text:
# Question
Title: What are the limits of Boolean Algebra?
Any decision problem algorithm can be represented as a boolean expression. The rules of boolean algebra (De Morgan's law, distributivity, etc.) can be used to manipulate and simplify that expression, similar to normal algebra.

1. Can any boolean expression be derived to its most simple form (i.e. has the least number of NOT, OR, and AND symbols) solely through these manipulations?
2. If the answer is yes, then why would that not be a foolproof way to find the most efficient form of any desired decision problem algorithm? For example, take some naive, slow algorithm for the Prime Decision Problem for numbers with 64 bits. Why could you not just start applying manipulations on that boolean expression until you have what you know is the most efficient algorithm?

# Answer
> 2 votes
According to Wikipedia,

> A powerful and nontrivial metatheorem states that any theorem of holds for all Boolean algebras. Conversely, an identity that holds for an arbitrary nontrivial Boolean algebra also holds in . Hence all the mathematical content of Boolean algebra is captured by .

What this means is that if $\phi = \psi$ is an equation in Boolean algebra, involving any number of variables, then $\phi = \psi$ holds in all Boolean algebras iff it holds in the two-element Boolean algebra , i.e., when the variables are only allowed to have the values $0,1$. This means that $\phi = \psi$ can be proved using any complete axiomatization of Boolean algebras, for example Huntington's.

Let's sketch how to prove this theorem. In order to reduce confusion, let us write $\phi \stackrel{0,1}= \psi$ if $\phi(\alpha) = \psi(\alpha)$ for any $0,1$-evaluation of the variables in $\phi,\psi$, and let us write $\phi \approx \psi$ if the axioms of Boolean algebra imply that $\phi = \psi$. We would like to show that $\phi \stackrel{0,1}= \psi$ iff $\phi \approx \psi$. The proof is by induction on the number of variables.

If $\phi,\psi$ involve no variables then $\phi \stackrel{0,1}= b \stackrel{0,1}= \psi$ for some $b \in \\{0,1\\}$. Simple structural induction shows that if $\phi \stackrel{0,1}= b$ then $\phi \approx b$, completing the proof in this case.

For the inductive case, let $x$ be an arbitrary variable appearing in $\phi$ and $\psi$. Define $N\[\phi\] = (x \land \phi|\_{x=1}) \lor (\lnot x \land \phi|\_{x=0})$. If we $\phi \stackrel{0,1}= \psi$ then $\phi|\_{x=b} \stackrel{0,1}= \psi|\_{x=b}$ for $b \in \\{0,1\\}$. The inductive hypothesis shows that $\phi\_{x=b} \approx \psi\_{x=b}$ for $b \in \\{0,1\\}$, and it easily follows that $N\[\phi\] \approx N\[\psi\]$. Hence to complete the proof, all we need to do is show that $\phi \approx N\[\phi\]$.

We show that $\phi \approx N\[\phi\]$ by structural induction. This amounts to proving finitely many identities involving finitely many variables. The base cases $\phi=0,1,x,y$ (where $y \neq x$ is a variable) are easy. There are three inductive cases for the three connectives $\lnot,\lor,\land$. As an example, consider $\phi = \lnot \chi$. We know that $\chi \approx N\[\chi\]$, and would like to derive $\lnot \chi \approx N\[\lnot \chi\]$. This amounts to proving $$ \lnot \[(x \land \chi|\_{x=1}) \lor (\lnot x \land \chi\_{x=0})\] \approx (x \land \lnot \chi|\_{x=1}) \lor (\lnot x \land \lnot \chi\_{x=0}), $$ an equation in three variables.

---

Finding the minimal expression equivalent to a given one is hard. Indeed, given a DNF, determining whether the minimal equivalent expression has size 1 is NP-complete (since it is easy to check whether a given DNF is a tautology).

The Formula-MCSP problem is, given a *truth table* of a function and a parameter $s$, to determine whether the function can be represented by a formula of size at most $s$. It is conjectured that Formula-MCSP is NP-complete. Your problem is likely harder: variants are known to be $\Pi\_2^p$-complete.

In some cases, we can provably show that some equations are hard to prove. For example, suppose that we want to prove that a CNF is unsatisfiable (equals 0), and that we are only allowed to use rearrangement laws (commutativity and associativity of $\lor$ and $\land$), absorption laws ($a \land a = a$ and $a \lor a = a$), constant absorption laws, and the Resolution rule $(a \lor b) \land (\lnot a \lor c) \approx b \lor c$. This axiomatization is complete — if the CNF is unsatisfiable then it can prove that it equals 0 — but explicit examples are known in which every proof has size which is exponential in the number of variables.

---
Tags: algorithms, logic, boolean-algebra
---


# Question
Title: Definition and use of a Boolean equation system
According to google, a *system of boolean equations* is defined as follows

> Essentially, a Boolean equation system is an ordered sequence of fixed point equations over Boolean variables, with associated signs, µ and ν, specifying the polarity of the fixed points. The equations are of the form σx = α, where α is a positive Boolean expression.

After reading a bit more, my interpretation is as follows. Is my interpretation correct?

For each variable $x\_i$ we have a boolean formula without negations and for each such $x\_i$ we also have a "preferred" assignment (0 or 1). It is the highest priority to assign a value to each variable so that the formula for $x\_0$ is such that $x\_0$ assumes its preferred value, even if it means that all other variables must assume their non-preferred value. After that (regardless of whether it failed for $x\_0$), the next top priority is to try to have $x\_1$ assume its preferred value, etc.

The main question is, what could possibly be the use of such a system? I don't mean a use in real life, but can it e.g. be used to help solving more conventional problems?

# Answer
I am not used to this definition. Instead, the definition I am used to states that a system of boolean equations has the form

$$\begin{align\*} f\_1(x\_1,\dots,x\_n)&=0\\ \vdots\\ f\_m(x\_1,\dots,x\_n)&=0. \end{align\*}$$

where $x\_1,\dots,x\_n$ are boolean variables and $f\_1,\dots,f\_m$ are boolean functions. The values $v\_1,\dots,v\_n$ are a solution to the system of equations iff $f\_i(v\_1,\dots,v\_n)=0$ for all $i$.

This is useful, for instance, in formal verification. For example, $f\_i$ might represent one bit of output of some boolean circuit.
> 1 votes

---
Tags: boolean-algebra
---


# Question
Title: Find optimal play by optimizing orders of each player alternatingly
A zero-sum game for two players allows a player to take no action during a turn. Can I reach optimal play (where both players always choose the best possible action in each turn) by the following scheme?

1. Randomly choose move orders $A\_{1}$: $O\_{A1}, O\_{A2}, ...$ for player A over turns $1,2,...$
2. Find player B's optimal orders $B\_{1}$: $O\_{B1}, O\_{B2}, ...$ for countering $A\_{1}$ (with an integer linear programming solver). If $B\_{1}$ makes some orders $O\_{Ai}$ in $A\_{1}$ invalid, pretend that player A takes no action during turn $i$. For example, capturing a piece can make $O\_{A3}$ an invalid order. In this case, pretend $O\_{A3}$ does not exist.
3. Same as step 2 except we find player A's optimal orders $A\_{2}$ that counters $B\_{1}$.
4. Repeat steps 2 and 3 until the orders of both sides don't change.

Optimal play, which is a Nash equilibrium, exists. The scheme looks like coordinated descent except for the bit that ignores invalid moves.

I ask this question because I am trying to use an integer linear programming solver instead of implementing minimax for finding optimal play.

# Answer
No. If the game is the prisoner's dilemma, depending on the random choices, this could converge to "everyone defects", which is not (globally) optimal; the (globally) optimal solution is "everyone cooperates". Also, it is possible that it may fail to converge at all and loop forever. Even if it does converge, it may only converge to a local optimum, not a global optimum.
> 0 votes

---
Tags: optimization, linear-programming, integer-programming, game-theory, minimax
---


# Question
Title: Deterministic Pushdown Automata that accepts #a = #b
I am trying to create a DPDA that accepts words from the following Language:

$$ L = \\{wx \\; | \\;w \in \\{a,b\\}^\*, \\#a = \\#b \\} $$

My intuition was to initially put an $x$ on the stack and then write an unlimited amount of $a$ or $b$, while both operations put an $B$ or $A$ on the stack. Then, in the second last state we can write an limited amount of $a$ and $b$ for popping an $A$ or $B$ from the stack.This ensures that the amount of $a$ and $b$ are equal before we can read the initial $x$ from the stack. As a last step, we read $x$ as the last element of the stack. However, building this determinstic seems too complex. Any hints?

# Answer
> 1 votes
You have to keep track of $\\#a - \\#b$ at each point of the input. This number can become negative, so say the number of excess $a$ is represented by that many $A$ on the stack, and the number of excess $b$ by $B$s. If at the end of the string there is no excess (empty stack), accept.

Details of the construction are left to the gentle reader.

# Answer
> 1 votes
Reading a $a$ and a $b$ should "compensate" each other. For example, reading a $a$ could push a $A$ or remove a $B$ depending on the stack, and conversely when reading a $b$.

You can then accept when the stack is empty (or contains the initial symbol).

---
Tags: pushdown-automata
---


# Question
Title: Is $(\log n)^c = O(n)$ for any constant $c$?
Is $(\log n)^c = O(n)$ for any constant $c$?

For example, is $(\log n)^5 = O(n)$?

# Answer
Yes, $\log^k n=o(n)$ for any constant $k$. Even stronger, for any $a,b\>0$ two constants, we have $\log^a n=o(n^b)$.

Try showing using the limit definition of big O, and by repeatedly using L'Hospital's rule.

The big-O definition using limits: $f=O(g)$ if $\limsup\_{n\rightarrow \infty}{\frac{f(n)}{g(n)}}=c$ for some constant $c\ge 0$.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: NP-Hardness of Half-SAT (at least half clauses)
I'm solving Problem 14.14 of What can be computed?.

> 14.14 Consider the computational problem HALFSAT defined as follows. The input is a Boolean formula B in CNF. If it is impossible to satisfy at least half of B’s clauses, the solution is “no”. Otherwise a solution is a truth assignment that does satisfy at least half of B’s clauses. For example, the input “(x1 OR NOT x2) AND (x2) AND (NOT x1)” is a positive instance, because the truth assignment “x1=1,x2=1” satisfies two of the three clauses and is therefore a positive solution. Prove that HALFSAT is NP-hard.

There some variants of half-SAT in this community, but I couldn't find the way of reduction to this version of HALF-SAT problem.

Is there any suggestion to solve this problem?

# Answer
If all clauses must be non-empty, then your problem isn't NP-hard, since *every* CNF can be half-satisfied: a random assignment satisfies at least half of the clauses in expectation, and so some assignment satisfies at least half of the clauses.

If clauses are allowed to be empty (unsatisfiable), then there is an easy reduction from SAT: given an instance of SAT with $m$ clauses, add $m$ unsatisfiable clauses. The new instance is half-satisfiable iff the original one is satisfiable.
> 3 votes

---
Tags: np-hard, satisfiability
---


# Question
Title: Sliding window max/min algorithm without dynamic allocations
I'm working on a suite of DSP tools in Rust, and one of the features of the library is a collection of windowed statistics (mean, RMS, min, max, median, etc) on streams of floating-point samples. For instance, if the window size is 7, then the windowed min is the smallest of the last 7 items in the stream (the window), and the windowed mean is the average of the last 7 items in the stream. The user provides an iterator of floats and a fixed-size mutable slice/array of floats as inputs and gets back an iterator that lazily calculates the desired stat one sample at a time. The contents of the float slice/array become the initial window and can be used as scratch space internally. This slice/array also determines the sliding window size.

```
// A sliding mean with a window size of 64, initially filled with 0.42.
let sample_iter = /* an iterator that yields floats */;
let buffer = [0.42; 64];
let sliding_mean_iter = SlidingMean::new(sample_iter, buffer);

```

I'd ideally like to have my library also usable in an embedded environment, and so far I've been able to do so by not using any dynamic memory allocations.

As of now, I have efficient mean and RMS implementations, but I'm stumped on the windowed min/max. Looking up sliding window min/max algorithms online\[\]\[\], I see that:

1. A naive approach of scanning the window after each update leads to an `O(nk)` runtime, where `n` is the length of the input iterator and `k` is the window length. This feels like it could be inefficient for larger window sizes.
2. Using a deque allows for an efficient implementation of `O(n)` (with amortized insertion of `O(1)`), but using a deque would require dynamic allocations.
3. Since the passed-in buffer is overloaded to both set the initial window contents as well as to serve as scratch space, I can't mess with the type of that, it has to stay as a slice/array of plain floats. This means I can't make it an array of (int, float) to store array indices alongside the data, for example.

Are there any clever tricks or optimizations I can use to have my cake (efficient sliding min/max) and eat it too (avoid having memory allocations)?

Here's a walkthrough example of a sliding max with window length 3:

```
Initial samples: {3 4 3 1 5 2 7 3 4 1}

Step 1: {[3 4 3] 1 5 2 7 3 4 1} -> The max of [3 4 3] is 4.
Step 2: {3 [4 3 1] 5 2 7 3 4 1} -> The max of [4 3 1] is 4.
Step 3: {3 4 [3 1 5] 2 7 3 4 1} -> The max of [3 1 5] is 5.
Step 4: {3 4 3 [1 5 2] 7 3 4 1} -> The max of [1 5 2] is 5.
Step 5: {3 4 3 1 [5 2 7] 3 4 1} -> The max of [5 2 7] is 7.
Step 6: {3 4 3 1 5 [2 7 3] 4 1} -> The max of [2 7 3] is 7.
Step 7: {3 4 3 1 5 2 [7 3 4] 1} -> The max of [7 3 4] is 7.
Step 8: {3 4 3 1 5 2 7 [3 4 1]} -> The max of [3 4 1] is 4.
Done.

The output is therefore {4 4 5 5 7 7 7 4}.

```

# Answer
Change your API so that the user must provide a buffer of type `(f32, isize)` (or a wrapper type thereof) so that you can store the indices associated with each sample in your window.

Then you can turn this buffer into a double-ended queue by having two indices, `head` and `tail`, and forming a ring buffer.

Then you can apply the algorithm I described here to get a constant amortized time algorithm.
> 1 votes

# Answer
Change the API. All reasonable data structures require more space. There is no solution that I am aware of within your constraints. Your current API imposes a limitation on the set of data structures you can use that is too strict to admit a good solution.

Fortunately, this is solvable, as long as you are willing to change the API. You just need to push the responsibility for allocating space for the data structure to the caller. This will require a change to the API.

Fortunately such a change to the API should be workable. The extra requirements it imposes on the caller are ones that can be discharged by the caller (but cannot be discharged by your library). So, this should work fine, and won't require `malloc`. Your current API requires the caller to know a constant upper bound on the size of the window. (Why? To allocate space for the `buffer` without using `malloc`, the caller needs to know an upper bound on the maximum possible size of `buffer` that could be needed in any execution, so it can statically allocate that much space.) This means that it will be feasible to solve the problem. Since the caller knows a constant upper bound for the window size, they can allocate space for a larger data structure. If the caller can allocate $k$ words for the buffer, they can just as easily allocate $2k$ words, and that will be enough.

In particular, I suggest you have them allocate twice as much space as your current API requires. This will be enough for you to store the data in a priority queue. In particular, I suggest a data structure that has two parts: a priority queue of all items in the window; and a circular buffer of all items in the window, in the order they appeared in the stream.

At each time step, compute the minimum value within the window using find-min on the priority queue, use the circular buffer to identify the item that is leaving the window, delete that from the priority queue, and insert to add the item that is entering the window. You could use a heap, which supports these operations in logarithmic time. The heap/priority queue can consist of indices into the circular buffer.

With this approach, if the window size is $k$, then the space requirement is $2k$ words of space -- twice as much as you have currently allocated. In fact, you can reduce this further; it suffices to have $k$ words to hold the ints/flots, plus another $k$ $\lceil \lg k \rceil$-bit words for the priority queue.

It's tempting to think that a heap would meet your needs, but it doesn't, because in each time step we need to know both the element that is entering the window and the element that is leaving the window, and it requires extra space to keep track of that.

So, if you want to avoid memory allocations and you want efficient data structures, change the API so that the caller pre-allocates more space for your library.
> 0 votes

---
Tags: algorithms, statistics
---


title: NP Reduction - Dominating set to SAT

text:
# Question
Title: NP Reduction - Dominating set to SAT
Given a graph G and an integer k , recognize whether G contains dominating set X with no more than k vertices. And that is by finding a propositional formula ϕG,k that is only satisfiable if and only if there exists a dominating set with no more than k vertices, so basically reducing it to SAT-Problem.

The solution to this problem is supposed to be similar to reducing clique to SAT. Here is how that looks like: https://blog.computationalcomplexity.org/2006/12/reductions-to-sat.html

# Answer
> 0 votes
Take a look at the Cook Levin theorem, that shows a reduction from any $NP$ problem to $SAT$. Since $Dominating-Set\in NP$, this is a reduction $Dominating-Set\le\_p SAT$.

In the case I didn't understand your question and you wanted a reduction $SAT\le\_p Dominating-Set$, consider creating the following graph: add a node for each variable $x\_i$ and add another node for its negation $\overline{x\_i}$, and add an edge between the two nodes. For each such variable, add another node $h\_i$ that has an edge to $x\_i$ and $\overline{x\_i}$.

Additionally, for each clause add a node $c\_j$ and add an edge between it to any literal in it.

Now we want to find a dominating set of size $k$, where $k$ is the number of variables in the SAT instance.

For more information on this, take a look here.

---

I hope this helped!

---
Tags: reductions, np, satisfiability
---


# Question
Title: Complement of $\{w\#x \mid w,x \in \Sigma^*, T(M_w) \neq \{x\}\}$
This is one of my homework assignment questions, that are quite difficult for me. The question states:

> Show that $L$ is not semi-decidable where $L = \\{w\\#x \mid w,x \in \Sigma^\*, T(M\_w)\neq \\{x\\}\\}$

So I just need a better understanding of $L$ in order to solve this homework. My question now is:

> Is the complement of $L$ the language $\overline{L} = \\{w\\#x \mid w,x \in \Sigma^\*, T(M\_w) = \\{x\\}\\}$?

If yes, I think it's possible to show that $\overline{H\_0} \leq \overline{L}$, but that's the second step that I would like to figure out by myself.

# Answer
The complement of a language $L$ over an alphabet $\Delta$ consists of all words over $\Delta$ which do not belong to $L$. In your case, $\Delta = \Sigma \cup \\{\\#\\}$. So a string $z$ is in $\overline{L}$ if it is *not* of the form $w\\#x$, where $w,x \in \Sigma^\*$ and $T(M\_w) \neq \\{x\\}$. This can happen in two ways:

* $z$ is not of the form $\Sigma^\* \\# \Sigma^\*$.
* $z = w\\#x$, where $w,x \in \Sigma^\*$ and $T(M\_w) = \\{x\\}$.
> 1 votes

---
Tags: sets
---


# Question
Title: 0/1 knapsack problem: Greedy Algorithm Counterexample
While reading about 0/1 knapsack problem on the Internet, many tutorials considered value/weight ratio to solve the problem and I was wondering will it always contain the element with the greatest value/weight ratio to find an optimal solution to a 0/1 knapsack problem or is there any example where we find the optimal solution without the greatest ratio?

# Answer
Consider this counterexample. Suppose the knapsack has a capacity 4. And suppose there are three items:

* Item A with weight 3 and value 5
* Item B with weight 2 and value 3
* Item C with weight 2 and value 3

The optimal solution contains items: B and C, in the knapsack with a total value = 6. However, item A has the highest value/weight ratio: 5/3, which is greater than 3/2.
> 4 votes

---
Tags: knapsack-problems
---


title: Terms related to optimal scheduling

text:
# Question
Title: Terms related to optimal scheduling
I am studying a certain theoretical optimization problem related to scheduling, and I am confused by the different terms used in the literature for such problems. In particular, I found the following terms:

* Job scheduling
* Machine scheduling
* Process scheduling
* Processor scheduling
* Multiprocessor scheduling
* Task scheduling

Are these terms all synonymous? Alternatively, are some of these terms more standard than others, or used in different contexts than others?

Wikipedia is not very helpful - there is quite a mess in the articles about these problems. Google Scholar also gives tens of thousands of articles and it is hard to understand the relations between them. I am looking for some clarification regarding the basic concepts.

# Answer
I think in the older literature there was a real distinction between *job shop scheduling* and *multiprocessor scheduling*. I tried to break down some of that distinction in an answer to a previous question about the distinction between job shop, flow shop, and open shop scheduling.

Briefly: In job shop scheduling problems the resources are different from one another, and each job may need to use some of each of those resources in some order. In multiprocessor scheduling the resources tend to be interchangeable.

I'm unaware of any agreed on formal definition of any of the terms *machine*, *process*, *processor*, or *task* scheduling in the theoretical scheduling literature (although their may be distinctions made between some of these terms in practical operating systems implementations).
> 2 votes

---
Tags: terminology, scheduling
---


# Question
Title: How to describe the language of an automaton in plain English?
How do I describe the following automaton in plain English?

The only thing that I can think about when explaining in plain English would be the states, alphabet, start, accepting state, but I think there is more to when explaining about automata. How do I answer that?

```
The states are as follows: Q = {q1, q2, q3, q4}
The alphabet is as follows: Σ = {0,1}
The start state is q1
The accepting state is q4

```

# Answer
There is a difference between describing the language accepted by an automaton and describing the automaton itself. There can be several different automata that accept the same language.

For the particular automaton you give, the language it accepts can be described in plain English as "the set of words that contain at least two 1's separated by at least one 0". However, this sentence does not clarify whether a 3rd occurrence of 1 should also be separated by at least one 0 from the previous (or next) 1. A better description could be: "the automaton accepts a word if that word has a substring that contains two 1's separated by at least one 0". I think, this way it is clearer that once we have found a substring of the form $10^{n+1}1$, we don't care about the rest of the string.

To describe the automaton, this would be my attempt: The automaton starts in state q1, on which it stays as long as it reads 0 from the input string. Once it reads 1, it moves to state q2 on which it stays as long as it reads 1 from the input string. Once it reads 0, it moves to state q3, on which it stays as long as it reads 0 from the input string. Once it reads 1, it moves to the accepting state q4, on which it stays forever.
> 0 votes

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


# Question
Title: Give a parallel algorithm that finds the minimal element of an unsorted array
I need to give a parallel algorithm which finds the minimal element of an unsorted array. Moreover, I need to show that $T\_1 = Θ(n)$ and $T\_∞ = Θ(\log n)$.

As I read $Θ(\log n)$, I thought about some sort of divide and conquer algorithm, like MS:

```
parallelMin(A, l, r):
    if l ≥ r:
        return min(A[l], A[r])
    m = l+⌊(r-l)/2⌋
    x = spawn parallelMin(A, l, m)
    y = parallelMin(A, m + 1, r)
    sync
    return min(x, y)

```

I know that $T\_1(n)=2T\_1(n/2)+Θ(1) \Rightarrow T\_1(n) = Θ(n)$.

But for $T\_∞$, I'm not certain that it is indeed $Θ(\log n)$.

So my questions are:

1. How do I calculate (and show) $T\_∞$? I know that it's the algorithm DAG span, but I would like to learn how to show it.
2. Can/Should the second call be parallelized too?

# Answer
> 1 votes
The recursive algorithm can be summarized in one sentence:

> Given an unsorted array $A$, break it into two equal halves $B,C$, calculate their minimum elements $\min(B),\min(C)$ in parallel, and output $\min(A) = \min(\min(B),\min(C))$.

When there are infinitely many processors, we can always calculate $\min(B)$ and $\min(C)$ in parallel, and so the recurrence for the running time is $$ T\_\infty(n) = T\_\infty(n/2) + O(1), $$ whose solution is $T\_\infty(n) = \Theta(\log n)$. (We are making the simplifying assumption that $n$ is a power of 2.)

---
Tags: parallel-computing
---


# Question
Title: Validity of formulas in very specific alphabet
> Let $\Sigma = \\{c\_1, c\_2, R(\cdot,\cdot) \\}$ be an alphabet in first-order logic without $=$, where $c\_1,$ $c\_2$ are constant variables and $R$ is binary relation. Let $\varphi$ be a formula without quantifiers such that $FV(\varphi)=\\{x\\}$.
>
> Prove or disprove: if the first-order sentence $\exists \\,x\\,\varphi(x)$ is valid, then there exists a variable $s$ ($s\in\\{c\_1,c\_2\\}$) such that $\varphi\[s/x\]$ is valid.

I tried to both prove and disprove, in both cases I failed. When I tried to disprove, I tried to think of formulas $\varphi$ such that $\exists \\,x\varphi(x)$ were valid, but for such formulas the claim was indeed correct.

So I tried to prove, I had an idea to use Herbrand model and the ground instances to come to some conclusion, but I could not move on from there.

I tried other things but I do not speak English and it is difficult for me to translate everything I tried. I really appreciate the helpers!

# Answer
> 0 votes
Consider the sentence $$ (R(c\_1,c\_1) \lor R(c\_2,c\_2)) \to R(x,x). $$

---
Tags: first-order-logic
---


# Question
Title: Is this a good way to arrange data in a tree?
I was recently learning about Binary Search Trees(BSTs) and thought it could be made even more efficient by making some changes.

As binary search trees have numbers greater than the root node on the right and the numbers lesser than the node on the left, we can further divide the tree into odd and even numbers to make the search easier(as we have to just check the last bit to verify if a number is odd or even)

Example:

S = {5,12,14,1,7,2,18,9,11,16,22}

This can be arranged in a tree as follows:

Here, if we have to search for element 9, we just have to look at the left side of the root node which is a BST as 9 is odd, and continue a normal binary search.

Does this make the normal BST any better or is it just unnecessary to divide it on the basis of Odd and Even elements?

# Answer
> 1 votes
It doesn't significantly increase the speed, the increase will just be a constant at best. Essentially, you still search the same tree, just in a different ordering, and that means you will still do $O(\log(n))$ operations to search a number.

It might be useful to think of this as just two separate BSTs, one for odd numbers and one for even numbers.

So, this isn't generally better than a normal BST (and is slightly harder to implement), unless you know something really special about the inputs.

---
Tags: algorithms, data-structures, search-algorithms, binary-trees, number-formats
---


title: Return Linked List elements as an array

text:
# Question
Title: Return Linked List elements as an array
Out of pure curiosity, if I have a Doubly Linked List, what would be the fastest way to return the elemenmts of the List in the correct order as an array? For example, would it be more efficient to create an empty list an append the elements or create a list with the length of the Linked List and insert each element?

# Answer
In terms of computational complexity, both approaches will be $O(n)$. Also, its impossible to do better than $O(n)$, since you must always go through all elements in the linked-list anyways.

So in those terms, the running times are equivalent. What about the space (memory) complexity? Well, in both cases we ultimately create an array of length $n$ and nothing more than it. So, both approaches will have also $O(n)$ memory complexity.

---

What is the difference then? The key difference is not in any complexity measure, but it has to do with how memory is allocated. In the *second* approach, you have to create an array with some constant size, and you wont change that size. Hence, you will allocate memory only **once**. In the *first* approach, you create a (dynamic) list, which uses a less-efficient data structure (when compared to an array with a constant size) that can increase in size. Additionally, since this array increases in size it means that it will allocate memory **more than once**.

---

So ultimately, what do you want to use? the second implementation would be a better option - even though it doesn't improve in asymptotic complexity measures.
> 1 votes

# Answer
Since you haven't mentioned if the elements have to be sorted into an array, I am assuming you just want to copy the elements of the list into an array.

Well, this can be done by pointing to the head and copying the data of the head (head-\>data) into the array one by one and deallocating the node and moving on to the next node, and repeat.

Pseudo-code:

```
 i = 0
 ptr = &head
 arr[i] = head->data
 head = head->next
 free(ptr)
 i++ until i = length of list

```
> 0 votes

---
Tags: linked-lists
---


# Question
Title: Proving that there are more problems than solutions
I have doubts regarding a proof of the following theorem:

*'Set of all problems' is larger than the 'set of all algorithms' (or set of all C programs).*

Put rhetorically, the theorem says that there are more problems than there are solutions.

The proof is by cardinality comparison of the two sets and has the following steps.

1. (Lemma 1) Prove that the 'set of all C programs' is at most countable.
2. (Lemma 2) Prove that the 'set of all problems' is at least uncountable.
3. Hence, $|$set of all problems$| \> |$set of all C programs$|$ ($|.|$ represents cardinality)

For completion, and to ensure that we all are on the same page, I have stated the proof below. However, my concern is not related to the proof directly.

**Proof of Lemma 1**

The vocabulary of C language is finite (say of size $K$). Therefore, every text of finite length written in C can be encoded as a number in base $K$. Hence, the set of all finite-length texts written in C is of the same cardinality as the set of all numbers in base $K$ i.e. countable. The set of all syntactically and semantically valid C programs is only a subset of this set, hence that set is at most countable.

**Proof of Lemma 2**

Consider the following set: $S = \\{f\ |\ f$ is a function from $\mathbb{N}$ to $\\{0,1\\}\\}$. Now, we shall find the cardinality of $S$. To that end, map each function $f$ in $S$ to a unique subset $T\_f$ of $\mathbb{N}$ s.t. $f(x)=1$ iff $x$ is in the subset $T\_f$. This mapping is a bijection and hence the cardinality of set $S$ is same as the cardinality of the set of all $T\_f$s i.e. the power set of $\mathbb{N}$ i.e. uncountable.

Then we agree/realize/assume that set $S$ is a subset of the set of all problems and hence the latter set is at least uncountable, which completes the proof.

I cannot see $S$ as being a subset of all problems. Why is every element of $S$ a problem in itself? Is it not more *sane* to talk only about the problems that you can understand and communicate (in English say)?

To me, any *problem* must be explainable in English, for it to be called a problem. It is not meaningful to be talking about other problems anyway. Therefore, the set of all (worthy) problems must at most be countable, since the set $E$ of all English texts of finite length is countable (proved like Lemma 1 above). So, if we assume that we can write each individual element of $S$ as a problem, that leads us to conclude that all problems in $S$ are elements of $E$, and therefore $|E| \geq |S|$ which is clearly false (since $S$ is uncountable).

Therefore, we cannot even write individual problems of $S$ in English, let alone the whole set. Why are we concerned about those problems then? $S$ may represent one set of decision problems, but are these decision problems worth solving? Should we just believe that there are uncountably many problems even if we would never want to solve uncountably many of them?

I do understand that the notion of a *problem* for me (the explainability in English) is different from the one that the proof uses. That is fair and in theory I can see why that might be appreciated as well. But this theorem and the corresponding proof limit all human efforts. They tell us that no matter what we do, we will never be able to get all the questions (forget about the answers). So, I want to be really sure that there is indeed no hope. Sorry for being sentimental about this but it is one of those things which render me powerless. It is right up there with Gödel's Incompleteness Theorems, results that forever limit our abilities and make us doubt our entire existence.

Please help me understand why is $S$ a set of problems worth considering and what is a problem after all? Thanks for your time!

# Answer
> 1 votes
> Should we just believe that there are uncountably many problems even if we would never want to solve uncountably many of them?

Yep. Thats the thing, we want to talk about *all* possible problems - why would we want to restrict ourselves to theoretically analyzing only a small portion of problems? So essentially what you are saying (and I totally agree with you), is that only a really small portion of the so-called "problems" are actually interesting and make sense to try and solve.

In a drastic switch, to my opinion, even though Godel's incompleteness therem, the halting problem's undecidability and Rice's theorem do show us that we are "powerless", just think about how much power we actually do have - to even *consider* thinking about such theoretical questions. Who would have thought its possible to prove that we cant do something? I believe you just have to "go with it", and accept the reality that there are things we can't do. Its part of what makes computer science interesting, since if we could do everything - nothing would be interesting...

---
Tags: computability, logic
---