title: How to turn a 3D polytope into a mesh?

text:
# Question
Title: How to turn a 3D polytope into a mesh?
Let us say you have a polyotpe define as the intersection of halfplanes. That is you are given N half-spaces. The polytope is the volume defined by all points which lie on the positive side of all N half-spaces.

I want to make a mesh of the surface of the polytope. I.e. find the positions of the vertices plus their connectivity.

A possible way to go about it is to do dual contouring on the SDF generated by this polytope, but that generates a mesh with a lot of superfluous vertices and edges with are not necessarily the same as the vertices of the polytope.

# Answer
**Hints:**

If efficiency is not your first concern, you can implement a simple solution.

Assume you have solved the problem for the first $k$ halfplanes and obtained a polyhedric representation, made of vertices, edges and faces. The next step is to cut that polyhedron with the next plane.

By means of the implicit equation of the plane, determine on which side lie every vertex and discard the ones on the wrong side. For all edges, discard those joining two vertices on the wrong side. Keep those with the vertices on the good side, and for the mixed ones, intersect with the plane and trim. Finally, some of the faces will be left untouched, some discarded, some trimmed, and a new one, joining all the edge intersections will be created.

Note that at any stage the poyhedron is convex, as are its faces. This eases the topological operations. It can be convenient to use a change of basis such that the cutting plane becomes $OXY$, making the intersection computations and reconstruction of the section an easier 2D problem.
> 3 votes

---
Tags: graphs, computational-geometry, topology
---


# Question
Title: Difference Between Small and Big-step Operational Semantics
What's the fundamental difference(s) between small and big-step operational semantics?

I'm having a hard time grasping what it is and the motivation for having the two.

# Answer
Small-step semantics defines a method to evaluate expressions one computation step at a time. Formally speaking, a small-step semantics for an expression language $E$ is a relation $\rightarrow : E \times E$ called the *reduction* relation. Small-step semantics describes what happens to an expression in detail. It's able to give a precise account of even non-terminating programs, with an infinite chain $e\_0 \to e\_1 \to e\_2 \to \dots$. A terminating program is one such that $e\_0 \to e\_1 \to \dots \to v$ terminates with a *value* $v$ such that $\forall e' \in E, v \not\rightarrow e'$. $\newcommand{\llbracket}{\[\\!\[} \newcommand{\rrbracket}{\]\\!\]}$

At the other end of the spectrum is denotational semantics. Denotational semantics assigns a “meaning” to each expression. It is a function from expressions to denotations: $\llbracket \cdot \rrbracket : E \to D$ ($D$ is called the domain). The space of denotations can be completely unrelated to the syntactic space, for example $E$ could be expressions that evaluated to a number and $D$ could be a set of numbers like $\mathbb{N}$ or $\mathbb{R}$.

Big-step semantics are kind of in the middle. A big-step semantics on an expression language $E$ and a set of values $V$ is a relation $\Downarrow : E \times V$. It relates an expression to its value (possibly multiple values if the language is non-deterministic). Often, a special value $\bot$ is used for non-terminating expressions.

So why do we have these three notions? All of these notions can model each other, but the model adds a degree of complexity.

* Given a small-step semantics $\to$, you can define a corresponding big-step semantics that relates each expression to its value (or values, if the reduction is non-deterministic): $e \Downarrow v$ iff there exists a chain $e \to e\_1 \to \dots \to v$ and $v$ cannot reduce any further. Note that in general you cannot reconstruct the small-step semantics from the big-step semantics. For example, all non-terminating expressions are indistinguishable under the big-step semantics.
* Given a big-step semantics $\Downarrow : E \times V$, you can say that it's a small-step semantics on $E \cup V$. This is not particularly useful.
* Given a small-step semantics $\to$, you can define a corresponding denotational semantics where the denotation of an expression is the set of reduction chains starting from it. This satisfies the formal definition, but it isn't particularly useful, because it adds a set theoretic overhead to objects which are easier to reason about by looking directly at the syntax.
* Given a denotational semantics $\llbracket \cdot \rrbracket$, you can define a small-step semantics by adding all possible denotations as values in the language. That requires creating values that are not part of the syntax that the programmer can write, which means that some interesting results have to state “for all programs that the programmer can write” rather than “for all programs”. This one is thus not very useful either.
* Given a big-step semantics $\Downarrow$, you can define a corresponding denotational semantics where the domain is the set of sets of values: $\llbracket e \rrbracket = \\{v \mid e \Downarrow v\\}$. If the big-step semantics is deterministic (each expression reduces to a single value), you can define a simpler denotational semantics where the domain is the set of values.
* Conversely, given a denotational semantics $\llbracket \cdot \rrbracket$, you can define a big-step semantics $E \Downarrow \llbracket \cdot \rrbracket$. Again this one is a little pointless.

Operationally speaking, small-step semantics corresponds to looking at each operation performed by an interpreter for the language. Big-step semantics only looks at the resulting value. Denotational semantics looks at a mathematical interpretation which may or may not have anything to do with what happens on a computer.

Small-step semantics is the most obvious one. It clearly provides useful information about non-terminating programs. More generally, it provides detailed information about the behavior of the program.

Denotational semantics transforms syntactic constructs into arbitrary mathematical objects; it can express whatever the scientists wants (you can define the denotation of an expression to be all possible reduction chains from it), but at the cost of adding a level of complexity. It's used when we do want to abstract away some details such as exactly how the expression is evaluated.

Big-step semantics is in the middle: it abstracts away the details of the evaluation but retains the syntactic nature of the result. Usually the concept is used when there is an underlying small-step semantics, as a way to express concisely “$\exists (e\_1, \dots, e\_n), e \to e\_1 \to \dots e\_n \text{ and } \not\exists e', e\_n \to e'$” as “$e \Downarrow e\_n$”. In such constructions, while the concepts are very different (one allows us to talk about individual computation steps and about non-terminating programs, the other doesn't), the definitions will look very similar, because in this case the rules that define the big-step semantics are basically of the form “if $e\_1 \to^\* e\_2$ and … and $e\_n \to^\* v$ and $v$ is a value then $e\_1 \Downarrow v$”.
> 49 votes

# Answer
I felt similar qualms about the difference between small-step and big-step semantics. I think I personally lacked a concrete example, so I will produce one here. I will use Haskell to encode both big-step and small-step semantics in the form of an evaluator.

Consider the simplest possible expression language with just one syntactic construct - `If-then-else`. Let's define the language.

```
data Expr = If Expr Expr Expr | E Val deriving Show

type Val = Bool

```

There is only one possible terminal value in this expression language, which is a `Bool`.

Now, the simplest to write is big-step operational semantics. Let us call the evaluator `evalB` (the `B` indicating the big-step)

```
evalB :: Expr -> Val
evalB (E val) = val
evalB (If e1 e2 e3) =
  case (evalB e1) of
    True  -> evalB e2
    False -> evalB e3

```

Nothing fancy at all. In fact, big-step semantics are the closest possible analogues to interpreters. Note the type `Expr -> Val`

Now, for the small-step semantics, we call our evaluator `evalS`.

```
evalS :: Expr -> Expr
evalS (E val)             = E val
evalS (If (E True) e2 _ ) = evalS e2
evalS (If (E False) _ e3) = evalS e3
evalS (If e1 e2 e3)       = evalS (If (evalS e1) e2 e3)

```

The above is the small-step semantics. This might seem somewhat *unnatural* compared to the big-step semantics. My usage of the term unnatural is intentional (Gilles Kahn calls big-step operational semantics as **natural** semantics, following that small-step might seem unnatural).

The notable difference is the type signature for small-step `Expr -> Expr` as opposed to `Expr -> Val` in big-step. As observable, we do not directly reduce the conditional check in the small-step semantics. We evaluate it to another expression, which will recursively continue evaluating it till it reaches a normal form where there are no further evaluation rules (`E False` or `E True`). In the process, the interpreter would capture every "small" step of the evaluation. Also, notably the terminal value `E val` is not reduced further but kept as an expression itself as there are no steps left to reduce (this form is also known as weak-head normal form).

As for the motivation for having these two styles, this example should illustrate the small step is better at capturing each constituent "small" evaluation step of an evaluator. As such this becomes useful for providing meaning to syntactic constructs where intermediate states (or "steps" if you will) are important, such as concurrency operators where the interleaving of states can result in different terminal values. You can try to run the evaluators to check the resultant value from the respective evaluators.

```
expr = (If (If (E True)  (E True)  (E True))
           (If (E True)  (E False) (E True))
           (If (E False) (E False) (E True)))

foo = evalB expr

bar = evalS expr

baz = evalB (evalS expr)

```
> 1 votes

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


# Question
Title: Translation between unit/bind and map/join in monads
Is there a translation between unit/bind and fmap/join in monads?

https://stackoverflow.com/questions/34398239/with-monads-can-join-be-defined-in-terms-of-bind

gives a partial one:

> bind f m = join (fmap f m)

and

> join x = bind x id

but can we express fmap in terms of unit and bind

and unit in terms of fmap and join?

# Answer
You can express `fmap` in terms of `unit` and `bind`:

```
fmap f xs = bind xs (\x -> unit (f x))

```

You cannot express `unit` in terms of `fmap` and `join`. Intuitively, both `fmap` and `join` "take" a monad as one of their arguments, which means that neither of those functions, even in combination, give you a way to manufacture a monad from a non-monad.
> 3 votes

# Answer
Pseudonym's answer is correct, but it might be useful to some people to look at this from a categorical point of view so that we can give a proof using the monad rules.

The Haskell function bind, or `>>=`, has signature `m a -> (a -> m b) -> m b`, and the related Kleisli composition `>=>` is `(a -> m b) -> (b -> m c) -> (a -> m c)`, where `m` is a monad. The relationships between these are that `(f >=> g) x = (f x) >>= g)` and `(p >>= f) = (id >=> f) p`.

The usual category-theoretical definition of monad is that it is an endofunctor equipped with natural transformations $\mu : T^2 \to T$ and $\eta : I \to T$ (the unit, or `return` in Haskell), satisfying associativity and unit conditions. The Kleisli composite of $f : a \to T b$ and $g : b \to T c$ is $$g \circ \_K f := \mu\_c \circ T(g) \circ f,$$ a morphism $a \to T c$. In this language it is more natural to swap the arguments of bind around so that it has signature `(a -> m b) -> (m a -> m b)`, and on doing so given $f : a \to T b$ we would have $$\operatorname{bind}(f) := f \circ\_K \operatorname{id}\_{T a} = \mu\_b \circ T(f)$$ and $$g \circ \_K f = \operatorname{bind}(g) \circ f.$$

We then have, for $h : a \to b$, that $$\operatorname{bind}(\eta\_b \circ h) = \mu\_b \circ T(\eta\_b h) = \mu\_b \circ T(\eta\_b) \circ T h$$ which is equal to $T h$ because $\mu\_b \circ T(\eta\_b) = \operatorname{id} \_b$ by one of the unit laws for the monad $T$. This shows that the action of $T$ on morphisms, `fmap` in Haskell language, can be expressed using bind.

As an example, consider the list monad `[]` on the category Hask of Haskell types and programs. If $f : a \to b$ then $\eta\_b \circ f : a \to \[b\]$ is $x \mapsto \[f(x)\]$. The multiplication $\mu$ for `[]` is concatenation of lists, so \begin{align\*}\operatorname{bind}(\eta\_b \circ f) (\[x\_1, x\_2, \ldots\]) &= \mu\_b \circ \[\eta\_b \circ f\] (\[x\_1, x\_2, \ldots\])\\ & = \operatorname{concat}(\[\[f(x\_1)\], \[f(x\_2)\], \ldots\])\\ & = \[f(x\_1), f(x\_2), \ldots\]\end{align\*} which is exactly $\[f\](\[x\_1, x\_2, \ldots\])$.
> 3 votes

---
Tags: functional-programming, monad
---


# Question
Title: Prove $\{a^kb^l: 1\leq k\leq l\}$ is not regular using Myhill-Nerode theorem
I have searched quite a few posts here so that I can prove that the language $$L=\\{a^kb^l: 1\leq k\leq l\\}$$ is not regular (using Myhill-Nerode's theorem). I know that I must find an infinite number of pairs $(c,d)$ such that if $R$ is the equivalence relation defined by Myhill-Nerode's theorem, there is a string $z \in \\{a,b\\}^\*$ s.t. if $cRd \Rightarrow \neg (cz R dz)$

I tried $c=a^{n+3}b^n$ and $d=a^{n+1}b^n$, using $z=b^2$.

What troubles me is: I can't assume that $c R d$ since it might not be holding like in this answer. However if I chose $c, d\in L$ I can't find a string $z$. What could I do?

And if I find $c,d$ how do I get that I have infinite number of classes? Can't all $c$ belong at the same class for example?

# Answer
> 1 votes
The idea is to find infinitely many strings that are distinguishable from each other with respect to the Myhill-Nerode equivalence relation defined by $L$.

Consider the strings $a, a^2, a^3, \cdots$. Let us check they are distinguishable from each other.

Let $a^{k\_1}$ and $a^{k\_2}$ be two of them. WLOG, assume $k\_1\<k\_2$.
Then $a^{k\_1}b^{k\_1}\in L$ but $a^{k\_2}b^{k\_1}\notin L$.
That is, $a^{k\_1}$ and $a^{k\_2}$ can be distinguished by appending $b^{k\_1}$ to them. That is, these two strings are distinguishable. That is, these two strings are in different Myhill-Nerode equivalence classes.

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


title: What is a type definition?

text:
# Question
Title: What is a type definition?
When reading about data types, "type definition" is often used without any prior explanation to what it means.

For example, in https://en.wikipedia.org/wiki/Type\_system, we have the sentence "... since C++ has stronger rules regarding **type definitions** ..."

Any help in clarifying what the difference between, for example, *type* and *type definition* is greatly appreciated!

# Answer
"Defining" a type is the act of building a new type composed of one or more pre-existing data types. For example, the "Complex Number" type is often declared as an ordered pair of "Real Numbers" :

```
Type Complex
  Real a
  Real b
End

```

a and b being the real and imaginary parts.

This sample of pseudo-code is a "Type Definition".
> 3 votes

# Answer
From "The C++ Programming Language" -by Bjarne Stroustrup the creator of C++.

> A type defines a set of possible values and a set of operations (for an object).

Also the following definitions are interrelated with type taken from the same book

> A declaration is a statement that introduces a name into the program.It specifies a type for the named entity
>
> An object is some memory that holds a value of some type.
>
> A value is a set of bits interpreted according to a type.
>
> A variable is a named object
> 3 votes

# Answer
# Type Systems

The page you link to is about type systems. The differences most people should be aware of when starting out is static vs dynamic typing and strong vs weak typing (though feel free to explore and ask about more).

Type systems are logical rules built into compilers and interpreters for assigning types (indicative of the kind of data something holds) to each term (variables, expressions, functions, modules) in a program, i.e. identify something as 'a list of ints' or 'an array of bools' or 'an array of arrays of chars'.

# Strong vs Weak Typing

Strong vs weak typing are relatively easy to understand, though these are sometimes used a bit loosely. I think these terms are best used to describe individual features than languages as a whole, though you can certainly argue, for instance, that some languages are more strongly typed than others.

Strong typing features include stricter type-checking at compile time or run time, checking the types at assignments, returns, function calls and so on to look for possible violations, and minimal implicit type conversions (except possibly those that lose no data, e.g. an int to a float). Weak typing features include the opposite. The extreme example is assembly, which is technically typeless - the concept of types simply doesn't exist. Another example is liberal type conversions, including those that may lose some information. A rather interesting example is pointer arithmetic in a language like C, which makes it easy to get around the type system. C++, for instance, requires each declaration to explicitly carry a type, so you can only have something like `int x` or `double y` or `bool* f`. In the line you quote, the page explicitly compares templatised code (roughly, generic code that can be reused with different types). In C++, that requires explicit type specification when a templatised function is called to guide the compiler.

```
// templatised code
template <typename T>
T add(T a, T b) {
  return a + b;
}

// assuming everything is declared, call as
sumD = add<double>(3.1415, 1.4489);
/*
// The compiler generates and adds
double add(double a, double b) {
  return a + b;
}
*/

sumI = add<int>(7, 2);
/*
// The compiler generates and adds
int add(int a, int b) {
  return a + b;
}
*/

```

Python, by comparison, uses 'duck typing' - 'if it walks like a duck and quacks like a duck, it must be a duck'. In Python terms, an object may be used in any context that it supports. This makes template code much easier to write, since you don't have to specify the type you're passing at every call.

# Static vs Dynamic Type Checking

Type checking can be done either statically (at compile time) and dynamically (at run time). Static and dynamic type checking is one example of static and dynamic analysis, the former using the source code, and the latter using the state at runtime. Unlike strong and weak typing, these two are not 'somewhat subjective'.

There are tradeoffs to which a language implements. Static type checking, for instance, allows the compiler to make extra optimisations and allows predicting some errors based on the source code alone, though at the cost of more boilerplate and sometimes complex error messages. Dynamic typing allows more polymorphism, at the cost of possibly more runtime errors and therefore more testing and maintenance, besides prohibiting some optimisations that static typing would allow.

Most languages that use static type checking combine it with some form of dynamic type checking as well to catch runtime errors or cover features such as downcasting (casting a base class pointer to one of its derived classes), which are impossible to statically type check.
> 0 votes

# Answer
A type definition is the creation of a new type, that gets a name. Can be a `typedef`, a `class`/`struct`/`union`/`enum` definition...

Simple example:

```
typedef int MyInt;

```

creates the type `MyInt`.
> 0 votes

# Answer
Variables can contain different sorts of values, e.g., integers, reals, characters... This is called the TYPE of the variable. Some languages are dynamically typed. That means that the interpreter or the compiler decides the type of the variable for you. In static typed languages, you have to define the type yourself when declaring the variable. This is the TYPE DEFINITION.

In a strong typed static languages the rules forbid to mix different types. if you want to add, e.g., a real and an integer you have to explicitly cast the integer to real.

in a weak typed language you can mix types. but since the low level bitpatterns differs between types, you can have unwanted results.

Most languages are somewhere in between. It will be clear that unwanted effects are not acceptable, while the need for an explicit cast makes the code heavy. So most compilers will do an implicit cast for some standard operations. Adding a real and an integer will in that case implicitly provoke a cast to real.
> -1 votes

---
Tags: terminology, programming-languages, typing
---


# Question
Title: Algorithm for length of longest common subsequence
The case of multiple strings. A slight modification of the dynamic programming algorithm for two strings is used as a subroutine. Here is the pseudo code:

```
# The modified dynamic programming algorithm for longest common subsequence.
# Inputs: x, y - the strings
          xL, yL - their respective length vectors
lcs(x, xL, y, yL)
    u = |x|
    v = |y|
    T = 2-dimensional table with default value 0 for all elements.
    for i in 0..u-1
        for j in 0..v-1
            if x[i] == y[j]
                T[i, j] = T[i - 1, j - 1] + 1
            else
                T[i, j] = max(T[i - 1, j], T[i, j - 1])
            # limit the value of the table element by the length vectors:
            T[i, j] = min(T[i, j], xL[i], yL[j])
    # Take the element wise minimum of the vectors for each of the strings and the bottom row and right-most column respectively.
    return x, element-wise-minimum-of(xL, T[_, v - 1]), y, element-wise-minimum-of(yL, T[u - 1, _])

# Algorithm to compute the length of the longest common subsequence of multiple strings.
# Inputs: strings - a list of strings
mlcs(strings):
    if for any string x: |x| == 0
        return 0
    R = a dictionary indexed by a string x, where the value is initialized to be the length vector of x (initially [1,2,..,|x|]).
    N = initially a copy of R.
    while true
        for i in 0..|strings|
            for j in i + 1..|strings|
                x, y = strings[i], strings[j]
                _, xL, _, yL = lcs(x, R[x], y, R[y])
                R[x], R[y] = xL, yL
        if for every string x: N[x] is element wise equal to R[x]
            break
        else
            N[x] = R[x]
    return the last element of any of the vectors in R

```

What follows is an implementation in the python language.

```
import collections

def lcs(x, xL, y, yL):
    u = len(x)
    v = len(y)
    T = collections.defaultdict(int)
    for i in range(u):
        for j in range(v):
            if x[i] == y[j]:
                T[i, j] = T[i - 1, j - 1] + 1
            else:
                T[i, j] = max(T[i - 1, j], T[i, j - 1])
            T[i, j] = min(T[i, j], xL[i], yL[j])
    return (x, [min(xL[i], T[i, v - 1]) for i in range(u)]), (y, [min(yL[j], T[u - 1, j]) for j in range(v)])

def mlcs(strings):
    if any(len(x) == 0 for x in strings):
        return 0
    R = {x: list(range(1, len(x) + 1)) for x in strings}
    N = {x: R[x] for x in strings}
    while True:
        for i in range(len(strings)):
            for j in range(i + 1, len(strings)):
                x, y = strings[i], strings[j]
                (_, xL), (_, yL) = lcs(x, R[x], y, R[y])
                R[x] = xL
                R[y] = yL
        if all(all(N[x][i] == R[x][i] for i in range(len(x))) for x in strings):
            break
        else:
            for x in strings:
                N[x] = R[x][:]
    return R[strings[-1]][-1]

```

The idea is to initialize for each input string a vector which holds information for each position of that string about what is the maximum length of a LCS up to that position. These are updated each time a pair-wise LCS computation is done. This in turn is done for all pairs until all the vectors are stable (ie. don't change) between iterations.

So far testing gives me mixed results. The correct length at first seems to be produced pretty reliably, but when trying to use the function mlcs as an oracle in an algorithm for retrieving an actual longest sequence, sometimes the result is not what is expected. This may or may not indicate that there are cases for which an incorrect length is produced.

So on to the question: Is the idea of the length computing algorithm sound?

# Answer
> 3 votes
The algorithm is incorrect. That is it may return a length that is greater than the actual length of a longest common subsequence. Here is a test case which fails to produce the correct length: \['baaa', 'aaba', 'baba'\].

# Answer
> 2 votes
I didn't try to read your pseudocode, but based on your description, if I understand your idea correctly, it has a (probably fatal) problem: **Even if all pairs $(i, j)$ of strings have a common subsequence with length $\ge k$, it may be that the LCS of the set of all strings has length $\< k$**.

Here's an example:

```
AB
BC
CA

```

Every pair of strings has an LCS of length 1, but no character appears in all 3 strings, so the LCS of the *set* of all 3 strings is 0.

# Answer
> 0 votes
The problem you're solving is called the MLCS (multiple longest common subsequence).

A standard sequential algorithm for three strings `A`, `B`, `C` of lengths `a`, `b`, `c` would look something like:

```
R <- a × b × c array
-- initialise the base cases
for i <- 1...a:
  R[i, 0, 0] <- 0
for i <- 1...b:
  R[0, i, 0] <- 0
for i <- 1...c:
  R[0, 0, i] <- 0

-- the actual bottom-up 3-LCS
for i <- 1...a:
  for j <- 1...b:
    for k <- 1...c:
      if A[i - 1] = B[j - 1] and B[j - 1] = C[k - 1]: -- match
        R[i, j, k] = R[i - 1, j - 1, k - 1] + 1
      else -- no match => get the max of the three predecessors
        R[i, j, k] = max(R[i - 1, j, k], R[i, j - 1, k], R[i, j, k - 1])

-- the length of the longest 3LCS is stored in R[a, b, c] at the end

```

As a bonus for reading through this pseudocode, here's a handy teaser for where you can take this idea going forward: There is an opportunity to parallelise this algorithm by wavefronts (each wavefront defined by `i + j + k`), processing the wavefronts successively, but the elements of each wavefront in parallel.

---
Tags: algorithms, optimization, strings, correctness-proof
---


title: Data Structure for strings on integers

text:
# Question
Title: Data Structure for strings on integers
Designing a datastructure which supports the following operations on integers (It can also be visualized as a datastructure on strings, if the alphabets/characters have total ordering)

Operations on the integer string.

1. Insert an element with value $v$ at index i.
2. Delete an element from index $i$
3. Increment value at index $i$ from $v$ to $v+1$.
4. Given an index $i$ and value $t$, find the index $j$ (if it exists) such that

a. $j\>i$

b. value at index $j$ is $t$

c. values of indices between $i$ and $j$ is not equal to $t$.

I understand that the operation #3, can be supported by operation #1 and #2, but I just mentioned it, to see if there is a slightly better way to do it.

I know a way to do this in $O(\lg n)$ time. I am looking for alternative solutions, which can be done in O(1) worst case or amortized time. I do not want to explain my answer, as it might hinder your natural thinking process(hint Young's tableau). I am stuck and unable to think of an alternative better solution because I know the answer which works in $O(\log n)$.

Example suppose the string is

1 1 2 3 2 1 1 1 4.

If I want to insert 1 at index 4, right after the value 2, then the updated string would look like this.

1 1 2 **1** 3 2 **2** 1 1 4.

The 2 in bold was previously a 1, but it underwent operation #3 after insertion of value 1 at index 4.

# Answer
There should be solution based on a weight balanced binary tree such that every node keeps its weight (number of descendants). For an insertion or deletion, you will find the $i^{\text{th}}$ node using the weight information. Then perform standard insertion or deletion.

The increment operation is trivial.

The search operation can be implemented as a modified search, where you disregard the first $i$ nodes.
> 0 votes

---
Tags: data-structures, strings
---


# Question
Title: How can you represent 4096 days with 12 bits?
With 12 bits, apparently you can represent $2^{12}$ different days or 11 years. But how?

If you have 6 characters YYMMDD and each character represents 8 bits, how can this represent $2^{48}$ days?

# Answer
$2^{12}$ days is indeed $11$ years, $2$ months and a few days (depending on the starting date). Convert from day number to YYMMDD date.

---

If I am right, there are $36524$ legal dates in the format YYMMDD in a complete century ($36525$ every fourth centuries).

The information content is about $15.16$ bits, which is $2.53$ bits per character. This comfortably fits in a `short uint`.

---

Using $48$ bits, you can encode dates for a little more than $7706417613$ centuries.
> 0 votes

---
Tags: storage
---


# Question
Title: Is there a theoretical foundation behind CSS?
You know how programming languages can be based on Lambda Calculus or the Turing Machine and SQL is based on relational algebra. Is there any such thing for CSS or any foundation that could be used for styling languages in general if we were to design a new language from scratch?

Styling and layout in general is something I'd expect to be possible to formalize mathematically, at least the layout and positioning part of it.

# Answer
I don't think there is a deeper foundation, as CSS is just a lookup table of key value pairs declared under certain rules. It then gets interpreted by the browsers' graphical renderer. From a linguistics perspective, I'd see CSS syntax as the following: `Map<Rule, Map<String, Value>>`, where `Rule` is its own querying or pattern matching statement.

I agree on that CSS seems like a mess sometimes. Especially when you have to re-use some of the rules, key-value pairs multiple times. For those cases, I recommend transpilers like Sass. It allows you to declare rules in a less verbose way, and allows you to encapsulate certain key-value pairs to be able to reuse later.
> 5 votes

# Answer
Selectors and combinators from CSS are a form of combinatory logic. This can be reduced to the SKI calculus.

I think it is also possible to see CSS rulesets as a form of lenses from functional programming. E.g. a CSS ruleset is a functor of `DOMElement -> DOMElement` which changes how it looks. An empty ruleset would be isomorphic to the `id` function. You could think of `calc` properties as lambda functions, too, I suppose.

Note, I don't know that CSS was intentionally designed with these theoretical foundations. Just that one could use these abstract ideas to understand how/why CSS works in the way that it does.
> 5 votes

# Answer
First, let's separate `styles` (which existed **before** css) and `css`.

Styles are just how things should look and I'm not going to delve deeper into it.

CSS on the other hand is a system of applying styles according to rules.

The core concept that CSS introduced is Aspect Oriented Programming (AOP). AOP is used whenever you have a feature that is a cross-cutting concern. That is, when something needs to be used by multiple things not related by type or flow control.

Things that need the same feature/operation within the same flow control can be handled by functions in functional languages or design patterns like command pattern or visitor pattern. This is because there is usually a single logical point in the program that handles the feature.

Things that need the same feature within a set of related types can be handled by inheritance. You can create an abstract parent class that have the feature and inherit from it.

However AOP covers the case when you need to apply a feature to a bunch of different things at different points in the program.

CSS achieves this by the introduction of classes. With classes you can define a set of features (eg. font size, color & padding) and then apply them to various parts of your document.

This is similar to how AOP is achieved in programming languages: either via mixins or decorators.

This is one of the two foundational cores of CSS: the **style sheet** (the "SS" in CSS).

The other part of CSS is style inheritance. There are two aspects of this:

* How styles are inherited by child nodes
* Which style to render when multiple styles are defined

Typically, non-layout styles such as color and font are inherited by child nodes and layout styles such as position and padding are not inherited. So for example a container div with red text and 10px padding will cause all its children to have red text but not the 10px padding.

Once inherited the style can be overridden by applying it to the specific child node by either assigning a class to the node or an id.

A single node may also find itself to be the target of many style definitions. For example a link may find itself to have multiple color defined. Which style is picked is based on a point based priority system.

Styles defined later in the program flow have higher priority (more points). However styles defined with higher level of specificity have even higher priority (eg. a style defined with `div div.container div.content span.announcement` is given more points than one defined with `span.announcement`). Similarly styles defined with id has higher priority than styles defined with class.

Together these make the other part of CSS: the **cascading** rules (the "C" in CSS).
> 0 votes

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


# Question
Title: Design a 1-bit ALU using the smallest MUX possible
Implement a one-bit ALU which takes two one-bit operands $a\_0$, $b\_0$, and produces a one-bit output $z\_0$. The ALU has a two-bit control input $cont\_0$, $cont\_1$, with codes as shown below.

|$cont\_0$|$cont\_1$ |**selects**
|--- 0 ---|--- 0 ---| AND
|--- 0 ---|--- 1 ---| NOR
|--- 1 ---|--- 0 ---| OR
|--- 1 ---|--- 1 ---| XOR
(Sorry I didn't know how to make a properly formatted table)

The questions is:
Design the ALU using the smallest MUX possible.

---

I made a truth table as a start, then I came up with an ALU model, but I am not too confident with it. Any input on how to tackle this problem is appreciated.

Here's the truth table I made:

And here's the ALU that I'm doubtful about because it seems too easy of an approach.

# Answer
> 1 votes
If you consider the table as a 4 input combinational circuit and try to derive an expression from the K-map you will get $$Z\_0 = cont\_0'cont\_1a\_0'b\_0'+cont\_0a\_0b\_0'+cont\_0 a\_0'b\_0+cont\_1'a\_0b\_0$$

Now you can see the pattern with $a\_0$ and $b\_0$ so you can make a smaller circuit with a 4x1 MUX having $a\_0$ and $b\_0$ as selection bit.

# Answer
> 0 votes
I am not entirely sure of all of the constraints on this question, but it seems to me that using explicit AND, OR, NOR, and XOR gates is kinda cheating.

The solution that ONLY uses a mux with no extra gates is a 16 to 1 mux. This would literally be based on the 16 element truth table listed in the question.

If a single inverter is allowed however, an 8 to 1 mux can serve.

```
c0 c1 a0   mux_channel  channel value
0  0  0         0          0
0  0  1         1          b0
0  1  0         2          not b0
0  1  1         3          0
1  0  0         4          b0
1  0  1         5          1
1  1  0         6          b0
1  1  1         7          not b0

```

BTW: This is an LU not an ALU as it does not perform any arithmetic operations.

# Answer
> 0 votes
Decode controls to a Karnaugh map, then let A vs B choose.

K00 = XOR(cont\_0,cont\_1)

K01 = cont\_0

K10 = cont\_0

K11 = NOR(cont\_0,cont\_1)

Two input gates less than when controls do the choosing...

No input gates required to decode after the 1st slice.

---
Tags: computer-architecture, logic, cpu
---


# Question
Title: How to calculate average hours worked from bar graph
I want to calculate average hours worked from below bar graph and following this method but I feel this method is not correct to find average working hours

Procedure A:

```
( 4*1+4*2 +6*3+7*4 + 13*5 +8*6 ) /(1+2+3+4+5+6)sum of worked hours
average= 171/21 =  8.14

```

procedure B:

```
average= ( 4+4+6+7+13+8)/6( total  green bar counts)
 average= 42/6= 7

```

Can anyone suggest which one is correct way to find average working hours ??

# Answer
Neither of the above mentioned procedures gives the correct average working hours. Average working hours is the ratio of the total working hours of employees to the number of employees. I don't understand the reason for posting this question in this platform it is in no way related to computer science and you could possibily find the answer by a simple search engine query or post the question in Mathematics Stack Exchange.
> 0 votes

---
Tags: algorithms, data-structures, average-case
---


# Question
Title: Could there theoretically exist a problem $A$ which is in $co$-$NP$, but its complement $A^{C}$ is $EXPTIME$-complete?
I was reading a bit about $NP$-problems and how it is widely assumed that $NP\neq co$-$NP$. This also implies that the complement of $NP$-complete problems are not in $NP$.

What is known is that the complement of a $co$-$NP$-complete problem is $NP$-complete and it could be that either $NP=co$-$NP$ or $NP\neq co$-$NP$.

I wonder though if a complement of a $co$-$NP$-problem (not necessarily $co$-$NP$-complete) $A^{C}$ can be $EXPTIME$-complete? Of course then $P\neq NP$ since if $P=NP$ we would have $NP=co$-$NP=P\neq EXPTIME$-complete.

Additionally (sorry if that counts as a second question), I was wondering if - in that case - any algorithm for a $co$-$NP$-problem $A$ with $A\notin P$ (and $A$ is *not* complete for $co$-$NP$) would theoretically **have to** be superpolynomial in the input size given that $P\neq NP$ or whether it is still possible that

* there is a polynomial time algorithm for $A\in co$-$NP$
* $A^{C}\in EXPTIME$-complete

In that case $A\notin P$ since $P$ is closed under complement (which means that problems in $P$ can be defined as those problems for which their complements are also in $P$, as far as I understand).

# Answer
With regards to the first question: "I wonder though if a complement of a $co$-$NP$ problem (not necessarily $co$-$NP$-complete) $A^C$ can be $EXPTIME$-complete?

The complement of a $co$-$NP$ language is, by definition, a $NP$ language. Hence, you are asking if there can be a $NP$ language which is $EXPTIME$-complete. This is the same as asking whether $NP=EXPTIME$, which is not known.

To see that your question is equivalent to ask $NP=EXPTIME$, notice that, if $NP=EXPTIME$, any $NP$-complete language would be $EXPTIME$-complete. On the other hand, if we had a $NP$ language in $EXPTIME$-complete, we have that all $EXPTIME$ languages could be reduced to it, and hence, $NP=EXPTIME$.

With regards to the second question: In the first part you say "any algorithm for a $co$-$NP$ problem $A$ with $A \not\in P$ would have to be superpolynomial?" If $A \not\in P$, then, by definition, any algorithm to solve $A$ will need to be superpolynomial.

In the second part you say "or is it possible that there is a polynomial time algorithm $A \in $co-$NP$ such that $A^C \in EXPTIME$-complete".

If you have a (deterministic) polynomial algorithm that decides $A$, you have a (deterministic) polynomial algorithm that decides $A^C$ by just negating the answer of the algorithm. In essence, you are asking if you can have an algorithm that decides an $EXPTIME$-complete languge in polynomial time, that is, you are asking if $P = EXPTIME$-complete, which, as you already know, is not true.
> 1 votes

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


# Question
Title: Chistofides' algorithm for the traveling salesman problem with relaxed triangle inequality
It is known that Christofides’ algorithm returns a 3/2-approximation for the traveling salesman problem given a complete graph $G$ such that distances obey the triangle inequality. Suppose that we weaken the triangle inequality to the setting where distances obey the guarantee that for each triple $i, j, l \in V$ it is the case that $d\_{ij} + d\_{jl} \geq d\_{il}/c$ where $c \geq 1$. How do I then express the approximation ratio in terms of $c$? To do this, I think I have to find the cost of the shortcutted tour of $G$ that visits each node in the set of nodes with odd degree $O$. I know that if the distance just obeyed the normal triangle inequality, then this shortcut tour on $O$ would at most be the cost of the whole tour of $G$. But what is the cost when distances only obey the relaxed triangle inequality?

# Answer
> 1 votes
It is possible to get a bound of OPT + 0.5C * OPT assuming that the cost of the MST is less or equal than OPT and that the cost of the perfect matching is at most 0.5C * OPT which can done by constructing a tour in the set of odd degree vertices by shortcutting the general optimal tour.

---
Tags: algorithms, graphs, algorithm-analysis, approximation, traveling-salesman
---


# Question
Title: Relation between Curry-Howard isomorphism and Kripke semantics for intuitionistic logic
Intuitionistic logic(s) are usually defined in a purely synthetic way, with their own deduction rules different from classical logic, but they also have semantic interpretations.

One of them, more known in mathematical logic, is Kripke semantics, originated in modal logic, in which a formula is valid iff it holds in all Kripke frames. Another interpretation, more known in computer science, is the Curry-Howard isomorphism, in which a proposition is interpretated as type in a suitable system and a proposition is valid iff there is a program of that type.

My question is: Is there any relation between these two interpretations? They are certainly equivalent, but merely concluding that from the two previous equivalences don't give any insight into a probably much deeper connection.

EDIT: Should I have posted this question in the Theoretical Computer Science Stack Exchange?

# Answer
Both Kripke semantics and propositions-as-types interpretation are sound and complete for the intuitionistic propositional calculus. In this sense they are equivalent.

However, there are formulas in intuitionistic first-order logic (IHOL) which are valid under propositions-as-types but are not intuitionistically provable. See Remark 6.6. of Propositions as \[Types\], where the following formula is given: $$ (\forall x . \exists y . R(x, y)) \Rightarrow (\forall x, x' . \exists y, y' . R(x,y) \land R(x',y') \land (x = x' \Rightarrow y = y')). $$ This is not provable intuitionistically, but it can be inhabited under propositions-as-types interpretation. Because Kripke semantics is complete for IHOL, the above formula provides a distinction between the two setups.
> 1 votes

---
Tags: logic, type-theory, curry-howard
---


# Question
Title: Is a CPU with a hybrid Instruction Set Architecture (ISA) possible?
Is it possible to (theoretically) develop a CPU having a hybrid ISA such that half of the cores in it use the x86 architecture and the other half uses the ARM architecture? The x86 cores would run the x86 instructions that the CPU receives, while the ARM cores would run the ARM instructions. This would allow the CPU to be natively compatible with softwares for both the ISA's without the need of any emulation, which would eradicate any performance penalty that might arise due to emulation.

# Answer
What you're talking about is known as *asymmetric multiprocessing*, where you have multiple logical cores with different ISAs.

Not only is it possible, you might have one. Many consumer-grade CPUs have GPUs on the same die.

There is one other famous example. The IBM Cell had a main PowerPC core (with two-way simultaneous multithreading, so 2 logical cores) called the PPE, each of these had 8 additional cores with a different ISA attached to them, called "synergistic processing elements", or SPEs for short. The SPEs were designed for extremely high throughput SIMD operations, at the cost of having no branch prediction.

This CPU shipped over 87 million units, and you probably know someone who had one, or may have had one yourself, since it was used in Sony's PlayStation 3 games console.
> 3 votes

---
Tags: cpu, instruction-set
---


# Question
Title: Axiomatically, what characterizes “recursion”?
My question is admittedly simple, but the desire is to have an insightful view on it behind a conventional definition.

In different foundational or axiomatic systems, I have come to consider “compositionality” as possibly the single most general concept to use as a structuring principle, in any system that gives rise to increasingly rich amounts of information. “Composition” is a highly general, even cognitive, idea of, “put two things together, and call it a new thing”.

The way I see it, whatever concepts or rules you start out some minimal system which is meant to define more complex informational structures, there is this fundamental “impasse”, which I think is like the Church-Turing thesis, where it’s actually hard or nigh impossible to derive a rule, which was not already implicitly there as a rule of interpretation, to begin with.

For example, the simplest possible “compositional” / “combinatorial” system is something like, the free infinite commutative(/symmetric) monoid or semi group, I think, in abstract algebra. You have some things, you can put them together to make another thing. That’s it.

Mathematically, you don’t have more rules of interpretation on if any of those elements generated are themselves “interesting” or useful in some way - they’re just “words” (compositions of elements).

I think it’s common to define functions in terms of sets - like a set of tuples, where the first element is the domain, and the second element is the codomain. Thus, a “function” is a set of ordered pairs.

But that requires a human interpreter to understand that way of writing down functional associations.

What if you wanted to have a computer do it instead?

I’m not sure, but it doesn’t sound elegant - maybe you need a program that’s checking every set generated in the cumulative hierarchy (of composition) - of it is a set of ordered 2-sets, then it recognizes that as a function. Perhaps you can also “use” the functions - you can specify a function (perhaps each object has a hash to identify it) and call it on an object in its domain: the program knows to return the corresponding value.

So, you generated / constructed functions from nothing but the composition of elements (basically, power sets, subsets of sets). But you didn’t really - your computer program already had a more robust program to run it, that had an “if” conditional, a match / equality operator, a true/false object, a “for all” quantifier, a concept of set size (cardinality), and even somehow the idea that a function paired with an element in its domain “is associated with the corresponding element in its codomain”. You can’t construct a mathematically rich system unless you already have a system of equivalent mathematical richness. Right?

I think we might be able to build up the idea of a universal Turing machine by considering very simple games or procedures, and adding in some fundamental capability, one at a time.

Imagine dropping colored pebbles in a row, perhaps at random. Ok. Not much to say. Not too much change or order, as time goes on.

Now: if we want to try to enhance how the system behaves by minimally importing rules or concepts from somewhere else (like, “every third stone shall be blue”), the *first* thing I am (only prematurely) confident we need is the ability to **read** our own sequence, and **act** based on a *condition* of that sequence - so, you have a ‘read’ and an ‘if’ command, and a concept of equality, let’s say. (Maybe, any of those three things alone would not be useful, so somehow we can bundle them together into a single thing?)

I think right now we have a ‘context-sensitive grammar’ (Chomsky type-1, I think?). **If we assume infinite colors for the marbles**, we have Chomsky type-0, Turing complete, yes? If we have finite colors, we require **infinite loops** in our instructions? Expressions that say things like “do while”? (I guess that was implied by the idea that we were dropping stones in a line continuously, with no intention of stopping or rules for the game to ‘end’ / halt).

I guess I am trying to see more clearly what might be a cleaner reduction on where “recursion” or infinite loops could come in - as there are different ways of presenting it. Is it a function which can call itself? Is it implied by any formal system with infinite starting elements, like my pebble game?

Someone told me “recursion” can even be expressed as a “fixed point”? “In untyped lambda calculus,” a fixed-point combinatorial such as the Y-combinator “is used to define recursion” ().

Can someone help me understand: how can you minimally specify what recursion really is, from an axiomatic perspective? Is the real point of recursion “infinitude”, in which case, you don’t need the concept if you already assume infinite elements? Is recursion a condition on finite sets for them to be able to imply/construct/determine infinite ones?

But is that just a mirror image, since a function which calls itself, has to actually be called an “infinite” number of times, to actually produce “infinite” elements.. can we say that there is no such “thing” as infinity, from a computability perspective - *only* halting, if something will stop on its own, or else, outer forces will have to stop it (someone has to turn off the machine / stop playing the game)?

If we try to reduce these systems to the fewest possible elements, I am considering choosing “rules” as the only existing objects in the system. A rule calls another rule: Rule 1: If Rule 2, Rule 3. This could be either that if Rule 2 has been acted on, next you just act on Rule 3; or it can be a swapping rule, where you can swap out Rule 2 if it is present.

This similarly I think reduces to the Universal Turing Machine - you can “read” in a way (you know what elements are present) - you can “write” (you can do, likes function, act on something, change in some way) - and you have *conditions* (if-statements). If we abandon a need to identify “recursion” and just focus on “halting” instead, then I think that makes “recursion” clearer. Any collection of rules that does not have some circularity, where one rule can lead back to itself, will not halt, and is “recursive” in the sense of a function calling itself (even if indirectly / via a chain of functions).

What interests me is that you can make all these different systems like anti-foundational set theory and study the resulting behavior of that system. The Church-Turing thesis tells us that the Universal Turing Machine will be the maximum possible, of any such game or collection of rules. Or does it?

Could there be all kinds of games we just haven’t explored yet, based on subtle changes in this or that simple scenario? It feels like a huge avenue for creative tinkering and poking around, navigating to uncharted territories.

But it makes me think that the Turing Machine maybe can be expressed in fewer than four “things”. Maybe that’s what type theory is for - the modern attempt to establish the minimum necessary, in any constructive system?

# Answer
> 2 votes
A lot to unpack here! It's hard to extract a clear question from your post, but I will just comment on a few of your statements:

> the Church-Turing thesis, where it’s actually hard or nigh impossible to derive a rule, which was not already implicitly there as a rule of interpretation, to begin with

> The Church-Turing thesis tells us that the Universal Turing Machine will be the maximum possible

Your interpretation of the Church-Turing thesis is not correct. For example, we know that it's possible to define many models of computation stronger than Turing machines, and plenty of researchers have studied such models. The point of the Church-Turing thesis is to formalize the intuitive notion of "effectively calculable" that was common parlance among mathematicians by the early 1900s; at the time, it basically meant "computable (by a human) by following routine algorithm" but no one had a precise definition. The Church-Turing thesis is, no more and no less, the proposal to identify "effectively calculable" with the formal definitions "computable by a Turing machine" or "computable by a lambda calculus expression". See the Stanford Encyclopedia of Philosophy's article on the topic for a good overview.

> For example, the simplest possible “compositional” / “combinatorial” system is something like, the free infinite commutative(/symmetric) monoid or semi group

> you don’t have more rules of interpretation on if any of those elements generated are themselves “interesting” or useful in some way

Actually, this structure actually already requires recursion to construct. The rule of interpretation here is that we know that *every element* of the free monoid was generated by some *finite* application of concatenation of individual elements. And this is also the core of what recursion is about.

> Axiomatically, what characterizes “recursion”?

In short: the core of recursion is inductive constructions. It's the idea that every element of a set is constructed via some *finite* number of applications of some list of allowed rules.

Mathematicians working on formal languages for proofs have found that this is sufficient -- you might be interested in the Calculus of inductive constructions which is used by the proof assistant Coq; it's been found that this very simple system is enough to formalize most properties of modern mathematics. The core idea of the calculus of inductive constructions is the idea that you can give an inductive definition, like "a string is either an empty string, or a character followed by a string" and interpret all ways of finitely constructing an object from that inductive definition.

---
Tags: recursion
---


title: Greedy algorithms criterion/ intution

text:
# Question
Title: Greedy algorithms criterion/ intution
Can anyone please explain (not just through examples) that why does the greedy approach does not work in this case? Or more generally, is there any particular condition under which only the greedy solution work? The problem link -https://codeforces.com/problemset/problem/1832/B. The problem states that we have an array of elements, and we have to perform k operation. An operation is either- Delete the maximum element, or take two of the minimum possible element and delete them. We want the sum at the end of all operations to be as large as possible. What should be the strategy be? The natural thing which comes to mind, is that do the operation which has the least sum. However, it is easy to give an counterexample to this, but I want to understand the condition due to which the greedy solution is failing.

# Answer
Sometimes it is good to delete the maximum element even when its value is larger than the sum of the two minimum elements. Deleting it allows the algorithm to remove the smaller elements in the next iterations.

For example: If the array is as follows: $4,4,4,4,4,4,5,5,9$ and $k = 3$.

Then, the greedy algorithm deletes $(4,4)$ in each iteration since the maximum element $9$ is always greater than $4+4$. After $3$ iterations, the sum of the array is $19$.

However, if suppose the algorithm does not choose the greedy approach initially. The algorithm chooses to delete $9$ in the first iteration. Then, it gives the algorithm the opportunity to delete $5$ in the next two iterations. This opportunity is not available in the greedy approach. This non-greedy approach gives the solution with total sum $24$ which is greater than $19$ for the greedy approach.
> 1 votes

---
Tags: algorithms, proof-techniques, greedy-algorithms, heuristics
---


# Question
Title: Reducing Graph Reachability to SAT (CNF)
So I came across this problem in my textbook. I was wondering how to develop a reduction from the Graph Reachability problem to SAT (CNF) problem. (i.e. formula is satisfiable iff there exists a path in graph G from start to end node)

1) I can't wrap my head around how to go from something that can be solved in polynomial time (Graph Reachability) to something that is NP (SAT).

2) I can't seem to find a way to formulate these nodes/edges of Graph into actual clauses in CNF that correspond to reachability.

I tried to think about algorithms like Floyd-Warshall that determine if a path exists from start to end node but I can't seem to formulate that idea into actual CNF clauses. Help would be much appreciated!

# Answer
> 1 votes
Since the other two answerers really didn't put thought into this question, I think I should give a genuine encoding for subsequent readers.

We consider a 2D matrix $R(i, j)$ meaning that the vertex $i$ can reach $j$. The matrix is initialized as follows:

1. For every direct edge $i \to j$, we set $R(i, j)$ to true.
2. For every $i, j, k$, we add the constraint $R(i, j) \wedge R(j, k) \Rightarrow R(i, k)$. This encodes the transitivity of reachability.

To ask if vertex $a$ can reach $b$, we add $\neg R(a, b)$ and solve the SAT problem. If the overall problem is UNSAT, it means that $a$ can reach $b$, because it is impossible for $a$ to not reach $b$ (that is the last constraint $\neg R(a, b)$).

# Answer
> 0 votes
Maybe the solution is to use the 2-SAT problem which does have a polynomial solution.

For a 2-SAT problem, you can indeed build an implication graph. Basically a clause $(a \vee b)$ leads to the implications $\neg a \implies b$ and $\neg b \implies a$. The problem is satisfiable if there is no variable $x$ such that $x$ and $\neg x$ are in the same SCC of the implication graph. Being in same SCC is equivalent to double reachability:

* it exists a path from $x$ to $\neg x$
* it exists a path from $\neg x$ to $x$

So for any skew-symmetric (required property) graph, you can build a 2-SAT problem for which it is the implication graph.

# Answer
> 0 votes
> 1) I can't wrap my head around how to go from something that can be solved in polynomial time (Graph Reachability) to something that is NP (SAT).

Note that, if the notion of reduction you use allows any function which can be computed in polynomial time (and not, say, log-space), we can use a trivial reduction function. Write $A$ for the P problem (e.g., graph reachability). Take any formula $q\_1$ in SAT (say, $p$) and any formula $q\_0$ not in SAT (say, $p\land\lnot p$). Then:

$$ f(x) = \begin{cases} q\_1 & \mbox{if } x \in A \\ q\_0 & \mbox{otherwise} \end{cases} $$

This function can be computed in polynomial time: we only have to decide $x\in A$, which we can since $A$ is in $P$, and then return one constant formula between $q\_1$ and $q\_0$.

The point is: we don't have to actually encode the problem in SAT, since we can solve the problem in the reduction function. (This may feel like "cheating", at first.)

Another general method for such a reduction is given by the proof of the NP-completeness of SAT, which generates a large circuit (or formula) from any instance of any NP problem (including those in P). (This is usually way more complex than needed, though.)

---
Tags: algorithms, graphs, reductions, satisfiability
---


title: How is P not trivially equal to ZPP?

text:
# Question
Title: How is P not trivially equal to ZPP?
The definition of ZPP seems to be

$$ZPP = RP \cap coRP.$$

I think ZPP should then be equivalent to P, because for any language L in ZPP, there is an algorithm A and B proving that it is in RP and coRP, respectively. Since A must tell for any x s.t. $x \notin L$ the truth and B for any x s.t. $x \notin L$ as well, we can just run both algorithms in polynomial time, and one of them has to give me the answer since these are the only two possible options.

Is there an error in my thoughts?

# Answer
> 5 votes
There is an error in your reasoning. Say that $x \not\in L$. Then when you run $A(x)$ you'll get a "no" answer with certainty. However, when you run $B(x)$ you'll get a "no" with some probability that can be up to $1/2$.

What do you do when both $A(x)$ and $B(x)$ return "no"? In order to answer correctly you'd need to return "no".

Consider now $x \in L$. $A(x)$ will return "no" with some probability that can be up to $1/2$, while $B(x)$ will return "no" with certainty. We already argued that you algorithm returns "no" in this case, but this is incorrect.

---
Tags: time-complexity, complexity-classes, randomized-algorithms
---


# Question
Title: Can you enumerate the set of all words over a finite alphabet?
Can you enumerate the set of all words over a finite alphabet?

# Answer
I think that the original poster wanted to point out that lexicographic order does not work for the purpose of enumerating all words.

1 11 111 1111 ...

and you never reach 2 (and you miss 0).

Of course, as pointed out by user253751, numeric order works. For example, the set of all numbers can be enumerated over the alphabet 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

That is a psychologic problem: we have difficulty in recognizing that letters and digits are the same kind, though literature and mathematics may not be.
> 2 votes

# Answer
**Hint:**

The set of words of length $l$ is made of all strings of length $l-1$ appended with one of the letters.

Check that

* they are all different,
* none is missing.
> 1 votes

# Answer
Of course. One way is to enumerate all the words of length 0 (if you consider them words), then all the words of length 1, then all the words of length 2, and so on.

Obviously, the set is infinite, so the enumeration never ends, but every word is enumerated at a finite step in the process.
> 1 votes

---
Tags: complexity-theory, regular-languages
---


# Question
Title: Are there pairs of connected graphs that always fail the k-wl test for any k?
Is there a pair of connected graphs for which the k-wl test always fails (= judges isomorphic when not isomorphic) for any k? If so, please give an example.

How about the following image? Are they non-isomorphic? I'm not sure...

---

now i got they are non-isomorphic. so then, does this correspond to the pair the question asks for?

# Answer
> 0 votes
Pick any two non-isomorphic $n$-vertex $r$-regular graphs.

Edit to address follow-up question. Yes, the two graphs in your figure are $k$-wl for all $k$, and yes, they are non-isomorphic.

One of the graphs has an induced $C\_4$ and the other does not.

---
Tags: graphs
---


# Question
Title: Prove or disprove that two regular languages are equivalent
I have $L\_1=\\{b^\*+b^\*a(b+ab^\*a)^\*ab^\*\\}$ and $L\_2=\\{(b^\*ab^\*a)^\*b^\*\\}$. I want to prove or disprove that they are equivalent.

I have proved that $L\_2\subseteq L\_1$ and I tried to transform the second expression in $L\_1$ in order to find an expression contained in $L\_2$ (without any luck so far). I tried also to find a word in $L\_1$ that doesn't belong to $L\_2$, but didn't have any luck either (all where in it).

Could anyone help?

# Answer
> 5 votes
It's hard to give hints without solving the problem for you. Some general hints:

* When working with regular expressions, the $^+$ sign ("one or more") is a useful shorthand:

$X^+ = XX^\* = X^\*X$

$X^\* = \epsilon \cup X^+$

For instance, in this case, we can write:

$L\_1 = L(b^\*+b^\*a(b+ab^\*a)^\*ab^\*) = L(b^\*) \cup L\_3$ $L\_2 = L((\epsilon+(b^\*ab^\*a)^+)b^\*) = L(b^\*+(b^\*ab^\*a)^+b^\*) = L(b^\*) \cup L\_4$, with $L\_3 = L(b^\*a(b+ab^\*a)^\*ab^\*)$ and $L\_4 = L(b^\*ab^\*a)^+b^\*)$,

and since all members of $L\_3$ and $L\_4$ contain an $a$, $L\_1 = L\_2$ only if $L\_3 = L\_4$.
* Expand the expressions into disjunctive form, $X\_1 + X\_2 + \ldots$, such that the subexpressions are, either:

+ the shortest strings in the language, or
    + expressions that only generate longer strings.

Your hope is to quickly find, either:

+ a string that is in one and not the other, or
    + some kind of recurrence relation proving that they are $=$ or $\subseteq$.
* No finite set of rewrite rules suffices to rewrite all equivalent regular expressions into each other. So you may fail to find a successful rewriting even when the expressions describe the same language.
* When rewriting or finding a proof by induction, consider using not only regular expressions, but also set-theoretic descriptions of languages ("the language such that ...") and properties defined in such terms.

For instance, above I used the property that languages $L\_3$ and $L\_4$ are such that all of their strings contain an $a$.

If all else fails: a completely rigorous method to prove or disprove equivalence of regular expressions is to convert them to NFAs, then to minimal DFAs: two regular expressions are equivalent if and only if the resulting minimal DFAs are isomorphic. However, both conversion steps may cause an exponential blowup in size.

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


# Question
Title: Turing machine that splits a string into 3 equal parts in $O(n\log n)$
I have the following question: given a string $X^n$, where $n$ is divisible by $3$, how to build a **one-tape** Turing machine with complexity $O(n\log n)$ that splits this string into $3$ equal parts?

I manage to build an $O(n^2)$ machine that performs this task. By the way, all my attempts always result in an $O(n^2)$ machine.

# Answer
Inspired by this answer, here is an idea for building a Turing machine, which follows these steps:

The problem requires that the input size ($n$) is a multiple of $3$. So, for example, let's use the input $X^{12}.$

1. Every $3$ $X$, do a mark: $$XXXXXXXXXXXX$$ $$XXAXXAXXAXXA$$ The number of marks will be exactly $\frac{n}{3}.$
2. In the first mark, replace it with $1$ and replace the previous $X$ with $C$ (to delimit the end of the number, as later this will prevent the head from going to the beginning of the tape): $$XC1XXAXXAXXA$$
3. Move this number to the next mark character by character until you find the delimiter $C$. After that, add $1$ to the number **in binary** and delimit it by marking $C$: $$XCXXX1XXAXXA$$ $$XCXC10XXAXXA$$
4. Repeat procedure 3 until the last mark: $$XCXCXXC11XXA$$ $$XCXCXXCXC100$$
5. Remove the $C$ marks (this can also be done during steps 3 and 4) and move the found binary number to the beginning, but in reverse: $$XXXXXXXXX100$$ $$001XXXXXX100$$
6. At the end of the tape, move the binary number one symbol to the left and subtract it by $1$. Repeat this step until the number is $0$: $$001XXXXXX11X$$ $$001XXXXX10XX$$ $$001XXXXX1XXX$$ $$001XXXX0XXXX$$ After reaching $0$, remove it and mark the previous position. $$001XXXXXTXXX$$
7. Repeat step 6, but at the beginning of the tape: $$001XXXXXTXXX$$ $$X11XXXXXTXXX$$ $$XX01XXXXTXXX$$ $$XXX1XXXXTXXX$$ $$XXXX0XXXTXXX$$ $$XXXDXXXXTXXX$$ Why must the digits of the number at the beginning of the tape be in reverse positions?
Let's assume the following case, where the number is in its standard binary form: $$...X100XX...$$ Moving it to the right: $$...XX100X...$$ Subtracting it: $$...XXX11X...$$ In this case, there was a double movement in the number, this does not occur if the number is inverted.

Regarding complexity, the number in binary increases the number of digits logarithmically. In steps 3, 4, 6 and 7, the number moves in $O(\log n)$ time. The number of iterations is according to the size of the input ($n$), so these steps are performed in $O(n\log n)$ time. As for step 5, the number of digits to be copied is in the order of $\log\frac{n}{3}$, as the entire tape is traversed in each iteration, so this step is also $O(n\log n)$.
> 1 votes

# Answer
Here is a high level idea that, for any positive integer $c$ of choice, splits a string of length $n$ (assume that $n$ is a multiple of $c$ for simplicity) into two parts of length $(c-1)n/c$ and $n/c$ using $O(n \log n)$ time. Two applications of this procedure with $c=3$ and $c=2$ (and some technical care) solve your problem.

The algorithm will be iterative and, between iterations, the contents of the tape will be of the form $\alpha \langle C \rangle \beta$, where $\alpha\beta$ is the input string and $\langle C \rangle$ denotes the encoding of a non-negative integer $C$ written in binary. The position of the head will be on the first character of $\beta$, if any. I assume that you can mark the start and end of the encoding of $x$ (for example using new tape symbols). I will use $|C|$ to denote the number of bits used in the binary encoding of $C$ (start and end markings are not counted). At the beginning you can just prepend $\langle 0 \rangle$ to the initial contents of the tape.

As long as $\beta$ is not empty, let $\beta = x \gamma$ (where $x$ is some input symbol) and do the following:

* If $C \neq 2^{|C|}-1$ (i.e., $C$ is not a sequence of $|C|$ ones):

+ Increment $C$ by $1$ (this will use the same number of bits as $|C|$). The contents of the tape are now $\alpha \langle C+1 \rangle x \gamma$.
* Otherwise ($C = 2^{|C|}-1$):

+ Move all the symbols in $\alpha$ one position to the left, the new tape contents become $\alpha\\\_\langle C \rangle x\gamma$, where $\\\_$ denotes a blank symbol.
    + Increment $C$ by $1$. This will use one extra bit, which will fit in the blank symbol. The contents of the tape are now $\alpha \langle C+1 \rangle x \gamma$.
* Perform a right cyclic rotation on $\langle C + 1 \rangle x$ (i.e., transform it in $x \langle C + 1\rangle$). The new tape contents are $\alpha x \langle C+1 \rangle \gamma$.

When this procedure is over, the tape contents will be of the form $\alpha \langle C \rangle$, where $\alpha$ is exactly the input and $C$ is the number of symbols in $\alpha$. We can now divide $C$ by $c$ and continue as follows.

As long as $C \neq 0$, the tape contents are of the form $\alpha \langle C \rangle \beta$, where $\alpha = \delta x$, for some input symbol $\delta$. Do the following:

* Decrement $C$ by $1$.
* Perform a left cyclic rotation on $x \langle C \rangle$ (i.e., transform it in $\langle C + 1 \rangle x$). The contents of the tape are now $\delta \langle C+1 \rangle x \beta$.

When this procedure stops, the counter $\langle C \rangle$ splits the input string as claimed. You can now delete the counter and, if desired, iteratively shift the right part of the input string to the left until there is a single blank space between the two parts.

To bound the time complexity notice that we perform $O(n)$ iterations in total before $C$ becomes $0$. Each iteration can be implemented in time $O(|C|) = O(\log n)$, since $0 \le C \le n$. Dividing $C$ by $c$ (which is a parameter of the algorithm), takes time $O(n \log n)$. Deleting $\langle C \rangle$ takes time $O(\log n)$. Shifting the two parts of the string at the end can be done with $O(\log n)$ left shifts of the right part, each of which requires time $O(n)$.
> 3 votes

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


# Question
Title: Proving a greedy algorithm of finding MINIMAL group
I am given a group $A$ of real numbers and I have to find the minimal group $B$ such that for each $a$ in $A$ there exists at least one $b$ in $B$ such that $|a-b|\leq 1$

So what I think the algorithm should do is first sort $A$, then insert $A\[0\]+1$ to $B$, and then iterate on $A$ and check if the last number we added to $B$ is still in his radius of $1$. If not - insert a new number to $B$ that will be that $A\[i\]+1$. The complexity is of course $O(n \log(n))$ because we have to sort $A$.

Now I have to prove that the algorithm gives us indeed the minimal group $B$. And here I am stuck. If there is a better solution (an algorithm that gives us a smaller group), then we can change the number of elements in $B$ and reorganize them so that they will cover more elements in $A$ using less elements then we originally had. How do I write a formal explanation?

# Answer
> 0 votes
Call a number $m$ a milestone if it is in $A$ and your greedy algorithm adds $m+1$ to $B$.

The greedy algorithm selects each next milestone so that it is greater than the current milestone${}+1+1$. So any two milestones are more than 2 apart.

Hence each number in any solution can cover at most one milestone. Any solution must add at least one distinct number for each milestone.

Since the greedy algorithm adds exactly one number for each milestone, it is optimal.

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


# Question
Title: Example of attribute grammar that is NOT l-ORD but non-circular
I am wondering if there exists an example attribute grammar that is non-circular but not l-ordered (l-ORD) as well.

The reason I am asking this is one can find an attribute grammar that is circular, then it will obviously not be an l-ORD. But I am wondering if there even exists a non-circular AG that is also not l-ORD.

# Answer
In Figure 12 of my paper on conditional attribute grammars, it gives the following strongly non-circular attribute grammar that is not doubly non-circular (and therefore not l-ORD):

```
S -> 0 L
    L.inh1 = 0
    L.inh2 = L.syn1
    S.result = L.syn2

S -> 1 L
    L.inh2 = 0
    L.inh1 = L.syn2
    S.result = L.syn1

L ->
    L.syn1 = L.inh1
    L.syn2 = L.syn2

```

It is non-circular (even strongly non-circular) since each synthesized attribute of L depends only on the corresponding inherited attribute, but depending on the context, each may need to be done before the other. Hence no fixed order of attributes can be required.
> 1 votes

# Answer
You could take an L-Ord Attribute Grammar, replace all inherit attributes by synthetic attributes and all synthetic attributes by inherit ones and reverse all assignments... then you have a grammar that isn't L-Ord and still non-circular. I would call that R-Ord, because you have reversed all arrows and can traverse it right-to-left instead of left-to-right.
> 0 votes

# Answer
The Grammar in my answer to Full circularity vs strong circularity for attribute grammars (that you had already found) is also not L-Ord, because L-Ord Attribute Grammars are strongly-non-circular. Since said grammar isn't strongly-non-circular, it's not L-Ord. (And it's also not circular).
> 0 votes

---
Tags: attribute-grammars
---


# Question
Title: Shortest path problem with multiple objectives
I would like to solve a shortest path problem on a graph $\mathcal{G}= (\mathcal{V},\mathcal{A})$, which comes to minimize : \begin{equation} \label{eq:1} \underset{\\{x\_{ij}\\}}{\text{argmin}}\biggl\\{\sum\_{(i,j)\in\mathcal{A}}a\_{ij}x\_{ij}\biggr\\} \end{equation} in which $a\_{ij}$ is a non negative scalar quantifying the cost of arc $(i,j)$, $x\_{ij}\in\\{1,0\\}$ whether the arc $(i,j)$ is in the path or not and, with constraints : \begin{equation} \label{eq:2} \forall i\in\mathcal{V}\\;,\quad y\_{i}= \sum\_{j\\,/\\,(i,j)\in\mathcal{A}}x\_{ij} - \sum\_{j\\,/\\,(j,i)\in\mathcal{A}}x\_{ji} = \begin{cases} 1 &,\\,\text{if}\\; i=s \\ -1 &,\\,\text{if}\\; i=t \\ 0 &,\\,\text{if}\\; i\notin \\{s,t\\} \end{cases} \end{equation} where $s$ and $t$ are respectively the starting and terminal nodes.

The cost $a\_{ij}$ of arc $(i,j)$ usually encodes many objectives :

* fuel consumption
* time of travel, the shorter the better
* whether nodes $i$ or $j$ are in a forbidden or restreint zone

A typical shortest path algorithm will give one optimized path with respect to how various objectives are weighted in the cost.

Is there a different formulation that would allow for an algorithm to give simultaneously several paths for different weighting of objectives ? like genetic algorithm are able to do ?

# Answer
I think one possibility would be to run normal shortest path algorithms on separate graphs which respectively encode the differing objectives, and then search across possible paths in the graph.

The rationale behind this is that the different objective costs are independent of each other. Thus shortest path algorithms can be used for the graphs of different objective costs separately.

For instance, if we use Dijkstra's Algorithm as the base method (perhaps not actually applicable to this case, just an example), we first could generate the cost trees based on each of the objectives. Thus now each node corresponds to a vector $\mathbf{c}\_{node}\in\mathbb{R}^N$ for the $N$ different objectives. Thus now for each set of objectives (represented by vector $\mathbf w$), we can search through the nodes while using the dot product $\mathbf{c}\_{node}\cdot\mathbf{w}$ as the loss.
> 0 votes

---
Tags: shortest-path
---


# Question
Title: How to calculate the growth function of a hypothesis class?
I have this hypothesis class:

H = {ha : R → {0, 1} | a \> 0, a ∈ R, where ha(x) = 1−a,a = { 1, x ∈ \[−a, a\] 0, x ̸ ∈ \[−a, a\] }

I need to compute the growth function for m\>= 0. So I think that this function has the VCdim=2 because you can't realize label (1, 0, 1), but I don't know how to calculate the growth function.

# Answer
> 0 votes
lets start from VC=1 - take for example C={1}, you can shatter it! it can can the + labeling by choosing a=0.5 for example and the - labeling by a=1.5. Now lets look at VC=2 - you can take C={1,2}:

* the labeling +, + can be easily obtained by a=0.5 again
* the labeling -, - can be easily obtained by a=2.5
* the labeling -, + can be easily obtained by a=1.5
* the labeling +, - is not possible! And it's not a coincidence.. for every two positive points, give the rightmost the sign of "-", the other sign of "+" and you cant shatter it. This is of course not enough, you need to show that for every to points in R, but you can without no problem to generalize my explanation to not just two positive points, I will leave that to you :)

---
Tags: machine-learning, statistics, vc-dimension
---


# Question
Title: Blockchains where new users don't need to wait for a new node to retrieve old transactions?
After watching 3b1b's brief primer on blockchains here, I noticed a bit of a "flaw" with blockchains. It isn't really a flaw, but I'm not sure how it is alleviated.

If we have two players, Alice and Bob, who are transacting with one another, each person stores their own copy of the blockchain. This is a given, as blockchains are necessarily decentralized.

But suppose a third party, Charlie, wants to join. But just as he wants to, both Alice and Bob stop transacting for an extended period.

In this case, Charlie cannot create any transaction; he doesn't have the history of the blockchain required to do pretty much anything.

So, he must wait for Alice or Bob to broadcast a new transaction for him to pick it up.

But is there a better way to do this?

# Answer
> 0 votes
Bitcoin has a gossip protocol by which nodes broadcast the state of the blockchain (or updates to it) to each other. Charlie can join the Bitcoin peer-to-peer network and take advantage of the gossip protocol to download a copy of the blockchain.

---
Tags: blockchain, transactions
---


# Question
Title: Generation regular languages by context free grammar
I came across problem asking whether given statement is true and false. The statement given was as follows:

> Every Type-2 grammar can generate regular language.

I felt that Type-2 grammar means, its context free grammar and is generated by PDA. PDA is more powerful than FA which generate regular languages. Hence any Type-2 grammar should be able to generate regular language. But the answer given was FALSE saying that there are Type-2 grammars which generate "pure CFL" (non regular languages).

So I was guessing whats going on here. I have following doubts:

1. Is the question asking whether all CFLs are also regular? (which is not the case and thats why the given answer states "pure CFL")?
2. Is the question asking whether every CFG generate "all" regular languages? (which is obviously senseless and hence is FALSE?)
3. Is the answer FALSE because deterministic context free automata accepting on empty stack cannot even accept regular languages?

# Answer
The question is poorly worded. Here is what they probably meant to ask:

> Is the language generated by a context-free grammar always regular?

Clearly, the answer is negative.

However, this is just a guess, since the question isn't really clear. I suspect ignoring questions which are not clearly stated. If you encounter such a question in an exam, ask the setter to rephrase the question using proper English.
> 1 votes

# Answer
The problem with the statement is the "can" word when it's talking about "every" grammar. Every grammar generates a language. They don't "can" or "cannot". The statemant should be "Every Type-2 grammar generates a regular language". And the answer is obviously false. Or "Type-2 grammars can generate regular languages" and the answer would be true.
> 0 votes

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


# Question
Title: Algorithm to find intersection between collection of sets
I have two dataframes representing products two distributors sell. They look like this:

df1 for distributor 1.

```
Country, Age group, Product
{USA, Canada}, {Toddlers, Teens}, {Jeans, Shoes}
{USA, Mexico}, {Teens, Adults}, {Hair bands, Mufflers}

```

So, the distributor 1 sells jeans and shoes for toddlers and teens in USA and Canada. They also sell hair bands and mufflers for teens and adults in USA and Mexico.

df2 for distributor 2.

```
Country, Age group, Product
{Russia, Canada}, {Toddlers, Babys}, {Shoes, Hats}
{Russia, USA}, {Adults, Elderly}, {Mufflers, Hats}

```

I want to find out if any particular value of Country, Age group and Product matches both df2 and df1. That is, I want of find out if there are conflicts where both distributor is trying to sell the same product to the same age group in the same country.

A straightforward approach would be to explode both the dataframes to look like this:

df1:

```
Country Age group   Product
Canada  Teens   Jeans
Canada  Teens   Shoes
Canada  Toddlers    Jeans
Canada  Toddlers    Shoe
...

```

df2:

```
Country Age group   Product
Canada  Babys   Hats
Canada  Babys   Shoes
Canada  Toddlers    Hats
Canada  Toddlers    Shoes
Russia  Adults  Hats
...

```

Then, convert them to to set of tuples, df1:

```
{('Canada', 'Teens', 'Jeans'),
 ('Canada', 'Teens', 'Shoes'),
 ('Canada', 'Toddlers', 'Jeans'),
 ...}

```

df2:

```
{('Canada', 'Babys', 'Hats'),
 ('Canada', 'Babys', 'Shoes'),
 ('Canada', 'Toddlers', 'Hats'),
 ('Canada', 'Toddlers', 'Shoes'),
 ('Russia', 'Adults', 'Hats'),
 ...}

```

Then find their intersection:

```
>>df1s.intersection(df2s)
{('Canada', 'Toddlers', 'Shoes'), ('USA', 'Adults', 'Mufflers')}

```

The problem I have with this approach is due to the number of columns and possible values in the set, the exploded dataframes have too many rows and final sets have too many items to fit in memory. Is there an (ideally efficient) algorithm to get this done without having to explode the dataframes?

# Answer
One algorithm is to consider all pairs of rows (one row from df1, one row from df2), and find whether there is any intersection between these two rows. Given two rows, this is easy: you compute the intersection of the sets in each column. The running time will be $O(n\_1n\_2)$ where $n\_1n\_2$ are the number of rows in df1,df2, which is quadratic and thus potentially slow, but the memory requirements are very small.

Another approach is to iterate over the intersection in lexicographic order. Here is the algorithm:

* Compute $$C = \bigcup \\{t.\text{country} \mid t \in \text{df1}\\} \cap \bigcup \\{t.\text{country} \mid t \in \text{df2}\\},$$ the set of countries that appear at least once in df1 and at least once in df2.
* For each country $c \in C$:

+ Compute $$A = \bigcup \\{t.\text{age} \mid c \in t.\text{country}, t \in \text{df1}\\} \cap \bigcup \\{t.\text{age} \mid c \in t.\text{country}, t \in \text{df2}\\},$$ the set of ages that appear at least once in df1 and at least once in df2, together with country $c$.
    + For each age $a \in A$:

    - Compute $$P = \bigcup \\{t.\text{product} \mid c \in t.\text{country}, a \in t.\text{age}, t \in \text{df1}\\} \cap \bigcup \\{t.\text{age} \mid c \in t.\text{country}, a \in t.\text{age}, t \in \text{df2}\\},$$ the set of products that appear at least once in df1 and at least once in df2, together with country $c$ and age $a$.
        - Output $(c,a,p)$ for each $p \in P$.

In the worst case, this could be inefficient if this iteration forces you to explore all possibilities of $c,a$, but in practice I suspect that it will allow you to prune the search early (e.g., $A$ will often not contain all possible age groups), hence this might be more efficient in practice.

You can compute $C,A$ efficiently by constructing appropriate indices. Computing $P$ might require iterating over the entire data frames.

A third approach is to compute the explosion for all pairs of attributes. In other words, compute all possible values for (country,age) that appear in df1, all possible values for (country,age) that appear in df2, and take the intersection. Then, compute all possible values for (age,product) that appear in df1, all possible values for (age,product) that appear in df2, and take the intersection. Finally, do the same for (country,product). Next, use the following algorithm:

* For each country $c$:

+ For each (country,age) $(c,a)$ in the intersection:

    - For each product $p$ such that $(a,p)$ is in the intersection for (age,product) and $(c,p)$ is in the intersection for (country,product):

        * Check whether there is a row in both df1 and df2 with $(c,a,p)$, by linearly scanning through both tables. If yes, output $(c,a,p)$.

You can compute the pairwise intersections pretty efficiently by exploding each row and taking the union over all rows. This might be the best of the three algorithms in practice. The memory requirement is not too great because you only require pairwise explosions, not three-way explosions.
> 0 votes

---
Tags: algorithms, graphs, computational-geometry, sets, set-cover
---


# Question
Title: Is there a polynomial algorithm which for each graph G and each value k determines whether all the cliques of G have size smaller than k?
Is there a polynomial algorithm which for each graph G and each value k determines whether all the cliques of G have size smaller than k? Is it correct to say that it doesn't exist because clique is NP-Complete?

# Answer
> Is there a polynomial algorithm which for each graph G and each value k determines whether all the cliques of G have size smaller than k?

We do not know the answer to this question.

> Is it correct to say that it doesn't exist because clique is NP-Complete?

No, that would not be correct. Since we currently do not know whether P=NP, it could be that Clique is polynomial time solvable.

However, if we assume that P != NP, there is no polynomial time algorithm for Clique.

---

Ps: Your problem is in fact co-NP-complete.
> 1 votes

# Answer
If there exists such a polynomial algorithm, then we can run this algorithm for each $k=1,2,...n$ thus a polynomial algorithm with an additional factor $n$ for clique problem is generated. This is a contradiction to the fact that clique is NP-Complete (a direct reduction from independent set can proof the hardness).
> 0 votes

# Answer
It depends on what you consider a polynomial-time algorithm in this case.

Given a graph and an integer $k$ you can determine if there all the cliques are of size at most $k$ by looking at all sets of $(k+1)$ vertices and determining if they form a clique. If there is any clique of size larger than $k$, then choosing any $(k+1)$ of those nodes will form a clique.

So you can answer your question in $O(n^{k+1})$ time. Is that polynomial? Depends on your framework.
> 0 votes

---
Tags: complexity-theory, np-complete, polynomial-time, clique
---


# Question
Title: Does this esoteric representation of integers have decidable equality?
Consider the following datatypes in Haskell:

```
data Foo = Halt | Iter Foo
newtype BigInt = BigInt {nthBit :: Foo -> Bool}

```

`Foo` is Peano numbers compactified by one limit point, namely `fix Iter`. `BigInt` represents arbitrary-length integers in two's complement. The limit point `fix Iter` forces the field `nthBit` to eventually terminate in infinite string of zeros, or infinite string of ones.

Since `Foo` is compact and `Bool` is discrete, `BigInt` expresses a discrete function space. But does this mean `BigInt` has decidable equality?

Semideciding inequality of `BigInt` is easy. Given two different integers, Keep evaluating their `nthBit` fields at `Halt`, `Iter Halt`, `Iter (Iter Halt)` and so on until they mismatch.

But what about semideciding equality? Given two equal integers, mathematically their equality at `fix Iter` should already serve as a proof that they might mismatch only at finitely many bits, but that doesn't give the range of the might-be mismatch.

Or was it my misconception that discreteness implies decidable equality?

# Answer
> 2 votes
Fun question! Yes equality is *externally* decidable here, though I don't know if the procedure is *internally* expressible in Haskell. Here's a more direct solution:

Let `infty` be the infinite integer `fix Iter`. On input `a` and `b`:

* Run `a infty` and `b infty`. If they are unequal, return "false"
* Otherwise, track the number of steps that each of the above computations takes to run, and let $N$ be the maximum of the two. Then it follows that, since `a` and `b` cannot distinguish `infty` from an integer that is N or greater, the Nth digits and greater of both `a` and `b` must be equal to `a infty` and `b infty`. So it remains only to check the digits from 0 to N are equal; if they are all equal, return "true", else return "false".

---

The crux of the argument is that "`a` and `b` cannot distinguish `infty` from an integer that is N or greater". This should be true in Haskell, but it is also why I am not sure if this procedure is internally expressible. Functions cannot introspect on `infty` to see its implementation, so they cannot do anything on input `infty` other than run it some finite number of times or diverge.

But the procedure above fundamentally relies on running `a infty` and `b infty` to see how long they run. That is a bit weaker than inspecting the implementation of `a` and `b`, but it may not be possible in a purely functional way, or at least I don't see how to do it.

# Answer
> 2 votes
Assuming that you intend to only count the total functions for $\mathsf{BigInt}$, then yes, equality should be decidable. Here's a sketch for how to do it for $i$ and $j$:

1. First test $i$ and $j$ on $\infty$. If they differ, then they are unequal. If they both yield $1$, then run the subsequent tests with $-i$ and $-j$ obtained by flipping the output of $i$ and $j$.
2. Due to continuity, we know that there are only finitely many $1$ indices remaining in $i$, so we can be sure that the following loop will complete:
    1. Search for $\bar{n} : \mathsf{Foo}$ such that $i\ \bar{n} = 1$. If you don't find one, the loop is complete. Otherwise check that $j\ \bar{n} = 1$. If not, then $i \neq j$. Otherwise ...
    2. Find $n : ℕ$ that corresponds to the above value. I believe this requires Markov's principle (unbounded search is okay as long as we know not all $n$ are $0$).
    3. Continue the loop with $i'$ and $j'$, which agree with $i$ and $j$, except that $i'\ \bar{n} = j'\ \bar{n} = 0$. This is accomplished by induction on $n$. In Haskell, you could just recurse on $\bar{n}$, but the reasoning that this is okay is analogous to Markov's principle ($\bar{n}$ is not $\infty$, so it is finite). Note of course that $i = j \leftrightarrow i' = j'$.
3. When this process finishes, you are left with $i = \mathsf{const}\ 0$. But now you can easily test for equality with the remaining $j$ by searching for $\bar{n} : \mathsf{Foo}$ such that $j\ \bar{n} = 1$. If you find one, $i \neq j$. Otherwise $i = j$.

Here is an Agda formalization of this approach. It might look lengthy, but quite a bit of that is due to proving things about how it behaves. Just writing down the more simply typed procedure in Haskell would be considerably shorter. Markov's principle and continuity are implemented as assertions about the termination of certain recursive functions that Agda's checker would otherwise reject.

---
Tags: computability, functional-programming, semi-decidability, equality, topology
---


# Question
Title: Bounded clique width graphs vs parameter clique width
I am Balchandar Reddy, a research scholar. I am currently working on the parameterized complexity of a problem for the parameter clique width. The problem is known to be polynomial-time solvable on graphs with bounded clique width; does this indicate that the problem is FPT for the parameter clique width? Similary, if the problem is linear-time solvable on graphs with bounded clique width, does this indicate the same? Please clarify.

# Answer
> 5 votes
Not necessarily, being polynomial-time solvable for graphs with bounded clique-width means that on graphs of clique-width less than $k$ an algorithm solves the problem in $O(n^{f(k)})$ time for some function $f$, so it only implies that the problem is XP (slice wise polynomial) with respect to clique-width.

On the other hand if the problem is linear-time solvable on graphs with bounded clique-width, then an algorithm solves it in $O(f(k)\cdot n)$ for graphs with clique-width at most $k$, so it is indeed FPT, as FPT means being solvable in $O(f(k)\cdot n^c)$ for some function $f$ and $c\>0$.

---
Tags: algorithms, graphs
---


title: PSPACE≠co-NP?Is the statement true?

text:
# Question
Title: PSPACE≠co-NP?Is the statement true?
Is the statement in question true? how can i prove it formally? I know that PSPACE=CO-PSPACE and NP ⊆ PSPACE and CO-NP ⊆ CO-PSPACE

# Answer
> 4 votes
If P = PSPACE then since $\text{P} \subseteq \text{coNP} \subseteq \text{PSPACE}$, we can conclude that coNP=PSPACE, and by contrapositive this means that if $\text{coNP} \neq \text{PSPACE}$ then $\text{P} \neq \text{PSPACE}$. Since the question of P vs PSPACE is unsolved, one can conclude that there's no known proof of $\text{coNP} \neq \text{PSPACE}$.

---
Tags: complexity-theory, time-complexity, proof-techniques, space-complexity, co-np
---


# Question
Title: Complexity of this variant of #Positive 2-SAT #P-complete?
In this variant of #Positive-2-SAT ,we divide set of all possible clauses like this :

A = \[ab ,ac ,ad ,.... \]

B =\[bc ,bd ,be ,....\]

C=\[cd ,de ,....\]

D=\[de ,....\]

....

In this variant ,we are allowed to select clauses from only 3 sets mentioned ,And for every k variable there are k such sets but for k variables ,we are only allowed to select clauses from any three of these k sets ,then , is counting the number of satsifiable instance of these clauses #P-complete or not.

If its not #P-complete for where we are allowed to select clauses from only 3 sets ,then does there exist a value k ,such that we are allowed to select clauses from only k sets ,for which this problem is #P-complete?

This problem is inspired from my previous problem ,here the restriction are vertical ,In my previous problem restriction was horizontal ,in a sense that we select clauses from every set but only a certain amount ,but here we can choose as many as we want but from a limited number of sets

# Answer
> 1 votes
The problem is in **P** for any fixed $k$. The clauses shouldn't need to be all positive, either.

For the positive example, let's say we choose from sets $A$, $B$ and $C$ (it doesn't really matter). For each of the 8 (or generally, $2^k$) possible truth assignments to $a$, $b$ and $c$ (which I will call the *main variables*), the number of satisfying assignments is simply $2^s$, where $s$ is the number of variables (obviously excluding the main variables themselves) that only occur in clauses where the main variable of that clause is chosen to be true.

You have to mind the existence of clauses like $(a \vee b)$, but they don't really complicate the picture - just set the number of satisfiable assignments to 0 for every assignment of the main variables where both $a$ and $b$ are chosen to be false.

---
Tags: complexity-theory, complexity-classes, counting
---