# Question
Title: Under which conditions a given program is deterministic on x86_64 machines?
Given a certain x86\_64 "vanilla" binary, without micro-architecture instructions, which can therefore be executed by any x86\_64 computer, what are the conditions for the result to be deterministic ?

Can we assume that without parallelization, without the use of entropy-generating instructions, the result will be "bit-perfect" on different CPU models ? If not: why ? Can the floating point implementation from different CPUs change the results ?

By deterministic, I mean the same inputs will always produce the same outputs. I also assume inputs are what we classically assume to be inputs: parameters of the programs that can be fully controlled by the user like what we can pass as command line parameters, for example.

To be clear, I'm not talking about the program generation, or the use of specific instructions on different micro-architecture, or scheduling differences, I'm wondering about the "best case scenario": is this best case scenario reproducible, and can we ensure some program will be reproducible ?

# Answer
I don't have all the details, but I think the conditions are not easy to identify. I am aware of several categories of challenges:

* Many instructions may have undefined behavior (e.g., the opcodes are reserved, or the spec does not define their behavior for some inputs), and thus it is possible that their behavior might vary on different CPU models. For instance, many instructions specify that some aspects of their effects are undefined, e.g., the effect on some flag bits may be undefined. As another example, SHLD says that the contents of the destination operand is undefined in certain cases.
* There are certain instructions that explicitly perform I/O or read external data: e.g., IN, OUT, RDTSC, RDTSCP, RDRAND, RDSEED, etc.
* Concurrency can cause nondeterminism, so you would have to rule out all associated instructions (e.g., LOCK). Also I think there is a lot of nondeterminism in the memory model when there is any concurrency or shared memory. So, you have to ensure that no other process/thread/etc. has access to any shared memory. You'll also need to make sure that the program does not make a system call to the OS to initiate DMA.
* System calls or interrupts (e.g., the INT, SYSCALL, SYSENTER instructions) might not have deterministic behavior.
* I'm not sure, but I suspect reading machine state might have nondeterministic behavior, e.g., reading the machine status word, global descriptors, reading timers and performance counters (e.g., RDPMC), CPUID, model-specific registers (RDMSR), etc.
* Supervisor-level / kernel-mode instructions are complex to analyze and I don't know whether they will be deterministic. If you want to ensure determinism I would suggest you ensure the code runs in user mode (e.g., ring 3). For instance, I don't want to think about instructions like VMLOAD, VMRUN, modifications to the page tables, etc.
* The initial state of memory before it is written to is not defined and thus any program that reads from uninitialized memory may trigger nondeterministic behavior. On the other hand, many operating systems zero out pages before handing them to the program, which eliminates this issue.

This is a complex topic and I wouldn't be surprised in the least to discover that I have missed other important challenges.

I don't know whether floating-point arithmetic is guaranteed to be deterministic and bit-for-bit identical on all platforms.

I think it is plausible that, given enough effort, you could come up with a subset of x86 instructions and an initial state for the process where, if the process only executes those instructions, its behavior will be deterministic. However, coming up with this subset might be quite tricky and require a lot of time with the Intel manual. Enforcing that the process only executes instructions from this subset will be quite challenging, given the ability to execute self-modifying code and runtime-generated code. It is also not clear how you will deal with instructions where some of their results are undefined. For instance, it's not clear how you'll deal with instructions that leave some of the flags undefined (and there are many of them), as there is a risk that a later instruction reads one of those flags whose value is undefined, and this could introduce nondeterminism (the spec makes no promises that undefined values will be a deterministic function of the inputs you care about). So, I suspect ensuring determinism at the x86 level would be a non-trivial project.

If it is helpful, I know of some efforts to enforce determinism in the context of higher-level programming languages, where the enforcement becomes easier; you could ask a separate question about that, if it is of interest.
> 2 votes

---
Tags: computer-architecture, randomness, cpu
---


# Question
Title: Show that if the discrete log problem is $(T,1-\epsilon)$-hard, then it's $(O(\frac{T}{\frac{1}{\epsilon}log\frac{1}{\epsilon}}-nlogm),\epsilon)$-hard
Show that if the discrete log problem is $(T,1-\epsilon)$-hard, then it's $(O(\frac{T}{\frac{1}{\epsilon}log\frac{1}{\epsilon}}-nlogm),\epsilon)$-hard

Let $G$ be a cyclic group of size $m$, and let $g \in G$ be a generator.

We say the the discrete log problem is $(T,\epsilon)$-hard if for every algorithm $A$ of complexity at most $T$, it statisfies: $$P\[A(a) = log\_g(a)\] \le \epsilon$$ when $a$ is chosen uniformly from $G$. This means that $A$ can give the correct value of $log\_g(a)$ with probability $ \le \epsilon$.

Now I assume that the discrete log problem is $(T, 1-\epsilon)$-hard and want to prove that it's $$(O(\frac{T}{\frac{1}{\epsilon}log\epsilon} -nlog(m)), \epsilon)\text{-hard}$$ where $n$ is the time to compute a group operation on $G$.

The complexity of $O(nlogm)$ it is what needed to calculate $g^a$ for an arbitrary $a \in G$, which makes me think that such thing can be used here.

I would want to assume that there is an algorithm $A$ of size $K$ that guesses the correct discrete log for an arbitrary $a \in G$ with probability $ \> \epsilon$.

Then, somehow use $A$ to solve the discrete log problem with probability $\> 1-\epsilon$.

However, I don't really see how to do it. Maybe run $A$ with the input $a \in G$ and return the opposite answer in some way. Help would be appreciated.

# Answer
Suppose that there exists an algorithm $A$ which runs in time $T\_A\le \frac{T}{\frac{1}{\epsilon}\log\frac{1}{\epsilon}}-n\log m$, and $\Pr\limits\_{a\sim U(G)}\left\[A(a)=\log\_g a\right\]\ge \epsilon$. We want to enhance the success probability of $A$. The trick is to evaluate $A$ on different elements $b\_1,...,b\_k$ (who of course depend on the input $a$) whose logarithm will allow us to recover $\log\_g a$. Define $A'$ as follows, given input $a$ pick independently $i\_1,...,i\_k\in \[m\]$ uniformly at random, and evaluate $A$ on the inputs $ag^{i\_1},...,ag^{i\_k}$. For each $1\le j\le k$ check whether $A(ag^{i\_j})=\log\_g ag^{i\_j}$ (the verification requires $n\log m$ time), and if there exists $j$ for which the equality holds return $A(ag^{i\_j})-i\_j \pmod m$. The running time of $A'$ is bounded by $k(T\_A+n\log m)\le \frac{k}{\frac{1}{\epsilon}\log\frac{1}{\epsilon}}T$. I leave it to you to show that $ag^{i\_1},...,ag^{i\_k}$ are independent and therefore we can write $\Pr\limits\_{a\sim U(G)}\left\[A'(a)=\log\_g(a)\right\]\ge 1-(1-\epsilon)^k\ge 1-e^{-\epsilon k}\ge 1-\epsilon$, for $k=\frac{1}{\epsilon}\log\frac{1}{\epsilon}$.
> 2 votes

---
Tags: algorithms, complexity-theory, reductions, cryptography
---


# Question
Title: Solving the Knapsack problem in $O(v^*n^2)$, where $v^*$ is the maximum value of all $n$ items
For my study I am supposed to develop an dynamic programming algorithm which solves the following simplification of the Knapsack problem in $O(v^\*n^2)$ time ($v^\*$ is the maximum value of all elements):

Let there be given $n$ elements $1,...,n$, a maximum weight $W$ as well as a weight & value function:
$w: \\{1,...,n\\}\to \mathbb{N}$
$v: \\{1,...,n\\}\to \mathbb{N}$
We then define $v^\* = \max(v(1),...,v(n))$

The goal is to find a subset $M\subseteq \\{1,...,n\\}$ so that $\sum\_{x\in M} w(x)\le W$ and so that $\sum\_{x\in M} v(x)$ is maximal.
(I.e. we want to pack the subset of items that have the highest summed up value while not using up more weight than $W$)

I've been trying for quite some time, but I can't seem to come up with any idea or reduction rule that makes use of $v^\*$.

Since this is a homework assignment, I'm looking for hints, not answers.

---

To be precise: The regular dynamic programming algorithm that solves the regular Knapsack problem can be used on this simplification as well (it might even be that the version given here is the standard version. The sources I've looked through so far don't say whether $w,v$ map to $\mathbb{R}$ or $\mathbb{N}$),
and find the optimal solution in $O(n\cdot W)$ time (see e.g. Wikipedia).

The algorithm variant I'm looking for however is independent of $W$, and instead uses the maximum value $v^\*$ of any of the items.

# Answer
> 1 votes
So, after eventually giving up on developing a different algorithm I looked back at the original solution, i.e. the one you can find e.g. on Wikipedia under 0/1 Knapsack problem.

The idea is to look closely at which fields of the table the algorithm builds are actually necessary, and which are not.

# Answer
> 0 votes
I think this is what you are looking for.

source : my professor

---
Tags: optimization, dynamic-programming, knapsack-problems
---


title: Return 3 smallest elements in a list

text:
# Question
Title: Return 3 smallest elements in a list
How would we find the three smallest elements in a list and return it as a tuple `(a,b,c)` using divide and conquer?

So far I've considered the following:

```
def sm(L):
    # base
    if len(L) == 3:
        return L sorted
    else:
        # divide

```

How would I divide the list so that we guarantee the list to be of size 3 and be in the base case?

# Answer
> 1 votes
In the divide and conquer approach, we break the problem into subproblems and we try to solve these subproblems.

So, you can divide your problem into two subproblems till you reach one element. Now you can combine these subproblems but in each step, you know the 3 smallest elements of these subproblems.

Fortunately, Merge Sort uses the divide and conquer idea to sort an array. Please note that in each step of combining subproblems, it is sufficient to hold only three elements of each sub-lists. So, it is not necessary to sort all elements. (Just the 3 smallest elements)

Check Merge sort here: https://www.geeksforgeeks.org/merge-sort/

---
Tags: algorithms
---


# Question
Title: Why is this implementation of the hash function bad?
I have a task of hashing DNA sequences. Let the DNA be long sequences of four amino acids, which we will denote by the letters $A, T, G$ and $C$.

My hash function $h$ take DNA as an input and return the sum of amino acid numbers by some large simple modulus as a hash, and then add it to a hash table with a public key. Why is this hashing implementation bad?

# Answer
Because

1. two sequences with the same acids in different order (e.g. two acids switch places) will have the same hash code;
2. this will only produce numbers from 0 to your large simple modulus instead of all $2^{32}$ or $2^{64}$ possibilities.
> 1 votes

---
Tags: hash, hash-tables
---


# Question
Title: Infeasible linear programming reduce errors to find solution
Most normal linear programming problems look like this:  We choose some point in the double shaded area that solves our optimizer and we're good to go.

However, I've come across a problem where it's fairly common to get a lp problem like this (infeasible):

I'd like to employ some metric such that the solution given reduces the errors between the closest possible solutions in any equation it does not fulfill such that it would be on the line right between the 2 solutions (something like reduce OLS or LAD).

Is there any formal algorithm for this or common way this is done?

# Answer
One approach: replace each inequality $a\_1 x\_1 + \dots + a\_n x\_n \le b$ by $a\_1 x\_1 + \dots + a\_n x\_n \le b + t$, replace each inequality $a\_1 x\_1 + \dots + a\_n x\_n \ge b$ by $a\_1 x\_1 + \dots + a\_n x\_n \ge b - t$ (using the same $t$ for all of them), and then minimize $t$.
> 1 votes

# Answer
Have a look at the Simplex algorithm. It works in two phases: In phase one, it tries to find an extreme point that is a feasible (but usually non-optimal) solution, and in phase two, starting with a feasible solution, it tries to find an optimal solution.

In phase 1, for every equation $\sum a\_{ij}x\_i = b\_i$, we introduce another variable $y\_i$ and change the equation to $\sum a\_{ij}x\_i +y\_i= b\_i$, with the obvious starting solution $x\_i = 0$, $y\_i = b\_i$. Then we minimise $\sum y\_i$. If we can achieve $\sum y\_i = 0$ then we remove all variables $y\_i$ and have a feasible solution for the original problem. If we can't reduce $\sum y\_i$ to zero, then the original problem has no feasible solution. And that is exactly your situation.

So at this point your problem is solved, kind of. You found a point closest to a feasible solution in terms of the original equations. But different equations may have different scaling. If you multiply one of the equations by 1,000, it doesn't change anything when you find a feasible solution, but minimising $\sum y\_i$ will try much harder to get the $y\_i$ for that particular equation as small as possible. So you want to look at all your equations and make sure they are scaled in a similar way.
> 1 votes

---
Tags: algorithms, linear-programming
---


# Question
Title: Determining the intersections of a line segment and grid
**Problem:** Given a line segment on the cartesian plane, determine where and which order it intersects a regular grid. This sounds simple, but is actually quite a tough problem. It's related to, but distinct from, both Bresenham and supercover.

More specifically, consider:

1. A line segment with start $(x\_1, y\_1)$ and end $(x\_2, y\_2)$
2. A grid of cells, bounded by all lines $x = k$ and $y = k$ for all integer $k$
3. Each cell therefore has four boundaries, called North, South, East, and West

The example plot shows the segment from (0.6,0.4) to (-0.2, 2.2) crossing three boundaries.

For a given line segment, we wish to determine the cell boundaries it crosses:

1. For each boundary type, the number of crossing. `{N:2 S:0 E:0 W:1}` in the example.
2. The sequence of crossings. `{N, W, N}` in the example.
3. The grid position of each crossing, defined as $(x - floor(x), y - floor(y))$. Approximately `N: (0.35, 1), W: (0, 0.8), N: (0.8, 0)` in the example.

I'll note that the problem as-is is not fully defined: line segments starting or ending on a boundary, coinciding with a boundary, and crossing a vertex all need definition. We can accept any reasonable, consistent definition of these.

Solving #1 is easy:

```
number of east (west if neg) crossings = floor(x2) - floor(x1)
number of north (south if neg) crossings = floor (y2) - floor(y2)

```

Solving #2 and #3 is surprisingly hard. I've come up with three approaches:

1. **Direct**. The ideal would be to calculate this directly (that is, without iteration), similar to the formula for #1. I have made no progress here.
2. **Iterative**. Determine the next crossing (by trying both directions and determining which is crossed first). Determine how far along the segment that is. Repeat until done. This works, though it lacks elegance or speed. The other issue is that chopping the segment repeatedly, if not done carefully, can cause inconsistency with floating point calculations leading to missed or double crossings.
3. **Mixed**. Use the calculation above to determine the total number of crossings of each type. For each, one $(x,y)$ coordinate is an obvious integer, and the other can be solved using simple algebra, as can the length of the segment to that point. Sort by segment length.

#3 is the best approach so far. **Is it possible to do better?**

# Answer
> 4 votes
I suggest using a simple iterative method.

Let's first find the places where it crosses a vertical grid lines. These are places where the line goes through a point $(x,y)$ where $x$ is an integer. The points $(x,y)$ on the line can be written in the form

$$(x,y) = (x\_0,y\_0) + t (x\_1-x\_0,y\_1-y\_0),$$

where $(x\_0,y\_0),(x\_1,y\_1)$ are the two endpoints of the line and $t \in \[0,1\]$ is a free variable. Now this point crosses a vertical grid line if $x$ is an integer, i.e., if $x\_0 + t(x\_1-x\_0)$ is an integer. This has solutions of the form $t = (i - x\_0)/(x\_1-x\_0)$, where $i$ is an integer with $x\_0 \le i \le x\_1$.

Therefore, to find all places where the line crosses a vertical grid line, you can iterative over $i$ in the range $\lceil x\_0 \rceil,\dots,\lfloor x\_1 \rfloor$, and for each such $i$, compute $t = (i - x\_0)/(x\_1-x\_0)$ and then compute the point $(x,y) = (x\_0,y\_0) + t (x\_1-x\_0,y\_1-y\_0)$. This enumerates all such points on the line.

You can repeat the same for places where the line crosses a horizontal grid line, i.e., where $y$ is an integer. You can then merge these two sequences, sorting them by increasing value of $t$ (note that no sort operation is needed as the list of horizontal crossings and the list of vertical crossings are both already sorted; you just need to merge these two sorted lists).

The running time is linear in the number of such points. This is asymptotically optimal; obviously any algorithm to output all such points must take at least $O(1)$ time per point, so needs to take at least linear time.

This does not have problems with accumulation of floating point errors, as far as I can see. I don't see how this would cause missed or double crossings. I find it elegant, though of course that is a matter of personal taste.

---
Tags: algorithms, computational-geometry, computer-graphics
---


# Question
Title: The situation when P is a superset of NP
Could it be that three languages $A, B, C$ such that $A \subset B \subset C$, and $B \in P$, but $A$ and $C$ are $NP$-complete?

# Answer
> 5 votes
Let $L$ be any NP-complete language over $\Sigma = \\{0,1\\}$, and take \begin{align} A &= \\{ 0x : x \in L \\} \\ B &= 0\Sigma^\* \\ C &= 0\Sigma^\* \cup \\{ 1x : x \in L \\} \end{align}

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


# Question
Title: Two way deterministic pushdown automaton accepting word consisting of two equal words
I have a homework where I have to construct two way deterministic pushdown automaton that accepts this language:

> {ww | w ∈ {a, b}\*}

Does anyone have any idea? Thanks a lot

# Answer
> 1 votes
Here are the two basic ideas.

(1) After checking that the input length is even, move to the middle position of the input. The trick to find that position uses the stack in a similar way that we recognize the language $\\{\\;a^{2n}b^n \mid n \ge 0\\;\\}$.

(2) Then check that the two halves are equal. Here the stack is used in a similar way that one recognizes the language $\\{\\; ww^R \mid w\in\\{a,b\\}^\*\\;\\}$, except that the head does not move forward in both cases.

---
Tags: automata, pushdown-automata
---


# Question
Title: What is the SetHorspool string searching algorithm and how is it implemented?
What is the SetHorspool string searching algorithm with pseudo-code so it can be easily implemented in a language of choice?

This has been implemented in 2 libraries I have come across:

But there seem to be very little details of the algorithm available online to understand its working.

# Answer
> 2 votes
Reading the source code we can see that it is an extension of Horspool to find a match from a set of needle strings $S$, rather than matching a single needle string.

How it works is by representing the set $S$ as a trie. This allows you to efficiently check character by character whether starting at position $i$ any of the strings on the trie can be found in the haystack. And like in Boyer–Moore–Horspool, if a position $i$ of the haystack fails to match any of the strings in $S$, instead of simply trying $i' = i+1$, a smarter skip lookup table is used: $i' = i + T\[\text{haystack}\[i + |\text{needle}| - 1\]\]$.

The second difference is how $T$ is computed. Normally the pseudocode is as follows (from the Wikipedia article):

```
function preprocess(pattern)
    T ← new table of |Σ| integers
    for i from 0 to |Σ| exclusive
        T[i] ← length(pattern)
    for i from 0 to length(pattern) - 1 exclusive
        T[pattern[i]] ← length(pattern) - 1 - i
    return T

```

But in SetHorspool, the minimum safe skip considering all patterns is computed instead:

```
function preprocess(S)
    T ← new table of |Σ| integers
    for i from 0 to |Σ| exclusive
        T[i] ← min(length(pattern) : pattern ∈ S)
    for pattern in S
        for i from 0 to length(pattern) - 1 exclusive
            T[pattern[i]] ← min(T[pattern[i]], length(pattern) - 1 - i)
    return T

```

---
Tags: algorithms, strings, string-matching, pseudocode, exact-string-matching
---


# Question
Title: Construct a CFG for $L = \{ w \in \{0,1\}^*\text{ } |\text{ } w = w^R \text{ and } |w| \text{ is even}\}$
I need to construct a CFG for the following language$$L = \\{ w \in \\{0,1\\}^\*\text{ } |\text{ } w = w^R \text{ and } |w| \text{ is even}\\}$$

I know that the two middle position should always be the same. E.g. $11,00,0\underline{11}0,0\underline{00}0,\dots$ Each position on the opposite sides of the middle points should also be the same.

So these are the production rules of the CFG I came up with $$ S\rightarrow00$$ $$S\rightarrow11$$ $$S\rightarrow ASA$$ $$A\rightarrow1$$ $$A\rightarrow0$$ $$A\rightarrow \epsilon$$ Is this solution correct?

# Answer
As HendrikJan stated, we can for example obtain the following languages with above CFG $$01, 0001,\dots$$ which do not meet the required conditions.

Instead, we need to make sure that the ends are always the same. We can do that by the following production rules.

$$ S\rightarrow 0S0$$ $$S\rightarrow 1S1$$ $$S\rightarrow \epsilon$$
> 3 votes

---
Tags: regular-languages, context-free
---


# Question
Title: Encoding 1-out-of-n constraint for SAT solvers
I'm using a SAT solver to encode a problem, and as part of the SAT instance, I have boolean variables $x\_1,x\_2,\dots,x\_n$ where it is intended that exactly one of these should be true and the rest should be false. (I've sometimes seen this described as a "one-hot" encoding.)

I want to encode the constraint "exactly one out of $x\_1,\dots,x\_n$ must be true" in SAT. What is the best way to encode this constraint, to make the SAT solver run as efficiently as possible?

I can see many ways to encode this constraint:

* *Pairwise constraints.* I could add pairwise constraints $\neg x\_i \lor \neg x\_j$ for all $i,j$ to ensure that at most one $x\_i$ is true, and then add $x\_1 \lor x\_2 \lor \cdots \lor x\_n$ to ensure that at least one is true.

This adds $\Theta(n^2)$ clauses and no extra boolean variables.
* *Binary encoding.* I could introduce $\lg n$ new boolean variables $i\_1,i\_2,\dots,i\_{\lg n}$ to represent (in binary) an integer $i$ such that $1 \le i \le n$ (adding a few boolean constraints to ensure that $i$ is in the desired range). Then, I can add constraints enforcing that $x\_i$ is tree and that all other $x\_j$'s are false. In other words, for each $j$, we add clauses enforcing that $i=j \Leftrightarrow x\_j$.

This adds $\Theta(n \lg n)$ clauses and I don't know how many extra boolean variables.
* *Count the number of true values.* I could implement a tree of boolean adder circuits and require that $x\_1+x\_2+\dots+x\_n=1$, treating each $x\_i$ as 0 or 1 instead of false or true, and use the Tseitin transform to convert the circuit to SAT clauses. A tree of half-adders suffices: constrain the carry output of each half-adder to be 0, and constrain the final output of the final half-adder in the tree to be 1. The tree can be chosen to be of any shape (balanced binary tree, or unbalanced, or whatever).

This can be done in $\Theta(n)$ gates and thus adds $\Theta(n)$ clauses and $\Theta(n)$ new boolean variables.

A special case of this approach is to introduce boolean variables $y\_1,\dots,y\_n$, with the idea that $y\_i$ should contain the value of $x\_1 \lor x\_2 \lor \cdots \lor x\_i$. This intent can be enforced by adding the clauses $y\_i \lor \neg x\_i$, $y\_i \lor \neg y\_{i-1}$, and $\neg y\_i \lor x\_i \lor y\_{i-1}$ (where we treat $y\_0$ as a synonym for false) for $i=1,\dots,n$. Next, we can add the restrictions $\neg y\_i \lor \neg x\_{i+1}$ for $i=1,2,\dots,n-1$. This is basically equivalent to the Tseitin transform of a half-adder tree, where the tree has a maximally unbalanced shape.
* *Butterfly network.* I could build a butterfly network on $n$ bits, constrain the $n$-bit input to be $000\cdots 01$, constrain the $n$-bit output to be $x\_1 x\_2 \cdots x\_n$, and treat each 2-bit butterfly gate as an independent gate that either swaps or does not swap its input with the decision of which to do based upon a fresh new boolean variable that is left unconstrained. Then, I can apply the Tseitin transform to convert the circuit to SAT clauses.

This requires $\Theta(n \lg n)$ gates and thus adds $\Theta(n \lg n)$ clauses and $\Theta(n \lg n)$ new boolean variables.

Are there any other methods I have overlooked? Which one should I use? Has anyone tested this or tried them experimentally, or does anyone have any experience with any of these? Is the number of clauses and/or the number of new boolean variables a good stand-in metric for estimating the impact of this on SAT solver performance, or if not, what metric would you use?

---

I just noticed that this answer has some references on enforcing cardinality constraints for SAT, i.e., enforcing the constraint that exactly $k$ out of the $n$ variables are true. So, my question comes down to a special case where $k=1$. Maybe the literature on cardinality constraints will help shed light on my question.

# Answer
For the special case of k out of n variables true where k = 1, there is commander variable encoding as described in Efficient CNF Encoding for Selecting 1 to N Objects by Klieber and Kwon. Simplified: Divide the variables into small groups and add clauses that cause a commander variable's state to imply that a group of variables is either all false or all-but-one false. Then recursively apply the same algorithm to the commander variables. At the end of the process demand that the exactly one of the handful of final commander variables be true. The result is O(n) new clauses and O(n) new variables.

Given the ubiquity of two-watched-literals in DPLL based solvers, I think the O(n) clause growth is a decisive advantage over encoding schemes that would add more clauses.
> 15 votes

# Answer
A paper by Magnus Björk describes two techniques that could be worth trying.

For 1-out-of-$n$, one can use both one-hot *and* binary encoding simultaneously. Thus, we have $x\_1,\dots,x\_n$ as a one-hot encoding, and $y\_1,\dots,y\_b$ as a binary encoding, where $b = \lg n$. We can encode the "at least one" constraint easily, in a single clause: $(x\_1 \lor \dots \lor x\_n)$. We can also force the two encodings to be consistent with $2 \lg n$ clauses: we simply add $x\_i \implies \neg y\_j$ or $x\_i \implies y\_j$, according to whether the $j$th bit of the binary encoding of $i$ is 0 or 1. Finally, the "at most one" constraint follows automatically. This also allows the rest of the SAT instance to use whichever encoding is more convenient.

For $k$-out-of-$n$, one can apply a sorting network to the input $x\_1,\dots,x\_n$ to get the sorted output $y\_1,\dots,y\_n$, and then add a clause requiring that $y\_k$ is true and $y\_{k+1}$ is false. There are a number of simple sorting networks that need only $O(n \lg^2 n)$ comparator units. Therefore, we get an encoding that uses $O(n \lg^2 n)$ clauses and temporary variables.

The paper is

Magnus Björk. Successful SAT Encoding Techniques. 25th July 2009.

The following paper has a detailed list of encodings for 1-out-of-$n$ and $k$-out-of-$n$, with some experimental evaluation of each of them. The conclusions are not entirely clear (the command encoding looks pretty good in their experiments).

Alan M. Frisch, Paul A. Giannaros. SAT Encodings of the At-Most-k Constraint: Some Old, Some New, Some Fast, Some Slow. ModRef 2010.
> 7 votes

# Answer
Here is my implementation of Kyle's answer:

```
def sat_1_of_n(vs, names):
    ''' Returns the name of a variable that's true when one of the variables is true.
        Also returns clauses making sure that at most one variable is true. '''

    if len(vs) == 1:
        return vs[0], []

    elif len(vs) == 2:
        a, b = vs
        clauses = []

    elif len(vs) > 2:
        p = len(vs)//2
        a, clauses1 = sat_1_of_n(vs[:p], names)
        b, clauses2 = sat_1_of_n(vs[p:], names)
        clauses = clauses1 + clauses2

    c = names.setdefault((a, b, 'commander'), len(names)+1)

    # Make c true when "a or b"
    clauses.append(f'-{a} {c}')
    clauses.append(f'-{b} {c}')
    clauses.append(f'{a} {b} -{c}')

    # We also want one of them to be false
    clauses.append(f'-{a} -{b}')

    return c, clauses

```

Here `names` is a dictionary I use for keeping track of the names of my variables.

If you want exactly one to by true, rather than "less than two" as the above code, just add a single extra clause with all the variables.
> 2 votes

---
Tags: satisfiability, sat-solvers, applied-theory
---


# Question
Title: Closure of Star-Free Languages under Substitution
Let $L$ be a star-free language over finite alphabet $\Sigma$. A *substitution* will be a map $\sigma : \Sigma \to \mathcal{P}(\Sigma^\*)$. It seems obvious that if $\sigma(a)$ is star-free for every $a \in \Sigma$, then $\sigma(L)$ will be star-free.
($\sigma(L) = \\{ w\_1 ... w\_n | w\_i \in \sigma(a\_i) \land a\_1 \ldots a\_n \in L \\}$) Take a star-free regular expression for $L$, and substitute star-free expressions for $L\_i$ for each $a\_i$ in that expression. The result will still be a star-free expression.

Now, my question is this: why is the following not a counterexample? $\Sigma = \\{ 0, 1 \\}$. $L = 1^\*$ and $\sigma(1) = 0^\* 1 0^\* 1 0^\*$. Both of these languages are star-free: $L = L( (\emptyset^c 0 \emptyset^c )^c )$ and similar tricks can be given to show that $\sigma(1)$ is star-free.

Now, the reason it seems like a counterexample: a word in $L$ contains only 1s. The substitution replaces each 1 with a word from a language whose words contain exactly 2 1s. So won't $\sigma(L)$ be the set of words with an even number of 1s, which is known to be non-star-free?

(Note: my proof suggestion of closure under substitution is a bit sketchy. The star-free expression for $1^\*$ only has 0s in it. But I could then substitute the star-free expression for $\sigma(1)$ under a complement, no?)

# Answer
> 3 votes
I do not understand your proof sketch. Where do you want to subtitute $\sigma(1)$ under a complement. The only thing substituable in the star-free expression for $1^\*$ is $0$. But 0, or $\sigma(0)$ is an independent element in the substitution, it is in no way related to the complement of $\sigma(1)$. So this can in no way make a proof.

Actually, if there was such a closure property, it should be easy to find in the literature on star-free RE. But all closure results under substitution put constraints on the type of substitution, such as being length preserving, or being injective. See in particular papers by Jean-Eric Pin and others.

Also,Pin defines star-free substitutions on $\Sigma$ as requiring an additional property, namely that $(\sigma(\Sigma))^\*$ is star-free. (though I did not check the precise role of this property)

It seems that you have just proved that star-free languages are not closed under star-free substitution as you define it.

This does not seem too surprising, since non injective substitution does not in general commute with complement or distribute with intersection.

Among other papers:
Jean-Eric Pin, H. Straubling, and D. Thérien. Some results on the generalized star-height problem. May 12 2002.

# Answer
> 2 votes
Substitutions are a rather broad class of mappings. Let me show that star-free languages are not even closed under projection mappings. A projection mapping is a special homomorphism given by deleting letters. More formally, if $\Gamma \subseteq \Sigma$, then the *projection onto $\Gamma^\*$* is given by $\pi\_{\Gamma}(x) = x$ for $x \in \Gamma$ and $\pi\_{\Gamma}(x) = \varepsilon$ otherwise, and extended to all of $\Sigma^\*$. Now, the language $L = (aba)^\*$ is star-free, as $$ L = \\{\varepsilon\\} \cup (aba\Sigma^\* \cap \Sigma^\*aba) \setminus (\Sigma^\*\cdot\\{aaa,bba,bab,abb\\}\cdot\Sigma^\*). $$ However, $\pi\_{\\{a\\}}(L) = (aa)^\*$ is not star-free.

Finally, let me mention that the commutative star-free languages are closed under projections. Note that the star-free languages coincide with the aperiodic languages.

I present a proof, using the following characterization from J.E.Pin, Syntactic Semigroups (Handbook of Formal Languages):

> For a given alphabet $\Sigma$, the class of aperiodic and commutative languages over $\Sigma$ is the boolean algebra generated by the languages $F(a, k)$ with $a \in \Sigma$ and $k \ge 0$, where $$ F(a, k) = \\{ u \in \Sigma^+ : |u|\_a \ge k \\} $$ and $|u|\_a$ denotes the number of $a$'s in $u \in \Sigma^\*$.

Set, for $k\_1, k\_2 \in \mathbb N\_0 \cup \\{\infty\\}$ and $a \in \Sigma$, with the obvious extensions of the operations to $\mathbb N\_0 \cup \\{\infty\\}$, $$ F(a, k\_1, k\_2) = \\{ u \in \Sigma^\* : k\_1 \le |u|\_a \< k\_2 \\}. $$ By using the laws of a boolean algebra, we can write an aperiodic and commutative language as a finite union of intersections of sets $F(a, k)$ and complements $\overline{F(a,k)}$. Such an intersection could be rewritten as an intersection of sets $F(a, k\_1, k\_2)$ as above, each such set corresponding to a different letter. As function application on sets preserves union, we only need to consider such intersections. We can suppose each set $F(a, k\_1, k\_2)$ is non-empty. Then, the projection equals the intersection over those languages $F(a, k\_1, k\_2)$ with $a \in \Gamma$, the other are left out. So, in total, the projection is a boolean combination of sets of the form $F(a, k\_1, k\_2)$ with $a \in \Gamma$. Hence, an aperiodic and commutative language over $\Gamma$.

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: NP-hardness of language of graphs with $\alpha(G)=n/3$
How to prove the NP-hardness of the language $\\{G \mid \alpha(G) =\frac{1}{3} |V(G)|\\}$?

Here $G$ is a graph, $V(G)$ is its vertex set, and $\alpha(G)$ is the independence number of $G$, which is the maximum size of an independent set.

# Answer
> 1 votes
1-IN-3SAT is the following problem: given a 3SAT instance, determine whether there is a truth assignment in which each clause contains *exactly* one true literal. It is known that 1-IN-3SAT is NP-complete.

Given an instance of 1-IN-3SAT, construct an instance of your problem in which each clause corresponds to a triangle, and contradicting literals are connected by edges. Details left to you.

---
Tags: complexity-theory, np-hard
---


title: Mergesort and some claims on comparison

text:
# Question
Title: Mergesort and some claims on comparison
suppose for $n$ elements we using **mergesort**.

each number compared at most $O(\log n)$ = False

in average each element compared with $O(\log n)$ elements = True

there exist an element compared with $\Omega (\log n)$ elements = True

is there anyone can share idea about these facts (i.e: why first is false and others is true).

# Answer
For the first fact, consider the array $1,\ldots,n,n+1,\ldots,2n$. Sorting its two halves doesn't alter the array. When the two halves are merged, the element $n+1$ would be compared against all elements in the left half.

The second fact is true for every $O(n\log n)$ sorting algorithm: such an algorithm performs $O(n\log n)$ comparisons overall, and so $O(\log n)$ comparisons per element on average.

The third fact is true for every comparison-based algorithm: any such algorithm must perform $\Omega(n\log n)$ comparisons, and so $\Omega(\log n)$ comparisons per element on average; in particular, some element is compared $\Omega(\log n)$ times.

Finally, let us note that the AKS sorting network corresponds to a sorting algorithm which performs $O(\log n)$ comparisons per element (since its depth is $O(\log n)$, and each element can only be compared once in each layer).
> 5 votes

---
Tags: algorithms, data-structures, sorting
---


# Question
Title: Why can PDAs have infinite stack but FSMs cannot have infinite state?
A Finite State Machine cannot accept the language

$$L = \\{ 0^n1^n \mid n \> 0 \\} $$

because it will require infinite amount of memory to remember the number of zeros. But a Push Down Automaton can recognize it with an infinite stack.

Why are we allowing infinite storage for the stack of PDA but not for the states of an FSM? If we can do with an infinite stack, we can also do it with an infinite FSM. So, why is there no "Infinite State Machine"? What's the problem with it?

# Answer
One of the crucial properties of a model of computation is that each *automaton* has a finite description. Both FSMs and PDAs have finite description. In contrast, an "infinite state machine" won't necessarily have a finite description, unless it is constrained somehow.

Also, as mentioned in the comments, an unconstrained infinite state machine can accept *any* language. Indeed, we can construct a machine whose states are $\Sigma^\*$. We define the transition function so that after reading the word $w$, the machine is at state $w$. Thus, by choosing the accepting states, we can obtain any language, making the model uninteresting.
> 2 votes

---
Tags: finite-automata
---


# Question
Title: Show linear bounded automata accepting w is PSPACE-complete
```
ALBA={⟨M;w⟩ | M is linear bounded automata which accepts input w}

```

Show that ALBA is PSPACE-complete.

How I would try to solve it...

1. We need to prove ALBA belongs to PSPACE. So I would construct TM A which accepts \<M;w\>. Simulate M till qng^n steps or when it halts. If it halts: Accept \<M,w\> if M accepts w, otherwise reject. How would be space complexity? I would say it will need n (=size of the tape) so space complexity should be O(n) and then ALBA belongs to PSPACE. Is it correct?
2. We need to do reduction from TQBH to ALBA to prove that ALBA is NP hard, but I have no idea how to do it. How should this reduction be done? TQBF must be 1 if ALBA accepts w i guess, but dont know how to show the proof...

# Answer
Savitch's theorem shows that PSPACE=NPSPACE, which immediately implies that ALBA is in PSPACE.

In the other direction, suppose that $L$ is a language in PSPACE. Thus $L$ is accepted by some machine that uses space $p(n)$. We can construct another machine $L'$ which accepts an input $(x,y)$, erases $y$, and simulates $L$ on $x$. We can reduce $L$ to ALBA by mapping $L$ to $L'$ and $x$ to $(x,0^{p(|x|)})$.
> 1 votes

---
Tags: complexity-theory, turing-machines, reductions, space-complexity
---


title: Random restart technique definition

text:
# Question
Title: Random restart technique definition
I have stumbled across this question about the Random restart algorithm in search problems:

Random restart is technique which used for:

a)algorithms for search in space state when they get stuck

b)algorithms for informed search for better solution

c)algorithms for uninformed search for better solution

d)algorithms for local search for better solution

My thoughts are : it's a) or d) but I cannot decide since random restart is used for local search but we don't need better solution, however I haven't found anywhere that random restart helps us getting unstuck?

# Answer
> 1 votes
Welcome to the Computer Science Stack Exchange.

We have two subjects in search algorithms: **Exploration** and **Exploitation**. Now, Random Restart increases Exploration in your search.

There is no guarantee that random restarts help you to find better solutions. But it will give you this chance to search the space solution better.

So, The answer to your question is that random restart doesn't necessarily help us get unstuck. According to the above facts, (**a**) is wrong. Between the other choices, I pick the last one (**d**). I think random restart doesn't belong to informed and uninformed search.

# Answer
> 1 votes
I could make an argument in favor of both (a) and (d).

If you get stuck, then at some point in the future a random restart will be applied, and then you won't be stuck on the future iteration. So that's a sense in which (a) could be taken to be true. On the other hand, within the current iteration, before you apply the random restart, it won't do anything to help you get unstuck, so that's a sense in which (a) could be taken to be false.

Yes, random restarts can be used with local search, and in some/many cases they allow finding a better solution. So that's a sense in which I view (d) as true.

I am not familiar with the phrases "informed search" or "uninformed search".

---
Tags: algorithms
---


title: Edge-disjoint paths in trees

text:
# Question
Title: Edge-disjoint paths in trees
How do I prove the following proposition?

> Let $T$ be a tree, and let $S$ be a subset of the vertices. If $|S|$ is even then we can partition $S$ into pairs $(x\_i,y\_i)$ such that the paths $x\_i-y\_i$ are edge-disjoint.

# Answer
> 1 votes
Here are some ideas:

* Suppose that $\ell$ is a leaf of $T$ which doesn't belong to $S$. Then we can safely remove $\ell$.
* Suppose that $\ell$ is a leaf of $T$ which does belong to $S$. If its unique neighbor is also in $S$, then we can safely pair them up.
* Suppose that $\ell$ is a leaf of $T$ which belongs to $S$, but its unique neighbor $r$ doesn't belong to $S$. We can safely remove $\ell$ and replace it in $S$ by $r$.

(How to implement these ideas efficiently is a different matter, but for an existence proof these ideas suffice.)

---
Tags: binary-trees
---


# Question
Title: Minimize $f(r,X)$ over all sets $X$ using Dynamic Programming
If a set of numbers $a\_1, a\_2, \cdots, a\_n$ $($such that each $a\_i \in \mathbb{N} \cup \\{0\\})$ and an $r \in \mathbb{N}$ are given, find set $X = \\{x\_0, x\_1, \cdots, x\_r \ | \ x\_0 = 0 \< x\_1 \< \cdots \< x\_r = n\\}$ such that $f(r,X) := \displaystyle\max\_{j=0}^{r-1} \sum\_{i = x\_j}^{x\_{j+1}-1} a\_i$ is minimized over all possible $X$.

---

I can think of a brute force approach, that is, generate $\Theta ({{n-1} \choose {r-1}})$ sets $X$ and calculate the $\max$ for each $X$, each of which takes as many as $r$ steps. This is a very inefficient approach. How do I make it better? I feel like there is a way using DP. (Please feel free to edit the title if this is not DP).

This seems like a possible solution. What if we pre-compute $\displaystyle\Sigma\_{i=j}^{j+k} {a\_i}$ $(k \geq 0)$ for all $1 \leq j \leq n$ first and then create a DP with function $$\text{best}(p,q) = \text{best way of having } q \text{ intervals such that we end at } \[p-x,p\] \text{ for some } x \geq 0$$ Our goal is to find $\text{best}(n,r)$ and backtrack to find the intervals.

$\text{best}(p,q) = \min \\{ \text{best}(p,q-1), \ \max(\text{best}(p-1,q-1), \text{dist}(p-1,p)), \ \max(\text{best}(p-2,q-1), \text{dist}(p-2,p)), \dots) \\}$

where $\text{dist}(x,y)$ = $\displaystyle\Sigma\_{i=x}^{y} a\_i$ which is pre-computed. This probably works but the backtracking seems difficult and time-hungry.

I tried greedy and I could generate counter-examples right away. Was not very helpful.

# Answer
> 2 votes
Main idea: Instead of finding $X$ itself, find the minimum value for $f(r,X)$. After you do this, it is easy to find a minimal $X$. Simply greedily add elements to an interval until the sum of the interval is too large - once this happens, create a new interval at that position.

Finding the minimal value for $f(r,X)$ is a classic (maybe prototypical) binary search problem. The algorithm is as follows: binary search over the answer. Within your binary search, greedily add elements to an interval until the sum of the interval is higher than the answer - once this happens, create a new interval. (Note that this is the same method as is used to construct $X$.) At the end, check how many intervals you have formed - if it is $\leq r$ then it is possible to divide the array into $r$ intervals such that $f(r,X) \leq ans$. The time complexity is $O(NlogS)$, where $S$ is the sum of all $a\_i$.

Although binary search does work for all practical values, your statement does state $\mathbb{N}$ as the possible size of elements. If elements can be arbitrarily large, we can use DP as you mentioned, fairly similar to the DP that you use. $best(p,q)$ can be the minimum $f(\cdot)$ taking $q$ intervals from the first $p$ elements. By transitioning in the same way as your statement, we get a trivial $O(N^3)$ solution.

We can also optimise this DP. One optimisation: $best(x,q)$ is monotonically increasing as $x$ increases, but $dist(x,p)$ is monotonically decreasing. So, we can use binary search to find the intersection of the two lines. The transition is now $O(logN)$ and the overall complexity is $O(N^2logN)$.

Important thing to note: this DP avoids the issues with your DP because it doesn't store the actual $X$ within the DP itself.

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


# Question
Title: Can we generate random numbers using irrational numbers like π and e?
Irrational numbers like $\pi$, $e$ and $\sqrt{2}$ have a unique and non-repeating sequence after the decimal point. If we extract the $n$-th digit from such numbers (where $n$ is the number of times the method is called) and make a number with the digits as it is, should we not get a perfect random number generator? For example, if we're using $\sqrt{2}$, $e$ and $\pi$, the first number is 123, second one is 471, the next one is 184 and so on.

# Answer
The most obvious disadvantage is the unnecessary complexity of PRNG algorithms based on irrational numbers. They require much more computations per generated digit than, say, an LCG; and this complexity typically grows as you go further in the sequence. Calculating 256 bits of π at the two-quadrillionth bit took 23 days on 1000 computers (back in 2010) - a rather prohibitive complexity for an RNG.
> 18 votes

# Answer
For any reasonable definition of perfect, the mechanism you describe is not a perfect random number generator.

* Non-repeating isn't enough. The decimal number $0.101001000100001\dots$ is non-repeating but it's a terrible generator of random digits, since the answer is "always" zero, occasionally one, and never anything else.
* We don't actually know if every digit occurs equally often in the decimal expansion of $\pi$ or $\mathrm{e}$ (though we suspect they do).
* In many situations, we require random numbers to be unpredictable (indeed, if you asked a random person what "random" means, they'd probably say something about unpredictability). The digits of well-known constants are totally predictable.
* We usually want to generate random numbers reasonably quickly, but generating successive digits of mathematical constants tends to be quite expensive.
* It is, however, true that the digits of $\pi$ and $\mathrm{e}$ look statistically random, in the sense that every possible sequence of digits seems to occur about as often as it should. So, for example, each digit does occur very close to one time in ten; each two-digit sequence very close to one in a hundred, and so on.
> 49 votes

# Answer
It is cryptographically useless because an adversary can predict every single digit. It is also very time consuming.
> 28 votes

# Answer
(**updated** after many people pointed out that random number generator is not the same thing as a single normal sequence)

If you ask whether you can get a normal sequence out of $\pi$ (i.e., all numbers appear uniformly), then there are several answers on mathoverflow. For example, the answer about Distribution of the digits of Pi says:

> ...it is *believed* that $\pi$ is a normal number (~uniform distribution of every digits sequence).

For digit distribution data, see e.g. http://www.eveandersson.com/pi/precalculated-frequencies or https://thestarman.pcministry.com/math/pi/RandPI.html (first 1000 digits):

At mathoverflow, there are also nice answers at:
> 7 votes

# Answer
In general, this approach does not work: "randomness" does not mean that you get a lot of different digits, but there are other aspects as well. For example, a classic test is to see if all two-digit, or three-digit etc. combinations occur with the same frequency. This would be a very simple test, which can rule out obvious non-random results, but is still by far too simplistic to check for really random behaviour.

See the Wikipedia page about Randomness Tests as a collection of links to primary sources regarding this. They do mention a good amount of quite complicated-sounding concepts; it is it not so important to go into deep detail about this - but it is clear that it is not intuitively possible to declare a specific number to be a good source for such digits.

On a positive note: For a specific irrational number, you are of course free to just try it; i.e., calculate the number to a sufficiantly large degree of digits, and run it through all known tests (there are tools for that, see above link). If the measure is good enough for your use case, and if you are aware that this is obviously useless for cryptographical applications, and always get the same numbers if you should start over, and that the quality might degrade if you get past the `n` you picked for testing the randomness, you could use those numbers. But it will be far better to use a dedicated (pseudo-)random number generator; and nothing beats a good physical source of randomness.
> 3 votes

# Answer
It provides a good random number right until you realize how it was produced, as with many pseudo random number. The irrational (non algebraic and non transcendental) numbers you have chosen are common and so easier guessed then others. I can see no issue with this method provided you choose less commonly seen generators.
> 2 votes

# Answer
I know this is old, but I can't help but see that the accepted answer is not quite right... so here we go:

Most pseudo random number generators leverage an irrational ratio somewhere in their calculation, because as your intuition suggests, irrational figures are the best source we have to a chaotic sequence of values. Many small implementations of PRNGs you can find in text books, and other such resources utilize a so called "magic number" that is actually a representation of an irrational figure -- for example a value which closely approximates the irrational figure relative to available fidelity of the medium -- and generates output by progressively applying a trivial arithmetic transform -- for example by having stored a seed value that is multiplied and asigned to by the "magic number" -- and returning it.

Ultimately a PRNG has a full cycle of values for any given seed that it will progressively output ad infinitum. The length of the cycles, and how many independent cycles there are and other qualities of the pseudo random sequences are a function of the irrational number used at the core of the algorithm. The golden ratio or phi is proposed as the MOST irrational number, and hypothetically a decent approximation of phi applied to the approach will result in a PRNG that has a single cycle that includes all the possible outputs of the medium, which is great!

Unfortunately, due to the nature of this generation, the cycle is deterministic and repeated ad nausea. This necessarily result in limited domain of ultimately predictable, and reproducible "chaos" that will not include permutations of sub-sequences of the PRNG output. It would literally output EVERY other value it could before it repeated itself, however an application could apply arithmetic operations such as floor, cieling, modulos, integer division, clamping, and so forth to map the many PRNG output values to a desired domain of fewer values, thus obtaining permutations of the fewer values within the desired domain. You Essentially have to throw away some fidelity to get permutations.

Alternatively you can devise a PRNG algorithm that takes into consideration multiple prior outputs, exponentially expanding the potential cycle length, and/or leverages a cycle of irrational figures (potentially from another PRNG) to really mix things up. This would be similar in approach to the enigma machines of WWII that introduces more chaos into the encoding of messages by way of a hidden progressing sequence of arithmetic modifications to determine the encoding of the next symbol. A good example of a method to generating irrational numbers, is to apply exponents to phi. However it should be noted that all irrational numbers you could compute through such means are LESS irrational than phi itself unless the exponent is 1, and especially so if the exponent is 0.

I hope that helped someone.
> 1 votes

---
Tags: randomized-algorithms, randomness, random-number-generator
---


# Question
Title: Uncertainty of coroutines writing to single socket
A program runs in a low-spec hardware utilizes coroutines writes to a single socket but how does the socket know when the data should be sent as there could more coroutines writing given **N** time.

I find this problem similar to *The halting problem* even tho contexts are different.

Does anyone know how could be a one find a optimal solution to solve this problem?

# Answer
I ended up using a buffer limit and a queue.

I knew that this may not answer this question fully but it's the only optimal solution I could find.
> 0 votes

---
Tags: halting-problem, concurrency, tcp
---


# Question
Title: How to apply the Ford Fulkerson algorithm to the assignment problem
I am quite familiar with Ford-Fulkerson algorithm but I am having a trouble to apply the algorithm to the following problem. Can someone please give me some hints or better instructions how to use FF method to this problem?

Let O be a set of n objects. It is required to form a set G of m groups. There are three possibly overlapping subsets of objects: A, B and C. Each object belongs to one or more of these subsets. Each object can be assigned to at most one group. It is required that every group must have at least ten objects: two are from subset A, three others are from subset B, and one other is from subset C; the remaining objects can be from any subset.

It is required to explain how to apply the Ford-Fulkerson algorithm to determine whether it is possible to assign n objects to m groups according to the given rules.

Small addendum (See below the idea suggested by @D.W.): In case of only two subsets A and B, the flow network could look like that (?). I assume that capacities c1, c2, c3 can be found from subset A and B

# Answer
I suggest you start with a simpler problem: there are only two (possibly overlapping) subsets, A and B; and every group must have two objects: one from subset A, and one from B.

Once I figured out how to solve that, it was clear to me how to solve your original question.

Hint on how to solve that:

> Have one left vertex per object. Have two right vertices per group, one to represent which object is chosen from subset A, and one to represent which object is chosen from subset B. Now figure out how to fill in the edges...
> 1 votes

---
Tags: ford-fulkerson
---


title: DNF and CNF and Complexity Theory

text:
# Question
Title: DNF and CNF and Complexity Theory
$F(z\_1,...,z\_n)$ is a Boolean expression. The assignment of variable ($x\_1,...,x\_n \in {0, 1}$) is the answer of $F$, if $F$ for that assignment equals to $1$.

If that case is true and the conditions are met, then both of them are considered to be *NP-Hard*.

---

A) The *number* of *answers* of $F$ in $DNF$ format.

B) The *number* of *answers* of $F$ in $CNF$ format.

> DNF and CNF are HERE

---

Can anyone describe to me in clear, simple, and concise words why both of them are true?

# Answer
Counting the number of satisfying assignments to $F$ is at least as hard as determining whether there is a satisfying assignment. (If the count is 0, there are no satisfying assignments; if the count is $\ge 1$, there is a satisfying assignment.)

For CNF formulas, testing whether there is a satisfying assignment is the SAT problem, which is a classic example of a NP-hard problem.

Counting the number of satisfying assignments of $F$ is at least as hard as determining whether all assignments satisfy $F$. For DNF formulas, this is NP-hard, too.
> 1 votes

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


# Question
Title: reduce k-colorable to 3-colorable graph problem
given a graph G = (V, E) of n vertices, decide whether G is k-colorable. if I were to have an oracle that solves for 3 color, how do I use it to solve the k color graph problem?

# Answer
> 1 votes
It is known that K-Colorability reduces to 3-Colorability in polynomial time as obviously both problems are NP-complete, and NP-complete problems are polynomial-time reducible to each other. However, in order to $k$-color a graph using a 3-coloring oracle, you need a specific reduction from $k$-colorability to $3$-colorability which is constructive in the sense that given a 3 coloring of the output graph, then you have a way to extract from it a $k$-coloring of the input graph (and not only prove that there exists a $k$-coloring). Such a reduction, was shown by László Lovász here. Specifically, it was shown that Colorability reduces to 3-Colorability in polynomial time which is sufficient to solve your problem using the same reduction. Here is a very good explanation by Vašek Chvátal's for Lovász's reduction. The reduction has the following format: given an instance to the Colorability problem which is a pair $\langle k, G \rangle $, where $k$ is a positive integer and $G$ is an undirected graph, the reduction outputs in polynomial time, a graph $G'$ such that $G'$ has a 3-coloring iff $G$ has a k-coloring. The proof in the link is actually constructive, in particular, it details how a k-coloring of $G$ can be easily extracted from a 3-coloring of $G'$ (When I say easily, I mean in polynomial time). So to solve your problem: given a graph $G$, you can consider the pair $x = \langle k, G\rangle$ ($k$ is constant in your problem) and feed $x$ as an input to the reduction to get $G'$ in polynomial time. Now using your oracle, you can 3-color $G'$, and then use the 3-coloring of $G'$ to extract a $k$-coloring of $G$.

---
Tags: algorithms
---


# Question
Title: What is the contradiction in the proof of the halting theorem?
In the standard proof of the halting theorem, you are asked to assume that a TM\_0() exists that takes another TM\_1() and a string W and outputs whether TM\_1() halts or executes forever right on string W, right? The proof seems to be to assume that such a TM\_0() exists. Now a new TM\_2() is taken that takes TM\_0() as input as halts if TM\_0() executes forever, and executes forever if it halts. Now from what I understand such a TM\_2() is supposed to mean a contradiction, which in turn implies that TM\_(0) is a contradiction. I have trouble understanding how this step in TM\_2() constitutes a contradiction. All these steps seem reasonable to me.

# Answer
You actually have a missing detail on how the machine $TM\_2$ is defined (and a bit of confusion between $TM\_1$ and $TM\_0$). Let's clear this up. You start by the assumption that there is a machine $TM\_0$ that operates as follows. On input $x = \<TM\_1, w\>$, the machine $TM\_0$ answers "yes" whenever $TM\_1$ halts on its input $w$, and $TM\_0$ answers "no" whenever $TM\_1$ does not halt on its input $w$.

Now we define a machine $TM\_2$. On input $z = \<TM\_1\>$ which a description of a machine, denoted $TM\_1$, the machine $TM\_2$ runs $TM\_0$ on $x = \<TM\_1, TM\_1\>$ and returns the opposite answer of $TM\_0$. In words, **the machine $TM\_2$ answers "no" when $TM\_1$ halts on itself, and answers "yes" when $TM\_1$ does not halt on itself.**

To get a contradiction, consider what happens when we feed $TM\_2$ to itself as an input. That is, consider the case where the input of $TM\_2$ is $z = \<TM\_2\>$. One of the following holds:

1. $TM\_2(TM\_2)$ = "yes", and so in this case $TM\_0(\<TM\_2, TM\_2\>)$ = "no". Hence, by the definition of $TM\_0$, $TM\_2$ does not halt on itself.
2. $TM\_2(TM\_2)$ = "no", and so in this case $TM\_0(\<TM\_2, TM\_2\>)$ = "yes". Hence, by the definition of $TM\_0$, $TM\_2$ halts on itself.

All in all, we have that by the two items above that $TM\_2(TM\_2)$ = "yes" iff $TM\_2$ halts on itself, which is clearly a contradiction to $TM\_2$'s definition (see the bolded sentence above).
> 1 votes

---
Tags: turing-machines, halting-problem
---


# Question
Title: What's the name of this sorting(?) algorithm?
Given the options of:

* Red
* Orange
* Yellow
* Green
* Blue
* Violet

You want to find your favorite color by comparing all pairs to each other, like so: Red vs...

* Red vs Orange = Orange
* Red vs Yellow = Red
* Red vs Green = Red
* Red vs Blue = Red
* Red vs Violet = Red

Orange vs...

* Orange vs Yellow = Orange
* Orange vs Green = Orange
* Orange vs Blue = Orange
* Orange vs Violet = Orange

Yellow vs...

* Yellow vs Green = Green
* Yellow vs Blue = Yellow
* Yellow vs Violet = Yellow

Green vs...

* Green vs Blue = Green
* Green vs Violet = Green

Blue vs...

* Blue vs Violet = Violet

In the end you'll find your "most preferred". Not sure if you get a full order of preference.

What's the name of this...thing?

Also as D.W. described, I believe it's solved by which color won most often. So in the example above:

* Orange = 5
* Red = 4
* Green = 3
* Yellow = 2
* Violet = 1
* Blue = 0

# Answer
> 1 votes
If we can assume that there is a total order on all colors: to find the largest element, there is a straightforward $O(n)$-time algorithm to find it: you scan through all colors, keep tracking of the largest element seen so far:

* Set $m$ to the first color.
* For each other color $c$:
    + Set $m := \max(m,c)$.

(Here $\max$ refers to the larger of the two colors, i.e., whichever is more preferred.) There is no need to "sort" all of the colors to find the largest (most favorite) color.

Alternative, suppose we cannot assume the colors are totally ordered, and the order is a partial order. Then you'd need to specify what is meant by "most favorite" color. One possible definition is a maximal color, i.e., one where no other color is more preferred. (Note that there may be multiple such colors.) If so, you can again find it via the same linear scan (if two elements are incomparable, you stick with the current element).

---
Tags: algorithms, sorting
---


# Question
Title: What is the correct definition of coNP/poly?
Complexity Zoo defines coNP/poly as
Complement of NP/poly
Thanks to Emil, I understand it as
"the class of decision problems whose complement can be **solved** in polynomial time by a non-deterministic Turing machine that has access to a polynomial-bounded advice function."

(A polynomial-bounded advice function is a function $f$ that maps each positive integer $n$ to an advice string $f(n)$ of length polynomial in $n$. To be clear, the advice string depends only on $n$; it is independent of the input to the Turing machine.)

I don't clearly understand this definition. A decision problem is basically a yes/no question, and I suppose "solving a decision problem" means answering the yes/no question correctly. But, if that is the case, then solving a decision problem is same as solving the complement of the problem. So, I wonder
**What is the meaning of the word 'solve' in the definition of coNP/poly (or NP/poly)?**

I am also interested in whether we can define coNP/poly (or NP/poly) in terms of deterministic polynomial time verifiers (as in the definition of NP). The best I could come up with are the following.

*NP/poly* is the class of decision problems whose yes certificates can be verified in polynomial time by a (deterministic) Turing machine that has access to a polynomial-bounded advice function.

*coNP/poly* is the class of decision problems whose no certificates can be verified in polynomial time by a (deterministic) Turing machine that has access to a polynomial-bounded advice function.

**Are these definitions correct?**

Disclaimer: I have asked a related question in cstheory.stackexchange. At the time of asking that question, I did not know that the problem is in my understanding of the definition. They recommended that I ask the question here. (I shall delete my other question if the only problem is my understanding of the definition).

Thank you

# Answer
Recall that a decision problem is a language $L \subseteq \\{0,1\\}^\*$. (This is the language of all words $w$ such that the answer to the yes/no question is "yes".)

In this context, a Turing machine solves a decision problem $L$ if $L$ is the language accepted by that Turing machine. In other words, when run on input $w$, the Turing machine halts and accepts if $w \in L$, and halts and rejects if $w \notin L$.
> 1 votes

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


# Question
Title: Showing semidecidability without using diagonalization
All the methods I know which shows a given language $L$ is $RE$ but note $REC$ deep down boils down to the cantor's diagonalization arguement in one way or the other, and most commonly it boils down to reducing it to membership/halting problem.

Is there any other fundametnally different way of showing some language is $RE$ but not $REC$, or otherwise is there any heuristic arguement as in we must employ diagaonlization arguement in some form (see also: https://ncatlab.org/nlab/show/Lawvere%27s+fixed+point+theorem)?

# Answer
Your question is a bit hard to answer, since "diagonalization" is not a formal concept (but see below). For example, does the following argument count as diagonalization? Consider the following function: $f(n)$ is the first string not generated by the first $2^n$ Turing machines. If the halting problem is decidable, then $f(n)$ is computable, and so its Kolmogorov complexity is $O(\log n)$. However, by construction, its Kolmogorov complexity is $\Omega(n)$, and we reach contradiction for large enough $n$.

One thing which is common to this proof and the usual one is the use of proof by contradiction. What happens if we disallow proof by contradiction? Can we prove that the halting problem is undecidable in constructive mathematics? I don't know the answer, but if it is negative, then this explains why proof by contradiction is necessary.

Another relevant piece of information is *relativization*. The halting problem is undecidable even relative to an oracle. Therefore, there should be an undecidability proof which uses only relativizing techniques. While this does not imply that *any* proof uses only relativizing techniques, perhaps it means that the "best" proofs should use such techniques. The advantage of this point of view is that it gives a slightly less informal definition of diagonalization, namely, any technique that relativizes.

Finally, let me mention that Kozen formalized the concept of diagonalization in his paper Indexings of subrecursive classes, and showed that every separation of complexity classes (subclasses of computable functions) can be proved by his notion of diagonalization. In his setting (which doesn't include undecidability proofs), diagonalization is the most general type of proof, which can prove all true statements. This means that any proof at all (of such statements) can be cast as a proof by diagonalization.
> 1 votes

---
Tags: turing-machines, semi-decidability
---


# Question
Title: Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free? How can it be shown?
Is $L = \\{ a^ib^j : 0 \< j \< i \< 2j\\}$ context free? If so, can there be a pushdown automaton described for it? If not, does the pumping lemma apply?

# Answer
> 1 votes
To show a language is context free we can create a context free grammar for it then show that it generates all strings in the language.

Consider the following grammar $G$.

```
S -> aaaRbb
R -> aRb | aaRb | eps

```

We must prove that $L(G) = L$.

Proof: The variable $S$ in the grammar starts off with the smallest string in $L$. This string is $aaabb$ with $j=2$ and $i=3$ (since $0 \< j = 2 \< i = 3 \< 2j = 4$).

The repetition happens within the variable $R$. Consider the string $s = a^ib^j \in L$. We want to see whether the string $s' = a^{i+1}b^{j+1}$ is in $L$. The first three conditions are trivial ($0 \< j+1 \< i+1$). The last condition is quick to check: \begin{align} i+1 &\< 2(j+1) \\ i+1 &\< 2j+2 \\ i &\< 2j+1 \\ \end{align} So $s' \in L$. We can show $s' = a^{i+2}b^{j+1} \in L$ similarly.

The rules `R -> aaaRb`, `R -> aR`, and `R -> Rb` cannot be in our grammar as it can generate strings that are not in the language. As an example, the strings `aaaaaabb`, `aaaabb`, and `aaabbb` can be generated if we add the above rules which are not in $L$.

Thus, $G$ is complete. Hence, $L(G) = L$.

As for creating a pushdown automata, there are many guides on how to construct a PDA from CFG. The following links will be useful (just from a quick google search).

1. Convert CFG to CNF
2. Convert CFG to GNF
3. Construct PDA from CFG

# Answer
> 0 votes
What's the smallest possible j, and which i goes with it (to allow j \< i \< 2j). So that's the minimum number of a's and b'. Beyond that, you need one or two a's for every additional b.

That should be enough to find a grammar.

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


title: write adt for stack operations

text:
# Question
Title: write adt for stack operations
Ok, I dont understand whats the difference between: write code for stack operations and write adt for stack operations?

lets say the operation is push() and pop(). So what different code is to be written for adt?

# Answer
> 0 votes
Code is literal programming code (be it C/C++, Java, Python, etc.). We can agree the code will be completely different between languages. In addition, if you are implementing a stack, then you have modify your code depending on what underlying data structure you're using to store the data (c style arrays in C, ArrayLists in Java, etc.).

ADT is a way to express the basic operations of the data type independently from the code (from any programming language). This leads to pseudocode.

For instance, a queue ADT might have the following functions: `enqueue`, `dequeue`, `front`. The `enqueue` function takes data and adds it to the back of the queue; the `dequeue` function removes data from the front of the queue and returns it; finally the `front` function simply returns the first data in the queue but does not remove it.

The above is the most basic queue ADT, but you could have other functions like `back`, `isEmpty`, or even something weird like `thirdPlaceInQueue`. It all depends on what your needs are. Be careful though, giving too much functionality may lead to a different ADT. For instance, if you gave a queue ADT the ability to add to the front and remove from the back, you would then have a deque ADT.

---
Tags: data-structures, stacks, abstract-data-types
---


# Question
Title: Is the language Turing machine-Input pairs for which the computation loops recognizable?
I'm wondering if the following language is $L \in \mathsf{R}$, $L \in \mathsf{RE} \setminus \mathsf{R}$, $\overline{L} \in \mathsf{RE} \setminus \mathsf{R}$: $$L=\\{\<M,w\> \\,\mid M \mbox{ Loops on input } w\\}$$ to be clear: We say that a TM loops on a string if during its run on the string it repeats the same sequence of configurations. Note that every TM that loops on a string is a TM that doesn’t halt on the string but not every TM that doesn’t halt on a string is a TM that loops on the string.
I'm leaning towards $\overline{L} \in \mathsf{RE} \setminus \mathsf{R}$ and wondering if it's possible to map $\overline{L}$ to HALT?

# Answer
The language $L$ is recognizable: you can build a Turing machine that recognizes $L$ by simulating $M$ and keeping track of all the traversed states. As soon as a state is repeated, you accept. If $M$ halts and no stated is repeated, then reject.

Moreover, $L$ is not decidable. Suppose that $L$ was decidable, then you could do the following to solve the halting problem:

* Create a new Turing machine $M'$ behaves as $M$, but instead accepting/rejecting, it goes into some looping state.
* Simulate a Turing machine $T$ that decides $L$ to check whether $\langle M', w \rangle \in L$.
* If $\langle M', w \rangle \not\in L$ then $\langle M, w \rangle$ must not halt.
* If $\langle M', w \rangle \in L$ then either $\langle M, w \rangle$ halts or loops.

+ Simulate $T$ to check whether $\langle M, w \rangle \in L$.
    + If $\langle M, w \rangle \in L$ then $\langle M, w \rangle$ loops, and hence it does not halt.
    + If $\langle M, w \rangle \not\in L$ then $\langle M, w \rangle$ does not loop, therefore it halts.
> 0 votes

---
Tags: turing-machines
---


# Question
Title: What parameter of optimizations, like time solving, can be used to show a phase transition in NP-hard problems?
Before asking the question, I should say that I am not sure here is a proper community to ask this question or not.

I have an NP-hard problem and an optimization to deal with the problem. Recently, I have found that the problem has a phase transition where, before a threshold for a property, the problem can be solved in polynomial time by a greedy approach and, difficult cases are after the threshold.

Now, I want to show this phase transition by some parameters related to the optimization that solves the problem. But, I don't know which parameters can show this phase transition in a valid way, like time-solving, the number of iterations to solve the problem, or .....

# Answer
> 1 votes
There is no contradiction. NP-hard does not mean "large instances can't be solved quickly", rather, it means "there is an infinite number of instances that are hard". Large instances can be easy while small instances can be hard - it's the structure that counts and not size. Put differently, if a problem is NP-hard, it is believed that there is no algorithm which runs in polynomial-time (and is correct) on *every instance*. It is perfectly possible to have algorithms that are fast on particular instances.

So perhaps you misunderstood what phase transition means. Nevertheless, if you want to learn more about it, remember that it is relevant only for *random instances*.

---
Tags: time-complexity, optimization, np-hard, iteration
---


# Question
Title: How can Chomsky hierarchy be applied to languages with alternated letters?
I have the following grammar, which I know it is regular because it can be represented by a finite state automata:

\begin{array}{l} \mathrm{S} \rightarrow \mathrm{X} \mid \mathrm{Y} \\ \mathrm{X} \rightarrow \mathrm{a} \mathrm{Y} \mathrm{b} \mid \mathrm{ab} \\ \mathrm{Y} \rightarrow \mathrm{b} \mathrm{X} \mathrm{a} \mid \mathrm{ba} \end{array}

According to Chomsky hierarchy:

> Type-3 grammars generate the regular languages. Such a grammar restricts its rules to a single nonterminal on the left-hand side and a right-hand side consisting of a single terminal, possibly followed by a single nonterminal (right regular). Alternatively, the right-hand side of the grammar can consist of a single terminal, possibly preceded by a single nonterminal (left regular).

However, I do not find the hierarchy applied to the grammar. Am I missing something?

# Answer
> 2 votes
Every regular grammar produces a regular language.

But:

Not every grammar for a regular language is regular.

In other words, a regular language can be described by any of an infinitude of grammars, some of which are regular and some not.

In this case, you can easily create either a left- or a right-regular grammar for your language. For example:

\begin{array}{l} \mathrm{S} \rightarrow \mathrm{X} \mid \mathrm{Y} \\ \mathrm{X} \rightarrow \mathrm{X} \mathrm{a}\mathrm{b} \mid \mathrm{ab} \\ \mathrm{Y} \rightarrow \mathrm{Y} \mathrm{b} \mathrm{a} \mid \mathrm{ba} \end{array}

Of course, that transformation only preserves the language parsed, not the induced parse trees.

---
Tags: formal-grammars, chomsky-hierarchy
---


# Question
Title: design a strange data structure, is it possible?
I need a FIFO QUEUE that can do Insert and Remove from Queue in amortized $O(1)$ but extract min in $O(log n)$. is it possible?

When just find min is important (not removing) there is lots of $O(1)$ solution for all operation.

Update: All given times is amortized cost.

# Answer
Let us denote four data structure: $Q$, $PQ$, $R\_Q$, and $R\_{PQ}$. $Q$ is a FIFO queue. $PQ$ is a priority queue implemented using a Fibonacci heap. $R\_Q$ and $R\_{PQ}$ are hash-sets. $R\_Q$ stores elements that have been removed from the queue but not removed from the priority-queue yet; $R\_{PQ}$ stores elements that have been removed from the priority-queue but not the queue yet.

Our operations are `insert`, `delete`, and `extract-min`. For insert, we insert the element into $Q$ and $PQ$.

We implement `delete` and `extract-min` lazily. For `delete`, let `x=Q.front()`. If $x$ exists within $R\_{PQ}$, that means it has been removed from the priority-queue already. We pop $x$ and remove $x$ from $R\_{PQ}$. Then, we set `x=Q.front()` and try again. If $x$ is not within $R\_{PQ}$, then this is the element we should remove. We pop $x$ and insert it into $R\_Q$.

For `extract-min`, we essentially do the reverse. We take `x=PQ.top()` until $x$ does not exist within $R\_Q$, and when it does we pop $x$ and insert it into $R\_{PQ}$.

Time complexity for `insert`: $O(1)$ (since we are using Fibonacci heap)

Time complexity for `delete`: amortized $O(1)$ (hash-sets work in amortized constant, and all our operations are either the deletion or lazy extract-min deletions.)

Time complexity for `extract-min`: amortized $O(logn)$ (hash-sets work in amortized constant, all our operations are either the deletion or lazy extract-min deletions, but logn factor due to PQ)

**Update** Code (C++):

```
struct strange_ds{
    queue<int> q;
    priority_queue<int> pq;
    unordered_set<int> rq, rpq;

    void insert(int x){
        pq.push(x); q.push(x);
    }

    void delete_ele(){
        while(true){
            int t = q.front();
            if(rpq.count(t)){ //already removed from pq
                q.pop();
                rpq.erase(t);
                continue;
            }
            q.pop();
            rq.insert(t);
            return;
        }
    }

    int extract_min(){
        while(true){
            int t = pq.top();
            if(rq.count(t)){ //already remove from q
                pq.pop();
                rq.erase(t);
                continue;
            }
            pq.pop();
            rpq.insert(t);
            return t;
        }
    }
};

```

Note that the code uses a standard C++ priority queue, which is *not* a Fibonacci heap, but this can be straight-swapped in. Also, the code assumes that element values are unique, but this can be accounted for in the case that they are not (by associating elements with unique IDs).
> 1 votes

---
Tags: algorithms, data-structures, arrays, amortized-analysis
---


title: How to determine if 2 rays intersect?

text:
# Question
Title: How to determine if 2 rays intersect?
We are given the 2D coordinates of 2 points: the first point is where the ray starts and it goes through the second point. We are given another ray in the same way. How do we determine if they have a point of intersection? I would like to know the general algorithm and its explanation, don't mind about the extreme cases (e.g. when the rays have the same starting point). P.S. I saw a similar question on another stack exchange, but the answers did were not backed up by explanation.

# Answer
> 1 votes
I'm copying my answer for the similar question \- with minimal changes.

---

The vector equation:

$$P\_1 + \alpha * (P\_2 - P\_1) = P\_3 + \beta * (P\_4 - P\_3)$$

where $P\_1 = (x\_1, y\_1)$ etc., should have a solution, satisfying following conditions:

$$\alpha \ge 0, \beta \ge 0$$

then these two rays $(P\_1, P\_2)$ and $(P\_3, P\_4)$ do intersect. However, there are many corner cases here (for example, $P\_1 = P\_2$ etc.). Also, you can get wrong answers because of the limited precision of your data representation in computer.

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


# Question
Title: How to reduce the original partition problem to one of its variation?
Here's a statement of the set partition problem:

The set partition problem takes as input a set $S = \\{ a\_1, a\_2, ..., a\_n \\}$(all positive integers). Can $S$ be partitioned into two sets $A$ and $B$ such that the sum of the numbers in $A$ is equal to the sum of the numbers in $B$?

Here's a statement of a variation of the set partition problem:

Given an input set $S = \\{ a\_1, a\_2, ..., a\_n \\}$ (all positive integers), can you partition $S$ into $A$ and $B$ such that $| \sum\_{i \in A} a\_i - \sum\_{i \in B} a\_i| \< 1000$?

My goal is to show that the variation is NP-complete by reducing the set partition problem to the variation, and here's what I've tried:

1. Given an instance of the set partition, $S$, let the total sum of its elements be $s$, then create a set $S \cup \\{ s + 1000, s \\}$ as an instance for the variation. But this doesn't seem to do the trick.
2. Given an instance of the set partition, $S$, do something to the elements in $S$ (for example, multiply by 2, subtract by 1000). This path feels promising but I'm again stuck.

# Answer
> 1 votes
Thanks to D.W.'s generous help, I managed to figure it out. Given an instance of the Partition problem, $S$, we can just scale every element in $S$ by 1000, and the new $S'$ becomes an instance of the variation. Then the reduction mapping holds, because scaling increases the difference between numbers. If $S$ is a YES instance, $S'$ can also be partitioned into two sets with equal sum, but if $S$ is a NO instance, all of the possible partitions of $S'$ must have difference $\geq 1000$. The reduction is clearly polynomial, and the variation is clearly in NP, so proof is complete.

# Answer
> 0 votes
Hint:

> If $k$ is an integer and $|1000k| \< 1000$, then what can you conclude about $k$? How could that be useful?

---
Tags: np-complete, partitions
---


# Question
Title: NP-complete problem of partitioning into several sets with a Hamiltonian cycle
How to prove the $NP$-completeness of the language $L$ = $\\{$$(G, k)$: the vertices of an undirected graph $G$ can be partitioned into $k$ pairwise disjoint sets of pairwise different sizes so, that all the corresponding induced subgraphs have a Hamiltonian cycle}. I had no problems how to prove that this language is in the $NP$, but it is not clear to me how to prove that this language is in the $NP-hard$ class.

# Answer
You can map any $\text{HamiltonianCycle}$ instance $G$ to an $L$-instance $(G, 1)$, yielding a polynomial time reduction from an $\mathsf{NP}$-complete problem to $L$ which implies the $\mathsf{NP}$-hardness of $L$.
> 1 votes

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


# Question
Title: Prove that following grammar is ambiguous; S → a | S + S | S S | S* | ( S )
Prove that the following grammar is ambiguous; S → a | S + S | S S | S\* | ( S ) checking ambiguity in grammar. the subject of this question is compiler construction and automation. would you please help me find the answer we only have to figure out whether its ambiguous or not

# Answer
To show the grammar is ambiguous, you must find a string derived by the grammar which has two or more distinct parse trees. I think we have a few options here. One that should work is S + S\*:

```
                   S
                  /
                 /
   S            S--+
  /            / \
 /            /   \
S--+         S     S
 \            \
  \            \
   S--S         *
    \
     \
      *

```

These derivations are fundamentally different (not just different orderings of the same derivation) and so the string S + S\* is fundamentally ambiguous. Does it mean (S + S)\* or does it mean S + (S\*)?
> 2 votes

# Answer
A grammar is ambiguous if it can generate a string in more than two ways, i.e. a string generated by the grammar does not have a unique parse tree.

The grammar you have can generate the string `a + a + a` by the following parse trees.

```
          S             S
        / | \         / | \
       /  |  S       S  |  \
      /   |  |       |  |   \
     /    |  |       |  |    \
    S     |  |       |  |     S
  / | \   |  |       |  |   / | \
 S  |  S  |  |       |  |  S  |  S
 |  |  |  |  |       |  |  |  |  |
 a  +  a  +  a       a  +  a  +  a

```

This shows that the grammar is ambiguous.
> 2 votes

---
Tags: automata
---


title: MST and some facts via an example

text:
# Question
Title: MST and some facts via an example
$M$ is an MST of the Weighted Graph - $GR$.

Let $A$ be a vertex of $GR$ then $M-${$A$} is also MST of $GR-${$A$}.

Let $A$ be a leaf of $M$ then $M-${$A$} is also MST of $GR-${$A$}.

If $e$ is a edge of $M$ then ($M-${$e$}) is a forest of $M1$ and $M2$ trees such that for $M\_i, i=1,2$ is a MST of Induced Graph $GR$ on vertexes $T\_i$.

My notes tell me that the **first** and **last** is false. I need some idea of how to understand the validity of these sentences in a more simple and concise manner.

# Answer
> 2 votes
## Preamble

I'll use the following example to illustrate each statement. The graph below will be $GR$.

Below is the MST $M$ of $GR$. These are the bolded edges.

## Statement One

The first statement is false if $A$ is an internal vertex of $M$. In that case, $M-\\{A\\}$ will result in a forest, which is not an MST.

Suppose we choose $A = d$, then $M-\\{A\\}$ will result in the following graph which is not a tree.

## Statement Two

The second statement is true. It is pretty easy to see why $M-\\{A\\}$ in this case is still an MST.

Suppose we choose $A = a$ (our only choices are $\\{a,g,i\\}$), then $M-\\{A\\}$ (left) will result in the following tree. We can compare it to $GR-\\{A\\}$ (right) and see that it is an MST.

## Statement Three

The third statement is true.

**Formal Proof of Statement Three**

Proof: Let $GR\[T\_1\]$ and $GR\[T\_2\]$ be induced subgraphs of $GR$ and $M\_1'$ and $M\_2'$ are their MSTs respectfully. Let $X$ be the set of edges that connect vertices of $T\_1$ and $T\_2$ in $GR$ (note $e \in X$).

To show $M\_1$ and $M\_2$ are MSTs, we must show is $M\_1 = M\_1'$ and $M\_2 = M\_2'$.

Let $w(M) = w(M\_1) + w(e) + w(M\_2)$ be the cost of the MST of $GR$.

Let $w(M\_1')$ and $w(M\_2')$ be the cost of the MST of $GR\[T\_1\]$ and $GR\[T\_2\]$.

Construct the graph $M' = M\_1' \cup e \cup M\_2'$. This graph is the MSTs of both induced graphs and a single edge that connects them. Note, we could use any edge from $X$, however for it to be a MST, we must select the minimum cost edge of $X$. So $w(M') = w(M\_1') + w(e) + w(M\_2')$.

Since $w(M\_1')$, $w(e)$, and $w(M\_2')$ are minimal, then $w(M')$ is minimal. Since $w(M')$ is minimal, then $w(M') = w(M)$. So,

\begin{align} w(M\_1') + w(e) + w(M\_2') &= w(M') \\ &= w(M) \\ &= w(M\_1) + w(e) + w(M\_2). \end{align}

So $w(M\_1') = w(M\_1)$ and $w(M\_2') = w(M\_2)$, thus $M\_1' = M\_1$ and $M\_2' = M\_2$. Hence, $M\_1$ and $M\_2$ are MSTs.

**Intuition of Proof**

I'll pick $e = \\{c,d\\}$ to be the edge with weight one for this example. Below is $M-\\{e\\}$

Let $M\_1$ be the tree on the left and $M\_2$ be the tree on the right. Then $T\_1 = \\{a,b,c\\}$ is the vertex set of $M\_1$ and $T\_2 = \\{d,e,f,g,h,i\\}$ is the vertex set of $M\_2$. We need to construct the induced subgraphs of $GR$ on $T\_1$ and $T\_2$, $GR\[T\_1\]$ and $GR\[T\_2\]$. Below on the left is $GR\[T\_1\]$, and below on the right is $GR\[T\_2\]$.

Now you can see the $M\_1$ is the MST of $GR\[T\_1\]$ (similarly for $M\_2$).

In the proof, we abuse the fact that the MST of the induced subgraph and the original graph are minimal. We also use the fact that $M$ must contain $e$, the smallest edge that connects $M\_1$ and $M\_2$. We can conclude the only MST of the induced graphs is $M\_1$ (for the left) and $M\_2$ (for the right).

I hope this helps!

---
Tags: algorithms, graphs, data-structures, trees
---


title: k-query oracle Turing machine

text:
# Question
Title: k-query oracle Turing machine
A k-query oracle Turing machine can query its oracle for at most $k$ times. How could I show that assuming $\text{NP} \not= \text{coNP}$, we have $\text{NP} \cup \text{coNP} \subsetneq \text{P}^{\text{SAT},1}$ (query only once)? I tried to show this strict inclusion directly or its counterexample but to no avail... There was such a question on this site, but the top vote isn't a direct answer. Could somebody provide me more insight into this again? Thanks!

More specifically, I wonder how should I think of these $k$-query machines from machines with unlimited number of queries. I can see that they should have limited computation power, but I'm not sure how to utilize that for the proof.

# Answer
Let's try to show the contrapositive. Since $\mathsf{NP} \cup \mathsf{coNP} \subseteq \mathsf{P}^{\mathsf{SAT},1}$, the contrapositive states that if $\mathsf{P}^{\mathsf{SAT},1} \subseteq \mathsf{NP} \cup \mathsf{coNP}$ then $\mathsf{NP} = \mathsf{coNP}$. Let us assume, therefore, that every problem in $\mathsf{P}^{\mathsf{SAT},1}$ is both in $\mathsf{NP}$ and in $\mathsf{coNP}$. We would like to show that this implies that $\mathsf{NP} = \mathsf{coNP}$.

We can imagine that the argument will have the following structure:

1. Come up with some language $L \in \mathsf{P}^{\mathsf{SAT},1}$.
2. The assumption implies that $L \in \mathsf{NP}$ or $L \in \mathsf{coNP}$.
3. Use these facts to say something about the relation between $\mathsf{NP}$ and $\mathsf{coNP}$.

Our goal is to show that $\mathsf{NP} = \mathsf{coNP}$, or equivalently $\mathsf{NP} \subseteq \mathsf{coNP}$. This, in turn, is equivalent to showing that $\mathsf{SAT} \in \mathsf{coNP}$. Considering the plan above, what we need is to find a language $L \in \mathsf{P}^{\mathsf{SAT},1}$ such that both $L \in \mathsf{NP}$ and $L \in \mathsf{coNP}$ imply $\mathsf{SAT} \in \mathsf{coNP}$.

We can take as $L$ the following language: $$ L = \\{(x,0) : x \in \mathsf{SAT}\\} \cup \\{(x,1) : x \notin \mathsf{SAT}\\}. $$ Details left to you.
> 0 votes

---
Tags: complexity-theory
---


title: What is the exponent of 0.00000072

text:
# Question
Title: What is the exponent of 0.00000072
And how do I solve this?

I know this is a decimal and we have to convert it to an exponent. I want to know how I would solve this and the steps as well so I will be able to solve questions similar to this in the future. Thank you

# Answer
> 2 votes
The number 0.00000072 has no exponent.

My best guess is that this question is about scientific notation. Every non-zero real number can be written in the form $\pm d\_0.d\_1d\_2d\_3 \ldots \times 10^e$, where $d\_0 \neq 0$. Here $e$ is the exponent. Some examples:

* $32 = 3.2 \times 10^1$. The exponent is $1$.
* $-0.0014 = -1.4 \times 10^{-3}$. The exponent is $-3$.
* $3.14159 = 3.14159 \times 10^0$. The exponent is $0$.

Hopefully now you can solve the question on your own.

---
Tags: discrete-mathematics
---


# Question
Title: What's wrong with this substitution for master's method
I was hoping to solve the following recurrence by performing a simple substitution followed by the master's method: $$T\left(n\right)=T\left(n-1\right)+n^2$$ I did $$S\left(2^n\right)=S\left(2^{n-1}\right)+\left(2^n\right)^2$$ Thus $$S\left(m\right)=S\left(\frac{m}{2}\right)+m^2$$ Which using the master's method yields $$T\left(n\right)=\Theta \left(\left(2^n\right)^2\right)$$ However, the correct answer to this is: $$T\left(n\right)=\Theta \left(n^3\right)$$ So what was wrong with my substitution?

# Answer
> 1 votes
The key thing to note is that you are replacing $T(n)$ function with an exponential $S(n)=2^n$. The variables do not change just the functions. So, $n^2$ stays.

---
Tags: complexity-theory, recurrence-relation, big-o-notation
---


title: P-NP related 3 sub-problems

text:
# Question
Title: P-NP related 3 sub-problems
This is a question on a practice final.

> Which of the following statements are true? If it is false, what is the underlying reason behind that?

> I. *If 3-CNF-SAT is in P, then Clique is also in P*.

> II. *For decision problems $L\_{1}, L\_{2}$ in NP, if P is not NP, $L\_{1}$ is at least as hard as $L\_{2}$, and $L\_{2}$ is at least as hard as $L\_{1}$, then $L\_{1}$ and $L\_{2}$ are NP-complete*.

> III. *For decision problems $L\_{1}, L\_{2}$ in NP-complete, if $L\_{1}$ is not in P, then $L\_{2}$ is also not in P*

We are told that only the third statement is True, but there's no explanation why on the key. I have tried to figure this out, and the only conclusion I've come to is:

(I) cannot be true because if A is polynomially reducible to B, this implies B is at least as hard as A, not vice-versa (Not sure if this is a correct conclusion, so feedback on this would be appreciated.)

---

This is the first time I'm learning about the notion of hardness, so I don't understand most of the technical explanations I've found. Any clarifications on why I, II is incorrect, and why III is correct would be appreciated.

Self study I've done includes reading multiple StackExchange posts, multiple Wiki pages, and the corresponding section in the Cormen book. I just personally understand concepts better if I see different explanations.

# Answer
You are right about $1$.

For $2$, $L\_1$ reduces to $L\_2$, means $L\_1$ as least as hard as $L\_2$. But not vice versa as adding numbers is in $P$ and tower of Hanoi is in $EXP$, so the later is hard but addition does not reduce to tower of Hanoi. Just knowing the hardness does not say much. Hence the statement is false. If it were not the case, then statement $2$ would have been true.

For $L\_1, L\_2\in NP\\;Complete$, as $L\_1,L\_2\in NP$, $L\_1$ reduces to $L\_2$ and $L\_2$ reduces to $L\_1$, according to NP-Complete definition. So, their hardness is same. So, they both belong to the same class. Hence, $L\_1\in P\Rightarrow L\_2\in P$ and vice versa. So, $3$ is correct.
> -1 votes

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


# Question
Title: Is Dual Graph of a Triangulation of a Polygon Tree?
I have read that; if a polygon contains a hole in it, then the dual graph of a triangulation of the polygon not have to be a tree. But could not get it exactly. How is it possible, what is the relation with the hole in it? If anyone could explain it with a polygon contains hole. I would be very happy and thanks in advance.

# Answer
Below is an example of a polygon with a single hole. The red area is the interior of the polygon, and the white triangle in the center is the hole (which lies outside the polygon). In the figure, I've also drawn a triangulation of this polygon. The dual of this triangulation is a cycle with $6$ vertices, and this is not a tree.

However, is this thing I've drawn here really a polygon? That depends on which definition of "polygon" you use. A polygon is often defined as an area bounded by a single polygonal chain that does not intersect itself. This type of polygon is also known as a *simple polygon*. Sometimes, we want to talk about generalizations of this simple polygon. A *polygon with holes* is a connected area bounded by several polygonal chains that do not intersect themselves or with each-other.

So, for this answer, I will define a *polygon* to be either a simple polygon or a polygon with holes. This means that above, I've shown an example of a polygon with a triangulation of which the dual graph is not a tree. This particular polygon is actually an example of something that holds more generally: the dual of a triangulation of a polygon is a tree if and only if the polygon is simple. (Proof idea: since a polygon is connected, the dual graph of the triangulation is also connected. Observe that the boundary of the polygon is disconnected if and only if the dual graph of the triangulation contains a cycle. Since a tree is defined as a connected acyclic graph, the claim follows.)
> 2 votes

---
Tags: algorithms, graphs, computational-geometry, polygons
---