# Question
Title: Algorithm to generate length $n$ strings of $4$ colors such that no two subsequent colors are the same
Alice is preparing decorations to decorate the classroom for Children's Day. She is using beads in the colors red (r), green (g), blue (b), and yellow (y) to create strings of beads. During the class meeting, it was established that two beads of the same color cannot be placed next to each other.

Help Alice design the strings of beads and write a function called "beads(lk)" where the result is a sorted list of words representing the strings that can be constructed using all available beads. The parameter "lk" is a four-element list of numbers that specify the number of red, green, blue, and yellow beads, respectively. The maximum total number of beads is n=10.

Here is my solution using permutation, but the complexity is high.

```
from itertools import permutations

def beads(lk):
    colors = ['r', 'g', 'b', 'y']
    all = []
    for i in range(len(lk)):
        for j in range(lk[i]):
            all.append(colors[i])
    all_possible_combinations = []

    for perm in permutations(all):
        valid = True
        for i in range(len(perm) - 1):
            if perm[i] == perm[i + 1]:
                    valid = False
                    break
        if valid:
            all_possible_combinations.append("".join(perm))
    unique_combinations = sorted(set(all_possible_combinations))

    return unique_combinations

```

I am looking for a better complexity algorithm, now is O(n!). Can you provide me with some ideas?

Edit

Thanks @Yves for your suggestion:

```
def beads(lk):
    def recursive_beads(prev_color, remaining, current_string):
        valid_strings = []
        if sum(remaining) == 0:
            return [current_string]
        for color, count in enumerate(remaining):
            if count > 0 and color != prev_color:
                new_remaining = list(remaining)
                new_remaining[color] -= 1
                valid_strings.extend(recursive_beads(color, new_remaining, current_string + colors[color]))

        return valid_strings

    colors = ['r', 'g', 'b', 'y']
    result = []
    valid_strings = recursive_beads(4, lk, "")

    return valid_strings

```

# Answer
Use a recursive function that takes as input

* the string assembled so far,
* the remaining amounts of beads of every color.

In this function, you will try and add a bead of every color (if available, and different from the previous), and recurse until no bead remains.

---

I believe that this is close to optimal, but the complexity is pretty difficult to evaluate.
> 1 votes

---
Tags: algorithms, complexity-theory
---


# Question
Title: Convert a rational number to a floating-point number exactly
We have two integers, $n$ and $d$. They are coprime (the only positive integer that is a divisor of both of them is $1$). They may be implemented as something that fits in a machine register, or they may be "big integers". Together, $n$ and $d$ represent the numerator and denominator of a rational number.

The goal is to convert the rational number into the corresponding floating-point number in a fixed-width binary floating-point format (for example, 32-bit binary IEEE 754 floating-point, known as `float` in the C programming language).

As long as using "big floats" (arbitrary-precision floating-point, for example with the MPFR C library) for implementing the algorithm is allowed, the solution is easy:

1. convert both $n$ and $d$ to big floats with a precision that is high enough so both integers would be exactly represented
2. divide the big float numerator with the big float denominator, yielding a big float number
3. convert the above big float number to the required fixed-precision floating-point format

I wonder, however, what would a more from-first-principles solution look like, one that wouldn't use big floats?

# Answer
Big floats are nothing but big ints with a scaling factor, which you can handle by yourself.

If the two numbers are given as big ints and you are only allowed integer division, multiply the numerator by a power of $2$ large enough that the quotient has at least $24$ (resp. $53$) significant bits. Then normalize the result to single (resp. double)-precision floating-point.

If the numbers are given as integers, you will need to resort to extended precision arithmetic, i.e. 64 bits over 32 or 128 over 64. Append a zero word to the numerator, divide and normalize the result.
> 3 votes

# Answer
I am investigating a floating point number bug in CCL (Clozure Common Lisp), which since Common Lisp is using an old standard by default 32 bit IEEE 753 float known as `single-float` in most implementation is used.

The bug is demonstrate by the observation that converting a rational number to `single-float` could be way off:

```
(float 41107100000541273/100000000000) ;; => 411071.03
(float 41107100000541273/100000000000 0.0D0) ;; => 411071.00000541273D0

```

This is because CCL used the naive implementation that when neither the numerator or denominator are bignums or if their bit length are both less than `single-float-bias` that is 126 bits, convert both to `single-float` and do division is used. This gives:

41107100000541273 converted to single float is `1.0 * 0.57047564 * 2^56` 100000000000 is `1.0 * 0.72759575 * 2^37` Division gives: `1.0 * 0.78405577 * 2^19` which in decimal is `4.1107103E+5`.

Note that `41107100000541273` is only 56 bits so their implementation is definitely wrong.

So I lookup SBCL's implementation which does not suffer from this inaccuracy issue and turns out the algorithm they used is the following, and despite the algorithm is also intended to work for bignum integers, not even bigfloat or double float is involved:

The only noun ANSI Common Lisp standard function is

```
(ccl::make-short-float-from-fixnums significand biased-exp sigN)

```

which should be self explanatory. `labels` defines local functions and `loop` just does infinity loop here, which the help of a reference book to CL this algorithm can easily be converted to C.

```
(defun short-float-ratio (x)
  (let* ((signed-num (numerator x))
         (plusp (plusp signed-num))
         (num (if plusp signed-num (- signed-num)))
         (den (denominator x))
         (digits 24) ; single-float-digits
         (scale 0))
    (declare (fixnum digits scale))
    ;; Strip any trailing zeros from the denominator and move it into the scale
    ;; factor (to minimize the size of the operands.)
    (let ((den-twos (1- (integer-length (logxor den (1- den))))))
      (declare (fixnum den-twos))
      (decf scale den-twos)
      (setq den (ash den (- den-twos))))
    ;; Guess how much we need to scale by from the magnitudes of the numerator
    ;; and denominator. We want one extra bit for a guard bit.
    (let* ((num-len (integer-length num))
           (den-len (integer-length den))
           (delta (- den-len num-len))
           (shift (1+ (the fixnum (+ delta digits))))
           (shifted-num (ash num shift)))
      (declare (fixnum delta shift))
      (decf scale delta)
      (labels ((float-and-scale (bits)
                 (let* ((bits (ash bits -1))
                        (len (integer-length bits)))
                   (cond ((> len digits)
                          (assert (= len (the fixnum (1+ digits))))
                          (scale-float (floatit (ash bits -1)) (1+ scale)))
                         (t
                          (scale-float (floatit bits) scale)))))
               (floatit (bits)
                 (let ((sign (if plusp 1 -1)))
                   (ccl::make-short-float-from-fixnums bits 126 ; single-float-bias
                                      sign))))
        (declare (inline floatit))
        (loop
          (multiple-value-bind (fraction-and-guard rem)
              (truncate shifted-num den)
            (let ((extra (- (integer-length fraction-and-guard) digits)))
              (declare (fixnum extra))
              (cond ((/= extra 1)
                     (assert (> extra 1)))
                    ((oddp fraction-and-guard)
                     (return
                       (if (zerop rem)
                           (float-and-scale
                            (if (zerop (logand fraction-and-guard 2))
                                fraction-and-guard
                                (1+ fraction-and-guard)))
                           (float-and-scale (1+ fraction-and-guard)))))
                    (t
                     (return (float-and-scale fraction-and-guard)))))
            (setq shifted-num (ash shifted-num -1))
            (incf scale)))))))

```

Unfortunately, *TAOCP 2nd Volume* and *Handbook of floating-point arithmetic* does not give useful information on this topic so I cannot give a confirmation on how reliable the method is. I upvoted the problem since this is actually a meaning real world problem and has pitfalls.
> 1 votes

---
Tags: algorithms, floating-point, number-formats, real-numbers
---


# Question
Title: Is this a zero knowledge proof algorithm (security)
Suppose we have a website and you log in the website with a username and a password.During registration your computer downloads a file containing a random 32 digit number.Now when you try to log in , the website asks you 5 questions.Which is the digit at position x?(with x being a random number from 0-31).Isnt this a zero knowledge proof type of user authentication?

# Answer
No. It is not a zero knowledge proof. Zero knowledge means, roughly speaking, that the verifier gains no additional information other than the statement is true (in this case, that the user knows the secret). But in your protocol, the verifier *does* gain additional information. The verifier learns some of the digits of the secret. Thus, it is not a zero knowledge proof.

It is a sort of interactive proof system (a proof of knowledge, roughly speaking), more or less.
> 2 votes

# Answer
A zero-knowledge proof intuitively can be understood as follows:

Party A, which wants to prove its credibility, presents two parts of the proof in two separate boxes to Person B. These two parts together would be successful at proving credibility. But B is only allowed to open one of the boxes. A does not have any information on what box B is going to pick.

This is sufficient to convince B after multiple rounds because B can only be lucky 50% of the time after each round. Why is this zero-knowledge? Because B can not convince any party C about the credibility, it can be claimed that the ordering of box picking was known to A before the proof began, giving it plausible deniability.

The model you described does not form a zero-knowledge because the website is gaining knowledge about the random bit, it would be zero-knowledge if you are able to present the proof that you are aware of the random number without leaking any information about the random number itself.
> 1 votes

---
Tags: algorithms, security, zero-knowledge-proofs
---


title: Halting Problem Question

text:
# Question
Title: Halting Problem Question
Let HALT be a program that can decide the halting problem for any program and its input. HALT has two inputs, the program and the program's input. Let OPPOSITE be a program that accepts a program as input, calls HALT with its input as both of HALT's inputs, and then does the opposite of whatever HALT has concluded. If we imagine running OPPOSITE(OPPOSITE), then the result is supposed to show a contradiction. Let's assume anyone using such logic will come to the same conclusion.

Pseudocode you've surely seen before

```
OPPOSITE (INPUT) :
   if HALT(INPUT, INPUT) == YES :
      LOOP_FOREVER
   else
      STOP

```

Since OPPOSITE runs/calls HALT, if HALT ran naively without analysis by simply running the program with its input, it would result in an infinite stack/loop without reaching a conclusion. This could prove HALT is not actually capable of deciding for all programs. However, if it does so, HALT may actually return the correct answer.

An infinite loop or an infinite stack must be detectable by HALT because this is a manner in which a program may fail to halt.

Suppose HALT runs OPPOSITE(OPPOSITE) naively without analysis. Thus the OPPOSITE run by HALT enters the infinite loop and this is detected by HALT, as mentioned above. HALT then decides to stop naively running the program at some point and in the last call returns an answer that OPPOSITE doesn't halt. The last OPPOSITE then halts. The last HALT then returns an answer that its input doesn't halt. The last OPPOSITE then attempts to run forever. The last HALT then detects the infinite loop, stops the last OPPOSITE, and returns an answer that OPPOSITE doesn't halt. ... This loops continues until the original OPPOSITE(OPPOSITE) regains execution.

Thus we have examples of OPPOSITE doing both, so no matter what the first HALT returns, it will be correct and not a contradiction.

So my question is, have I made any logical errors so far?

# Answer
> 4 votes
Yes, you seem to have made at least one error. Programs don't "know" anything. That was the first error I spotted, and then I stopped reading, as a single logical error invalidates an argument. Therefore, the statement "Let us further assume that HALT knows it can decide the halting problem" is meaningless and nonsensical.

# Answer
> 0 votes
"So my question is, have I made any logical errors so far?" Your descriptions are far too informal to interpret what is meant by each statement. I'm referring to the paragraph: "Suppose Halt runs ... " Even before that point, matters are not clear. I would suggest taking this off cs stackexchange and discuss with someone who is well versed in the Halting Problem. The statements are so imprecise that only a very long list of exchanges may bring some clarity. This is too labour intense for substack imo. An expert in the area will ensure you get matters clear in no time.

---
Tags: halting-problem
---


# Question
Title: How to provide a reduction from 3SAT to domatic number problem
How to provide a reduction from 3SAT to domatic number problem. Domatic number problem: Given a graph $G = (V, E)$ and an integer $k$, can we partition $V $ into at least k disjoint sets of vertices, such that each set is a dominating set of $G$?

I have made many attempts, but still have no clue.

# Answer
> 2 votes
The following is a reduction from 3-SAT to the domatic number problem:

Let $\phi: C\_1 \wedge C\_2 \wedge \dotsc C\_m$ be an instance of 3-SAT with $n$ variables $x\_1,\dotsc,x\_n$. Create a graph $G = (V,E)$ such that for each clause $C\_i \in \\{C\_1,\dotsc,C\_m\\}$ there is a vertex $vc\_i$, and for each variable $x\_j \in \\{x\_1,\dotsc,x\_n\\}$ there are three vertices $a\_j$, $b\_j$, and $c\_j$. The three vertices $a\_j$, $b\_j$, and $c\_j$ form a triangle in the graph as shown in the figure below:

The vertex $a\_j$ corresponds to the positive literal $x\_j$ and the vertex $b\_j$ corresponds to the negative literal $\bar{ x\_j }$. There is an edge between vertices $vc\_i$ and $a\_j$ iff $x\_j$ appears in clause $C\_i$. Similarly, there is an edge between vertices $vc\_i$ and $b\_j$ iff $\bar{x\_j}$ appears in clause $C\_i$. Moreover, there is a vertex $r$ which is connected to vertex $vc\_i$ via a path $r \to s\_i \to vc\_i$ for each $i \in \\{1,\dotsc,m\\}$. Moreover, the vertex $r$ is directly connected to vertices $a\_j$ and $b\_j$ by an edge for each $j \in \\{1,\dotsc,n\\}$. This completes the construction.

*Claim:* $\phi$ is satisfiable iff $G$ has domatic number at least $3$.

*Proof:* $(\to)$ Suppose that $\phi$ has a satisfying assignment such that without loss of generality, $x\_1,\dotsc,x\_k$ variables are true and the remaining variables $x\_{k+1},\dotsc,x\_n$ are false. We show that the reduced graph $G = (V,E)$ has domatic number $3$. The vertex set $V$ can be partitioned into three sets $V\_1 = \\{ a\_1,\dotsc,a\_k,b\_{k+1},\dotsc,b\_n\\} \cup \\{r\\}$, $V\_2 = \\{ b\_1,\dotsc,b\_k,a\_{k+1},\dotsc,a\_n,vc\_{1},\dotsc,vc\_m\\}$, and $V\_3 = \\{c\_1,\dotsc,c\_n, s\_1,\dotsc,s\_m\\}$. It is easy to see that each of these vertex sets is a dominating set of graph $G$.

$(\gets)$ Suppose the graph $G = (V,E)$ has domatic number at least $3$. Note that the domatic number can not be greater than $3$ since $c\_i$ has degree two and it can be dominated by at most three distinct sets. Therefore, let $V\_1$, $V\_2$, $V\_3 \subseteq V$ be a partition of the vertex set $V$ such that each vertex set is a dominating set. Without loss of generality, assume that $r \in V\_1$. Then there are only two possibilities for each $i \in \\{1,\dotsc,n\\}$ as stated below:

$(1)$ $vc\_i \in V\_2$ and $s\_i \in V\_3$

$(2)$ $vc\_i \in V\_3$ and $s\_i \in V\_2$

Otherwise, $s\_i$ can not be dominated by one of the sets $V\_2$ or $V\_3$. Without loss of generality, consider a particular vertex $vc\_i$ and suppose that $vc\_i \in V\_2$. Therefore, $s\_i \in V\_1$. Now note that $vc\_i$ must be dominated by some vertex in $V\_1$. Therefore, at least one of the $a\_j/b\_j$'s connected to $vc\_i$ must be in $V\_1$. Therefore, the vertex set $V\_1 \cap \\{a\_1,\dotsc,a\_n,b\_1,\dotsc,b\_n\\}$ is a satisfying assignment for $\phi$. Note that for any $j$, both $a\_j$ and $b\_j$ can not be picked into $V\_1$ otherwise $c\_j$ won't get dominated by either $V\_2$ and $V\_3$. Therefore, the assignment is a valid assignment. This completes the proof of the claim.

---
Tags: complexity-theory, computability, np-complete, np, polynomial-time-reductions
---


# Question
Title: Algorithm to find optimal currency denominations
Mark lives in a tiny country populated by people who tend to over-think things. One day, the king of the country decides to redesign the country's currency to make giving change more efficient. The king wants to minimize the expected number of coins it takes to exactly pay any amount up to (but not including) the amount of the smallest paper bill.

Suppose that the smallest unit of currency is the Coin. The smallest paper bill in the kingdom is worth $n$ Coins. The king decides that there should not be more than $m$ different coin denominations in circulation. The problem, then, is to find a $m$-set $\\{d\_1, d\_2, ..., d\_m\\}$ of integers from $\\{1, 2, ..., n - 1\\}$ which minimizes $\frac{1}{n-1}\sum\_{i = 1}^{n-1}{c\_1(i) + c\_2(i) + ... + c\_m(i)}$ subject to $c\_1(i)d\_1 + c\_2(i)d\_2 + ... c\_m(i)d\_m = i$.

For instance, take the standard USD and its coin denominations of $\\{1, 5, 10, 25, 50\\}$. Here, the smallest paper bill is worth 100 of the smallest coin. It takes 4 coins to make 46 cents using this currency; we have $c\_1(46) = 1, c\_2(46) = 0, c\_3(46) = 2, c\_4(46) = 1, c\_5(46) = 0$. However, if we had coin denominations of $\\{1, 15, 30\\}$, it would take only 3 coins: $c\_1(46) = 1, c\_2(46) = 1, c\_3(46) = 1$. Which of these denomination sets minimizes the average number of coins to make any sum up to and including 99 cents?

More generally, given $n$ and $m$, how might one algorithmically determine the optimal set? Clearly, one might enumerate all viable $m$-subsets and compute the average number of coins it takes to make sums from 1 to $n - 1$, keeping track of the optimal one along the way. Since there are around $C(n - 1, m)$ $m$-subsets (not all of which are viable, but still), this would not be terribly efficient. Can you do better than that?

# Answer
This is related to the well-known change-making problem. So well-studied, in fact, that this question has been investigated for $m \leq 7$ \[1\] using brute force. As of 2003, the hardness of finding optimal denominations appears to be an open problem.

If you check the articles citing Shallit, it seems as if denominations enabling greedy change-making strategies were of particular interest. It is clear that such denominations have advantages in practice.

---

1. What This Country Needs is an 18c Piece by Jeffrey Shallit (2003)
> 6 votes

# Answer
I guessed (wrongly, but bear with me) that the series $\\{b^i |\ b = \lceil n^{1/m} \rceil, 0 \leq i \< m\\}$ of coins would be the optimal, as the coins would be exponentially spaced, thus reducing the remaining value as much as possible per added coin. For your example, this would be $\\{1,3,9,27,81\\}$.

This is a notch better ($390/99$) than the USD denominations ($420/99$), but that doesn't have to mean anything.

I wrote a hackish Haskell script to get some numbers by brute force, as I'm not sure right now how to approach this analytically.
It turns out, the exponential distribution is not always the best: there are sometimes slightly better ones, for example, for $(m,n) = (4,30)$ we get $75/29$ for $\\{20,8,3,1\\}$ but $87/29$ for $\\{27,9,3,1\\}$. My sluggish machine can't get to $(5,100)$, so we have to use smaller numbers, here.

However, I noticed that the error seems to be quite small. Most of the time, the division of the sums yields something starting with an 1.0..., so I ran some more tests.

From a test set with $3 \leq m \leq 5$ and $6 \leq n \leq 40$, we get an average error of our exponential growing compared to the best solution of $1.12$ with a standard deviation of $0.085$.

You might argue that the test parameters are rather small, but as you point out, it's just a lot to brute force if you set $n = 100$ (there's most probably a better solution, but this was an excellent excuse to slack off and do some Haskell).

---

Here is my test suite, if you want to try it out:

```
getopt :: [Integer] -> Integer -> [Integer]
getopt _ 0 = []
getopt coins target = choice:(getopt viable $ target - choice)
                          where
                            viable = filter ((>=) target) coins
                            choice = maximum $ viable

getsum :: [Integer] -> Integer -> Int
getsum coins n = sum $ map length $ map (getopt coins) [1..(n-1)]

buildall :: Integer -> Integer -> [[Integer]]
buildall 1 _ = [[1]]
buildall m n = foldl1 (++) $ map (\am -> map (\x -> x:am) [((head am)+1) .. (n-1)]) $ buildall (m-1) n

buildguess :: Integer -> Integer -> [Integer]
buildguess m n = reverse $ map ((^) $ ceiling $ (fromInteger n)**(1.0/(fromInteger m))) [0..(m-1)]

findopt :: Integer -> Integer -> ([Integer],Int)
findopt m n = foldl1 (\(l@(_,lhs)) -> (\(r@(_,rhs)) -> (if (lhs < rhs) then l else r)))
            $ map (\arr -> (arr,getsum arr n)) $ buildall m n

intcast :: (Integral a,Num b) => a -> b
intcast = fromInteger.toInteger

esterror :: Integer -> Integer -> Double
esterror m n = (intcast $ getsum (buildguess m n) n) / (intcast best)
                 where (_,best) = findopt m n

```

I ran the test with

```
map (uncurry esterror) [(m,n) | m <- [3..5], n <- [6..40] ]

```
> 2 votes

# Answer
I found out that for m=2 the set should be {1, floor(√n)+1} or {1, ceil(√n)} unless n is a perfect square times the unit the two numbers are equal, if n is a perfect square,both √n and √n+1 work the best
> 0 votes

# Answer
I think that the optimal solution is when a denomination is used it should be used at most (m√)n times and also using as close denominations as the value as possible. I tried using {1,3,7,16,40} for n= 100 (or 99) as I tried to generalise the m=2 solution, however 28 is better made as 7+7+7+7 rather than 16+7+3+1+1 and similarly 68 as 40+4×7 rather than 40+16+7+1+1 so it skips using 16 which is closer to 28 than 7 is. Also 21= 7+7+7=16+3+1+1 , 37= 16+7+7+7=16+16+3+1+1, 61= 40+7+7+7=40+16+3+1+1, 77=40+16+7+7+7=40+16+16+3+1+1 Yes I found many. What is interesting about this set is that you can replace 3+3+1 with 7, 7+7+1+1 with 16, 16+16+7+1 with 40, and weirdly 16+3+1+1 with 7+7+7
> 0 votes

---
Tags: algorithms, optimization, combinatorics, integers
---


# Question
Title: Algorithm for iteratively distributing $5$ units to two variables
Please point me to the right place if this isn't the right one to ask in.

* There are 2 initial integer variables (the values of the two can be changed). $a = 4$ and $b = 1$
* There's a function. Each run of the function can distribute a total of $5$ to $a$ and $b$.
* So any positive integer combination of $5$ is possible.
* So a run for example could be $a = a + 1$ and $b = b + 4$.
* Another run could be $a = a + 3$ and $b = b + 2$.
* Another run could be $b = b + 5$.
* Also, the function increases $a$ by $1$ at the end of each iteration. (So at each run, $a$ will increase by $1$).

What is the lowest number of runs that could be done such that $a \geq 99$ and $b \geq 99$?

Here's sample code where I did a super simple inefficient approach that's also probably not correct/doesn't give the lowest number possible:

```
public static void Main()
{
    int core = 4;
    int shell = 1;
    int counter = 1;
    while (core < 99 || shell < 99)
    {
        ++core;
        for (int i = 0; i < 5; i++)
        {
            if ((shell + 1) <= 99)
            {
                shell++;
            }
            else
            {
                core++;
            }
        }
        Console.WriteLine($"counter: {counter} | core: {core} | shell: {shell}");
        ++counter;
    }
}
//////////// output of above:
    counter: 1 | core: 5 | shell: 6
    counter: 2 | core: 6 | shell: 11
    counter: 3 | core: 7 | shell: 16
    counter: 4 | core: 8 | shell: 21
    counter: 5 | core: 9 | shell: 26
    counter: 6 | core: 10 | shell: 31
    counter: 7 | core: 11 | shell: 36
    counter: 8 | core: 12 | shell: 41
    counter: 9 | core: 13 | shell: 46
    counter: 10 | core: 14 | shell: 51
    counter: 11 | core: 15 | shell: 56
    counter: 12 | core: 16 | shell: 61
    counter: 13 | core: 17 | shell: 66
    counter: 14 | core: 18 | shell: 71
    counter: 15 | core: 19 | shell: 76
    counter: 16 | core: 20 | shell: 81
    counter: 17 | core: 21 | shell: 86
    counter: 18 | core: 22 | shell: 91
    counter: 19 | core: 23 | shell: 96
    counter: 20 | core: 26 | shell: 99
    counter: 21 | core: 32 | shell: 99
    counter: 22 | core: 38 | shell: 99
    counter: 23 | core: 44 | shell: 99
    counter: 24 | core: 50 | shell: 99
    counter: 25 | core: 56 | shell: 99
    counter: 26 | core: 62 | shell: 99
    counter: 27 | core: 68 | shell: 99
    counter: 28 | core: 74 | shell: 99
    counter: 29 | core: 80 | shell: 99
    counter: 30 | core: 86 | shell: 99
    counter: 31 | core: 92 | shell: 99
    counter: 32 | core: 98 | shell: 99
    counter: 33 | core: 104 | shell: 99

```

# Answer
> 0 votes
Since you add $1$ to $a$ at each iteration, while $b$ can only be increased summing a portion of $5$ at each iterations, the idea is that of bringing $b$ to $99$ and then take care of $a$.

This is an outline for the algorithm:

1. while $b\<95$ add $5$ to $b$. As a consequence, you will add $1$ to $a$
2. if $b\<99$ (so it would be between $95$ and $98$ add to $b$ the remaining quantity in order to get $b=99$. Add the remaining part to $a$
3. while $a\<99$ add $5$ to $a$ ($+1$ at the end of the run$

This algorithm provide an optimal solution. In your case where $a=4$ and $b=1$:

1. Step 1 executes $\lfloor \frac{98}{5}\rfloor=19$ runs in order to get to $b=96$. As a consequence, $a$ is increased by $19$. So, at the end of first step we have done $19$ runs and we have $a=23$, $b=96$.
2. Step 2 executes one run, adding $3$ to $b$ and $2$ to $a$. At the end of the run $a$ is increased by $1$. So, at the end of second step we have done $20$ runs and we have $a=26$, $b=99$.
3. Step 3 executes $\lceil\frac{99-26}{6}\rceil=\lceil\frac{73}{6}\rceil=13$ runs. At the end of third step we have done $33$ runs and we have $a\geq 99$ and $b=99$.

So 33 is the minimum number of runs.

---
Tags: algorithms
---


# Question
Title: Knapsack with fixed size and flexible profit
We have $3n$ items with profits $p\_1, \dots, p\_{3n}$ (sum = $P$) and weights $w\_1,\dots,w\_{3n}$ (sum = $W$). We want to determine whether we can choose **exactly** $n$ items with profit at least $P/2 - 1$ and weight at most $W/2$.

If the profit must be at least $P/2$, we can set the profits to be equal to the weights and reduce from the partition problem to show NP-hardness. With the requirement of profit slightly lowered to $P/2-1$, I think the problem should remain NP-hard, but the reduction doesn't work anymore. Is there a way to modify the reduction to work?

# Answer
Let $\mathcal{I}$ be an instance of the problem with profit requirement at least $P(\mathcal{I})/2$, where $P(\mathcal{I}) = p\_1+\dotsc+p\_{3n}$. By the previous reduction, we know that the problem is $\mathsf{NP}$-hard. Moreover, the reduced hard instances had profits $p\_i$ as non-negative integers. We will exploit this fact for our reduction.

We reduce the instance $\mathcal{I}$ to an instance $\mathcal{I}'$ with profit requirement at least $P(\mathcal{I}')/2-1$. The instance $\mathcal{I}'$ is the same as instance $\mathcal{I}$ but with each profit four times the original value. Therefore, we have $P(\mathcal{I}') = 4P(\mathcal{I})$

*Claim:* There exists a feasible solution for $\mathcal{I}$ iff there exists a feasible solution for $\mathcal{I}'$.

*Proof:* $(\to)$ Let $\\{x\_{i\_1},\dotsc,x\_{i\_{n}}\\}$ be a feasible solution of $\mathcal{I}$ with profit at least $P(\mathcal{I})/2$. Then, the same solution is a feasible solution of $\mathcal{I}'$ with profit at least $4P(\mathcal{I})/2 \geq 4P(\mathcal{I})/2 - 1 = P(\mathcal{I}')/2 - 1$.

$(\gets)$ Let $\\{x\_{i\_1},\dotsc,x\_{i\_{n}}\\}$ be a feasible solution of $\mathcal{I}'$ with profit at least $P(\mathcal{I}')/2-1 =2P(\mathcal{I}) - 1$. Since the profit values are all even integers, the cost of the solution must be at least $2P(\mathcal{I})$. Then, the same solution is a feasible solution of $\mathcal{I}$ with profit at least $P(\mathcal{I})/2$.

---

This proves that the problem with profit requirement at least $P/2-1$ is $\mathsf{NP}$-hard as well.
> 2 votes

---
Tags: np-hard, knapsack-problems
---


# Question
Title: $log(n)\leq f(n)$, $L\in DSPACE(f(n))$ means $L\in DTIME(C^{f(n)})$ for some C
by definition log(n)=O(f(n)) therefor if M uses O(f(n)) cells it might as well uses log(n) cells, how do I continue?

# Answer
> 0 votes
No, that doesn't follow. 1 is $\le$ a million. Therefore if $M$ uses at most a million cells, it might as well use 1 cell. Wait, there is something wrong with that logic...

---
Tags: complexity-theory
---


title: Show that the language is undecidable

text:
# Question
Title: Show that the language is undecidable
Consider the language L = {\< M \>| M accepts iff input length is divisible by 3}. I'm supposed to use reduction to show that the language is undecidable. I tried proving it but didn't know what to do.

# Answer
> 1 votes
What languages are you familiar with? Are you familiar with the fact that $ALL\_{TM}=\\{\langle M\rangle : L(M)=\Sigma^\*\\}$ is not decidable? If so try a reduction from $ALL\_{TM}$ where given a machine $M$, construct a machine $M^3$, such that $w=w\_1\cdot w\_2\cdots w\_k$ is a accepted by $M^3$ iff $|w|(\mathrm{mod}\ 3)=0$ and $w\[i,\infty)$ is accepted by $M$ for all $i=0,1,2$, where $w\[i,\infty)$ is the suffix $w\_i\cdot w\_{i+1}\cdots w\_k$.

# Answer
> 1 votes
This follows immediately from Rice's theorem. However, if you don't know that theorem yet and you're asked to prove it by an explicit reduction, see oleshkowitz's answer.

---
Tags: turing-machines, reductions, undecidability
---


title: Subexponential reduction

text:
# Question
Title: Subexponential reduction
I am working on exact algorithms for an NP-hard problem $P$. I was able to get a $(1.75^n$) time algorithm for split graphs. When it comes to bipartite graphs, the problem becomes hard to tackle. Now, I want to prove that there is no sub-exponential algorithm for the problem on bipartite graphs. So to prove this, I have to provide a reduction from 3-SAT, which doesn't admit a $2^{o(n)}$ algorithm. I have reduced 3-SAT ($m$ clauses, $n$ varibales) to $P$ ($G'$ with $n'$ vertices) such that
(1) the reduction is done polynomial time.
(2) the size of the reduced instance $n'$ is $m+n^3$.
(3) 3-SAT is satisfiable if and only if $G'$ satisfy the necessary condition for the problem $P$
(4) $G'$ is bipartite
Now, can i say that the problem $P$ does not admit a $2^{o(n)}$ time algorithm for bipartite graphs? My main question is: does the reduction has anything to do with the size of the reduced instance, $n'$.

# Answer
Yes, obviously the lower bounds you get depend on the size of the reduction. Second thing is, you have no lower bounds as we don't know if P = NP. You have a *conditional* lower bound.

Under ETH, your problem cannot be solved in time $2^{o(\sqrt\[3\]{n})}$.
> 1 votes

---
Tags: algorithms, np-hard
---


# Question
Title: Can proofs by induction be achieved by defining a recursive function between two recursive objects?
I have two types of objects, X and Y, each are recursive structures, and contain different structures sets of tuples containing sets.. etc. The number of elements in X and Y are is the same.

I need to proof that for every x in X, there is a unique y in Y.

Can this be achieved by defining a bijective function which uses recursion to construct a y from each x?

Could I also achieve this proof using a proof by induction, if so how would I lay this out?

Is proof by induction the same a defining a recursive function between two recursive structures?

# Answer
> 1 votes
If you can establish that the function you define is a bijection from $X$ to $Y$, then that constitutes a proof, whatever technique you use, induction or other.

The proposition you wish to prove is essentially the **definition** of *bijection*.

# Answer
> 1 votes
Induction applies to infinite processes. Unless you address a special theoretical problem, I don't think that induction can be of any use. In any case, you would not establish equal values, but equicardinality.

---
Tags: proof-techniques, recursion, induction
---


# Question
Title: Can you verify the end of a function declaration through syntax analysis?
In some languages, it is expected that a function declaration be terminated by syntax that includes the function name. For example, in MODULA-2, a function is declared as shown below:

PROCEDURE P ;

BEGIN

...

END P ;

Is it possible to verify such a requirement using a syntax analyzer? If yes, explain how to do it. If not, provide an alternative explanation.

From what I understand, this part should be the job of semantic analysis, something like verifying the scope of variables, particularly that of "P," and in general, I believe the answer should be no. Well, I don't see how in the process of syntax analysis, this part can be verified. For example, if we generate the syntax analysis tree or parse tree, one way we could verify that the termination of the function is correct is by ensuring that there are at least 2 derivations to reach the leaves where "P" would be, but this wouldn't necessarily indicate that this is correct. For instance, if there were recursion or another call to "P" in the code block, the idea wouldn't work.

Any advice?

and well jeje,and ... how would the syntax analysis tree be? I've tried to do it, but what I'm doing doesn't make much sense. Any ideas on how I could guide myself to do it?"

thanks for your time

# Answer
It depends on what is meant by a *syntax analyzer*.

Generally, in computer science, different people often mean different things by the same term, so always consult the definition you were given.

It is very easy for a syntax analyzer to do this. Let's assume it is based on a parser that uses a well-known parsing technique for parsing a context-free grammar for the language.

The grammar will probably have a rule similar to this:

```
<procedure definition> :==
  PROCEDURE <name>;
  BEGIN
  <procedure definition body>
  END <name>;

```

The grammar is context-free, so it cannot express the fact that the two names that will expand to must be the same. What you really need is something like this:

```
<procedure definition> :==
  PROCEDURE <name(p1)>;
  BEGIN
  <procedure definition body>
  END <name(p2)>;
  <where(p1 == p2)>

```

Any sane parser generator based on context-free grammars will allow you to do this., except that the `<where ...>` clause may not be part of the grammar; you may need to check that condition by writing code in the programming language you're using.

It would be easier if the grammar formalism itself allowed you to do this. That would make something like the above a valid grammar in that formalism. Such grammar formalisms exist; they are called *attribute grammars*, or *affix grammars*, or *Van Wijngaarden grammars*, and no doubt some other names for them exist. But they are not taught in all compiler construction causes. So look at your course notes and textbook and base your answer on them.

Another question is whether to call this requirement a *syntactic* property and its analysis *syntactic* analysis. Many people would call it *semantics* rather than syntax. Once again, this is a matter of definition.
> 2 votes

# Answer
Nope,

```
PROCEDURE P;
BEGIN
END Q;

```

is syntactically valid. A BNF description cannot express the equality of the identifiers.
> 2 votes

---
Tags: formal-languages, programming-languages, compilers
---


# Question
Title: Support Vector Machines vs K-Nearest Neighbors
Let's say we have trained a **Support Vector Machine** with a **Gaussian Kernel**. When we feed our model an example, it classifies it based on its similarity to landmarks (distance to examples in our training set).

If instead our model is a **K-Nearest Neighbors algorithm, with k=size of the training set**, it classifies a given example based on its distance to examples in our training set (similarity to landmarks).

I know the math behind SVM and KNN is different, but on a high level, are they both employing the same idea? What am I missing if I think they are doing the same thing in different ways?

# Answer
Obviously, classification rests on the idea of similarity. Always. And in a metric space, similarity is measured with distances, and equal-distance loci are planes. \[In fact, you try to minimize the intra-class distances while maximizing the inter-class distances.\]
> 1 votes

# Answer
SVM:

* Faster to compute
* Requires less data to validate
* Less accurate than KNN where KNN is for nonlinear data as well.

Hint: Use a kernel with SVM, then you will get a very good result.
> -2 votes

---
Tags: machine-learning, artificial-intelligence, classification, nearest-neighbour, svm
---


# Question
Title: What do "JAMZ", "JAMN", and "JMPC" stand for in Mic-1?
I am wondering what do `JAMZ`, `JAMN`, and `JMPC` stand for in Tanenbaum's Mic-1 architecture. I know that `MPC`, the control store’s memory address register, stands for "MicroProgram Counter", but what does `J` mean? Likewise, there are 1-bit flip-flops where the values of `N` and `Z` are latched. The book says that if `JAMN` is set, the 1-bit `N` flip-flop is ORed into the high-order bit of `MPC`. Similarly, if `JAMZ` is set, the 1-bit `Z` flip-flop is ORed there. If both are set, both are ORed there. Effectively, this changes the address of the next instruction to be executed. So, it looks like `J` has something to do with "jump", but I'm not quite sure that's the case. The book does not spell out the names anywhere, just abbreviations. I also assume that `N` has to do with "negative", and `Z` with "zero", but those are just wild guesses.

Here is the Mic-1 microinstruction format:

Here is the Mic-1 block diagram:

# Answer
From this reference: http://wtkrieger.faculty.noctrl.edu/csc220\_winter2014/lecture/note22.pdf,

12 bits control the selection of the next microinstruction:

* Addr (9 bits) - the address of the next micro-instruction
* JAM (3 bits) - these bits determine how the next micro-instruction is chosen

JAM bits are complicated.

* JMPC = use the PC address
* JAMN = if N is true (negative result in ALU), then add 1 to high-order bit of Addr
* JAMZ = if Z is true (zero result in ALU), then add 1 to high-order bit of Add
> 1 votes

# Answer
Dont know the meaning of JMPC but I do know that both, JAMN and JAMZ are just Flags, which show that the result of the ALU is negativ or zero.

Edit: I think they use the flags and are relevant for using if in MAL. (Correct me if I'm wrong).
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Function of data pin(s) in a single RAM chip
Consider a very simple RAM chip that has 20 address pins and 4 data pins. I would like to know the function of the 4 data pins when only 1 data pin is enough.

What do I mean by 1 data pin is enough? If an address is applied to address pins, a memory cell is selected (which can only have value 0 or 1 — in a very basic RAM). Isn't it counter-intuitive to send 0 bit using 4 data pins when 1 data pin is okay. So why would the RAM have 4 data pins in this case?

If it's a memory system that combines multiple RAM chips, I understand having multiple data pins but I don't understand it for a single RAM chip

**NB**: Something might be missing from my base understanding because I've been struggling to understand how 4 data pins are necessary.

# Answer
Each address in this RAM chip stores 4 bits. For example, you can write data 0100 to address 01010101010101010101 and then write data 0011 to address 00000000001111111111 and then read address 01010101010101010101 and you get the data 0100 again.

You can view it as 4 1-bit RAM chips in parallel. Each address selects a group of 4 memory cells.

Each address has a separate 4 bits. It does not read 4 addresses at once. The second data bit from the first address is not the first data bit from the second address.

---

If you want 8-bit memory, you can combine 8 1-bit chips like you said, or you can use 2 4-bit chips, or 1 8-bit chip, and the circuit designer usually finds it more convenient and cheaper if there are less chips.
> 1 votes

---
Tags: computer-architecture
---


title: Trajectories with collisions

text:
# Question
Title: Trajectories with collisions
Say that I have a plasma gun:

It's easy to compute the trajectory of the plasma ray starting from the gun.

However, another ray may come from afar:

As everybody knows, plasma rays are deviated when they collide. In fact, they are always deviated 90°, away from the other ray:

Space is discreet (like a chess board). Each tile may contain either a plasma gun, a plasma ray or nothing. Rays can go either straight or diagonally. An important precision: rays are "instant", they do not take any time to propagate.

I need to compute a "solution" trajectory for all rays that satisfies all constraints.

I can easily compute a ray propagation step by step, but if a collision is detected with other ray, it seems that I will need to "backtrack" that ray up to the point of collision, to then restart propagating it correctly.

Any suggestion of an algorithm to do this? Maybe lists are not really indicated for this, and I should use graphs (nodes being collisions)?

I would be also glad if you point me to some class of similar algorithms/research... Thanks!

EDIT: Note that collisions can have cascading consequences. For example in this situation:

If I fire the red plasma gun, This is what I should get:

The green trajectory was affected by the new collision between red and blue. New collisions can also appear:

Last but not least, paradoxes can appear:

# Answer
> 3 votes
One possible approach is to use the Bentley-Ottman algorithm (or similar algorithm) to find all intersections between line segments.

More specifically: for each plasma gun, add a directed line starting at the plasma gun and proceeding in a straight line to infinity. The algorithm lets you find all pairs of intersections between the lines in the data structure. We're going to enumerate intersections in order of the increasing distance from the start to the intersection. More specifically, we'll repeat the following until there are no intersections remaining:

* Find the intersection point that has the minimum (smallest) possible distance from start of line to the intersection point. Call this intersection point $I$.
* $I$ is the intersection of two directed line segments, one starting at (let's call it) $G$ and going through $I$ and one starting at (let's call it) $H$ and going through $I$.
* Delete those two lines from the data structure.
* Output line segments $GI$ and $HI$.
* Add to the data structure two lines starting at $I$, representing the reflected directions, and proceeding to infinity.

Repeat until there are no intersections remaining among the lines in the data structure, and then output all lines remaining in the data structure.

Then the solution trajectory will be the line segments that have been output.

The core idea here is to start with the closest collision first, and proceed outward, as each collision will have cascading effects. (Thanks to @cdupoint for this insight.)

If you implement the Bentley-Ottmann algorithm with appropriate persistent data structures, it should be possible to make this run fast, with each operation (adding or deleting lines from the data structure, finding the nearest intersection) all running quickly ($O(\log n)$ or $O(\log^2 n)$ time).

In your specific situation, you might be able to simplify or speed up the data structure and algorithm by specializing ti to advantage of the fact that all lines will be horizontal, vertical, or diagonal at a 45 degree angle.

---
Tags: computational-geometry, backtracking, path
---


# Question
Title: Why is infeasibility of linear programming considered to be an NP problem?
I recently came across this question, and the way I think people usually go about this is to find a certificate that answers 'yes' to the decision problem 'Is this LP infeasible?' Or, given a certificate, verify if that yields infeasibility or not. I know of the theorem that says Ax = b is infeasible if there exists y such that ATy = 0 and yTb = 1. (AT = transpose of A). So given a y, we can check in polynomial time if these two conditions hold, and that is why the infeasibility problem is in NP. Am I missing something, or is this a good enough approach?

# Answer
> 0 votes
I expect you'll also have to prove that: (1) the "infeasible if" is an "infeasible iff", (2) the "size" of $y$ (the number of bits needed to represent it) is polynomial in the size of $A,b$, and (3) you can find $y$ in polynomial time.

---
Tags: complexity-theory, np, linear-programming, co-np, simplex
---


# Question
Title: Relation between NOT gate and negative numbers 2's complement
The steps to get a number in 2's complement are simple:

1. Flip the bits (Using NOT)
2. Add +1 (afaik this step is done to eliminate the duplicate 0)

Recently I've seen an ALU design that can operate negative numbers in 2's complement without the seconds step. For example, we want to perform the following operation $y-x$

The ALU is basic, has the following inputs:

* x
* y

Following control flags:

* ny (Not y)
* f (0 = AND; 1 = ADD)
* no (Negate output)

There are more, but for the sake of this example its enough.

So, to execute the following operation $y-x$ we pass the ALU with:

* a: 2
* b: 2
* ny: 1
* f: 1
* no: 1

NOTE: The ALU doesn't have special circuitry to ADD +1, so what the ALU does:

1. Negate y: NOT(y) -\> -3
2. Add x + -y = 2 + -3 = -1
3. Negate the output again: 0

So, as seen it jus works just like magic, without adding +1 to anyplace.

I've found the following relation between NOT and 2's complement numbers:

$NOT(y) = -(y+1)$

Actually, doing the same steps using this relationship, I get the same result which is correct:

1. Negate y: NOT(y) -\> -3
2. Add x + -y = 2 + -3 = -1
3. Negate result: NOT(x + NOT(y))
4. Expand equation: -(x -(y+1) + 1)
5. Simplify equation: y-x

So you get the correct operation, double negating, im confused how this is possible, and where can I read more about this relationship?

# Answer
The 1's complement of a number $n$ equals $2^w-1-n$, where $w$ is the word length. The two's complement is $2^w-n$.

So $x-y=-(y+(-x))=2^w-1-(y+2^w-1-x)=2^w-(y+2^w-x)$ and the subtraction can indeed be made using 1's complement or 2's complement logic.
> 1 votes

---
Tags: combinatory-logic
---


# Question
Title: Are Haskell monads stronger than strong monads?
Haskell's monads are usually considered to mean strong monads in category theory, but it seems like the former is a bit stronger than the latter. With strong monads, you have a Kleisli extension operator

$-^\* : C(a, Tb) → C(Ta, Tb)$

that operates outside the category $C$, whereas with Haskell's monads you can write an internal extension operator

$e : \mathbf{Hask}(a ⇒ Tb, Ta ⇒ Tb)$

that operates entirely inside $\mathbf{Hask}$. The intuitive difference is that $M^\*$ could involve a translation on $M : C(a, Tb)$ that inspects its syntax, whereas $eM$ can only operate on $M$ extensionally, only manipulating $M$ through whatever accessors are available for its type.

AFAICT, $-^\*$ can be derived from $e$, but not vice versa, even assuming tensorial strength and Cartesian-closed structure. Is this true, or is there a way to derive $e$ from $-^\*$ that I missed?

If Haskell's monads are not just strong monads, then do they have a name, and is there any interesting difference known about them vs. strong monads?

# Answer
> 3 votes
In a CCC, we have the following equivalence:

$$C(a ⇒ Tb, Ta ⇒ Tb) \cong C((a ⇒ Tb)×Ta, Tb)$$

Using tensorial strength, to give an element of the latter it suffices to give an element of:

$$C(T((a ⇒ Tb) × a), Tb)$$

And then using the evaluation map, it suffices to give:

$$C(TTb, Tb)$$

But this is given by the multiplication of the monad. So, strong monads in a CCC actually do have this sort of internal 'bind' operation. Despite the presentation, this is actually one of the core motivations behind strong monads/functors—internalizing the operations. The tensorial strength is just a characterization that makes sense without the category necessarily being closed.

---
Tags: category-theory, haskell, monad
---


# Question
Title: Quickhull vs T.M. Chan vs Avis and Fukuda
From Discrete lizard's answer and Handbook of Computational Geometry (Third edition, 2018) Section 26, Chazelle's solution of high dimensional convex hull achieved worst case optimal. T.M. Chan's algorithm made the practical implementation, and Avis and K. Fukuda's solution was more efficient.

However, I recently came across the Quickhull algorithm based on Qhull librtary, and from Mauricio Fernández's answer, it seemed that the Quickhull was faster than T.M. Chan's algorithm. This confused me a bit because T.M. Chan's algorithm was designed specifically for the high dimensional convex hull computation, while the Quickhull arise from the lower dimensional algorithms.

Which algorithm was faster in theory and which algorithm is faster in practical, Quickhull,T.M. Chan's algorithm, or Avis and Fukuda's algorithm?

# Answer
> 2 votes
"Faster" has no meaning when you compare theoretical algorithms. In general the complexities are only known asymptotically, and for practical problem sizes these expressions can be completely irrelevant. Furthermore, in practice you deal more with expected complexities than with worst cases, and the former can strongly depend on the data distribution.

In the case of the convex hull, an important aspect is how soon the internal sites are discarded, leaving only the hull vertices. QuickHull is good at that and might perform favorably when $h$ is small (the expected complexity can drop to $O(n)$), though its worst-case complexity is terrible ($O(n^2)$).

---
Tags: convex-hull
---


# Question
Title: Is the set of all strings over $\Sigma$ countably infinite or not?
Let $\Sigma$ be an alphabet. Is the set of all strings over $\Sigma$ (i.e. $\Sigma^\*$) countably infinite or uncountably infinite?

# Answer
> 3 votes
$\lambda$, $a$, $b$, $aa$, $ab$, $ba$, $bb$, $aaa$, $aab$, $aba$, $abb$, $baa$, $bab$, $bba$, $bbb$, $aaaa$, $\dots$,

# Answer
> 0 votes
Let us assume your set is $S=\cup\_{n\geq1}\Sigma^n$. Clearly, this set is infinitely large. All that is left to figure out is if $S$ is countable.

Any set with a bijection to the set of Natural Numbers, i.e., $\\{0,1,2,\ldots\\}$, is countable.

*Use the above fact to determine why $S$ is an infinitely large countable set*.

---
Tags: formal-languages, regular-languages, counting, uncountability
---


# Question
Title: Exploiting weaknesses in virus-detecting software?
If a virus is defined as a self-reproducing program, then Rice's theorem implies there can be no infallible virus-detecting algorithm.

Can we take that one step further, as follows? If you have the source code for a virus-detecting program, could you use it to produce a virus that the program will fail to detect?

# Answer
> 3 votes
Following the reasoning of the Halting Problem, you can indeed make a "virus" that performs the following action:

```
if (this very virus will not be flagged)
    infect everything in sight
else
    do nothing

```

This is practically possible: you just would have to bundle the entire antivirus with your program in order to perform that check.

However, this will not be helpful, because the antivirus can just **flag it anyway**, despite the fact that in that case it's actually harmless. After all, actual virus-detecting programs are allowed to have false positives, as opposed to that ideal detector from Rice's theorem.

So, in summary: this trick is possible, but it doesn't actually give you any advantage against the antivirus.

# Answer
> 2 votes
That line of reasoning demonstrates that if you have a virus-detecting program, there exists a virus that the program will fail to detect.

But it says nothing about how easy or hard it might be to actually construct (find) such a virus. Such matters are beyond the scope of computability theory. If you care about the running time of an algorithm to solve some problem, that gets into complexity theory, which is beyond the scope of Rice's theorem, computability, the halting problem, etc.

If you care about the difficulty of constructing such a virus in practice, then this turns out to be more of an engineering matter, that depends on systems and implementation details. Computability theory and complexity theory are not terribly informative.

---
Tags: rice-theorem
---


# Question
Title: Use of the degree variable in an MSOL formula
I am working on giving an MSOL formula for an NP-hard problem; this proves that the problem is linear-time solvable on bounded treewidth graphs. Given a graph $G = (V, E)$, the problem would be to find a subset $S \subseteq V$ such that each vertex of degree at least three has at least two neighbors and at most three neighbours in $S$. The MSOL formula for the problem is:
$\exists S \subseteq V:\forall v \in V\setminus d(v) \leq 2: ((\exists {u\_1, u\_2} \in S) \land (u\_1 \in N(v)) \land (u\_2 \in N(v)))$ $\land ((\exists u\_3 \in S) \land ((u\_3 \in N(v) \lor (u\_3 \notin N(v))))$ $\land ((\forall u \in S \setminus \\{u\_1,u\_2, u\_3\\}) \land (u \notin N(v)))$ where $d(v)$ indicates the degree of $v$.

1. Is this a valid MSOL formula? can i make use of $d(v)$ in the formula?
2. If not, how can i modify it in such a way that the formula solves the problem?

# Answer
> 1 votes
> main concern is whether or not $d(v)$ can be used in the formula

The answer to this is *no*.

However, if you want to ask whether the degree is (equal to, at least, at most) some fixed constant $c$, then you can make a formula like this:

$$d(v) \geq c \\; \triangleq \\; \exists u\_1 \exists u\_2 \cdots \exists u\_c \\; vu\_1 \in E \land vu\_2 \in E \land \cdots \land vu\_c \in E \land u\_1 \neq u\_2 \land \cdots \land u\_{c-1} \neq u\_c$$

---
Tags: algorithms, np-hard, treewidth
---


# Question
Title: Why there can't be two instances of a "reverse" program in the Halting problem?
So in the halting problem, there is a program that reverses the output of a program that tells if the input program halts or runs forever(I'll call it the main program further). The whole paradox is based on the fact that if we feed this "reverser" program to the main program the reverser program will be in two different states simultaneously: "halt" and "run forever". But what if we have multiple instances of the "reverser" program? One runs forever, and one halts. What am I missing?

# Answer
> 2 votes
The main point of the halting problem is that you are running programs on deterministic machines, that means that the execution is always the same.

Given a program and an input, it either halts or it doesn't halt, there is no in between, and certainly not both at the same time.

# Answer
> 0 votes
Let me remind the principle of the proof:

* Assume that we can write a program $H$ that is able to tell if any input program $I$ halts or not.
* Using $H$, we create a program $G$ that halts if $I$ does not halt, and conversely.
* Now we apply $G$ to itself as input ($I=G$). If $G$ halts, $H$ will say so and $G$ will not halt. Reciprocally, if $G$ halts, $H$ will say so and $G$ will not halt.
* This creates a contradiction, so we won't be able to write $H$, nor $G$.

---

It is important to understand that you can easily write a program $H$ that is conclusive for *some* inputs $I$ (an easy example is checking the absence of loop constructs), but we are requesting a program that works on *any* input.

If I am right, your objection is that there could be different $H\_i$ programs, with corresponding $G\_i$ programs, so that the set of input programs that can be processed would be larger. In fact, this would be equivalent to a larger "metaprogram" that would collect the results of the constituent $H\_i$ programs. And the proof applies identically to this metaprogram, leading to the same contradiction: it cannot conclude for itself.

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


# Question
Title: Can a decider return "Undecidable" on the Halting Problem?
So, I know there is no general algorithm for the halting problem, but I was curious if a three output decider could at least give us "an" output **{0 if doesn't halt, 1 if halts, U if undecidable for this decider}**.

Here's the halting problem, roughly, in python:

```
    # The decider function tries to determine if a function 'f' halts or not
def decider(f, x):
    try:
        return f(x)
#This is just a stand in for the logic which works fine for our example
    except RecursionError:
        return "doesn't halt"

# Function 'g' is an "adversarial" function
def g(y):
    # If decider says it halts, go into an infinite loop
    if decider(g, y) == "halt":
        while True:
            pass
    # If decider says it doesn't halt, then halt
    elif decider(g, y) == "doesn't halt":
        return "halt"

# Test the decider on the adversarial function 'g'
# This will lead to an infinite loop or a recursion error, depending on the Python interpreter.
result = decider(g, "some_input")
print(result)

```

Here's the same with the logic for returning in cases which we are not able to solve:

```
# Function to check if a function is "adversarial"
def is_adversarial(f):
#this is where the logic would go, for our case, we just single out g()
    return f == g

# The decider function with added adversarial checking
def decider(f, x):
    if is_adversarial(f):
        return "Unable to determine for this problem set."
    try:
        return f(x)
    except RecursionError:
        return "doesn't halt"

# Function 'g' is an "adversarial" function
def g(y):
    if decider(g, y) == "halt":
        while True:
            pass
    elif decider(g, y) == "doesn't halt":
        return "halt"

# Test the decider on the adversarial function 'g'
# This should return "Unable to determine for this problem set."
result = decider(g, "some_input")
print(result)

```

Note that even if we tried to leverage the "is\_adversarial" result, any decision it makes will be countermanded by g() due to the fact that g() explicitly calls decider() and countermands it. It is equivalent to receiving the news that you will die tomorrow and saying "ah, but if you got that information, you would be able to avoid death," but in fact, it is something entirely outside of your control, assuming you are deterministically defined. I want to make this explicit as I think it trips a lot of people up in my explanation, and their assumption the above would reduce to the halting problem.

It may not seem useful, but if there is nothing that demonstrates it to be contradictory, I can use it in another thing I'm working on that is useful.

# Answer
Presumably, you don't use the term "undecidable" in its formal sense. It is easy to write a program that returns "halts", "does not halt" or "don't know". In particular, a program that always returns "don't know" can do (though there are also less trivial solutions, for instance by detecting Pascal-style for and while loops).

I don't see in what way this would "break" the Halting problem.
> 4 votes

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


title: From big-step to small-step semantics

text:
# Question
Title: From big-step to small-step semantics
Ciobaca: From Small-Step Semantics to Big-Step Semantics, Automatically

describes how to go from small-step to big-step semantics.

I need to do the other way around: from big-step to small-step. Is there literature for this? What should I be careful of?

EXTENSION: I have a big-step operational semantics for a functional language and for my purposes I need to write a small-step operational semantics for it. Can you point to relevant scientific literature on how I should do this, what are the pitfalls?

# Answer
Here are a couple articles on the matter.

From Big-Step to Small-Step Semantics and Back with Interpreter Specialisation and Automatic Transformation of a Big-Step Skeletal Semantics into Small-Step

Also, if you need to write your own semantics for a functionnal language, you should have a look at pcf's semantics, for example here. If you feel adventurous, start with a semantics for the lambda calculus and go your own way.
> 1 votes

---
Tags: operational-semantics, small-step-semantics
---


# Question
Title: Time Complexity of Linear Search vs Brute Force
I am currently watching the FreeCodeCamp Algorithms and Data Structures Tutorial. In the explanation for exponential time complexity, they explain that using a brute force attack on a combination lock would create O(x^n) time complexity. I am confused as this attack sounds very similar to a linear search of the passcode, going one by one until you find the right combination.

The confusion comes when you find that while brute force has a time complexity of O(x^n), linear search only has a time complexity of O(n). This therefore means that, depending on what you call the algorithm, the same instructions can have differing time complexities, which makes no sense.

Can someone explain whether FreeCodeCamp have made an error in the course or I am mistaken?

Thanks :)

# Answer
> 14 votes
Time complexity is expressed as a function of some parameter, which is usually the size of the input.

The combination lock is not a perfect analogy as it is not immediately clear what the input would be. This confusion goes away once you deal with formally specified computational problems.

However, say that you want to express the time worst-case complexity of brute-forcing combination lock with $n$ dials, each of which can be in one of $x$ positions, where a single combination can be tested in constant time. Then the problem can be solved in time $\Theta(x^n)$.

The above time complexity is in $\Omega(x^n)$ since any algorithm needs to try each of the $x^n$ combinations in the worst case, and it is in $O(x^n)$ since there is an algorithm that takes time $O(x^n)$ to test all these combinations (this is not immediately obvious since you need to account for the time needed to generate the next combination to try from the current one, but it can be done).

If you are measuring the time complexity with respect to the number $N$ of all possible combinations, then it would be $\Theta(N)$, although this is somewhat less natural.

# Answer
> 7 votes
You are absolutely right that they are the same algorithm! At least, in this context. "Brute-force attack" is a general term referring to finding a solution to the problem at hand by trying every possibility. Linear-search usually refers to a more specific case where you are scanning through a specified, arbitrarily ordered set (like an array) and looking for a specific value. But you are correct that a "brute-force attack" is just a linear-search through the set of possible solutions according to some ordering.

The discrepancy comes from the variables meaning different things in these contexts. When talking about linear-search, we usually use $n$ to represent the size of the set we are searching through. But in the context of a combination lock, they are using $n$ to represent the length of the passcode (and $x$ to be the number of values each "digit" can take.) Thus the set of all possible passcodes is actually of size $x^n$ and the analysis of linear search agrees that this will have a worse-case runtime of $O(x^n)$.

# Answer
> 4 votes
It's all about what you call $n$.

If $n$ denotes the length of the key, then the complexity can be exponential $O(a^n)$.

If $n$ denotes the number of combinations that can be tried, obviously $O(n)$. But given that $n=a^l$ where $l$ is the key length, that is still $O(a^l)$.

---

**Other example:**

Ordinary matrix product takes $O(n^3)$ operations for $n\times n$ matrices. But only $O(n\sqrt n)$ for matrices of $n$ elements.

# Answer
> 2 votes
They are both correct, but the N is different.

Algorithmic brute force: Inputs: X: Size of each combination element N: Number of combination elements Algorithm generates all possible combinations and tries each one. Algorithm is O(X^N)

Linear brute force: Inputs: N: List of all possible combinations Algorithm tries each item in list Algorithm is O(N)

but N here is the same as X^N from the other, and would probably be generated in O(X^N) time itself.

# Answer
> 0 votes
Linear search runs in linear time $O(n)$ where $n$ is the input size. For example, if you add one item to the array, one extra step is needed.

Brute-force attacks need linear time $O(n)$, but here, $n$ is the value, because the value does not index an array. Therefore, to increase the memory usage in constant steps, you need to add a bit to brute-force. Adding a bit doubles the steps. This is called Pseudo-polynomial time.

---
Tags: algorithms, time-complexity, search-algorithms, big-o-notation
---


title: How do I make an A.I. reward system?

text:
# Question
Title: How do I make an A.I. reward system?
This question is because I think it would be fun to make an A.I.

Any programming language is acceptable. I am wondering how do I make a simple program that can associate certain things with points and learn to prefer things with more points associated with them. It is a very general question.

If you need an example, how would I make a program that can retrieve an input like "hello" and then search through a list of appropriate responses and choose the response that currently has the most "points" and then the user (me) can add points or take away points from that association in the console?

I know how to code already I just don't understand how the process would work. You don't even need to give me any code I am just asking about how this procedure would work? Sorry if the post is worded poorly I have autism and can't communicate effectively sometimes lol.

# Answer
The concept of reinforcement learning is what you're looking for.

> Reinforcement learning (RL) is an area of machine learning concerned with how intelligent agents ought to take actions in an environment in order to maximize the notion of cumulative reward.

As for code examples, this collection of algorithm implementations on GitHub may serve as a reference.

In general, an "agent" takes an "action" based on the current "state" of an environment to change it, calculates a "reward" based on the action taken and observed change in state, and works to optimize the reward gained.
> 2 votes

---
Tags: artificial-intelligence
---


# Question
Title: GA/GP subtree crossover/mutation with all items present?
I have a genetic algorithm/programming problem where I need the best arrange of items in a binary tree. My question is the best way to mutate/cross this binary tree subject to constraints described below.

All items need to be leaves in this binary tree and there are no nodes with only one branch populated. That is, all nodes are attached to two items and/or branches. So for example, this could work where 8, 9, 5, 6, 7 are items and all nodes have two branches:

This would not work because node 10 has only one branch:

My goal is to find the best binary tree arrangement of the items subject to an evaluation function, so all items have to be present.

For mutation, I thought about swapping nodes in this tree, but what would be a good algorithm for this? Clearly, we pick two nodes, and swap their attachments. But it is tricky, because one node cannot be the parent of another, otherwise attachment does not work.

Are there established algorithms for crossover/mutation for this problem setup where a binary tree needs to be mutated assuming all items are leaves and must be present?

# Answer
> 0 votes
You have at least the following 2 options.

## Option 1: use local moves

You can use 2 moves: rotations and local swaps. Both can be implemented in $O(1)$ assuming you keep a list of pointers to all non-leaf nodes and each node has 3 pointers: parent, left, and right.

### Rotation

1. Pick any non-leaf non-root node `B`.
2. Let `A = *B.parent`.

* 3a: If `A.left` points to `B` let `D=*B.right`. Point `A.left` to `D` and `B.right` to `A`.
* 3b: Otherwise `A.right` points to `B`, let `D=*B.left`. Point `A.right` to `D` and `B.left` to `A`.

4. Point `B.parent` to `*A.parent`, `A.parent` to `B`, and `D.parent` to `A`.

### Local swaps

1. Pick any non-leaf node `A`.
2. Swap `A.left` and `A.right`.

These two operations are both $O(1)$ and are sufficient to transform any tree to any other tree preserving the set of leafs, non-leaf nodes, and the condition that any non-leaf node has exactly 2 children.

## Option 2: implement swaps correctly

You can implement a function `is_descendant` which takes `node` and `ancestor` and calls `node.parent` until you either reach a root of the tree (return `False`) or reach `ancestor` (return `True`; also (optionally) provide which link (left or right) leads from the `ancestor` to `node`).

In the swapping move you can handle the case `is_descendant(node1, node2) or is_descendant(node2, node1)` as you wish. The easiest is to skip the move, but you can also, e.g., swap with the other child of `node2` if `node2` is an ancestor of `node1`.

---
Tags: genetic-algorithms
---


# Question
Title: Unusual applications of regular expressions?
I am looking for some interesting applications of regular expressions.

Can you name any unusual, or unobvious, cases where regexes find their application?

# Answer
> 43 votes
I don't know if this question belongs here (the answer could be subjective and depend on your definition of "unusual") but here is my favorite unusual application of regex:

> converting T9 input (2-9) to English text.

For example if the user wants to write `hello` they presses `42556`. Convert the input to `[ghi][def][jkl][jkl][mno]` and test this regex against the whole vocabulary: the word `hello` will match.

# Answer
> 18 votes
From this page, here's a regex for validating an RFC822-compliant email address

```
(?:(?:\r\n)?[ \t])*(?:(?:(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t]
)+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:
\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(
?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[
\t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\0
31]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\
](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+
(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:
(?:\r\n)?[ \t])*))*|(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z
|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)
?[ \t])*)*\<(?:(?:\r\n)?[ \t])*(?:@(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\
r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[
 \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)
?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t]
)*))*(?:,@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[
 \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*
)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t]
)+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*)
*:(?:(?:\r\n)?[ \t])*)?(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+
|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r
\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:
\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t
]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031
]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](
?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?
:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?
:\r\n)?[ \t])*))*\>(?:(?:\r\n)?[ \t])*)|(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?
:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?
[ \t]))*"(?:(?:\r\n)?[ \t])*)*:(?:(?:\r\n)?[ \t])*(?:(?:(?:[^()<>@,;:\\".\[\]
\000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|
\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>
@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"
(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t]
)*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\
".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?
:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[
\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*|(?:[^()<>@,;:\\".\[\] \000-
\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(
?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)*\<(?:(?:\r\n)?[ \t])*(?:@(?:[^()<>@,;
:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([
^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\"
.\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\
]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*(?:,@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\
[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\
r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\]
\000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]
|\\.)*\](?:(?:\r\n)?[ \t])*))*)*:(?:(?:\r\n)?[ \t])*)?(?:[^()<>@,;:\\".\[\] \0
00-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\
.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,
;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|"(?
:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*))*@(?:(?:\r\n)?[ \t])*
(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".
\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t])*(?:[
^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\]
]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*\>(?:(?:\r\n)?[ \t])*)(?:,\s*(
?:(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\
".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(
?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[
\["()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t
])*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t
])+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?
:\.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|
\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*|(?:
[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".\[\
]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)*\<(?:(?:\r\n)
?[ \t])*(?:@(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["
()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)
?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>
@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*(?:,@(?:(?:\r\n)?[
 \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,
;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\.(?:(?:\r\n)?[ \t]
)*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\
".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*)*:(?:(?:\r\n)?[ \t])*)?
(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\["()<>@,;:\\".
\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])*)(?:\.(?:(?:
\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z|(?=[\[
"()<>@,;:\\".\[\]]))|"(?:[^\"\r\\]|\\.|(?:(?:\r\n)?[ \t]))*"(?:(?:\r\n)?[ \t])
*))*@(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])
+|\Z|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*)(?:\
.(?:(?:\r\n)?[ \t])*(?:[^()<>@,;:\\".\[\] \000-\031]+(?:(?:(?:\r\n)?[ \t])+|\Z
|(?=[\["()<>@,;:\\".\[\]]))|\[([^\[\]\r\\]|\\.)*\](?:(?:\r\n)?[ \t])*))*\>(?:(
?:\r\n)?[ \t])*))*)?;\s*)

```

The original definition is a context-free grammar, hence the unwieldy regex

# Answer
> 16 votes
How about fighting cancer with the power of regex?

https://www.sciencedirect.com/science/article/pii/S2352914819303120

> **Title:** Regular expression based pattern extraction from a cell - Specific gene expression data
>
> **Abstract:** Cancer cells are formed when active genes stop functioning properly. Timely activation of a gene is governed through the combined effort of multiple Transcription Factors (TFs). TFs are proteins that bind on DNA in a sequence-specific manner. It is difficult to trace the target and role of TFs in the gene regulation process. The same element acts differently in different places, similar to the way the same word has a different meaning in a different context. This approach treats the cell line in a language context, whereas the genes and TFs are the symbols or letters of the language. Different combination of symbols forms a sequence with repetitive patterns. Identifying and analysing such frequently occurring patterns will give a better insight into the cell. This work mainly aims to identify such patterns found in the cell line using regular expression technique. The patterns generated in this work can be chosen as a feature for identifying the effect of regulatory elements in the genomic region. For improving readability identity of each character present in the pattern is documented in the form of a text file. Acute Myeloid Leukaemia (AML) data from GEO repository and the related two TFs binding narrow peak data, calibrated in K562 cell line from ENCODE consortium are taken as a case study.

# Answer
> 13 votes
Again, I don't know how unusual it is, but Paul Heckbert introduced regular expressions in path tracing to distinguish the light transport paths that various algorithms can correctly solve.

# Answer
> 11 votes
A simple PCRE expression (not exactly an regular expression, this one includes a `+?`) **can say if an unary number is non-prime** (so when it doesn't match, the unary number is prime): http://stackoverflow.com/questions/3296050/ddg#3296068

edit: thanks to @Pseudonym to point out that expresion was PCRE and not ERE or RE

# Answer
> 10 votes
One of the best ones I've seen using regex is to 'shift a number right by half a bit', i.e. to divide a number by $\sqrt 2$ and return the closest integer! Take a look at @Deadcode's Code Golf answer here.

# Answer
> 4 votes
You can use regular expressions to define a kind of constraint on the types of the leaves of a data structure. The example pictured below is a binary tree which, when traversed from left to right, yields a sequence of elements of type b, followed by a leaf with no data, followed by leaves of type a. We can describe this with a regular expression like `b*1a*`. There is now a procedure for converting the original tree type, and the regular expression, into a tree type constrained by the regexp. A special case is the example of zippers.

You can read a bit about it here and a paper giving the details is Polynomial Functors Constrained by Regular Expressions.

Briefly: the transition matrix for the regular expression is reinterpreted as a bunch of "simultaneous" equations defining a collection of types through mutual recursion. For example, the tree pictured might be defined in Haskell like so:

```
data Tree11 a b  =  Leaf11 a
                 |  Fork11  (Tree12 a b)  (Tree11 a b)
                 |  Fork11' (Tree11 a b)  (Tree21 a b)
data Tree22 a b  =  Leaf22 b
                 |  Fork22  (Tree22 a b)  (Tree12 a b)
                 |  Fork22' (Tree21 a b)  (Tree22 a b)
data Tree21 a b  =  Fork21  (Tree22 a b)  (Tree11 a b)
                 |  Fork21' (Tree21 a b)  (Tree21 a b)

```

The three definitions here correspond to entries in the transition matrix of the finite state machine recognising `b*1a*`.

(By the way, this particular example can be thought of as representing the intermediate state of a recursive algorithm to walk the tree converting `b`'s to `a`'s. Normally in such a recursive algorithm, the stack "keeps track" of where you are. But by making your current state explicit like this it allows you to remove the dependence on the stack and rewrite the algorithm with tail-recursion.)

# Answer
> 3 votes
It's debatable whether it's "unusual", since it's a classic Unix program, but Lex is probably not the first think people imagine when they think of Regexes.

Lex (or the newer variant, Flex) uses regular expressions for tokenization, in something like a compiler or interpreter. So you have one regular expression for matching strings, one for integers, one for the `if` token, etc.

Matching things like this with regular expressions doesn't seem that unusual. But the interesting part is what's done with them. The regular expressions are combined by Lex into a single minimal DFA for matching all of the tokens, and a representation of this DFA is written to a C file.

So multiple regular expressions are turned into one DFA, and minimized, at compile time.

The compiler's code can then invoke the generated lexer to retrieve the next token from a string of source code, which can then be parsed into a hierarchical structure (a related tool called Yacc can be used for that).

# Answer
> 3 votes
Test if a positive integer is a multiple of 3:

```
^([0369]|[258][0369]*[147]|[147]([0369]|[147][0369]*[258])*[258]|[258][0369]*[258]([0369]|[147][0369]*[258])*[258]|[147]([0369]|[147][0369]*[258])*[147][0369]*[147]|[258][0369]*[258]([0369]|[147][0369]*[258])*[147][0369]*[147])*$

```

Original article: https://www.quaxio.com/triple/

# Answer
> 3 votes
Raku (formerly known as Perl 6) parses raku scripts with Perl 6 regular expressions which directly outputs an AST, used by the interpreter. This means that modules in raku can modify the grammar of the language itself.

# Answer
> 2 votes
As an example of regular expressions not applied to strings, regular path queries (RPQs) are essentially regular expressions on paths that are widely used in the context of graph queries.

Need to find ancestors in a graph query language like SPARQL? You can write

```
?x (:mother|:father)* ?y

```

This will return all pairs of nodes in a directed edge-labelled graph where the edge labels on the path match the regular expression `(:mother|:father)`.

Similar regular-expression-like patterns are used in popular graph databases, like Neo4j.

# Answer
> 1 votes
> They're not regular, but finite state transducers can be used to generate and recognize complicated morphology, such as Finnish numerals. – phipsgabler May 7 '20 at 7:31

Similarly, a long time ago I worked using FST to identify multiword verbal expressions (such as 'tomar el pelo' \[to pull somebody's leg\]) in Spanish texts; words were previously tagged. That's how it looks like:

\<tomar.V:VAR-1:VAR-2:VAR-3\> ( \<ADV\1\> + \<PALABRA\1\>\* )
\<el.DET:ms\> \<pelo.N:ms\>
\[&tomar/el/pelo.LOCVPRED,VAR-1,VAR-2,VAR-3 | 1 \]

( \<tomar.V:INF\> + \<tomar.V:GER\> + \<tomar.V:IIMPE:VAR-1\> )
( + \<me.CLI\1\> + \<te.CLI\1\> + \<le.CLI\1\> + \<nos.CLI\1\> + \<os.CLI\1\> + \<les.CLI\1\> )
( \<ADV\2\> + \<PALABRA\2\>\* ) \<el.DET:ms\> \<pelo.N:ms\>
\[&tomar/el/pelo.LOCVPRED,1-3,VAR-1 | 1 | 2 \]

# Answer
> 0 votes
This is not very awesome trick but demonstrates usage of `\G` construct supported in Java regex - zero-width match at position where last match was found.

Example: how to insert separator after every three characters:

```
"abcdefgh".replaceAll("(?<=\\G.{3})"," ")

```

yields

```
"abc def gh"

```

---
Tags: regular-expressions
---


title: Time complexity of a convergent series

text:
# Question
Title: Time complexity of a convergent series
I wanted to ask a simple question: Assume I have a function whose time complexity is given by the following function: $T(n)=\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+...+\frac{1}{n^2}$. Would it be correct to say that the time complexity of the function is $Θ(1)$ because $T(n)$ is represented by a convergent series?

# Answer
> 2 votes
For every sufficiently large $n$ (here $n \ge 1$ suffices), $T(n)$ is both lower bounded by a positive constant (e.g., $1$) and upper bounded by another positive constant (e.g., $\pi^2/6$). Therefore it is correct to say that $T(n) = \Theta(1)$.

---
Tags: time-complexity
---


# Question
Title: Relational algebra statement for a query
For the following schema

```
Country ("countryID", cName)
CoffeeShop ("shopID", sName, countryID, city)
Product ("productID", size)
Serves ("shopID", "productID")
ProductNames ("productID", "countryID", pName)

```

where attributes in quotation marks are primary keys, I must write a relational algebra statement for the following query:

```
List names of products that have same names in all countries they are served.

```

The thing that made me stuck on this problem is the fact that the product must not necessarily be served in all countries, but rather have the same name in all countries it is served. Without comparing for an initial value, I couldn't get a solution that makes more sense and that is possible to be written as a relational algebra statement.

# Answer
> 0 votes
Hint: A product has the same names in all countries if for every two countries, it has the same name in both countries.

# Answer
> 0 votes
Try to systematically reformulate the query into tuple calculus (or domain calculus).

This is effectively a normalization operation on the natural language statement. Recasting it into tuple calculus makes it much longer, but unambiguous and much closer to relational algebra.

Use the fact that $\forall = \neg\exists\neg$.

Once you're done, you can similarly try a piecewise transformation into relational algebra.

For instance,

* *products with the same names in all countries they are served*

is the same thing as

* *products for which there is no name that is used in some but not all countries the product is served*

which is the same thing as

* *products for which there is no name that is used in one country it is served, but not in another* (Yuval Filmus's hint)

which is the same thing as

* *products for which there is no name such that there are two countries such that* (...)

which is the same thing as

* *products for which it is not the case that there is a name such that* (...)

and so forth.

I'm not writing these statements down in tuple/domain calculus syntax, but it is a good idea to do so.

If all is well, you will end up with a long statement (and a tuple calculus expression) that will be easy to transform into relational algebra.

---
Tags: relational-algebra
---


# Question
Title: Are there situations where we can decrease the time complexity of a program by increasing its ordinal complexity?
Are there (interesting) situations where we can decrease the time complexity of a program by increasing its ordinal complexity?

For example, is it possible to find a primitive recursive function such that:

* The fastest primitive recursive program to compute it runs in $O(f(N))$.
* The fastest non primitive recursive (for example doubly recursive) program to compute it runs in $O(g(N))$.
* $O(g(N)) \< O(f(N))$ i.e. the complex program is faster than the simple one.

I can't find the correct terminology for "primitive recursive program", since those words usually refer to functions themselves. That is why I use "ordinal complexity" instead, as defined here for example.

# Answer
Okay, as discussed in the comments, I will be assuming that the programming language has something like a "break" statement, which completely skips all the remaining iterations of a loop, spending $O(1)$ time on them, no matter how many iterations were remaining.

Let $M$ be an abstract machine (a Turing machine, a RAM machine, whatever is more convenient) which calculates our function by the non-primitive-recursive way. The point is, the running time of $M$ is $O(g(N))$.

Write a primitive-recursive program that does the following:

* Create a simulation of $M$ in its initial state, ready to run.
* Calculate our function in a primitive-recursive way (with $O(f(N))$ complexity), EXCEPT:
    + After each and every every step of this calculation, do the following:
        - Advance the simulation of $M$ by one step.
            * (Doing one step of a machine should be an $O(1)$ operation.)
        - If it turns out that $M$ is in its finished state, then:
            * **break out of all the loops**, stop the calculation, return the result that $M$ has inside it.
* If the calculation has finished while $M$ is still not done, forget about it and return the result we have calculated.

This program is "supposed to" do $O(f(N))$ operations, but if $N$ is large enough, then $M$ will finish first, and the program will return early after just $O(g(N))$ operations. Therefore, the asymptotic complexity of this thing is $O(g(N))$.

**In summary**: if you have a non-primitive-recursive solution for a problem, as well as a worse primitive-recursive solution, then you can rewrite the better solution in a primitive-recursive way. So the "inversion" of complexities is impossible.

(Really, the main purpose of the worse solution is merely to wait an appropriate amount of steps for the machine to complete. If we had a perfect predictor of how long the machine would take, then we wouldn't need the worse solution at all. But here, I'm using it as a backup, in case my estimation of the running time was too low.)
> 2 votes

---
Tags: complexity-theory, time-complexity, turing-machines, recursion, primitive-recursion
---