# Question
Title: Generate a set of X int numbers positive and negative that add up to target value
I want to generate a set of X int numbers, were 4 \<= X \<= 100, both positive and negative that add up to target value. The numbers are between -6 and 4 and there needs to be at least 2 negative numbers, and up to half of the numbers can be negative.

I have seen posts about this being done for all positive numbers but I haven't figured out how adapt it to my case were there need to be negatives.

I have thought of an algorithm but was wondering if a better solution is already available/known or possible improvements to my algorithm.

Psudo Code with Example

PositiveNumbers = [0, 1, 2, 3, 4]
OriginalTarget = 4
numOfTerms = 5

numberOfNegatives = rand(2, numOfTerms/2)
numberOfPositives = numOfTerms - numberOfNegatives

// Restriction only 10% of positives can be 4s
maxNumberOfFours = numberOfPositives * .10

//Generate and save negatives numbers between -6 and -1
int[] negatives = generateNegatives(numberOfNegatives)
negativeSum = calculateNegativeSum(negatives)

// Calculate new Target
Target = OriginalTarget - negativeSum

// Makes sure we can reach the target with the amount of numbers we have left
// Calculate max positive sum possible >= Target
targetRechable = CalculateMaxPossibleSum(numberOfPositives, maxNumberOfFours, target)

If targetReachable --> use algorith to generate positive numbers that reach target

else {
    while (!targetRechable) {
        int[] negatives = removeLastNegative()
        negativeSum = calculateNegativeSum(negatives)

        Target = OriginalTarget - negativeSum

        targetRechable = CalculateMaxPossibleSum(numberOfPositives, maxNumberOfFours, target)

    }
    use algorithm to generate positive numbers that reach target
}
 ```

# Answer
> 1 votes
# Quick and dirty hack

Here is a simple, easy-to-implement approach that meets your requirements and might be good enough when $X \le 100$. It does not guarantee a uniform distribution.

We will randomly and independently select $X$ numbers, from some distribution. Then, we'll test whether that list of $X$ numbers meets all the requirements (sums to the target $T$, has at least 2 negative numbers and at most $X/2$ negative numbers). If it does, we'll use that list of numbers. If it doesn't, we'll go back to the beginning and try again with new random choices. This is known as rejection sampling.

I propose a distribution on each number, to make this more efficient. In particular, let $T$ be the target number, and define $t=T/X$. Then there are two cases:

* If $t \le 1.8$, define $p=(t+3.5)/5.5$, and with probability $p$, choose a random number from 0..4; otherwise choose a random number from -6..-1.
* If $t \> 1.8$, define $p = \min(1-2/X,(t - 1.5 + 10/X)/2.5)$, and with probability $2/X$, choose a random number from -6..-1, with probability $p$, choose 4, and with probability $1-p-2/X$, choose a random number from 0..3.

Use this distribution for each number in the list. These distributions are chosen to have expected value equal to $t$ (so that rejection sampling will work well, and the number of iterations needed will be manageable), and so that it's likely we'll have an acceptable number of negative numbers in the list.

# Principled solution

Alternatively, here is a solution that gives the best possible randomness, but unfortunately will be more complicated to implement. Let's say that a list of numbers is a *solution* if it satisfies all of your conditions. Then, it is possible to sample uniformly at random from the set of solutions.

The core technique is that we'll construct an algorithm count the number of solutions. In fact, we'll define an ordering on all possible solutions, call it $\prec$, so that $x \prec y$ means that the solution $x$ comes before $y$ in the ordering. Then, we'll design an algorithm that given an index $r$, lets us find the $r$th solution in this ordering. With these building blocks, it becomes simple to generate a random solution: we count the number $n$ of solutions, we randomly pick a number $r$ in the range $1,\dots,n$, and then we find the $r$th solution and output it. By construction, this will sample uniformly at random from the set of all solutions.

How do we count the number of solutions? Using dynamic programming. Let $A\[i,s,k\]$ count the number of solutions such that the first $i$ numbers sum to $s$, and there are $k$ negative numbers among the first $i$ numbers. We can use dynamic programming to compute $A\[i,s,k\]$ for every value of $i,s,k$, using a recurrence:

$$A\[i,s,k\] = \sum\_{x=-6}^{-1} A\[i-1,s-x,k-1\] + \sum\_{x=0}^4 A\[i-1,s-x,k\].$$

Finally, if $t$ is the target value, then $\sum\_{k=2}^{X/2} A\[X,t,k\]$ counts the number of solutions.

Now, given an index $r$, how do we find the $r$th solution in an appropriate ordering? This is called "unranking". The procedure itself gets messy, but conceptually it is simple: we are traversing backwards through the recurrence, using $A$ to figure out how to fill in the last element so that the number of elements that precede the solution we'll pick will be less than $r$.

Basically, we can put solutions to your problem into one-to-one correspondence (isomorphism) with paths through a DAG. Each vertex in the graph corresponds to a tuple $(i,s,k)$. The DAG has a single starting node, with an edge from the start node to $(X,t,k)$ for each $k=2,3,\dots,X/2$. The DAG also has a single ending node, $(0,0,0)$. Using the recurrence above, we can see that each path through the graph from the start node to the end node can be mapped to a solution to your problem. The dynamic programming above is basically counting the number of such paths in this graph.

Now our unranking algorithm can be viewed as finding the $r$th path in this graph, and mapping it to a solution to your problem. For how to do that, see Efficiently sampling shortest $s$-$t$ paths uniformly and independently at random and Algorithm that finds the number of simple paths from $s$ to $t$ in $G$ to understand the core concepts here.

If we expand this out in the specific case of your particular problem, I think it looks something like the following (warning: it gets incredibly messy). First, we find $k^\*$ such that

$$\sum\_{k=2}^{k^\*-1} A\[X,t,k\] \le r \< \sum\_{k=2}^{k^\*} A\[X,t,k\].$$

Next, we let $r' = r - \sum\_{k=2}^{k^\*-1} A\[X,t,k\]$. Next, defining

$$f(x^\*) = \sum\_{x=-6}^{\min(-1,x^\*)} A\[X-1,t-x,k^\*-1\] + \sum\_{x=0}^{x^\*} A\[X-1,t-x,k^\*\],$$

we find $x^\*$ such that

$$f(x^\*-1) \le r' \< f(x^\*),$$

we define $r'' = r - f(x^\*-1)$, and $k'=k^\*-1$ if $x^\*\<1$ or $k'=k^\*-1$ if $x^\*\ge 1$. Then we decide that the last element in the list of numbers will be $x^\*$, and the list will contain $k^\*$ negative numbers. We can recurse to fill in the entire list, going backwards to front.

I haven't checked the math above carefully, so please try to understand the concept, and then work out the solution for yourself, to make sure I haven't made mistakes along the way.

# Answer
> 0 votes
For example, if X = 100 then obviously the smallest number is -300 (50 times -6 and 50 times 0) and the largest is 390 (2 times -1 and 98 times 4). An algorithm to pick the numbers for each target is quite trivial.

# Answer
> 0 votes
The case with negatives is not different.

Consider $X$ numbers in the range $1$ to $11$ and add $7X$ to the target. Then you can apply the known algorithm. (I assume that this algorithm can also handle the constraint "between $2$ and $X/2$ numbers are below $7$".)

---
Tags: algorithms
---


# Question
Title: Non rigorous argument that $P \ne NP$ implies $avgP \ne distNP$
Consider the following nonrigorous argument that $P \neq NP$ implies $avgP \neq distNP$. (For those unfamiliar with the latter complexity classes, they deal with average case hardness.)

Suppose A is the algorithm that solves some NP complete problem (say 3-SAT) with the fastest average case complexity possible and suppose that this complexity is polynomial. Then given that $P \neq NP$, this algorithm must run in super-polynomial time on some subset of all inputs to 3-SAT.

Now let us define a new NP-complete problem (call it 3-SAT’) where its instances are all instances of 3-SAT in which algorithm A takes super-polynomial time to run.

Then no algorithm A’ that solves 3-SAT’ can run in polynomial time on average - if it could, then it would be possible to create a new algorithm that solves 3-SAT faster on average than algorithm A by applying algorithm A to all non instances of 3-SAT’ and applying algorithm A’ to all instances of 3-SAT’.

Therefore, $P \neq NP$ implies $avgP \neq distNP$.

One problem with this argument is that it assumes that it is possible to tell the difference in polynomial time between instances of 3-SAT’ and non instances of 3-SAT’; in other words the argument assumes it is possible to efficiently determine which instances of 3-SAT are hard, which I am not sure is true.

Has my observation been made in the literature and how has it been dealt with? Are there any other problems with my argument?

# Answer
Let $X$ be the chosen subset of inputs to which we can restrict 3-SAT such that algorithm A remains superpolynomial.

> Then no algorithm A’ that solves 3-SAT’ can run in polynomial time on average

This does not follow from your argument. At best, assuming you can determine whether input lies in $X$ in polynomial time, this argument shows any algorithm that solves 3-SAT' in polynomial time has the same running time as A on $X$. For example, if we choose $X$ to be equal to all inputs of 3-SAT, the algorithm A is a valid choice for A'.

In general, you would need to prove there is an algorithm that is *strictly* faster on average than algorithm A on $X$. While it would seem easier to construct an efficient algorithm for only $X$ and not the rest of the input, there is no guarantee that the restricted input gives a more efficient algorithm.

---

As for the literature, I believe it is unknown whether $\mathsf{P}\neq \mathsf{NP}$ implies $\mathsf{avgP}\neq \mathsf{distNP}$. What is known is that $\mathsf{E}\neq \mathsf{NE}$ implies $\mathsf{avgP}\neq \mathsf{distNP}$ (S. Ben-David, B. Chor, O. Goldreich, and M. Luby. *On the theory of average case complexity*, Journal of Computer and System Sciences 44(2):193-219, 1992.)
> 2 votes

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


# Question
Title: Need to create CFG that requires sum of other letters
I have a homework assignment that requires me to create CFG $G$ for

$$L = \\{a^i b^{i+j+k} c^j d^k\\}$$

so that it can accept words like ab, aaabbbbd, abbbcd, but it should not accept abba, aabbbbbc, or abc since the number of b must be the number of a+c+d.

I need CFG of L(G)

* I tried using chatgpt but the answers are not correct as I cross checked them with both gpt and myself.
* I tried to cross check this pdf but they are not as complex as my question.
* There is also a solution on chegg I can't see the whole solution as I don't have a subscription, but the final solution is also wrong as I checked it with both chatgpt and myself.
* Also researched multiple sources but did not found the answer.

The best one i came up with this grammer but it doesn't feel right since it does not have corelation between b c and d.

```
1. attempt:

S → AB
A → aAb | ε
B -> bCEdD
C -> bB | ε
D -> dD | ε
E -> bEc | ε

2. attempt :

S → AB
A → aA | ε
B → bBC
C → cC | Cd | ε
D → dD | ε

```

Is it possible to do it with cfg and how?

# Answer
Use the nesting structure of the language to obtain a context-free grammar.

$a^i\\, b^{i+j+k}\\, c^j d^k = a^i b^i\\, b^k b^j c^j d^k $

We can see that the language is the concatenation of strings of the form $a^i\\, b^i $ and strings of the form $b^{j+k}\\, c^j d^k$ which each separately form context-free languages.
> 0 votes

# Answer
$S\rightarrow AD$
$A\rightarrow aAb,\varepsilon$
$D\rightarrow bDd, C$
$C\rightarrow bCc, \varepsilon$.

In this solution I divided the word into a prefix of $a^ib^i$ and a suffix of $b^{j+k}c^jd^k$. The latter part is generated by building $b^kCd^k$ and then replacing $C$ with $b^jc^j$.
> 0 votes

---
Tags: finite-automata, context-free, pushdown-automata
---


title: Find $T(n)$ from $T(n^3)$

text:
# Question
Title: Find $T(n)$ from $T(n^3)$
Consider $$\begin{align} T(n^3)&=T((n-1)^3)+n\\ T(1)&=1 \end{align}$$

According to the substitution method, $T(n^3)=O(n^2)$ (please if I wrong, correct me). Now, what is the answer of $T(n)$? I think $T(n)=O(1)$ but the answer of my teacher is $T(n)=O(n^\frac{2}{3})$.

# Answer
> 1 votes
Define a function $S(n) = T(n^3)$. Then $S(n) = T(n^3) = T((n-1)^3 + n = S(n-1) + n$, and $S(1) = T(1^3) = T(1) = 1$. The answer is obviously the sum of n from 1 to n, or $n(n+1) / 2$.

So $S(n) = T(n^3) = n(n+1) / 2$, and $T(n) = n^{1/3} (n+1)^{1/3} - 1$ whenever n is a cube of some integer.

Just try T(1000) = T(729) + 10 = T(512) + 9 + 10 = ... = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55. It's often useful not to just do some formula manipulation but use real numbers (I think there's a quote by Euler about that, after he worked all night proving a completely nonsensical result once).

---
Tags: algorithms
---


# Question
Title: Making statements about quantum complexity theory
It is my understanding, based on this question that problems solved on quantum computers with oracles don’t make any statements about BQP in relation to other complexity classes.

> The fallacy is in the construction of the algorithm. It uses an oracle. That oracle computes something using the function in a very specific way. So the statement is really "if we compute using this oracle, then we can prove that separation".

So how do we make statements about BQP then? Almost all quantum algorithms input some sort of oracle. Grover’s algorithm inputs an oracle $U |x \rangle = (-1)^{f(x)} |x\rangle$. Shor’s algorithm inputs $U |y \rangle = |ay \\; mod \\; N\rangle$.

Does this mean that factoring isn’t actually in BQP (or functionBQP) as we know? If so, how could we prove or disprove this claim.

# Answer
Shor's algorithm does not use an oracle. The input is a number $n$ to be factored. $U$ is not an oracle; it is a computation that is done by the algorithm (akin to a subroutine).
> 1 votes

---
Tags: quantum-computing, oracle-machines, factoring, oracles
---


title: Complexity of this variant of $⊕2SAT$?

text:
# Question
Title: Complexity of this variant of $⊕2SAT$?
The problem $⊕2SAT$ is defined as a problem where we need to find the parity of the number of solutions of $2$-$CNF$ formulae and is known to be $\oplus P$ complete.

I introduce the following variant of $⊕2SAT$:

In this variant we put the restriction on the input of the $⊕2SAT$ problem the restriction is that every input must contain all clauses that contain a specific variable ,for concretness ,let's say we put the restriction on the input such that every input must contain all 2-literal clauses that contains variable (a) .

I want to ask if this variant of variant remains $\oplus P$ complete.

I think this variant is $\oplus P$ complete ,my reasons are that the output of this type of problem is restricted to either true or false thus ,I think even if we apply the above restriction the input should be able to express any $⊕2SAT$ without changing the output of the $⊕2SAT$ instance.

# Answer
> 2 votes
This problem can be solved easily: trivially, the number of solutions is 0, so the parity is even.

Consider any other variable $b$. Then because the formula $\varphi$ must contain all clauses that contain the variable $a$, $\varphi$ must have the form

$$\varphi = (a \lor b) \land (a \lor \neg b) \land (\neg a \lor b) \land (\neg a \lor \neg b) \land \cdots$$

It is easy to see that no assignment can satisfy this formula. As such, it is very unlikely that the problem is $\oplus P$ complete.

The reasoning you give makes no sense to me. There are plenty of problems whose output are true or false but are not $\oplus P$ complete.

---
Tags: complexity-theory, 2-sat
---


title: The extent of NP-Completeness

text:
# Question
Title: The extent of NP-Completeness
I am told that if a decision problem that is in **NP** Complete can be solved in polynomial time, then **P**=**NP**. However, would this mean that we would instantly have an algorithm to solve *any* **NP** problem. Like if someone solved the traveling salesman problem, would that mean that we would instantly have an algorithm to factor large integers? Or instead, would it mean that an algorithm exists to factor large integers, but it would still be very difficult to find that algorithm, and we would just have the assurance from a theoretical perspective that such an algorithm exists.

Any help is appreciated!

# Answer
Yes and no, even if we assume P $\not=$ NP was not proven. It depends on how someone "solved" the traveling salesman problem.

---

If someone constructed a polynomial-time algorithm that solves the traveling salesman problem, we would be able to instantly specify a polynomial-time algorithm that factors integers. This is the "yes" part of the answer.

If someone proved non-constructively that there exists a polynomial-time algorithm that solves the traveling salesman problem, we would instantly know there exists a polynomial-time algorithm that factors integers. This is the "no" part of the answer, since "it would still be very difficult to find an algorithm" that factors integers in polynomial time, as you have noted.

There are other possible situations. For example, it is possible that "the P versus NP problem may be independent of standard axiom systems like ZFC", quoted from Wikipedia. In that case, it may need significant effort to understand the exact meaning of "someone solved the polynomial-time traveling saleman problem."
> 1 votes

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


# Question
Title: Representing classical circuits with quantum gates
Many problems in computer science input boolean circuits to problems.

Just as a toy example, let's define the below problem to be called $A$:

> Given a polynomial depth circuit with $N$ bits of output, C, does there exist an input $x$ such that $C(x) = 0$?

Is it correct to say that an equivalent problem, on a quantum computer is this:

> Given a quantum gate, $U | x, y \rangle = | x, y \oplus C(x) \rangle$ determine if there is an $x$ such that $C(x) = 0$

Now suppose problem $A$ is complete for a complexity class $B$. If a quantum algorithm existed to solve $A$ with a polynomial complexity, would that imply that $B \subseteq BQP$? Is there any oracle separation business to worry about here?

# Answer
No, it's obviously not equivalent, because computation on a quantum computer is not known to be equivalent to computation on a classical computer.

Also, it's not clear what you mean by a "quantum gate" or how it is specified on the input.

Yes, depending on the notion of completeness - it may depend on under what notion of reduction you are using for completeness. If the notion of reduction you are using is polynomial time algorithms (as is common), then yes, it follows that. You should spend some time trying to prove it. It follows directly from the definitions -- so see what you can come up with.
> 0 votes

---
Tags: circuits, quantum-computing
---


# Question
Title: "Succinct circuit representation" on Turing machines?
The famous PPAD class revolves around the End-Of-The-Line problem. Basically, it states that you are given two polynomial depth circuits, $P$ and $Q$, which act as "possible previous" and "possible next" functions, each with an exponentially sized domain. And the task is to find an input that satisfies $P(Q(x)) \neq Q(P(x)) \neq x$.

But I raise the question: How can these circuits be represented on a Turing machine?

To answer this question, I think two things must be proven.

1. Arithmetic circuits have a polynomial time and space translation to a Turing machine language
2. Polynomial depth circuits can compute any choice of $P$ and $Q$

My question is mostly about $1$, but I don't really see how $2$ can be true either. Do we need these to translate this problem to a Turing machine context?

# Answer
A circuit is not represented "on" a Turing machine, rather a representation of the circuit is provided as input. It is straightforward to represent a circuit as a bit-string. For instance, you can list each gate of the circuit, and which gates' outputs are connected to which gates' inputs.

I can't make sense of the things that you suggest must be proven. I suspect there is some misunderstanding or faulty premise.
> 1 votes

---
Tags: turing-machines, circuits, game-theory
---


# Question
Title: How to determine agreement between two sentences?
A common Natural Language Processing (NLP) task is to determine semantic similarity between two sentences. Has the question of agreement/disagreement between two sentences been covered in NLP or other literature? I tried searching on Google Scholar but didn't get any relevant results.

# Answer
> 1 votes
I would propose to do some researching in the field of **Stance Classification**. Given a target claim or argument we can classify whether a number of sentences are in favor, against or neither of that claim. So an idea is to extract the topic of those sentences classify whether they agree or disagree with it and depending that classification you can determine if those sentence agree or disagree.

Here are some papers you can look at:

https://paperswithcode.com/task/stance-classification

https://arxiv.org/abs/1907.00181

https://www.mdpi.com/2078-2489/13/3/137

https://dl.acm.org/doi/abs/10.1145/3488560.3501391

---
Tags: natural-language-processing
---


# Question
Title: Base transcoding with minimum storage and complexity
I want to reversibly transcode arbitrary information (a digital signature), initially $n$ bits, into symbols in an alphabet with $s$ symbols, with little space loss. In my application‡ $s=45$. Thus I can e.g. transcode $n=192$ bits into $m=\lceil n/\log\_2s\rceil=\lceil34.961\ldots\rceil=35$ symbols with less than $0.12\\%$ density loss.

I have working C code for this using textbook base conversion, including the necessary arbitrary-precision arithmetic on an integer up to $s^m\approx2^n$. It require $\mathcal o(n)$ bits of temporary space for that integer, and $\mathcal O(n^2)$ time. For the beauty of it, I'm in search for (not exclusive)

* a method achieving the same density (or at least $m=35$ for $n=192$, $s=45$) with a simpler symbols-to-bits conversion algorithm, even if somewhat more temporary space is needed to run the algorithm, and the bits-to-symbols conversion was complex.
* a proof (or disproof) that for odd $s$, any method with density as good as base conversion requires $n$ bits of temporary space in the decoder, on top of the $m$-symbols read-only input.

Update: I do not need compatibility with a pre-existing encoding. I could live without detection at decoding that a combination of $m$ symbols among $s$ can't be generated by proper encoding of $n$ bits.

---

Encoding on "QR codes" using the "Aphanumeric mode", which is more compatible with various deployed readers than the "Byte mode". $s=45$ is such that $2\log\_2(s)\approx10.9837\lesssim11$, allowing the QR code standard to store $2$ symbols into $11$ bits with less than $0.15\\%$ space loss.
Update: Problem with the binary mode is that existing readers (physical devices, apps on a mobile phone) are harder to interconnect to other devices/wares when their output is arbitrary bytes, e.g. a digital signature. Issues include 7-bit serial mode; XOFF (0x13) halting serial communications; binary mode being intentionally disabled to block denial of service by the previous method; NUL (0x00) terminating a C string; filters limiting strings to valid UTF8.

# Answer
Divide the first 187 bits into 17 blocks of 11-bit values. This leaves 5 bits left over. Call each 11-bit block *good* if it it corresponds to a number in the range $0 \ldots 2024$, or *bad* if it is in the range $2025 \ldots 2047$. (Note that $2025 = 45^2$, so a good block can be encoded into two symbols.) We'll store the left-over 5 bits (in a symbol or less), a list of bad blocks, then a list of good blocks. To handle the specifics of exactly how to do that, we'll case-split into two cases:

* Case A: All of those 17 11-bit blocks are good.
* Case B: One or more of those 17 11-bit blocks is bad.

We will encode those two cases differently.

* Case A: Encode the left-over 5 bits into the first symbol, using values $0 \ldots 31$. Then, encode each of the 17 11-bit blocks into two symbols. Since they are all in the range $0 \ldots 2024$, each can be encoded into two symbols. This uses a total of $1+2\times 17 = 35$ symbols.
* Case B: The general concept is that we'll store the left-over 5 bits, then a list of all bad blocks, then a list of all good blocks. The rough idea is that each bad block can be represented in two symbols, and each good block can be represented in two symbols, but we'll have to make some tweaks to squeeze the left-over 5 bits in somewhere.

Specifically, we will store the 5 left-over bits and the first bad block in the first three symbols. They will be followed by a list of the rest of the bad blocks. Each bad block will correspond to a tuple $\langle i,\ell,v \rangle$, where $i$ represents the index of the bad block, $\ell$ is a boolean indicating whether it is the last bad block, and $v$ is the value of the bad block. There are $17$ possible values for $i$, $2$ possible values for $\ell$, and $23$ possible values for $v$, so in total we have $17 \times 2 \times 23 = 782$ possible tuples.

The first bad block will be encoded in a special way. In particular, we encode the 5 left-over bits and the tuple of the first bad block into the first three symbols. Here we have $2^5 \times 782=25024$ possible values to represent, and there are $13 \times 45^2$ possible values for the first three symbols (we have to avoid the 32 possible values for the first symbol that is taken up by case A), so the tuple of the first bad block and 5 left-over bits can be encoded into the first three symbols.

Then, we'll store a list of the rest of the bad blocks,

$$\langle i\_2,\text{False},v\_2 \rangle, \dots \langle i\_{k-1},\text{False},v\_{k-1} \rangle, \langle i\_k,\text{True},v\_k \rangle,$$

where each tuple $\langle i\_j,\ell\_j,v\_j \rangle$ represents a single bad block. Here $i\_j$ represents the index of the $j$th bad block, $\ell\_j$ is a boolean that indicates whether it is the last bad block in the list or not, and $v\_j$ represents value of the bad block itself. There are $17$ possible values for $i$, $2$ possible values for $\ell$, and $2048-2025=23$ possible values for $v$, so there are $17 \times 2 \times 23 = 782$ possible values for the tuple. Therefore each tuple can be encoded easily into two symbols.

The list of good blocks will be represented by simply encoding each good block into two symbols.

So, assuming there are $k$ bad blocks, the first 3 symbols will contain the 5 left-over bits and the first bad block, the next $2k-2$ symbols will encode the list of the rest of bad blocks (2 symbols per bad block), and the remaining $34-2k$ symbols will contain the list of $17-k$ good values, in order (2 symbols per good block). Thus, case B uses a total of $35$ symbols.

---

This provides a valid encoding that can be uniquely decoded. Also, the total amount of additional storage required is about 12 bits for Case A, or about 24 bits for Case B. Regardless of which case we are in, this is less storage and probably faster running time than textbook base conversion.
> 4 votes

---
Tags: space-complexity, base-conversion
---


# Question
Title: ASCII invariant string for base64 Encoding
I know the basics about base64 encoding, but thinking about it abstractly I have a theoretical question.

If we consider base64 a mathematical function(in our case computable), Does there exists an invariant for base64-encoding function ? It only make sense or to narrow down the scope of the question I assume input binary is ASCII string.

For given ASCII string we can convert it to base64 encoded string in following way

```
user@machine$ echo "Many hands make light work." | base64
TWFueSBoYW5kcyBtYWtlIGxpZ2h0IHdvcmsuCg==

```

How can I find a ASCII string whose base64 representation is same as its input, if it exists ?

Is there any way to prove it's non-existence ?

# Answer
The base64 encoding of the empty string is the empty string, so arguably the empty string could be considered an example of the sort you are looking for. But there are no other examples. The base64 encoding of any (non-zero-length) string is always longer than the string itself.
> 3 votes

---
Tags: computability, strings, binary, encoding-scheme
---


title: Enumerator for $L=\{0^{3^n}| n\ge 0\}$

text:
# Question
Title: Enumerator for $L=\{0^{3^n}| n\ge 0\}$
I need to build an enumerator for $$L=\\{0^{3^n}| n\ge 0\\}, \Sigma = \\{0\\}, \Gamma = \\{0, x, \sqcup\\}$$ that has **at most 10 states**, including print and halt states. I can ignore the halt state and any edge that leads towards it.

I tried to approach this in the simplest way i could think of, build a Turing machine that decides $L$ and then build an enumerator around it, and this is the result

the states are:

* I - initializing state, puts a blank, $\sqcup$, at the start of the tape
* q0 - starts a division by 3
* q1 - checks if we reach a single 0 if so print else continue with division by crossing a single 0
* q2 - cross first/second 0 for division if there is none, i.e not divisible by 3, add 0 to tape and rewind
* q3 - check if divisible by 3, if so rewind to check again, else continue with division
* q4 - continue with division by crossing first 0 if there is none, i.e not divisible by 3, add 0 to tape and rewind
* rw - rewind to start of tape at the end of successful division
* rr - rewind to start of tape following addition of a single 0, replacing x with 0 to check again if the input length is a power of 3
* rnp - rewind to start of tape following successful run of the Turing machine, replacing x with 0, and for each symbol, 0 or x, put 0 in output
* print - prints output and start a new run of the Turing machine

But I have 2 problems I would appreciate help with:

1. I have 11 states, and I need no more than 10. Is there a way to simplify my existing machine?
2. The question says at most 10 states, thus I assume there might be an even simpler machine I can describe, yet after several days working on this, I'm just unable to find anything

# Answer
> 1 votes
I think I found an answer to my first question by sort of splitting $q0$, merging half of it into $q1$ and merging the $I$ state into the rest of it

In the new machine, I use the blank, $\sqcup$, at the start of the tape to mark the first 0 (the empty word isn't part of $L$ so I can ignore the case $q0$ came to handle in the first machine), and the move from $q1$ to $rnp$ also puts a 0 in the output to compensate for the missing 0 at the start.

The machine now has 10 states (including halt state) which is what was required

---
Tags: turing-machines, enumeration
---


# Question
Title: Question about the length of certificate of an polynommial-time verifier
We defined a polynomial-time verifier so that it has certificates of length AT MOST p(|x|) for some fixed polynomial p.

Why does it not make a difference to require a certificate $c$ to have EXACLTY length p(|x|)?

# Answer
> 0 votes
Instead of a variable-length certificate $c$, you can always modify the certificate to have the form $\text{len}(c), c, 00\cdots 0$ where you append enough zeros to pad it out to the max length, thus yielding a fixed-length certificate.

---
Tags: polynomial-time
---


# Question
Title: I would like to know what are the directions to work on if I want to prove that $NP=coNP$?
I am currently learning about NP and coNP related content and have been exposed to the$NP \overset{\text{?}}{=}coNP$ problem.

I would like to know what are the directions to work on if I want to prove that $NP=coNP$? For example, currently I know that if I can prove that a coNP-complete language belongs to NP, then I can prove that $NP=coNP$.

If I want to prove that $NP \neq coNP$, what are the directions to work in, or what results have already been obtained?

# Answer
There are no directions that are likely to be accessible to an amateur. The problem is believed to be extremely hard. No one knows of any directions that are believed to be very promising. Instead, I recommend that you work on a different problem.
> 3 votes

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


# Question
Title: Proof: Solving a 9x9 sudoku is just as hard as determining whether there is a solution
I have so show that, for the normal 9x9 sudoku, determining whether there is a solution is just as hard as computing a solution if it exists. I should do that by assuming i have a polynomial-time algorithm for checking whether a given sudoku is solvable and i then should explain how to obtain a polynomial-time algorithm for computing such a solution.

I have no idea how to show that using this "hint".

# Answer
Let's say you have 20 boxes filled out.

You put the number 1 in the first empty box and check if a solution exists. If yes, you put down 1 in the first empty box permanently and now you have a problem with 21 boxes filled out. If no, you put the number 2 in the first empty box and try again, up to 9. If you don't find a solution with 9 in the first empty box, then there is no solution.

In the worst case, you try numbers 1 to 9 in 81 empty boxes. So you check 729 times if a solution exists in the worst case. That's only a constant factor.

And as pseudynom says, if you take general n x n sudoku, then the factor 729 is just the special case for n=9. In general the factor is $n^3$.
> 2 votes

---
Tags: sudoku
---


# Question
Title: Is the language with at least as many 0 as 1 on any prefix $\omega$ regular?
Let $L$ be the language of infinite words in $\\{0,1\\}^\omega$ such that any finite prefix of a word in $L$ has at least as many $0$'s as $1$'s. Is $L$ büchi recognisable?

I think that $L$ is not $\omega$ regular, but standard tricks such as complementation or intersecting with some other language don't seem to work.

# Answer
As you suspected, $L$ is not büchi recognisable/$\omega$-regular. Here is a proof.

---

Towards a contradiction, suppose $L$ is $\omega$-regular. Then $$L= A\_1B\_1^\omega\cup A\_2B\_2^\omega\cup\cdots\cup A\_nB\_n^\omega$$ for some $n$, where $A\_i$ and $B\_i$ are regular languages for all $i$.

Consider $s=0^11^10^21^20^31^3\cdots\in L$. WLOG, suppose $s\in A\_1B\_1^\omega$. Suppose $s=at$, where $a\in A\_1$, $t\in B\_1^\omega$.

Let $p$ be a pumping length for $B\_1$ as in *the general version* of the pumping lemma for regular languages, as stated here on Wikipedia.

Consider $\ell=1^{\max(|a|, 2p)}$ that appears in $s$. $\ell$ must appear after $a$ since $0^{|a|}$ appears before $\ell$ in $s$. In other words, $\ell$ is a substring of $s$ without $a$, which is $t$. Since $t\in B\_1^\omega$, $\ell$ is the concatenation of a nonempty suffix of a word in $B\_1$, zero or more words in $B\_1$ and a possibly-empty prefix of a word in $B\_1$. There are two cases.

* $\ell$ contains a word in $B\_1$.
Let $g$ be that word, which contains only $1$s.
* $\ell$ is a suffix of a word in $B\_1$ followed by a possibly-empty prefix of a word in $B\_1$.
Hence $B\_1$ contains a word that contains at least $\frac{2p}2=p$ consecutive $1$s. Let $uwv$ be such a string, where $w=1^p$.

We can write $uwv=uxyzv$ for some string $x,y,z$ with $|y|\ge1$ such that $uxy^iz\in B\_1$ for all $i\ge0$, thanks to the general version of the pumping lemma. Since $w$ is all $1$s, so is $y$. Hence for $i$ large enough, $uxy^iz$ has more $1$s than $0s$. Let $g$ be such a word, i.e. $g\in B\_1$ has more $1$s than $0$s.

In both cases, we have identified a word $g\in B\_1$ that has more $1$s than $0$s. Then $ag^\omega\in A\_1B\_1^\omega\subseteq L$. However, $ag^\omega\notin L$ since its prefix $ag^{|a|+1}$ has more $1$s than $0$s. This is a contradiction.
> 1 votes

---
Tags: regular-languages, automata, buchi-automata, omega-automata
---


# Question
Title: What is the difference between sparse conditional constant propagation and constant propagation?
Reading the Wikipedia pages on these topics, it seems that sparse conditional constant propagation (SCCP) is a more powerful form of constant propagation (CP)? E.g all optimizations available in CP are subsumed in SCCP.

# Answer
In general, SCCP will remove the unreachable blocks based on the previous const propagation, that's why it can propagate more constant (some phi's oprands can be removed)

And it's sparse, which means it runs on SSA form IR, that would make the analysis and procedure faster.

I read from a blog that there are four kinds of constant propagation, that is

* (simple) constant propagation
* conditional constant propagation
* sparse constant propagation
* sparse conditional constant propagation : the most powerful

Based on the attributes of each algorithm, I guess we can understand what they do.
> 1 votes

---
Tags: program-optimization
---


title: If f = O(h) and g = Ω(h) then f+g is?

text:
# Question
Title: If f = O(h) and g = Ω(h) then f+g is?
Is the answer O(h) or Ω(h) for **f+g?** My professor says its Ω(h), but I can't get it.

# Answer
> 1 votes
I'm going to assume that $f(n)$ is non-negative.

From $g(n) \in \Omega(h(n))$ you know that there is some $n\_0$ and some $c$ such that, for all $n \ge n\_0$, $$g(n) \ge c \cdot h(n).$$ Then: $$f(n) + g(n) \ge g(n) \ge c \cdot h(n) \quad \text{ for all } n \ge n\_0.$$ Therefore $f(n)+g(n) \in \Omega(h(n))$.

# Answer
> 1 votes
$f+g$ being larger than $g$, the lower bound of $g$ still holds. And we know nothing about the upper bound.

---
Tags: big-o-notation
---


# Question
Title: Regular Expression of {w : w contains an even number of 0s and exactly two 1s}
I know the answer if it was OR would be `(1*01*01*)* U 0*10*10*`, but with the AND I have no clue how this can be achieved. There are lot's concatenations that I can't cover by getting the regular expression.

# Answer
> 1 votes
There are a limited number of cases. For instance, one case has an odd number of 0's followed by consecutive 1's, followed by an odd number of 0's. Another case is that there is an initial 1, followed by an even number of 0's, followed by a terminating 1. List all the cases and make up an OR-type expression to cover them all.

---
Tags: automata, regular-expressions, discrete-mathematics
---


# Question
Title: Forwarding in pipelined processors can increase throughput by decreasing amount of stalls, but can it in some cases impair performance?
Pipelined processors suffer from stalls due to different kind of hazards and one way of dealing with it is to implement forwarding of different types. For example ALU-ALU forwarding or full forwarding (MEM stage -\> EX stage). A result of implementing forwarding in a pipelined processor is that we get an increased throughput as we have reduced the amount of stalls. According to my teacher forwarding can potentially impair performance too but he didn't go into much detail at all and as such I am left curious about what exactly he meant. I have tried to find information about it but to no avail. One thought I have is that it might impair performance in the sense that it makes the processor slower as extra logic is added to support the forwarding step. **Can forwarding in pipelined processors impair performance in any way, if so how?**

# Answer
> 1 votes
Modern cpus have deep pipelines with 20 stages or more. Attempting full forwarding would require far too many bypasses to be practical. For example, if the depth is 20 the first stage would be connected to 19 bypasses, the second 18 bypasses, the third 17 bypasses, and so on. This would consume way too much silicon for wires, muxes, and control signals, so bypasses are only added for the commonly used cases. And even with all these bypasses, the cpu would still stall waiting for memory and in other situations.

# Answer
> 0 votes
Take an out-of-order processor. At any cycle, there may be multiple instructions ready for execution. The choice which to execute next can affect the total execution time in unpredictable (for the processor) ways.

Register forwarding can lead to a different instruction being executed next, with a different total execution time, which may be longer. But you save one cycle, and you will save more cycles by more forwarding, so losing out is unlikely. Not impossible but unlikely.

---
Tags: performance, cpu-pipelines
---


# Question
Title: Finding the smallest subset s.t. all elements satisfy condition, using as few tests as possible
I'm having a hard time describing this problem without an example, so let's go with this: Say you have a program that is made up of many files. There are some files you could delete, and, while it might be crippled, the program could still run. We're assuming each file is independent from the others, so behind the scenes there's a subset of necessary files, and the only condition for the program to run is that none of them are missing.

You want to reduce the number of files as much as possible, by classifying all files and deleting the unnecessary ones. You can achieve this by running a trial, choosing some random subset and trying to run the program with it. If it runs, we know that none of the files we omitted are necessary files.

How can you solve this problem most efficiently, i.e., classify all files using as few trials as possible?

---

**Update:** A naive algorithm to solve this problem would be:

```
necessaryFiles = []
for each file f:
    testSet = All files except f
    if programRuns(files = testSet):
        Add f to necessaryFiles

```

This algorithm tests files one at a time, and thus runs in $O\left(\text{# of files}\right)$. I am looking for a way to group files into different tests that runs faster. Of note here is that simple binary search doesn't work, because we have multiple target files, and as such splitting all files between two lists doesn't guarantee one of them will contain all targets.

# Answer
> 1 votes
Your algorithm is a good one, about as good as you can get.

If you care about the worst-case number of tests, your algorithm is optimal. Let $n$ denote the total number of files. Then any algorithm must perform at least $n$ queries in some cases. There are $2^n$ possibilities for the final answer (since there are $2^n$ possible subsets of the $n$ files). Each test gives you only 1 bit of information. After $k$ tests, we have only $k$ bits of information; to choose among $2^n$ possibilities, we need $n$ bits of information, so you can't do better than $n$ tests, in the worst case.

If you care about the average-case number of tests, and you assume that each file has a $1/2$ probability of being necessary, then I expect that your algorithm is also optimal. In this case, there are $2^n$ possibilities for the subsets, all equally likely, so $n$ bits of information are needed, and each test gives you 1 bit of information, so on average I believe you need at least $n$ tests.

If you have some prior knowledge about the likelihood that each file is necessary, you may be able to do better. For instance, suppose you know that only about a $p$ fraction of the files are necessary, and specifically, the probability that each file is necessary is $p$, independent of all other files. I'll show one algorithm for this problem below. There may be better algorithms; I don't know. For simplicity, I'll assume $p\le 1/2$; if $p\>1/2$, you can solve the problem similarly, reversing everything appropriately.

Algorithm:

1. If $p \ge 1-\sqrt{1/2} \approx 0.293$, then run the basic algorithm above, using one query per file.
2. Otherwise, set $k := \lfloor -1/\lg(1-p) \rfloor$. Randomly partition the $n$ files into $\approx n/k$ blocks of $k$ files.
3. For each block, query the set of all files except for that one block.
    * If the program still runs, then you know all the files in that block are unnecessary.
    * If the program doesn't still run, then you know that at least one file in the block is necessary, but you don't know which one(s) are necessary.
4. Set $q := p/(1 - (1-p)^k)$. Let $S$ be the set of files that are not known to be unnecessary, i.e., all the files from all the blocks where the program didn't still run. Recursively run this algorithm on $S$, but now with probability $q$ instead of $p$.

If you use this algorithm, after step 3 on average $S$ will contain $|S| \approx n(1 - (1-p)^k) \approx n/2$ files, on average about $q |S|$ of those files will be necessary, and typically we'll have $q \approx 2p$. For small $p$, if we unroll the recursion, I think we'll find that this algorithm will perform a total of about $n (h\_2(p) + o(1))$ queries, where $h\_2(p) = -p \lg p - (1-p) \lg (1-p)$ is the binary entropy function.

There is a matching lower bound, which says that on average you need at least $n h\_2(p)$ queries. This is because the Shannon entropy of the distribution of possible sets of necessary files is about $n h\_2(p)$ bits, and each query gives you at most one bit of information about this value, so you need at least $n h\_2(p)$ queries on average.

---
Tags: algorithms, optimization, search-problem
---


# Question
Title: Finding the Equation for Potential Method and Amortization Analysis
I am trying to figure out the solution to this problem:

In this problem we consider two stacks $A$ and $B$ manipulated using the following operations ($n$ denotes the size of $A$ and $m$ the size of $B$):
PushA($x$): Push element $x$ on stack $A$.
PushB($x$): Push element $x$ on stack $B$.
MultiPopA($k$): Pop $\min(k; n)$ elements from $A$.
MultiPopB($k$): Pop $\min(k;m)$ elements from $B$.
Transfer($k$): Repeatedly pop an element from $A$ and push it on $B$, until either $k$ elements have been moved or $A$ is empty.

I need to define a potential function $\phi(n;m)$. The solution guide comes up w/ a function of $3n+m$. How can we come up with that function?

# Answer
> 3 votes
Amortized analysis is a technique for showing how to distribute the total cost of a worst case sequence of operations among all the operations in the sequence to get an average cost. So, even if there are operations that are expensive, as long as there are enough cheap operations the average cost will be cheap. In your case, a `push` is cheap, assuming it takes 1 step, while a `multipop` and `transfer` are expensive since they require non-constant amount of steps.

When cost are distributed among operations, the cost of expensive operations decreases while the cost of cheap operations increases, compared to their actual cost. Now a potential function is a way to quantify this difference between the average cost (also called the **amortized cost**) and the actual cost. The potential may increase for cheap operations and may decrease for expensive operations. A potential function is correctly defined if all increase in potential are enough to shoulder all decrease.

Before you define any potential function, make sure you have an intuition as to how to distribute the cost of expensive operations to cheap operations:

* A `multipop` pops multiple elements previously pushed. Assuming that one pop takes a step, the cost of a `multipop` can be covered if one additional step is charge to a `push` for a pop in a `multipop`. This additional charge to `push` must increase the potential. And performing a `multipop` should consume that same amount of increase.
* A `transfer` is like a `multipop` on stack $A$ followed by a sequence of `push` on stack $B$. If the cost of a push in $A$ can be additionally charged again when an item is popped from $A$ and then another when it is pushed to $B$, then the cost of `transfer` can be covered. This again should increase the potential when performing a `push` and decrease when a `transfer` is performed.

From above the cost of a push in stack $A$ will have 3 extra charge while a push in $B$ will have 1 extra charge. Now think of a way to represent these extra charges using some properties of the data structure. An easy and hopefully intuitive way is to associate the charges with the number of elements in both stacks, since the change in the number of elements is in parallel to change in potential. That is, associate a value of 3 to each element in $A$ and associate a value of 1 for those in $B$. This should give you $3n + m$.

On a final note, there can be more than one way to define a potential function. In the above definition, the amortized cost of both `multipop` and `transfer` are zero, so they are essentially free of charge.

---
Tags: algorithms, amortized-analysis, stacks
---


# Question
Title: Writing an Algorithm to Represent a Bit Matrix in Minimal Operations?
I am trying to come up with an algorithm to find the minimal representation of the transformation from a zero matrix to a target matrix. Specifically, I have an empty matrix and can perform operations such as `set(x1,y1,x2,y2)` and `unset(x1,y1,x2,y2)` to edit submatrices. I looked at some greedy algorithms and quadtree data structures to partition the target matrix and with those, the transformation could be represented with just `set()` operations. That is a naive approach because of this 3x3 bit donut matrix example:

Using just `set()` you can see it is going to take a total of four operations. However, it can also be done in one `set()` and one `unset()` which leaves me thinking about how this could even be calculated in a large matrix.

I am not sure where to begin research on this or keywords to ask google, any insights or references would be greatly appreciated.

# Answer
> 1 votes
I believe the problem is NP-hard, even with only set(), and is even hard to approximate within a factor better than 2. See https://mathoverflow.net/q/105164/37212, https://cstheory.stackexchange.com/q/12376/5038, https://stackoverflow.com/q/3516044/781723, https://en.wikipedia.org/wiki/Polygon\_covering.

A pragmatic approach might be to use a SAT solver or ILP solver.

---
Tags: algorithms, optimization, matrices
---


# Question
Title: What is the difference in heap configurations? Separation logic with CVC5 SMT solver
I am figuring out separation logic and trying to run simple examples in CVC5 smt solver. I am missing some core understanding of how pointers and values are treated there and I don't know where to look for more information.

I am sorry for the long snippets, but they are very simple.

## First query

```
(set-logic QF_ALL)
(set-info :smt-lib-version 2.6)

(set-option :produce-models true)
(set-option :produce-proofs true)
(set-option :produce-unsat-cores true)

; heap with uninterpreted sort as Data
(declare-sort Data 0)
; "single" element for the pointers to point to
(declare-const unit Data)
; Heap declaration
(declare-heap (Int Data))

; Two pointers
(declare-const left Int)
(declare-const right Int)

; constraints for better readability of the model
(assert (= (as sep.nil Int) 0))
(assert (>= left 0))
(assert (>= right 0))

; query itself
(assert (not
    (sep
        (pto left unit)
        (pto right unit)
    )
))

(check-sat)
(get-model)

```

### CVC5 output

```
sat
(
; cardinality of Data is 1
; rep: (as @Data_0 Data)
(define-fun unit () Data (as @Data_0 Data))
(define-fun left () Int 1)
(define-fun right () Int 2)
)
(heap
(sep (pto 2 (as @Data_0 Data)) (pto 1 (as @Data_0 Data)))
(= (as sep.nil Int) 0)
)

```

---

## Second query

```
(set-logic QF_ALL)
(set-info :smt-lib-version 2.6)

(set-option :produce-models true)
(set-option :produce-proofs true)
(set-option :produce-unsat-cores true)

; heap with uninterpreted sort as Data
(declare-sort Data 0)
; "single" element for the pointers to point to
(declare-const unit Data)
; Heap declaration
(declare-heap (Int Data))

; Two pointers
(declare-const left Int)
(declare-const right Int)

; constraints for better readability of the model
(assert (= (as sep.nil Int) 0))
(assert (>= left 0))
(assert (>= right 0))

; query itself
(assert
    (sep
        (pto left unit)
        (pto right unit)
    )
)

(check-sat)
(get-model)

```

### CVC5 output

```
sat
(
; cardinality of Data is 1
; rep: (as @Data_0 Data)
(define-fun unit () Data (as @Data_0 Data))
(define-fun left () Int 1)
(define-fun right () Int 2)
)
(heap
(sep (pto 2 unit) (pto 1 unit))
(= (as sep.nil Int) 0)
)

```

---

# Question about the second heap

```
(heap
(sep (pto 2 unit) (pto 1 unit))
(= (as sep.nil Int) 0)
)

```

Why the second heap satisfies `(sep (pto left unit) (pto right unit))`, despite both pointers pointing to the same `unit`?

# Question about the first heap

```
(heap
(sep (pto 2 (as @Data_0 Data)) (pto 1 (as @Data_0 Data)))
(= (as sep.nil Int) 0)
)

```

Why is this heap satisfies `not (sep (pto left unit) (pto right unit)` even with `unit` being equal to `@Data_0`, which works for the other query?

---

Why these similar-looking heaps are satisfying mutually exclusive conditions?

I am looking to some paper or documentation page for the in-depth explanation.

# Answer
> 3 votes
Thanks for the question. The model construction for the separation logic heap in cvc5 was wrong in this case. This will be fixed by https://github.com/cvc5/cvc5/pull/9574.

---
Tags: logic, smt-solvers
---


title: Checking forbidden moves in Renju

text:
# Question
Title: Checking forbidden moves in Renju
I am trying to detect forbidden moves for black in a game called Renju. First, here is an explanation of how Renju works.

Renju is a board game played on a 15x15 Go board. There are two players in the game, which we will call black and white, and they place stones of their color on the board turn by turn. Black starts first, and whoever gets 5 pieces of their color in a row wins (so it's basically like tic-tac-toe but on a bigger board).

However, this game is not balanced for white (since black starts first), so there are some restrictions on what moves black can make. Here are some of them:

1. Black cannot create an *overline*. (6 or more stones in a row)
2. Black cannot make a 3x3 fork, which look like these:

Take a look at the fork at the upper-right corner. You can see that if black places a stone at J, then they will create two 'open three's (an *open four* is a pattern of four stones in a row with both sides open, and an *open three* is a pattern of three stones such that adding a stone to it creates an open four) and they are guaranteed to win since white cannot block everything in time. Same thing goes for other forks shown here.

The problem I am facing is that I cannot detect these 3x3 forks just by detecting patterns. Here is a more concrete example of what I mean.

We would like to know whether black creates a 3x3 fork by placing a stone at A or not. Therefore, we must check whether placing a stone there creates two 'open three's at the same time.

Here, we've placed a black stone at A. The horizontal bar is an open three, since we can create an open four by placing a black stone at B. However, the diagonal is **not** an open three, since placing a black stone at C would not leave the bottom end of the four to be open, whereas placing a black stone at D would not leave the top end open (since black is not allowed to place a piece there, otherwise it will create 6 stones in a row or an overline). Therefore, this is not a 3x3 fork, and so black is allowed to place a stone at A.

My main issue is that the problem of checking this seems to be recursive, in that in order to know if I can place a piece at the point A, I need to know whether I can place a piece at other points of the board. My naive idea at first was to use dynamic programming, but I found that it's not likely to work since the forbidden moves at turn $n$ is quite different from those at turn $n - 2$, and are heavily dependent on what black and white do in the turns between. I'd like to know if there is an efficient algorithm to check this sort of thing. I'm not experienced with algorithms at all, so please pardon me if this is a trivial question. Thanks for reading till the end.

\[Here is a link for a better explanation of the game in case mine isn't good enough.\]

# Answer
> 1 votes
The rules are recursive in some sense, but note that the recursive parts depend on collections of one stone larger. Since 5 is the largest number of stones to check for, the depth of the recursion is constant, so you only need to test a constant number of board positions to check if a move is valid.

In particular, to test for a 3x3 fork, you need to check for a valid open three. A valid open three is a set of stones that can be expanded into a valid open four (which involves not making the 4x4 fork), which is a set of stones which can be expanded to a valid five (which involves not making an overline).

---
Tags: algorithms, dynamic-programming, board-games
---


# Question
Title: Regex where all strings containing an even number of 0's:
Question is to construct a regex where all strings containing an even number of 0's: By constructing DFA graphically, it is

$$(1^\*+01^\*0)^\* $$

But it is also

$$1^\*(01^\*01^\*)^\*$$

Can we prove that they are equal algebraically?

# Answer
> 3 votes
According to the wikipedia page on Kleene Algebra, we can use two properties:

* $(a^\*)^\*= a^\*$
* $(a+b)^\* = a^\*(b(a^\*))^\*$

If you allow those it is quite straightforward:

$(1^∗+01^∗0)^∗ = (1^∗)^\*\cdot (01^∗0(1^\*)^\* )^∗ = 1^∗(01^∗01^\* )^∗$.

There is probably not a single set of rules for equivalence of regular expressions that everyone egrees on. The rules at wikipedia that I used above are from Dexter Kozen (A completeness Theorem for Kleene Algebras\[...\], Information and Computation, 1994, open access). The second rule we applied is Proposition 2.7 in that Kozen article. In his notation Kozen uses a partial order $x\leq y$ to represent $x+y= y$. Earlier approaches came from Arto Salomaa (1966) and John Conway (1971). See the History section at wikipedia. I did not study the approaches so I have no comment on this.

Here a (I think) complete set of rules, copied from a presentation of Jacques Sakarovitch. Here that specific rule is called "denesting". It seems an essential rule.

$$ \begin{array}{rc} \text{trivial} & E+0 = 0 + E = E \\ & E\cdot 0 = 0 \cdot E = 0\\ & E\cdot 1 = 1 \cdot E = E \\ \text{associative} & (E\_1+E\_2)+E\_3 = E\_1+(E\_2+E\_3)\\ & (E\_1\cdot E\_2)\cdot E\_3 = E\_1\cdot (E\_2\cdot E\_3) \\ \text{distributive} & E (E\_1+E\_2) = EE\_1+EE\_2\\ & (E\_1+E\_2)E = E\_1E+E\_2E \\ \text{commutative} & E\_1+E\_2 = E\_2+E\_1 \\\\[0.5ex\] \text{unrolling} & E^\* = 1 + EE^\* = 1 + E^\*E \\ \text{denesting} & (E\_1+E\_2)^\* = E\_1^\* \cdot (E\_2\cdot E\_1^\*)^\* \\ \text{sliding} & (E\_1\cdot E\_2)^\*\cdot E\_1 = E\_1\cdot (E\_2\cdot E\_1)^\* \\\\[0.5ex\] \text{cyclic Zn} & E^\* = (1 + E + E^2 + \dots E^{n-1})\cdot (E^n)^\* \\\\[0.5ex\] \text{idempotency} & E+E=E\\ & (E^\*)^\* = E^\* \end{array}$$

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


# Question
Title: Does a non-deterministic Turingmachine reach every possible result?
I have problems to imagine a non-deterministic Turingmachine. Let's make an example: There is the problem of a Vertexcover. Let $G=(V,E)$ be an undirected graph and $k\geq 0$. The question is whether there is a vertexcover $C$ of size $|C|\leq k$. My book says that this problem is in $NP$, because a Turingmachine could just guess a subset $C\subset V$ with $|C|\leq k$ and check in polynomial time, whether we have a vertex cover. If it guesses the set $C$ randomly, it could be possible that it does not work. So it just guesses another $C$. My question: Will it guess **every** possible pair $(C,k)$? In other words, is it possible that the machine is stuck in an infinite loop by always guessing the same?

# Answer
A non-deterministic machine finds the solution "by magic": whenever there is a decision to be taken, it immediately takes the right one so that the search for a solution essentially amounts to the verification of the solution. There is no randomness involved and the machine is run once on the given problem.
> 0 votes

---
Tags: turing-machines, nondeterminism
---


# Question
Title: What is the fastest algorithm to approximate an irrational number with specified precision?
**Problem Background:**

Let $a\in(0,1)$ to be an irrational number. Suppose there is a black box, the input is a real number in $\[0,1\]\backslash \\{a\\}$, denoted as $x$, the black box outputs boolean values according to the following rules:

* When $x\>a$, the output is **True**.
* When $x\<a$, the output is **False**.

Given $k$, we need to find a number $b$ such that

$$ |a-b|\<10^{-k},\quad b\>a,\quad \text{$b$ has $k$ decimal places} $$

For example, let $a=\sqrt{2}/2\approx0.70710678\cdots$, $k=3$, then $b$ should be $0.708$.

***Here again: we don't know $a$, our purpose is to find $b$.***

I thought of four ways to find $b$, listed below:

(The next four methods all use the above example)

---

**Linear search:**

Generate a list of length $1001$ in steps of $0.001$:

$$ \[0, 0.001, 0.002, \cdots,0.998,0.999, 1\] $$

Traverse this list, for each value $x$ in it, put it into the black box, if the output is **True**, stop traversing immediately, and $x$ at this time is $b$.

The time complexity of this method is: $O(10^k)$.

---

**Binary Search:**

Generate a list of length $1001$ in steps of $0.001$:

$$ \[0, 0.001, 0.002, \cdots,0.998,0.999, 1\] $$

Set two pointers. At first, the index of the left pointer is $0$ and the index of the right pointer is $1000$.

Calculate mid = (left + right) // 2.

Put the $x$ value at mid into the black box, if the output is **True**, move the right pointer to mid, otherwise move the left pointer to mid.

Repeat the above steps until left = right - 1, then the $x$ at the right pointer is $b$.

The time complexity of this method is: $O(k\log10)$.

---

**Linear Search + Use Previous Results:**

Step 1:

$$ \[0, 1\]\to\[0.0, 0.1, 0.2, \cdots,0.9, 1.0\]\to \[0.7,0.8\] $$

Step 2:

$$ \[0.7,0.8\]\to\[0.70,0.71,0.72,\cdots,0.79,0.80\]\to\[0.70, 0.71\] $$

Step 3:

$$ \[0.70,0.71\]\to\[0.700,0.701,0.702,\cdots,0.709,0.710\]\to\[0.707, 0.708\]\to 0.708 $$

The time complexity of this method is: $O(10k)$

---

**Binary Search + Use Previous Results:**

Similar to the method above, The time complexity of this method is: $O(k\log10)$

---

Are there any faster algorithms? If so, what is it?

# Answer
You are in fact asked to find $b$ independent bits of information (such that $2^{-b}\sim10^{-k}$)\*, using queries that return a single bit of information each. So you can't get an answer in less than $b$ queries in the worst case, and this is achieved by binary search.

---

\*Justification: the problem is equivalent to finding an integer $n$ such that $|a\cdot10^k-n|\<1$, with $n$ in range $\[0,10^k\]\sim\[0,2^b\]$.
> 30 votes

# Answer
Let's suppose for a moment that instead of finding a decimal expansion, you're trying to find a binary expansion; you want to find the irrational number to $k$ binary places.

Then the information theory problem is straightforward. You are trying to discover $k$ bits of information. Each query gives you exactly $1$ bit of information. Therefore any correct algorithm must perform at least $k$ queries. There is no way around this.

Now in the decimal case, you are trying to discover between $\left\lfloor k \log 10\right \rfloor$ and $\left\lceil k \log 10\right \rceil$ bits of information. So, once again, any correct algorithm must perform at least $\left\lceil k \log 10\right \rceil$ queries in the worst case.
> 19 votes

# Answer
Well, $O(k\log10) = O(k) = O(k\log\_210)$, and $k\log\_210$ is the amount of bits of information needed, so if you have a process that can only return $1$ bit per query, you'll need that many queries. There are cases where the queries can return more than $1$ bit, however. For instance, there's something called a "timing attack" where you design the queries to take a different amount of time based on the number. Asking "Is $100$ greater than $1$?" might take less time than asking "Is $\pi$ greater than $\sqrt 10$?" Then the amount of time you have to wait to get your answer gives you additional information. But as long the number of additional bits doesn't depend on $k$, this doesn't affect the time complexity (big O notation doesn't care about constant multiples). Of course, using a timing attack usually means using more *time*, even if it's fewer *queries*.
> 5 votes

# Answer
Your number is in $(0,1)$, and you want $b$ bit precision after the faction point. black\_box return $1$ if $x \geq a$ else $0$.

The following code will provide your answer.

```
function precise_float(black_box, b):
    x = 0
    for i = 1 to b:
        x = 2*x + black_box(x)
    return x

```

N.B. The doubling of 2 can be done using bit-shift in a real application.
> 0 votes

# Answer
If you know that a is within an interval of width $2 \cdot 10^{-k}$ then you would pick b in the middle of the interval. There are $10^k / 2$ intervals, 500 if k=3.

You split 500 intervals into 250+250, 250 into 135+125, 125 into 63+62 etc. until one interval is left. This minimises the number of guesses, and gives you a chance to need one guess less. So close to but not quite binary search.
> 0 votes

---
Tags: algorithms, approximation, real-numbers
---


title: Ackermann Decision Problem

text:
# Question
Title: Ackermann Decision Problem
I have been studying the Ackermann function, specifically the two-argument Ackermann–Péter version.

With the Ackermann function, I developed a problem I call the "Ackermann Decision Problem"

> Given non-negative integers, x and y, does A(x,x) = y?

The naive solution to verify the Ackermann Decision Problem would be to compute the Ackermann Function. From my research, I seem to be unable to find a way to compute the Ackermann Function in polynomial time.

Is this problem in NP?

Is the time complexity for verifying and solving the Ackermann Decision Problem the same?

# Answer
No, you don’t need to compute the Ackerman function to verify this at all.

The problem is trivial for x \<= 3. And for x \>= 4, if you can write down y, then the answer is “no”.

More serious, if you actually wrote down say y ≈ A(4), you can solve it easily in linear time in the size of y. If calculating A(4) takes more time than that then you know it is greater than y and stop calculating.

PS. This is a question/answer site, not a free proof writing service.
> 1 votes

---
Tags: algorithms, complexity-theory, decision-problem
---


title: Details of sqrt.c library source code

text:
# Question
Title: Details of sqrt.c library source code
Have seen library code for finding square-root, using the Newton Raphson method. It uses a table of 256 entries, whose significance is unclear, as the initial guess should be dependent on the quantity (x), whose square-root need be found. So, request if some details could be given.

It states about it, that :

> Initial guesses for g and y are determined from argument x via table lookup into the array SqrtTable\[256\].

> SqrtTable\[256\] contains initial estimates for the high significand bits of sqrt and correction factor. This table is also used by the IBM arccos and arcsin functions.

> It states the usage of some terms as: xhead, and compares with 0x7ff00000, and 0x07000000ul, as in the code.

If some light be thrown, on the details; or some reference be given; would be highly thankful.

# Answer
The table covers two consecutive binades, so is indexed by the least significant bit of the stored exponent and the most significant seven bits of the stored significand of the function argument, which is an IEEE-754 `binary64` number. In essence, $x \in \[1,2)$ is mapped to indexes $128 \ldots 255$, and $x \in \[2, 4)$ is mapped to indexes $0 \ldots 127$. Each 16-bit table entries comprises two bytes, the most significant of which represents an 8-bit approximation to $\sqrt{x}$ while the least significant represents an 8-bit approximation to $\frac{1}{2\sqrt{x}}$.

What is stored in the table are the leading bits of the significands of the two approximations which get combined by bit manipulation with the exponent bits of an IEEE-754 `binary64` in the appropriate range and re-interpreted as an IEEE-754 `binary64` number. The square root approximation winds up in $g$ and the approximation to half the reciprocal square root winds up in $y$.

The table provides approximations valid to slightly under eight bits. Three steps of a Newton-Raphson type coupled sqrt / rsqrt iteration are performed. This iteration has quadratic convergence. This delivers square root approximation results with slightly under sixty-four valid bits to the final rounding step. Several different arrangements of such Newton-Raphson iterations are described in the literature and in practical use. The one used in the linked code matches with that shown in Figure 2 of the following publication:

P. W. Markstein, "Computation of elementary functions on the IBM RISC System/6000 processor," *IBM Journal of Research and Development*, Vol. 34, No. 1, Jan. 1990, pp. 111-119.

The approximations provided by the table include both overestimates and underestimates, which suggests that they were selected to minimize the approximation error in each sub-interval. I am not able to replicate the table exactly, despite trying for some time. I am able to generate a table that only differs by ± 1 in the least significant bit of each tabulated value, using the following C code:

```
    double x;
    int idx = 0;
    for (x = 2.0; x < 4.0; x += 1.0 / 64) {
        double midpoint = x + 1.0 / 128;
        double s = sqrt (midpoint);
        double r = 1.0 / s;
        int hi = round ((s - 1.0) * 256);
        int lo = round ((2 * r - 1.0) * 256);
        int tab = hi * 256 + lo;
        printf ("%d, ", tab);
        idx++;
        if ((idx % 12) == 0) printf ("\n");
    }
    for (x = 1.0; x < 2.0; x += 1.0 / 128) {
        double midpoint = x + 1.0 / 256;
        double s = sqrt (midpoint);
        double r = 1.0 / s;
        int hi = round ((s - 1.0) * 256);
        int lo = round ((2 * r - 1.0) * 256);
        int tab = hi * 256 + lo;
        printf ("%d, ", tab);
        idx++;
       if ((idx % 12) == 0) printf ("\n");
    }

```
> 2 votes

# Answer
This is by far not an answer, but a first hint. Below, a plot of the content of the lookup-table, which is addressed with the eight first bits of the mantissa.

The values in the table are in fact two bytes packed together but later processed independently. The blue byte is for $g$ and the orange for $y$. We have shifted the values to let a sign appear and absorb discontinuities across the value $106$ (?).
> 1 votes

# Answer
There’s a union if double and 64 bit int in a file that’s not shown, which lets you extract the sign, biased exponent, and mantissa without leading zero bit.

For numbers from 1 to 2 the square root would be from 1 to 1.414. For numbers from 2 to 4 the square root would be from 1.414 to 2. If you look at the ieee format, the last bit of the exponent and the leading bits of the mantissa are stored side by side which lets you extract one value for the whole range from the table.

There are checks whether the first iteration can be done in single precision, and one check for tiny (denormalised) numbers. Once you get used to the idea that you can create floating point numbers by gluing bits together it’s quite straightforward.

I’d check if the square root for the floating point number just below 4 is rounded correctly. The original IBM code had/needed a special case for that.

But the key to understanding this is to lookup the ieee754 floating point format and figure out how the various bit manipulations are translated into floating point numbers.
> 1 votes

---
Tags: algorithms, approximation, numerical-algorithms
---


# Question
Title: Placing K gas stations among n cities to minimize distance
> There are $n$ cities on a highway with coordinates $x\_1$ , . . . , $x\_n$ and we aim to build $K \< n$ gas stations to cover these cities. Each gas station has to be built in one of the cities, and we hope to minimize the average distance from each city to the closest gas station. Please give an algorithm to compute the optimal way to place these $K$ gas stations. The algorithm should run in $O(n^2K)$ time.

I brute forced the answer by finding every single possible placement of gas stations and returning the minimum combo. Then I spent way too long fiddling with different ideas in Python to try and reduce the big-$O$ notation to no avail. Eventually I found a thread on the subject, but the formula isn't working for me.

How to minimize the average distance between pumps and cities?

I tried replicating the formula given in this thread in Python and it just doesn't work. It comes *close* but no dice. Here's my code (assume "cities" is the list of cities):

```
def f(n, k):
    if k == 1: # if k is 1, return total distance from the cities to the median
        pump = n // 2
        return sum([abs(loc - cities[pump]) for loc in cities[:n]])

    min_list = []
    for i in range(n-1):
        sum_list = []
        for j in range(i+1, n):
            pumpk = ((j + 1) + (n-1)) // 2
            sum_list.append(abs(cities[j] - cities[pumpk]) + f(i, k-1))
        min_list.append(sum(sum_list))
    return min(min_list)

```

I'm at such a loss! How can I solve the problem with the required time-complexity?

# Answer
> 1 votes
It looks that the recurrence relation is not implemented correctly in the code given in the question.

---

Here is a correct implementation.

```
# `cities` is a list of increasing integers that gives the
# locations of all cities such as follows
cities = [1, 5, 20, 22, 40, 100, 110]
K = 2

def min_sum_distances(start, end):
  """ Cities between `start` inclusive and `end` exclusive. One pump is installed."""
  pump_loc = start + end >> 1
  return sum(abs(city - cities[pump_loc]) for city in cities[start:end])

def min_sum(total_pumps):
  n = len(cities)

  # `dp[c][p]` is the minimum sum of distances from the first `c` cities
  # to the nearest pump when `p` pumps are installed.
  # 1 <= c <= n and 1 <= p <= K
  dp = [[float("infinity")] * (K + 1) for number_of_pumps in range(n + 1)]
  for c in range(1, n + 1):
    dp[c][1] = min_sum_distances(0, c)
    for p in range(2, min(c + 1, total_pumps + 1)):
      for cities_covered_before in range(p - 1, c):
        dp[c][p] = min(dp[c][p], dp[cities_covered_before][p - 1]
            + min_sum_distances(cities_covered_before, n))
return dp[n][total_pumps]

print(min_sum(K) / len(cities))
# 9.42857142857

```

The implementation runs in $O(n^3K)$ time.

---

In order to spend up the performance, we can reimplement `min_sum_distance` so that it runs in $O(1)$ instead of $O(n)$. We can use precomputed prefix sums of `cities`.

```
from itertools import accumulate
pre_sums = list(accumulate(cities, initial=0))

def min_sum_distances(start, end):
  pump_loc = start + end >> 1
  return pre_sums[start] + pre_sums[end] - 2 * pre_sums[pump_loc] \
      - (cities[pump_loc] if (end - start) & 1 else 0)

```

With the improvement, the implementation runs in $O(n^2K)$ time.

---
Tags: algorithms, optimization, dynamic-programming, big-o-notation
---


# Question
Title: How is a direct address table different from an array?
I found this from this PDF (https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture9.pdf)

# Answer
> 0 votes
The **direct access table** can be implemented as an **array**, which means that all operations you are to do to the array must be limited to the what is expected for a direct access table, which in turn is an implementation of a **dictionary**.

In a direct access table, the index of the array is treated as the integer representation of a key of the dictionary, while an element in the array is the value attached to the key. An empty index in the array means that key of the dictionary is not present. And also, the array must be large enough to be able to store all possible keys of the dictionary, even though in most cases small subset of the keys are being used.

All those requirements above is not necessarily true to all use cases since an array is a general purpose structure for representing group of elements. The index may or may not mean anything, which is entirely dependent on how the array is used.

# Answer
> 0 votes
As shown in the figure, the pairs key/data are decoupled from the array of links, and this is clearly different from a pure array. Also note that it allows to represent *empty* slots.

But this data structure is essentially introduced to prepare the next topic: hashing with chaining. It is not really useful in itself.

# Answer
> 0 votes
An array can be a very simple data structure - although you can have more complex structures for example if you want adding/deleting items at the start or end, or at arbitrary places, fast.

These guys implement a sparse array in a reasonable way. The size requirement is number of possible indices times size of a pointer or index, plus number of used indices times size of array element. But the requirement remains that the set of possible indices must be small(ish).

Why this is called “direct access table” is beyond me, since it is quite obviously an indirect access table.

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


# Question
Title: Select a subset of k intervals which form maximum length if we take union of these k intervals
Suppose we have $n$ intervals given in the form of (startTime,EndTime). I wish to calculate maximum length of the region that is exactly union of $1\<=k\<=n$ intervals.

Note that there are 2 cases for which I am trying to find an algorithm individually

1. Union of selected intervals might not be a single interval
2. Union of selected intervals should be a single interval

For example, if we have intervals $$ I\_1 = (2,6)\\ I\_2 = (4,9)\\ I\_3 = (7,11)\\ I\_4 = (10,13)\\ I\_5 = (8,12)\\ $$ and $k=3$

If we have the ability to select disjoint intervals (Case 1), one of the solutions would be $I\_1,I\_3,I\_4$ whose union would be $(2,6),(7,12)$ for total length of 10

If we do not have the ability to select disjoint intervals (Case 2), we would not be able to select $I\_1,I\_3,I\_4$ but we could select $I\_1,I\_2,I\_5$ spanning $(2,12)$ which is also length 10.

For case 1, I came up with a greedy approach where I **greedily pick the best length interval and update all other intervals to remove the overlap from the interval I just picked** which has the complexity of $O(n\*k)$, please let me know if I am on the right path.

# Answer
> 1 votes
## Case 1: Union of selected intervals might not be a single interval

First of all, sort the intervals in increasing order of $I\_i.start$

Use the following Dynamic Programming solution:

$$ \mathrm dp(i, j, k) = max( \text{extend\_union} + dp(i + 1, j’, k - 1), dp(i + 1, j, k) ) $$

where $$ \mathrm j' = \begin{cases} i & \text{if } I\_i.end \> I\_j.end \\ % & is your "\tab"-like command (it's a tab alignment character) j & \text{otherwise.} \end{cases} $$ $$ \mathrm extend\\\_union = \begin{cases} max(0, I\_i.end - I\_j.end) & \text{if } I\_j \text{ intersects }I\_i \\ % & is your "\tab"-like command (it's a tab alignment character) I\_i.end - I\_i.start & \text{otherwise.} \end{cases} $$

* $dp(i, j, k)$ denotes the maximum sum of lengths of the segments in the range the $\[i, N)$
* $j$ is the range $I\_j$ such that $I\_j.end$ is the maximum among all the segments that we chose until now
* $k$ denotes how many more segments are left to choose.

We have 2 choices at each state

* **Choice 1**: Consider the interval $I\_i$ in our subset. In this case, the union length will increase by the amount $\text{extend\_union}$ as mentioned above
* **Choice 2**: Don't consider the interval $I\_i$ in our subset. In this case, the union length will not increase
* If you have reached, with $i=N$ and $k=0$, return $0$ else $-\infty$
* **Time Complexity**: $O(N^2K)$

## Case 2: Union of selected intervals should be a single interval

First of all, sort the intervals in increasing order of $I\_i.start$

1. Now, create a graph of $N$ nodes such that for every $i$, there an edge from $i$ to $j$ $(i \< j)$ such that $j = \underset{j}{\operatorname{argmax}} I\_j.end$ where $I\_i \bigcap I\_j \neq \phi$ and $I\_j.end \> I\_i.end$.

Don't add an edge if such $j$ doesn't exist

This $j$ can be found out using any range querying data structure like segment trees in $O(log(N))$ or in $O(1)$ with sparse tables and precomputations

This will add $O(N)$ edges in the graph

2. The resulting graph will be a **DAG**, with at most one path between any pairs of nodes $i$ to $j$
3. It will be similar to this:
4. Now, if we choose any starting node in this graph and traverse $K$ nodes to the right, we will end with the most optimal subset of size $K$ having a certain union length. We can use this to maximize the answer
5. It may happen that there are $M \< K$ nodes to traverse, in that case, we can consider this subset only if there are $K-M$ other intervals that lie within this union.

Finding these $K-M$ **other intervals** may take $O(N)$ time in the worst case

To speed this up, the following observations are helpful:

From the image above, if number of **x** segments + number of **y** segments is $\geq K-M$, this subset can be consider in our answer

* Let $l$ be the index of starting interval of our subset and $r$ be the index where we end up in this case
* Notice that number of **x** segments is simply $(r - l + 1) - M$, computing in $O(1)$ time To find the number of **y** segments, we can use binary search to find the rightmost index $id$ in the range $\[r+1, N\]$ and $I\_{id}$ lies within $I\_r$
* Then the number of **y** segments is simply $id - r$, computed in $O(log(N))$ time
* We can use the binary search here because the interval $I\_r$ can no longer extend further and the ranges after that will lie completely within the interval $I\_r$ or start anywhere $\> I\_r.start$ If that is the case we can update the answer with the union length of this subset

6. Considering every interval as the starting point of the subset and traversing $K$ nodes each time will result in $O(N\*K$) time
7. To optimize it further, notice that we only require the starting and ending indices and not the entire subset indices. Furthermore, nodes chosen by a subset can be reused by other subsets based on their connectivity in the DAG that we defined above
8. Instead of adding the edges from $i$ to $j$, we keep them from $j$ to $i$. This is because the resultant disjoint trees formed will have their roots(nodes that don't go further) to the right. The following diagram depicts what we are doing:
9. DFS on nodes indexed from $N$ to $1$ and keep a list of nodes that are the nodes traversed from root to this node.

This will help us finding the $K^{th}$ node from each node in every DFS call in $O(1)$ time

Update the answer for each DFS($u$) call considering $u$ as the starting interval of the chosen subset

* **Pseudo Code**

```
answer = 0
parents = []
visited = [false] * N

function update_answer(starting_point):
    # update answer
    # based on the conditions
    # mentioned above

function dfs(u):
    parents.add(u)
    update_answer(u)
    visited[u] = true
    for each neighbor v of u:
        dfs(v)
    parents.pop(u)

for i = N to 1:
    if not visited[i]:
        dfs(i)

print(answer)

```
* Refer my C++ implementation for the same link
* **Time Complexity**: $O(N\*log(N))$

# Answer
> 2 votes
Unfortunately, you greedy algorithm for case $1$ may not yield the wanted maximum length sometimes.

Here is an example. We are given $$ \begin{aligned} I\_1 &= (1,6)\\ I\_2 &= (3, 9)\\ I\_3 &= (5, 10)\\ \end{aligned}$$ and $k=2$. The greedy algorithm will pick $I\_2$ and then $I\_1$, whose union is length $8$. However, the union of $I\_1$ and $I\_2$ is length $9$.

I would bet no greedy algorithm can always work for case $1$.

---
Tags: dynamic-programming, greedy-algorithms, intervals
---


# Question
Title: Let A, B two languages such that A=B does that implies that coA=coB
I'm getting to a problem while studying my computability and complexity exam. If two languages A and B, such that A=B does that implies that coA=coB?

And in general if two language are describe by different TM such that they accept a certain input. One reject everything else, while the other doesn't define anything (loop)

For example: let A= {\<\>M| M accept every even number and reject on everything else}

B= {\<\>M| M accepts every even number and loop on everything else}

Are those two languages equals even if their complements are not?

# Answer
> 1 votes
This question is not answerable, as you have not defined the notation coA. Normally, we use the "co-" prefix with complexity classes (sets of languages) rather than languages (sets of strings). See the definition of the complement of a set.

Regarding the rest of your question, you have a confusion. A language is a set of strings. The language accepted by a Turing machine is the set of strings that cause the Turing machine to halt and accept. So with your definitions of $A,B$, we have $A=B$: they are exactly the same language, and the complement of $A$ is equal to the complement of $B$.

---
Tags: computability, complexity-classes
---


# Question
Title: Partition a family of sets to maximize cumulative overlap and cardinality
My problem is this: I have a list of $n$ items $N$ (think of them as the natural numbers $1,\dots,n$) and $m$ subsets of $N$ $S\_1,\dots,S\_m$ which may overlap. The objective is to find a partition of the $m$ subsets $(P\_1,\dots,P\_k)$ for any $1\leq k\leq m$ maximising the following quantity $$ \sum\_{i=1}^k\left|\bigcap\_{S\_j\in P\_i}S\_j\right|\cdot (|P\_i|-1) $$ i.e. I want to maximise the sum of the overlap of the sets within each component of the partition, multiplied with the number of sets in that component minus 1.

I want to show that this problem is NP-hard or I want a polynomial time algorithm solving it. The closest problem I have found is this one but it is not quite what I need. I would appreciate any help, including suggestions for problems I may be able to reduce from.

Thank you!

# Answer
> 1 votes
If all of your subsets $\mathcal{S}=S\_1,\dots,S\_m$ have exactly two elements, then this family is effectively a graph $G$ with vertex set $N$ and edge set $\mathcal{S}$ (and $|\mathcal{S}|=m,|N|=n$). Now, you can prove that there exists a partition of $\mathcal{S}$ for which your objective function yields at least the value $m-k$ (for some $k\<n$) if and only if $G$ admits a vertex cover of size at most $k$. As Vertex Cover is NP-hard, so must this problem be, even in this restricted setting.

---
Tags: np-hard, polynomial-time-reductions
---


# Question
Title: If we have f(n) ∈ O(h(n)) and g(n) ∈ Ω(h(n)), does that mean that f(n) + g(n) ∈ Θ(h(n))?
It is quite easy to prove that f(n) + g(n) ∈ Ω(h(n)), but I am having trouble with proving/disproving that f(n) + g(n) ∈ O(h(n)).

Someone suggested that this question answers mine, which it doesn't. As I've written above, proving that f(n) + g(n) ∈ Ω(h(n)) is easy. I am having trouble disproving that f(n) + g(n) ∈ O(h(n)).

Thanks for any help.

# Answer
> 1 votes
"We know nothing about the upper bound" is a good intuition but it is not a formal proof that you can't hope to show $f(n) + g(n) \in O(h(n))$ if your only assumptions are $f(n) \in O(h(n))$ and $g(n) \in \Omega(h(n))$.

Fortunately, a counterexample is easily obtained by considering, e.g., $f(n)=1$, $g(n)=n^2$, and $h(n)=n$.

# Answer
> 1 votes
Thanks to Yves Daoust for providing the answer. We know nothing about the upper bound of f(n) + g(n) so we cannot prove f(n) + g(n) ∈ O(h(n)).

---
Tags: asymptotics, big-o-notation
---


# Question
Title: Speeding up an array search for duplicate
I was tasked with writing a function that finds the value of an element that is the first duplicate in an array to be encountered. For the array

`[2, 1, 3, 5, 3, 2]`

The answer is 3, not 2.

for an array like this:

`[5, 3, 8, 2]`

(no dups) the answer is -1.

I wrote this function:

```
def solution(a):
    # return if no dups
    if len(set(a)) == len(a):
        return -1

    unique = []
    for e in a:
        if e in unique:
            return e
        else:
            unique.append(e)

    return -1

```

It does fine with small test inputs but it takes too long on large ones. How can I speed it up?

I tried this same algorithm in Perl on the same data and it processed all the inputs in time.

```
sub solution {
  my ($a) = @_;
  my %h;
  foreach my $e (@{$a}) {
    if (exists($h{$e})) {
      return $e;
    } else {
      $h{$e}++;
    }
  }
  return -1;
}

```

# Answer
> 0 votes
I changed the `unique` variable in the python snippet to signify a hash (dictionary in pythonspeak) instead of an array (list in pythonspeak) and it speeds it up enough to deal with all the inputs on time:

```
def solution(a):
    if len(set(a)) == len(a):
        return -1
    unique = {}
    for e in a:
        if e in unique:
            return e
        else:
            unique[e] = 1
    return -1

```

hashes lookups are theoretically O(1) and so are faster than array traversals O(N).

# Answer
> 0 votes
Your “unique”, the way you wrote it using \[\], is an array. Lookup time grows linear with the size of the array when the element you are looking for is not there. That’s why the time will grow quadratic with the index of the first duplicated element.

The answer you got made “unique” a hash table by using {}. Lookup in a hash table is practically constant time, so the time is now linear with the index of the first element not found.

As far as the question goes: it’s very hard to make an array lookup faster. We get around that by not using an array in the first place.

---
Tags: arrays, python
---


# Question
Title: How to generate all possible colour vectors generated by greedy colouring on a graph?
Given a graph $G$, how can we generate all possible color vectors that could be generated via greedy coloring?

N.B. Greedy coloring takes a graph and an order of vertices. It traverses vertices following that order and, while visiting a vertex $v$, puts the minimum color absent in all neighbors of $v$.

If $G$ has $n$ vertices, there are $n!$ possible orders. But by applying greedy coloring on all those $n!$ orders, obtained set of color vectors may be very small. Ex: Consider $n$ isolated vertices. Only one color vector $(1,1,\cdots, 1)$ is possible.

I am looking for an efficient solution to identify those color vectors.

# Answer
> 2 votes
Let $V\_i := \\{ u \mid c\_u = i \\}$ to denote the color classes of a proper coloring $c$. Let $V\_{\leq i} := \bigcup\_{j \leq i} V\_j$ to denote the union of the first $i$ color classes.

The coloring can be generated by a greedy coloring if and only if $V\_{\leq i}$ is *maximal* for all $i$, meaning that there is no new vertex $v \in V \setminus V\_{\leq i}$ that can be recolored as $i$ while still maintaining a proper coloring.

Proof:

* ($\implies$): Suppose for contradiction that there exists a vertex $v \in V \setminus V\_{\leq i}$ that can be recolored as $i$. During greedy coloring, the smaller color $i$ could have been used for $v$, contradicting the how greedy coloring works.
* ($\impliedby$): Order the vertices in $V\_1$ first, those in $V\_2$ next, and so on. We show that greedy coloring on this order will produce coloring $c$. Consider a vertex $u$ such that $c\_u = i$. Because $V\_i$ is an independent set, we can use the color $i$. Any smaller color $j \< i$ is already used by a neighbor of $u$, since otherwise we could recolor $u$ to $j$, contradicting the assumption that $V\_{\leq i}$ is maximal.

By using the characterization, we can design a recursive enumeration algorithm. To enumerate all greedy colorings of vertices $V$, first enumerate all maximal independent sets. An independent set will be a color class $V\_i$. For each independent set $V\_i$, the algorithm recurses for the graph with $V\_i$ removed. Pseudocode:

```
def enumrate(V, C = []):
  if V = ∅ then:
    yield C
    return
  for each maximal independent set I in G[V]:
    enumerate(V - I, C + [I])

```

There is an output-sensitive maximal independent set enumeration algorithm that runs in $O(VE)$ time per output (see Listing all maximal cliques - Wikipedia). Using that subroutine, the enumeration algorithm is output-sensitive because the recursion depth is bounded and any leaf node yields one solution. I'm uncertain whether the runtime per output can be further optimized.

---
Tags: algorithms, graphs, discrete-mathematics, greedy-algorithms, colorings
---


title: CDCL SAT solvers and don't cares

text:
# Question
Title: CDCL SAT solvers and don't cares
Modern CDCL SAT solvers often can return *partial* assignments where missing literals mean that the value of that variable is not important for the satisfaction of the formula (*i.e.* it is a *don't care*).

What I can't understand is which guarantee do I have that such don't cares are identified.

So, are state-of-the-art solvers (*e.g.* CryptoMiniSAT or Glucose or whatever) always able to identify the don't cares and give me a partial assignment instead of a single specific one, or how can they be used to obtain that?

# Answer
State-of-the-art CDCL SAT solvers typically use sophisticated algorithms and techniques to identify and return partial assignments with don't cares. These solvers are designed to maximize their efficiency in identifying the don't care assignments to minimize the amount of time it takes to solve a problem. Depending on the solver, users can configure certain parameters that impact the solver's ability to identify don't cares. By tweaking these parameters, users can increase the likelihood that the solver will return a partial assignment with don't cares.
> 2 votes

---
Tags: sat-solvers
---


# Question
Title: How to find infinite set $X$, which satisfies $T(n)=Ω(n)$ when $n∈X$
Consider the following recurrence relationship.

\begin{eqnarray} T(n) &=& \begin{cases} T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is even number}& \\ 2T\left(\displaystyle\frac{n-1}{2}\right), &n \ \mbox{is odd number}& \end{cases} \nonumber \\ T(1) &=& 1 \end{eqnarray}

How to prove there exists an infinite set $X$, that when $n∈X$, $T(n)=Ω(n)$?

# Answer
Here is the idea. When $n$ is even, $$ \frac{T(n)}{n} \approx \frac{1}{2} \frac{T(n/2)}{n/2}. $$ In contrast, when $n$ is odd, $$ \frac{T(n)}{n} \approx \frac{T(\lfloor n/2 \rfloor)}{\lfloor n/2 \rfloor}, $$ due to the factor 2 in the recurrence.

This suggests that in order to find your set $X$, you want to hit the "odd" case all the way. If $m = \frac{n-1}{2}$ then $n = 2m+1$, so if $m$ is a good choice, so is $n$. This suggests considering the sequence defined by $n\_0 = 1$ and $n\_{t+1} = 2n\_t+1$, which is $1,3,7,15,\ldots$. As you can see, $n\_t = 2^{t+1}-1$. The value of $T$ on this sequence is $1,2,4,8,\ldots$, that is, $T(n\_t) = 2^t$.

We can now prove by induction that $T(2^{t+1}-1) = 2^t$. When $t = 0$, this just states the base case $T(1) = 1$. When $t \> 0$, $$ T(2^{t+1}-1) = 2T\left(\frac{2^{t+1}-2}{2}\right) = 2T(2^t-1) = 2\cdot 2^{t-1} = 2^t. $$ Finally, note that $$ T(2^{t+1}-1) = 2^t \geq \frac{1}{2} (2^{t+1}-1), $$ and so you can take $X = \\{ 2^{t+1}-1 : t \in \mathbb N \\}$ as your infinite set.
> 1 votes

# Answer
If all arguments of $T$ are even, i.e. when $n$ is a power of $2$, the solution of the recurrence is $T(n)=\log\_2(n)+1$. (Because $\log\_2(2^k)+1=\log\_2(2^{k-1})+1+1$.)

On the opposite, when all arguments of $T$ are odd, the solution is $T(n)=\dfrac{n+1}2$ (Because $\dfrac{n+1}2=2\dfrac{\dfrac{n-1}2+1}2$.)

---

**Resolution of the second recurrence**:

For all odd arguments,

$$T(n)=2T\left(\frac{n-1}2\right)$$ becomes, with the ansatz $T(n)=an+b$,

$$an+b=2a\left(\left(\frac{n-1}2\right)+b\right),$$ giving $a=b$. Then the initial condition makes $a+b=1$.
> 0 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: How to tackle Big O proofs that involve multiple parameters
I am getting more and more familiar with the whole concept of time complexity but I have never encountered an example where more than one parameter is involved. Therefore, is it possible(well, I am sure it is :")) and how to prove

> a^n = Θ(logn)

or any other, similar-looking expression?

> c1 * logn ≤ a^n ≤ c2 * logn

where, e.g. c1 = 1 and c2 = 2,

> logn ≤ a^n ≤2 * logn.

Can I go one step further and set n, to be equal e.g. 2? This way I will get

> log(2) ≤ a^2 ≤ log(4)

Which is surely true(for a between ~ 0.55 and 0.77)...

...but isn't that too specific and interfere with the inequality too much? Sorry if the answer is trivial but Google is not helping and I have nobody to ask for explanation.

# Answer
> 0 votes
That isn't true. As you say, it implies there are $c\_2$ and $N$ so that for all $n \ge N$ you have $a^n \le c\_2 \log n$. Consider:

$\begin{align\*} \lim\_{n \to \infty} \frac{a^n}{\log n} &= \lim\_{n \to \infty} \frac{a^n \log a}{1 / n} = \infty \end{align\*}$

Here we used l'Hôpital. But that the limit is infinite means that eventually the ratio is larger than any given $c\_2$. In fact, it proves $a^n = \Omega(\log n)$.

# Answer
> 0 votes
Your example shows two "parameters", but only one is the variable of interest ($n$, usually denoting the problem *size*).

Unfortunately, your example is not really suitable for an explanation, as only

$$a^n=\Theta(a^n)$$ can be shown to hold, and this is trivial. \[$a^n=\Theta(\log n)$ is just wrong.\]

For a less trivial parametric example, consider

$$(n+a)^3=\Theta(n^3).$$

Indeed,

$$\frac{(n+a)^3}{n^3}=1+3\frac an+3\frac{a^2}{n^2}+\frac{a^3}{n^3}$$ and by taking $n\gg|a|$ you can make the last three terms as small as you want. E.g., take $n\>10|a|$ and

$$1-0.3+0.03-0.001=0.729\<\frac{(n+a)^3}{n^3}\<1+0.3+0.03+0.001=1.331$$

---
Tags: asymptotics, landau-notation
---