title: Two Generals' Problem Definition

text:
# Question
Title: Two Generals' Problem Definition
I've read various descriptions of the TGP, most of which seem vague or conflicting on the precise constraints of the problem. Specifically:

* is it always or sometimes impossible to reach consensus
* finite/infinite messages required
* given unreliable communication, is actual message loss important or not.

As another point, the depiction of the problem seems inadequate, as there's no need for the generals to always require acknowledgement for their last message if they regard previous ones:

0 A ----time info--\> B

1 A \<---AckForA0---- B

2 A ----AckforB0---\> B

3 A \<---AckforA1---- B

1... A knows B received his time info and is ok with it but might not attack if he doesn't receive confirmation for his ack.

2... B knows A received his ack because he responded.

3... A knows B got his ack because he responded

Can anyone give a better example which illustrates this specific need to rely on acks of the respective last messages.

# Answer
> 1 votes
Whenever you think you have solved the two general problems, there is only 1 thing you need to do to find why your solution is wrong.

Take every step s\_1...s\_n of your algorithm and treat it as the final step before a permanent network failure. Does a general end up dead if any step s\_i is the final step before total network failure? Then you haven't solved it.

> A knows B got the ack before, which is sufficient for a general.

So if I understand correctly in your scenario, B upon receiving AckforB0 is now fully confident to charge into battle? Then let's say he gets it and then a permanent network failure happens. B sends messengers to A but none go through and A never becomes confident enough to ride into battle. So B goes into battle alone and dies.

If you try to argue that A should be confident enough to go to into battle at this step because he already received AckForA0 then all you've done is shifted the problem backwards. Now if A gets AckForA0 and a permanent network failure occurs then A will ride out to their death alone.

# Answer
> 1 votes
A lot of misunderstanding is caused by explaining the problem as an ongoing process. It's a lot easier to understand if one simply considers the possible states that the generals can be in.

Assume the generals have agreed that they will attack if they get at least N messages.

* B) Before both generals have received N messages, both know that they *should **not** attack*.
* A) After both generals have received N messages, both generals know that they *should attack*.
* T) Between those two states is a time interval during which:
    + T1) One general receives the Nth message.
    + T2) The other general receives the Nth message.

The problem is that T1 and T2 are independent.

Between T1 and T2 the generals are in a state where:

* One general knows that he should attack.
* One general knows that he should not attack.

If all communication is cut off within this period, everyone dies.

---
Tags: distributed-systems, computer-networks, fault-tolerance, byzantine
---


# Question
Title: Show that Lu is m-reducible to the language L = {⟨M, x⟩ | M(x) terminates with an empty tape}
Question: Given a language L, L = {⟨M, x⟩ | M(x) terminates with an empty tape}, show that Lu is m-reducible to L by finding a computable function f: Σ\* -\> Σ\*, where for every w, w ∈ Lu if and only if f(w) ∈ L. (Recall Lu = {⟨M, x⟩ | x ∈ L(M)})

My general understanding of m-reducibility is that if you can assume there exists a decider machine M' for M, and given this assumption prove that there is a decider for Lu, you can arrive at a contradiction and therefore prove L is undecidable.

This problem is asking to demonstrate it using a function though. How does one do this?

# Answer
> 1 votes
Recall that there are when running $M(x)$, there are three possibles results:

* $M(x)$ terminates in an accepting state;
* $M(x)$ terminates in a rejecting state;
* $M(x)$ doesn't terminate.

The reduction you want is such that $x\in L(M) \Leftrightarrow M'(x')$ terminates with an empty tape, $\langle M', x'\rangle$ being equal to $f(\langle M, x\rangle)$.

What you could do is tweak $M$ a little bit such that:

* if $M$ accepts $x$, then it empties the tape before terminating;
* if $M$ rejects $x$, then it write a symbol on the tape before terminating.

---
Tags: turing-machines, computability, undecidability, decidability
---


# Question
Title: Knowing if there's an equivalent Turing machine
Is it always possible to know if there's an equivalent Turing machine to a given machine such that it'll have a smaller number of states? (1-tape machine, minimizing it)

My intuition says that finding such machine in the general case is not possible, but what about just knowing if there's a simpler machine?

Is my question like asking "How to know if there's a simpler solution to a given problem"?

# Answer
If you don't care about the number of symbols in the alphabet, then there are constructions of universal Turing machines that only use $2$ states.\* This means that every Turing machine with at least $3$ states admits an equivalent Turing machine with less states.

Turing machines with just two states don't admit smaller equivalent machines, unless their language is trivial. This is because the standard definition of Turing machine restricted to have a single state would force the machine to either always accept or to always reject, so the machine can only decide trivial languages (but see \*, which could allow the machine to run forever).

If you alter the definition slightly, then you can obtain single-state Turing machines that are a bit more powerful. See this paper for details.

---

\*The precise definition allows transition from halting states. The machine stops when it is in a halting state and no transition is defined for the current symbol-state pair. Additionally, an infinitely repeated word on the otherwise blank portions of the tape is allowed. See the paper for details.
> 2 votes

---
Tags: turing-machines
---


# Question
Title: In C, why limit || and && to evaluate to booleans?
In some languages, e.g. Ruby, an expression like:

```
val = call_fn() || DEFAULT_VAL;

```

will set val to the results of `call_fn()` if it is *truthy* (non-zero, non-NULL, etc), or to `DEFAULT_VAL` otherwise. This can be really useful.

In C, the result of the `||` operator is always a boolean value (1 or 0).

Is there a strong argument for C limiting the result to a boolean value (other than tradition)?

## Addendum

Using some gnu extensions, a macro that approximates the behavior I'm looking for could be written as:

```
#define OP_OR(a, b)                                 \
    ({                                              \
        __typeof__(a) _a = (a);                     \
        _a ? _a : b                                 \
    })

```

This evaluates to `a` iff it is *truthy* (i.e. non-0 for numeric values, non-NULL for pointers, not '\0' for chars), otherwise it evaluates to `b`. The `__typeof__` line guarantees that `a` is evaluated exactly once.

# Answer
> 21 votes
Boolean types and Boolean expressions are the crux of the logical formalism and the latter is ubiquitous in programming. C was lacking them in the beginning, yet another design flaw of this language (took like twenty years to be fixed!).

Tinkering a boolean type with integers is not just a conceptual mistake, it is a source of problems, such as comparisons not behaving as expected.

I don't know about the semantics of `&&` in Ruby, but presumably it has to make an asymmetric choice between the two values in case of two non-zeroes.

This said, the ternary `?` operator allows you constructs like

```
val= call_fn();
val= val != 0 ? val : DEFAULT_VAL;

```

---

Independently of this answer, I don't see the trick

```
val = call_fn() || DEFAULT_VAL;

```

with a good eye, as it forces you to reserve the value `0` to somehow indicate "do not use this returned value" and cannot work with functions that can legitimately return `0`. I'd prefer a function that returns `DEFAULT_VAL` directly.

# Answer
> 17 votes
An operator can be described in terms of three things:

* The accepted range of values (type) of each of its operands
* Its behaviour
* The possible values (type) of its result

The simplest "or" operator is defined as having two operands and a result all with values "true" or "false", i.e. a "boolean" type. With such a definition, the result of `42 || 69` would be undefined, just as the value of `"hello" / "world"` is undefined. The result of any valid pair of operands would always be either "true" or "false", never another value.

C evolved gradually from a language called B, which had no distinction between types, so all operators were defined over the range of binary values that could be contained in a particular memory location. For operators that would normally require "true" and "false" values, B defined a value of all zero bits as "false", and any other value as "true". This carried over into early versions of C, where the `||` operator was defined† for any pair of integers, with the same rules. However, the *result* was still defined as only having two possibilities: 0 for false, 1 for true.

Other languages have generalised the operator further, and said that the range of *results* also has more than two values: the representation of "false" is fixed, but "true" is replaced by a direct copy of one of the inputs.

We can speculate why early versions of C didn't generalise the result in that way:

* A fixed result may be more efficient to implement than a memory copy
* The possibility simply didn't occur to the language's designers at the time

More clearly, we can answer why C didn't *later* adopt a different definition: **it could break existing code**. Consider the following snippet of code:

```
c = a || b;
z = x || y;
switch ( c + z ) {
    case 2: ... // both c and z are true
    case 1: ... // one or other is true
    case 0: ... // neither is true
}

```

This code relies on the guaranteed range of outputs from the `||` operator. If `a || b` evaluated to `2`, the wrong branch would be entered; if it evaluated to `42`, *none* of the branches would be entered.

In general, this is similar to the rules around covariance and contravariance:

* It is safe to *widen the input*, e.g. to define a result for `"hello" / "world"` if that was previously forbidden or Undefined Behaviour
* It is safe to *restrict the output* more narrowly than previously guaranteed, e.g. to add a guarantee that a certain operator will never evaluate to `NaN`
* It is *not* safe to *narrow the input*, and forbid code that was previously acceptable
* It is *not* safe to *widen the output*, and produce values that code was not previously expecting

---

† - According to Dennis Ritchie's description of the language's development, B only had the *bitwise or* operator, `|`. That gives the same result as a *boolean or* with the above definition of "true" and "false", because `0 | 0` yields `0`, and any other operands yield a non-zero result. The downside is that you need to examine both operands to produce a result, whereas a *boolean or* can "short-circuit" if the first argument is true. The separate `||` operator was added to early C as a replacement for a special case that allowed `|` to short-circuit in conditional statements, along with even more complex rules for `&`.

# Answer
> 8 votes
Edit: After re-reading the question and wovano's comment I think my answer below misses the point because the suggestion to return the non-zero operand or zero if there isn't any would not be overly complicated or abstract if the operands stayed restricted to scalar types. I let the answer stand because I still think it's a good text ;-).

---

The reason is that C, by design, is a really simple language that provides operations closely aligned with what machine code of machines like the PDP11 offered. You posted the question in the *computer science* stack exchange, but computer science is not what C was designed for or from which it came. C is the creation of engineers writing an operating system and hitting a limit of what was maintainable and portable in assembler. They were in a unique spot because they had the insight, skill, time and attitude to backtrace and write a tool for that: C. They seized the day and, one may say without exaggeration, changed the world.

**C is a language created to solve an engineering problem.**

Because of the memory and computing limits the language had to be dirt simple, so that even a simple compiler could produce good code.

**The language had to be closely aligned with what the machine offered.**

While I'm not familiar with PDP11 machine code I bet you there is a test for zero, an AND operation on registers, and a conditional jump. On that level there is no concept of a boolean; everything is integers.

This is what C mimics. The machine operation has a C equivalent which makes it totally obvious what the compiler would produce. (The same "everything is an integer" concept was used for pointers.)

In order to appreciate the differences of C's "engineering" approach to a computer science approach, have a look at Algol68. That is a (seriously) great language designed without concerns for the resources the compiler or code would need. It is also instructive to compare the language descriptions1,2, a contrast which more than highlights the pragmatic approach of the C creators.

As others remarked, a shortcut for selective evaluation dependent on a condition exists with the ternary `?:` which is about as complicated as you get with C.

---

1  For Algol68: https://www.softwarepreservation.org/projects/ALGOL/report/Algol68\_revised\_report-AB.pdf

2 For C: The first edition of Kernighan/Ritchie: *The C Programming Language*

# Answer
> 5 votes
The operand of `if`, `while`, etc. isn't limited to integer types, but will also work with floating-point or pointer types. For a value x of any integer, floating-point, or pointer type, `if(x)` is equivalent to `if ((x) != 0)`, with the literal zero being interpreted as a value of `x`'s type. Making a construct like `if ((x) || (y))` work with any combination values `x` and `y` that could be used as conditionals individually, without regard for whether the types would be compatible with each other, would require that the `||` operator be capable of yield a value of a type that was incompatible with at least one operand.

Note that the behavior of a construct like:

```
double d = 0.125;
char *p = "Hello there!";

if (d || p)
  printf("The values are %5.3f, %s!", d, p);

```

is quite different from what it would be if the condition were written as

```
if ((int)d || (int)p)

```

The value of `(int)d` would be zero, even though `d` is regarded as non-zero by the `||` operator, and the while the value of `(int)p` probably wouldn't be zero, there are some platforms where pointers are longer than integers, and where the value of that expression might be zero by chance.

While there probably would have been no difficulty saying that the `&&` operator be syntactic sugar for `leftOp ? rightOp : 0`, I can't think of any nice way of describing the behavior of `||` that would allow it to be used in scenarios where the types of the operands differ, but wouldn't introduce behavioral inconsistencies in such cases.

Given that C is in fact generally parsed outside-in, and efficient processing of `||` and `&&` operators would require knowing whether they are being used as part of a top-level conditional construct, it might have been practical to specify that when the result of `||` or `&&` is coerced to a "conditional test", the operands would be likewise coerced, and that the operands of those operators must be integers in all other cases. A similar principle could also have been usefully applied to constructs like `uint1 = ushort1*ushort2;` on implementations that don't use quiet-wraparound two's-complement semantics: since the result of the multiplication will be coerced to `unsigned int`, the operands should be likewise coerced and then multiplied as that type. Unfortunately, this kind of thing is easier to do than to formally specify, and thus language specs make no accommodation for it.

# Answer
> 4 votes
The `||` and `&&` operators in Ruby are closer to basic process algebra composition operators than to boolean connectives. The languages just happen to use the same symbols for these two different sorts of operators due to the lack of glyphs on the keyboard.

Keeping this in mind there are important distinctions between the `||` operator in Ruby and alternative composition. One such distinction is that `||` in Ruby is not commutative.

The analogy stands in the sense that in basic process algebra one can simulate boolean algebra but not vice versa.

Coming now to the original question. The C programming language exists as a language on its own and not as a subset of C++ precisely because it has a relatively clean semantics and it is relatively easy to tell how an expression is to be evaluated. If we instead allow things like `-1L || 4U` or `0.0 || 42` with numeric type promotion, this would make compilation results less predictable.

Finally as it was mentioned before the ternary conditional operator `x>0 ? x : y` in C would be an almost perfect drop in replacement for the proposed numeric choice operator `x || y`.

# Answer
> 4 votes
In many Lisp dialects, there is usually an `or` operator which returns the leftmost value that is not `nil`, and stops evaluating the rest.

GNU C does have an operator which evaluates A, and returns A if A is nonzero, otherwise B, namely: `A ?: B`.

Why, in C, we don't want `||` to have this semantics because C is statically typed in a particular way. The expression `A || B` has to have a type. The type has to be derived from the types of `A` and `B`. If it has the semantics of evaluating either to `A` or `B`, that then requires `A` and `B` to be compatible. They have to have the same type, or else one has to convert to the type of the other.

Suppose P, Q and R are pointers to different object types, and thus incompatible. You cannot write `P || Q || R` under this semantics; it violates a type constraint. Under the C semantics of `||` as they are, the above is allowed: it yields true if any of the three pointers is non-null.

In terms of type theory, such an operator calls for a sum type: its type wants to be the sum type of the constituent expressions. Thus if we have `W || G` where `W` is a Widget and `G` is a Grommet, the resulting type is Widget | Grommet: a type that can be either.

This is why the `or` operator works in Lisp dialects, and its equivalentin other dynamic langauges: they are dynamically typed, and so every value is potentially a sum type of everything, making the type problem go away into run-time. `(or W G)` has no problem yielding a value that is either a Widget or a Gadget, because that dynamism is already everywhere.

# Answer
> 2 votes
One possible reason is that bitwise operations on relations would give the wrong results. For example, the code

```
if ((printf( "hello, %s, it's", higher_power ) == 16) &
    (printf( " me, %s\n", luser ) <= 15)) {

```

would evaluate to *false* if both conditions are met, if logical operations returned the value of one of their operands, and not execute the body of the loop! And the programmer could not change `&` to `&&` without potentially short-circuiting the second function call, which has side-effects. When both results are constrained to be either 1 or 0, the above works.

This doesn’t literally use `&&` and `||`; I picked a more natural example using comparison relations. The principle is exactly the same. But, in B, the predecessor language to C, there were no `||` or `&&` operators, and everyone used `&` and `|` instead. This worked because false was always `0` and true was always `~0`.

The choice of `1` as TRUE in C, rather than `~0`, also means that the representation of TRUE is the same for every integral type, and can round-trip convert with floating-point, so treating boolean results as `int` values could just work. If `x == y` returned `0xFFFFU` on a DEC PDP-11 when the types of X and Y were `unsigned int`, but `0xFFFFFFFFUL` when the types were `unsigned long int`, suddenly any subexpression that widened the result of a 16-bit unsigned boolean true to `unsigned long int` width would have produced `0x0000FFFFUL` and caused these logical operations to fail on the upper word. (This had not been an issue for B, as it was an untyped language.) With no special Boolean type, automatic conversion to and from a `float` would have been an issue as well. Later, although we know this was unfortunately not something on their minds at the time, the default type promotion rules would have caused even more bugs in the 16-to-32-bit transition. Migrating this code to a 32-bit VAX would have caused all the boolean operations on `int` values to suddenly produce `0xFFFFFFFF`, not `0xFFFF`.

The choice of 1 as the value of Boolean true also follows the precedent of Algol, a trendy language in the early ’70s.

The above is my own speculation. Dennis Ritchie would later write about the creation of separate logical operators: What he had to say about it in his own words:

> Rapid changes continued after the language had been named, for example the introduction of the && and || operators. In BCPL and B, the evaluation of expressions depends on context: within if and other conditional statements that compare an expression's value with zero, these languages place a special interpretation on the and (&) and or (|) operators. In ordinary contexts, they operate bitwise, but in the B statement
>
> ```
> if (e1 & e2) ...
>
> ```
>
> the compiler must evaluate e1 and if it is non-zero, evaluate e2, and if it too is non-zero, elaborate the statement dependent on the if. The requirement descends recursively on & and | operators within e1 and e2. The short-circuit semantics of the Boolean operators in such \`truth-value' context seemed desirable, but the overloading of the operators was difficult to explain and use. At the suggestion of Alan Snyder, I introduced the && and || operators to make the mechanism more explicit.
>
> Their tardy introduction explains an infelicity of C's precedence rules. In B one writes
>
> ```
> if (a==b & c) ...
>
> ```
>
> to check whether a equals b and c is non-zero; in such a conditional expression it is better that & have lower precedence than ==. In converting from B to C, one wants to replace & by && in such a statement; to make the conversion less painful, we decided to keep the precedence of the & operator the same relative to ==, and merely split the precedence of && slightly from &. Today, it seems that it would have been preferable to move the relative precedences of & and ==, and thereby simplify a common C idiom: to test a masked value against another value, one must write
>
> ```
> if ((a&mask) == b) ...
>
> ```
>
> where the inner parentheses are required but easily forgotten.

In Section 2.6 of *The C Programming Language*, Kernighan and Ritchie specify:

> By definition, the numeric value of a relational or logical expression is 1 if the relation is true, and 0 if the relation is false.

Since then, C and all of its successor languages have been boxed in by backward compatibility.

### Postscript

Since one commenter requested an example of code involving literal `&&` and `||` that breaks when a boolean sub-expression either takes the value of its truthy argument, as you ask about, or promotes from `0xFFFFU` to `0x0000FFFFUL`, as it would have if Ritchie et al. had represented TRUE as in B and given C the same implicit-promotion rules, here is an arbitrary one.

```
(function_returning_unsigned_int() && function_returning_signed_int()) ^
(unsigned_long_value || function_call()) /* 0x0000FFFFUL ^ 0xFFFFFFFFUL is truthy. */

```

I make no claim about how likely it is to occur, but at the time, Ritchie, Kernighan and Thompson had a large codebase that always used bitwise operators on logical expressions.

# Answer
> 1 votes
I think the direct answer is, "No, there is not a strong argument."

It seems to me that the functionality you're describing would have worked overall pretty consistently in C (if introduced at the start), and if you had been able to make your case to the creators of C at the time they might well have at least considered it on the strength of your arguments (if you had some good examples for them of why "this can be really useful").

# Answer
> 0 votes
The question states

> "In C, the result of the || operator is always a boolean."

This is misleading. The result of both || and && is type **int**. The value of the int is either 0 or 1.

Note that the C11 standard introduced type **\_Bool**, and the upcoming C23 standard goes further with primitive type **bool**. However, in neither case is the type of || or && changed. It is still **int**.

This statement should always test true even if the size of an int is different from the size of a boolean:

> sizeof(A || B) == sizeof(int)

Anyway, the answer to the question is that || means "or" and is the C version of "or" in earlier languages like Algol. It was never intended to mean "else". The rule that says the right side is not evaluated if the left side is true was intended as an efficiency plus an convenient way to guard the second part (such as "if (i \> n || a\[i\] == 0)" if a\[n\] is the last element of the array).

Brendan.

# Answer
> 0 votes
If I understand the use here correctly it's because C languages already have another operator for that: `?:`

So in C languages

```
val = call_fn() || DEFAULT_VAL;

```

would be written as

```
val = call_fn() ? call_fn() : DEFAULT_VAL;

```

or

```
tmp = call_fn();
val = tmp ? tmp : DEFAULT_VAL;

```

Depending on constness of `call_fn()`.

The `||` and `&&` operators are meant exclusively for boolean logic in C and so they condense to only the minimum definition of true and false for their output.

---
Tags: c
---


# Question
Title: Can two different binary trees can have identical post-order sequence
I have found that when drawing two trees having different structures, we can get the same in-order sequence and pre-order sequence. But I haven't found if two different binary trees can have an identical post-order sequence. Is it possible?

# Answer
> 1 votes
# Yes

If we allow nodes with 1 child to have that child in either position and consider the resulting trees distinct, the smallest such pair of trees has 2 nodes.

Tree 1 with traversal \[b, a\]:

```
   a
 b

```

Tree 2 with traversal \[b, a\]:

```
   a
     b

```

This is a somewhat unsatisfying answer, because the two trees are not really "different." If we increase the requirements by saying that two trees are the same iff their roots are the same and they have the same **non-empty** subtrees in the same order (this way, the two trees above are defined to be the same tree and so don't count), then the smallest such pair of trees has three nodes each.

Tree 1 with traversal \[b, c, a\]:

```
   a
 b   c

```

Tree 2 with traversal \[b, c, a\]:

```
    a
  c
b

```

# Answer
> 0 votes
Consider any arbitrary binary tree and get its postorder sequence. Now starting from the root(the right-most element in the post order sequence) construct all possible degenerate binary trees. They all would have the same postorder sequence.

An example

```
                  1                 1           1          1          1
                 / \        =>     /           /            \          \
                2   3             3           3              3          3
            postorder = 231      /            \             /            \
                                2              2           2              2

```

For $n$ elements you have $2^{n-1}$ degenerate trees and the original tree having the same postorder sequence.

---
Tags: algorithms, trees, binary-trees
---


# Question
Title: Converting a regular expression to a context-free grammar
Does this conversion look right? I am learning conversion from RE to CFG.

RE:

$$(a \cup b)^\* \cup ab(a \cup b)^\*$$

CFG:

*Terminals:* $$ S\_1 \to a \\ S\_2 \to b $$

*This is for the first $(a + b)^\*$:*

\begin{align} &S\_3 \to S\_1 \mid S\_2 && (a \cup b) \\ &S\_4 \to S\_3S\_4 \mid \epsilon && (a \cup b)^\* \end{align}

*This is for the $ab$ in the middle:*

$$ S\_5 \to a \\ S\_6 \to b $$

*This is for the second $(a \cup b)$ and $(ab)$ in the middle:*

\begin{align} &S\_7 \to S\_1 \mid S\_2 && (a \cup b) \\ &S\_8 \to S\_7S\_8 \mid \epsilon && (a \cup b)^\* \\ &S\_9 \to S\_5 S\_6 && (ab) \end{align}

*Concatenated $ab$ with the second $(a \cup b)^\*$:*

\begin{align} &S\_{10} \to S\_8 S\_9 && (ab(a \cup b)^\*) \end{align}

*This the final CFG:*

\begin{align} &S\_{11} \to S\_4 \mid S\_{10} && (a \cup b)^\* \cup ab(a \cup b)^\* \end{align}

# Answer
This CFG is indeed correct, but can be greatly simplified.

* First, there is no need to create a new variable that would derive only a terminal value, that is - $s\_1,s\_2,s\_5,s\_6$ are not required.
* For a similar reason, we don't need $s\_9$.
* Another simplification is that $(a\cup b)^\*$ was already generated by $s\_4$. There is no need to create $s\_7$ and $s\_8$ for this usage

Considering those things, the CFG will be reduced to:

* $S\rightarrow A\space|\space abA$
* $A \rightarrow AB\space|\space\epsilon$
* $B \rightarrow a\space |\space b$

Notice also that $L(ab(a\cup b)^\*)\subseteq L((a\cup b)^\*)$, and thus:

$L((a\cup b)^\*\cup ab(a\cup b)^\*) = L((a\cup b)^\*) \cup L(ab(a\cup b)^\*) = L((a\cup b)^\*)$

And thus an even smaller CFG will be:

* $S \rightarrow A$
* $A \rightarrow AB \space | \space \epsilon$
* $B \rightarrow a\space | \space b$

Essentially we removed one unnecessary derivation rule. This can be simplified a bit further, go ahead and give it a try :)
> 3 votes

# Answer
As @nir\_shahar said the mentioned language is equivalent to $L((a \cup b)^\*)$, hence the grammar may be written much simpler:

$$ S \rightarrow aS | bS| \epsilon $$
> 0 votes

# Answer
Yeah, that's right. You just read the sub-expressions from bottom up; but do bear in mind, there are only 7 distinct sub-expressions, not 10. They are: $$A = a, B = b, C = A∪B, D = C^\*, E = AB, F = ED, G = D∪F.$$ So, the grammar could just as well be written as: $$A → a, B → b, C → A, C → B, D → ε, D → DC,\\E → AB, F → ED, G → D, G → F, G,$$ with the top-level expression, as indicated at the end, being $G$. The $=$'s become $→$'s, the unions split ($q = r∪s$ becomes $q→r, q→s$), and the stars recurse ($q = r^\*$ becomes $q→ε, q→qr$ or $q→ε, q→rq$ or even $q→ε, q→qrq$).

Since all regular expressions have finite right-affine grammars (which count as context-free grammars), you can also write them that way, by adopting certain algebraic rules. This time, set the top-level expression to: $$A = (a∪b)^\* ∪ ab(a∪b)^\*.$$ Then, after using the identity $x^\* = ε ∪ x x^\*$ and distributivity $x(y∪z) = xy∪xz$, as well as associativity $x(yz) = (xy)z$, we have: $$(a∪b)^\* = ε ∪ (a∪b)(a∪b)^\* = ε ∪ a(a∪b)^\* ∪ b(a∪b)^\* \\ab(a∪b)^\* = a\left(b(a∪b)^\*\right) $$ and, from this, we get: $$A = ε ∪ a\left(b(a∪b)^\* ∪ (a∪b)^\*\right) ∪ b\left((a∪b)^\*\right) = ε ∪ aB ∪ bC,$$ where $$B = b(a∪b)^\* ∪ (a∪b)^\*\\C = (a∪b)^\*.$$ Similarly, we have $$B = b(a∪b)^\* ∪ ε ∪ a(a∪b)^\* ∪ b(a∪b)^\* = ε ∪ a(a∪b)^\* ∪ b(a∪b)^\* = ε ∪ aC ∪ bC\\ C = ε ∪ a(a∪b)^\* ∪ b(a∪b)^\* = ε ∪ aC ∪ bC.$$ where, in $B$, we make use of idempotency: $x∪x = x$ (as well as commutativity $x∪y = y∪x$ and associativity $(x∪y)∪z = x∪(y∪z)$). Thus, we also have the grammar $$A → ε, A → aB, A → bC, B → ε, B → aC, B → bC, C → ε, C → aC, C → bC,A$$ with $A$ as the top-level expression, as indicated at the end.

That process is one and the same as that of deriving a deterministic finite state automaton from a regular expression.

Noting the equivalence of $B$ and $C$, this can be optimized by just setting $C = B$, to get: $$A → ε, A → aB, A → bB, B → ε, B → aB, B → bB,A.$$ This, in turn, reveals the equivalence of $A$ and $B$, so it can be optimized yet further by setting $B = A$ to get: $$A → ε, A → aA, A → bA,A.$$

That process is one and the same as that of minimalizing a deterministic finite state automaton.
> 0 votes

---
Tags: regular-languages, context-free, formal-grammars, regular-expressions
---


# Question
Title: Exists and forall in formal language definition in the case of kleene star
Let's suppose we have language $Y = \\{a^ib^j:i,j \in N^\*\\}$ defined over the alphabet $\Sigma^{}\_{} = \\{a, b\\}$

If we want to define this language $\Sigma^{\*}\_{}$ \ $\ Y$ such that we don't have the case of $a$ preceding all occurances of $b$, one way I found it defined is like this: $ \Sigma^{\*}\_{}$ \ $\ Y = \\{w\_1baw\_2 : w\_1,w\_2 \in \Sigma^{\*}\_{}\\}$ but this doesn't include $aa$ for example, which should be there as well. Also, they assume intermediate following.

Thus, I made this solution:

$\Sigma^{\*}\_{}$ \ $Y = \\{w \in \Sigma^{\*}\_{}: \exists i \in \\{1,2, ...,|w| \\}, w\_i = b \implies \exists j \in \\{i+ 1, i+2, ...,|w| \\}, w\_{j} = a\\}$

The second language is $X = \\{a, ba\\}$, if we want t get $X^\*$ which is for each $b$ to be followed by $a$, I gave this solution: $X^\* = \\{w \in \Sigma^{\*}\_{}: \forall i \in \\{1, 2, 3, ..., |w|\\}, w\_i = b \implies w\_{i+1} = a\\}$ Is this correct?

# Answer
First let $Y = \\{ a^i b^j \mid i,j\>0\\}$.You are looking for $\Sigma^\* \setminus Y$, the complement of $Y$. As you state this consists of all strings having a $b$ before an $a$, or having only $a$ or only $b$'s. Your second solution ("if there exists a $b$ then there is an $a$ at a later position") does not seem to cover the case of only $a$'s.

I would use the regular expression $\Sigma^\* \setminus Y = \Sigma^\* ba \Sigma^\* \cup a^\* \cup b^\*$. Indeed $\Sigma^\* b\Sigma^\*a \Sigma^\*$ would cover the "$b$ before $a$" part of the language, but you can verify that then there must be a $b$ immediately followed by an $a$. (Start with any pair $b\dots a$, what is after the $b$? If that is an $a$ you are done, if that is another $b$, continue from there.)

In your second question $X^\* = \\{ a,ba\\}^\*$ is indeed the language where each $b$ is followed by an $a$. Related to your first language, that is the complement if the language where two $b$ are next to another, and also we cannot end with a $b$: $\Sigma^\* \setminus (\Sigma^\* bb \Sigma^\* \cup \Sigma^\* b)$.

Interestingly you use a logical notation for your languages. You use positions $i,j$, specify letters at these positions "w\_i=a", I would use $a(i)$, and can compare the order of positions $i\<j$. This is known as the first-order specification of languages. These form a strict subset of the regular languages, to be precise the star-free regular languages. To cover all regular languages you need monadic second order logic, which also allows one to use sets of positions and quantify over them. An example if a language that cannot be expressed in first-order is $(aa)^\*$ the set of strings with an even number of $a$'s.

For $\Sigma^\* \setminus Y $ we have $ (\exists i)(\exists j) \[\\; b(i) \land a(j) \land i\<j \\;\] \lor\lnot(\exists i) b(i) \lor \lnot(\exists i) a(i)$

For $\\{ a,ba\\}^\*$ one needs to specify "successor" $j=i+1$ in the logic. When this is not a given predicate one can define it using $\<$ as follows: $i\<j \land \lnot(\exists k)\[i\<k \land k\<j\]$.

Then we get $(\forall i)\[\\; b(i) \to (\exists j)(\\;a(j) \land j=i+1\\;) \\;\]$. Your syntax may vary.
> 0 votes

---
Tags: formal-languages, automata, finite-automata
---


# Question
Title: Are all Turing machines Turing complete?
I have recently been reading up on TOC, and had this thought, which does not seem to be answered explicitly anywhere.

They way I have understood it, a system is Turing complete if it can simulate any Turing machine. But Turing machines are limited to their instructions. Does that mean not every TM is actually Turing complete? If I am not completely mistaken, only the universal TM would truly be Turing complete. Am I missing something?

# Answer
> 8 votes
Turing completeness is *not* a property of a single program or a single machine. It **does not make sense** to ask “is this machine/program/gadget Turing-complete?”

Turing-completeness is a property of a **model of computation**, which is a mathematical structure that describes a particular way of performing computation. Some examples of models of computation:

1. The set of *all* Turing machines.
2. The set of *all* Turing machines with an oracle.
3. The set of *all* general recursive functions.
4. The set of *all* valied expressions in the $\lambda$-calculus.
5. The set of *all* deterministic finite automata.
6. The set of *all* push-down atomata.

**Remark:** There are several possible precise mathematical definitions of what a model of computation actually is. We also need a precise definition of what it means to exhibit a simulation betwen models. Computability books usually skim over these notions and just show simulations on case-by-case basis.

Anyhow, say that a model $M$ is **as capabable** as model $N$ when $M$ can simulate $N$. (Notice that at all times we are talking about entire models, not single machines or programs). Say that models are equivalent if each is as capabable as the other. Finally, a model is Turing-complete if it is as capable as the Turing machine model.

In the above list, the model of Turing machines with oracles is as capable as the model of Turing machines. The models of Turing machines, general recursive functions, and $\lambda$-calculus are equally capable, whereas finite automata and push-down atomata are not as capable as Turing machines.

**Supplemental:** There is a notion that applies to a single machine, namely that of a **universal Turing machine**. It is an important concept, it plays a role in proofs of Turing-completeness, but a universal Turing machine isn't by itself "Turing-complete" – that's the wrong phrase to use.

# Answer
> 3 votes
Andrej Bauer rightly points out that in general, it does not make sense to ask whether a particular machine/program/gadget is Turing complete.

However, it does make sense when such a device is *programmable*: when it can read a specification of what it needs to do, and then do that. In other words: when it implements a model of computation. We might call a programmable device Turing complete when the model it implements is Turing complete.

(Andrej Bauer maintains that we call such devices *universal*, not Turing complete. Let's just say that I have seen the term Turing completeness being applied to devices and to programs, e.g. Minecraft, Doom, and Vim.)

In this sense, every *universal* Turing machine is Turing complete (universal): it is programmable, and it implements the model of computation of Turing machines. However, most Turing machines aren't programmable, and most programmable Turing machines do not implement a Turing complete model of computation. So the answer to your question is still: *no*.

For instance, consider a Turing machine that reads a decimal number, then a hash mark, then an arbitrary string up to the next hash mark, and then outputs Y if the string has as many characters as the decimal number indicates, and N otherwise. We can say that this Turing machine is programmable, with each of its programs being a decimal number and the meaning of each program being to decide whether the given input string has the given number of characters. Clearly, this programming language, if you want to call it that, isn't Turing complete by a long stretch, so the machine isn't, either.

# Answer
> -4 votes
I believe....

According to the Church-Turing thesis: "any algorithm that can be computed in a finite length of time, can be calculated on a Turing machine". Technically making any language that can do the same thing, 'Turing Complete'. Other computers may be faster but none can be more powerful than a Turing machine because it can do anything. Remembering Turing Machines are only a mathematical concept used to evaluate the strength of modern computing programs.

---
Tags: turing-machines, turing-completeness
---


# Question
Title: Construct a Turing machine that accepts strings $w \in \{a,b\}^*$ such that any non-empty prefix $w'$ of $w$ has $n_a(w') > n_b(w')$
## Question Description

I’m facing a problem asking me to construct a (deterministic) Turing Machine that can accept such a language:

$L = \\{ w \in \\{a,b\\}^\* \mid \mbox{for any non-empty prefix $w'$ of $w$}, n\_a(w') \> n\_b(w')\\}$

The problem isn’t expressed in English originally. To make sure I’m translating correctly, I’ll provide some example:

$a \in L$, $ab \notin L$, $aab \in L$, $aabb \notin L$, $aabab \in L$, $aababb \notin L$

## What I’ve done so far

We have an existing Turing machine which can accept a string that contains same number of ‘a’ and ‘b’ (I.e. $n\_a(w) = n\_b(w)$). I think it might be possible to modify this one to solve my problem, so I wrote this:

```
# pip install automata-lib
from automata.tm.dtm import DTM

machine = DTM(
    states={'q0', 'q1', 'q2', 'q3'},
    input_symbols={'a', 'b'},
    tape_symbols={'a', 'b', 'x', 'y', '.'},
    transitions={
        'q0': {
            'a': ('q1', 'x', 'R'),
            'y': ('q0', 'y', 'R')
        },
        'q1': {
            'a': ('q1', 'a', 'R'),
            'b': ('q2', 'y', 'L'),
            'y': ('q1', 'y', 'R'),
            '.': ('q3', '.', 'L'),
        },
        'q2': {
            'a': ('q2', 'a', 'L'),
            'x': ('q0', 'x', 'R'),
            'y': ('q2', 'y', 'L'),
        }
    },
    initial_state='q0',
    blank_symbol='.',
    final_states={'q3'}
)

```

I’m providing this python code because it’s easy to run and test. Those transitions can be explained as: $\delta(q\_0, a) = (q\_1,x,R)$ and so on.

This DTM can accept any string that begin with ‘a’ and have more ‘a’ than ‘b’. However, it doesn’t meet the condition “any prefix”. I’m stuck right here, can somebody give me a hint?

# Answer
You can build a two-tape Turing machine quite easily. The first tape will contain the input string, while the second tape will act as a counter.

The machine will work in at most $|w|$ phases, indexed from $1$. In the generic $i$-th phase it will check that $n\_a(w\_i) \> n\_b(w\_i)$, where $w$ is the prefix of the input containing the first $i$ symbols.

During this process, the second tape will contain only $c$s (the specific symbol is not important, I'm using $c$ for the sake of readability) and its head will be placed on the last $c$ (if any). We will preserve the following invariant: at the end of the $i$-th phase, the number of $c$s on the second tape will be exactly $n\_a(w\_i) - n\_b(w\_i)$. As soon as this quantity becomes $0$ (i.e., the tape becomes empty), the machine rejects. If $|w|$ phases are completed (i.e., the whole input has been processed) and the second tape is not empty, the machine accepts.

The machine works as follows:

1. If the current (i.e., first) symbol on the first tape is not $a$, reject.
2. If the current symbol on the first tape is blank, accept.
3. If the current symbol on the first tape is $a$:
    * Move the second head to the right.
    * Write $c$ on the second tape.
4. If the current symbol on the first tape is $b$:
    * Write a blank on the second tape.
    * Move the second head to the left.
5. If the current symbol on the second tape is blank, reject.
6. Move the first head to the right and repeat from step 2.
> 0 votes

---
Tags: turing-machines, automata
---


# Question
Title: Maximum weighted matching in Bipartite Graph
I was solving a coding question which boiled down to this problem.
Given a bipartite graph $G=\\{V\cup U,E\\}$. There is a positive value given for every node in $U$.
Now we have to find the matching in which the sum of value of every node in $U$ which is also in the matching is maximum.
Consider an example, Let valueArray for $U = \[1,2,3\]$ . If in a matching nodes 0 and 1 of array are in matching the value of matching will be valueArray\[0\]+valueArray\[1\] = 3.
We have to find this maximum possible value of all possible matching given the graph and valueArray.
Matching nedd not be of maximum cardinality.

# Answer
You can turn the problem into an edge-weighted variant by setting the weight on edge $vu$ to be $\texttt{valueArray}(u)$ where $w(vu) = \texttt{valueArray}(u)$ is the value of $u \in U$.

Now a maximum weight matching in this graph is a matching which maximizes the sum of the values of the nodes in $U$. Note that you can flip the sign of all values to obtain a minimization problem, and if you add all missing edges with $w(e) = 0$. Now you have a *minimum-weight perfect matching* problem.

Ps, this is called the *assignment problem* and can be solved using LP, by the Hungarian algorithm (augmenting paths), or the *min-cost* max flow algorithm.
> 2 votes

---
Tags: graphs, bipartite-matching
---


# Question
Title: What is the complexity of problems with randomized polynomial time verification?
Imagine a Problem $A$ with input size $n$ for which you can get a proof certificate (polynomial number of bits).

Next you try to use this string to verify if your problem is solved or not.

You know that verification gets almost as good as if you'd try to verify an $NP$-problem in the sense that the verification process itself is trying to solve a $co-$$RP$-Problem, meaning that everytime you get a proof string for $A$ the (polynomial time-) verifier will output "YES" with probability $1$ when it is correct and "NO" with probability $1/2$ when it is not a correct proof.

However, the verifier needs a polynomial amount of random bits $r(n)\in O(n^k)$ for this to make sure that the probabilities are as written above for **one** attempt of verification. Maybe think of all possible random bit strings as the search space which would be all "YES" if you had a correct proof and had to verify for every single possible random string (otherwise at least half of them were "NO").

For this question, to understand what type of complexity class I am actually trying to learn about here, I read about the $PCP$ theorem and how you can characterize $NP=PCP\[O(log(n)),O(1)\]$. On Wikipedia they also mentioned a weaker result $NP=PCP\[n^3, 1\]$ and that $PCP\[poly(n),poly(n)\]=NEXP$ which confuses me, probably because there is a mistake in my understanding of $PCP$. Here I was wondering if it is true that $NP=PCP\[n^3,O(n^k)\]$ (?) and would then $A\in NP$ for $n^3$ random bits?

Most importantly though, what complexity class does $A$ belong to and how do $(co-)RP$, $(co-)NP$, $NEXP$ and $PCP$ relate to $A$? Is $A$ well known?

**Edit:** To make this more precise in terms of the $PCP$ characterization: If $A$ only needs random bit strings of size $n^3$ then I think that $A\in PCP\[n^3,O(n^k)\]$, but we do not only use a portion of the proof of size $O(n^k)$, but the whole proof is at maximum of size $O(n^k)$. I don't know if that makes a difference since when reading about $PCP$ I read that you don't query every bit that there is, but a fraction of the available bits. Also $A$ uses non-adaptive queries.

# Answer
> 0 votes
Alright, I think I finally found what I was searching for. What I was trying to describe turns out to be the complexity class $MA$ because the proof is of polynomial size and we use the full proof and a polynomial amount of bits. It's similar to $NP$ but since we don't know whether $MA=NP$, only that $NP\subseteq MA$, we cannot say if $A\in NP$.

If anyone disagrees and wants to correct my answer or answer the question, I would be glad.

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


title: Proof About P!=NP

text:
# Question
Title: Proof About P!=NP
**Problem description:**
Given a P-time function(program) pchk:{0,1} ⃰ -\> {0,1}. A function f,
f:pchk×ℕ -\> {0,1}: f can only simulate pchk with arbitrary argument x.
And, f(pchk,n)==1 iff ∃x, |x|\<=n, pchk(x)==1.
Obviously, the time complexity of f is in O(2^N) (the length of pchk can be
assumed a constant). f∈NP and f∉P. Therefore, P!=NP. QED.
There must be something wrong with such a proof, but I cannot figure it out.
**Note:** I read **Naive argument that P ≠ NP** in **Similar questions**. The difference
is that the function f is 'defined' to be in O(2^n).

# Answer
You didn't prove any lower bound here, which is required to imply that $P\neq NP$, but rather you have shown an upper bound.

So essentially you have shown that the problem is in $Exp$ but you haven't proven that the problem is *not* in $P$
> 1 votes

---
Tags: complexity-theory
---


title: Decision tree to check 2 rectangles

text:
# Question
Title: Decision tree to check 2 rectangles
Given two disjoint rectangles $(a,b\]\times (c,d\]$ and $(e,f\]\times (g,h\]$ in $\mathbb{R}^2$ how can I check with a decision tree of least depth if a given point $(x,y)$ lies within the union of the rectangles?

I think that I need 4 decisions to check if $x$ is within $(\min(a,e),\max(b,f)\]$ and if $y$ is within $(\min(c,g),\max(d,h)\]$. However I am stuck afterwards, as we don't know how exactly the rectangles are positioned (they could overlap in $x$ or $y$ coordinates and we don't know which of them is to the 'left' and which to the 'right').

Thank you.

# Answer
If no preprocessing of the rectangles is allowed, in the worst case you need $8$ comparisons, full stop. That's because there are $8$ independent coordinates and the answer depends on them.

---

If preprocessing is allowed, you can determine a vertical or horizontal line by one of the sides that separates the two rectangles. After comparing to this line, you need additional $3$ or $4$ comparisons to check insideness.

I don't think that you can do any better with comparisons alone. (By extending the sides, you delimit $25$ rectangular regions in the plane, and it takes $\sim4.64$ bits to number them.)

---

If arithmetic is allowed, the sign of the expression $(x-a)(x-b)$ combines two comparisons in one.
> 1 votes

---
Tags: algorithms, binary-trees, decision-problem
---


title: A (False) Proof That ℙ≠ℕℙ

text:
# Question
Title: A (False) Proof That ℙ≠ℕℙ
**Why the following proof is invaid?**

Using C-like pseudo-program:
**Definition**: bool S(Func, UInt): S(f,n)==true iff ∃x, x\<=n, F(x)==true
F is defined in ℙ as a certificate function, so S is in ℕℙ.
Now, if S∈ℙ, then, there exists a function F∈ℙ:
bool F(UInt n) {
return !S(F,n);
}
Given an UInt m:
If F(m)==true, then, S(F,m)==false. From definition of S: ∀x\<=m, F(x)==false.
This contradicts the premise F(m)==true when x==m.
If F(m)==false, then, S(F,m)==true. From definition of S: ∃x\<=m, F(x)==true.
Assume ∃m',m'\<m, F(m')==true, but previous proof showed this will cause
contradiction when m\>=1.
Conclusion: As x\>=1, S and F cannot be both in ℙ, thus ℙ≠ℕℙ.
QED.
**Note**: This proof is similar to the Halting Problem proof.

# Answer
> 2 votes
$\mathsf{P}$, $\mathsf{NP}$ or $\mathsf{EXP}$ are not sets of functions, but sets of problems. As an example, consider the following problem $\texttt{SORTED}$:

> Input: an array $a = \[a\_1, …, a\_n\]$.
>
> Question: is $a$ a sorted array?

This problem can easily be solved by a polynomial time function, something that would look like:

```
is_sorted(a):
    for i = 1 to n - 1:
        if a[i] > a[i + 1]:
            return false
    return true

```

That proves that $\texttt{SORTED} \in \mathsf{P}$: for a problem, there EXISTS a function running in polynomial time that solves this problem.

But you could also do it in a very stupid, complicated way, something like:

```
is_sorted(a):
    n = |a|
    if n ≤ 1:
        return true
    if n = 2:
        return a[1] ≤ a[2]
    for each proper subset I ⊊ {1, …, n}:
        define b as {a[i] | i ∈ I}
        if !is_sorted(b):
            return false
    return true

```

Now this function is correct (it will give the right answer to the question), but its running time is at least exponential, even with memoization.

Does that mean that $\texttt{SORTED} \in \mathsf{EXP}$? Absolutely! Because we found an exponential running time algorithm solving the problem.

Does that mean that $\texttt{SORTED}\notin \mathsf{P}$? Absolutely not! We previously proved that $\texttt{SORTED}\in \mathsf{P}$.

What I wanted to show here is that the **same** problem can results in **different** algorithms. But when we try to classify into complexity classes, we classify **problems**, not algorithms. As such, we want to find the best algorithm solving one problem.

What you tried to prove in your (complicated to understand because you confuse problems and functions) proof is that there exists an exponential time function solving a $\mathsf{NP}$ problem. But that does not mean that there is not a polynomial time function solving it!

# Answer
> 0 votes
You may or may not have shown that one particular function doesn't provide valid certificates (may or may not because it's not quite clear what you are saying). That's true for most functions. You haven't shown that no function *can* be used.

---
Tags: complexity-theory, time-complexity, complexity-classes
---


title: Maximum flow in integer flow network

text:
# Question
Title: Maximum flow in integer flow network
Let's say you have a maximum integer flow function in a network with 7 **directed** edges, meaning the flow cannot be increased anymore. The capacity of each edge is then increased by one. The capacity of all edges is always an integer, and so is the flow. Is there an algorithm that can find a maximum flow in this new network with complexity O(|E|), where E is the set of edges? If so, what would this algorithm look like?

# Answer
> 1 votes
Since you only have $7$ edges (and hence at most $8$ vertices reachable from the flow source) any flow algorithm whose runtime is independent of the edge weights will take time $O(1) = O(|E|)$. See, for example, the Edmonds-Karp algorithm.

# Answer
> 1 votes
In case the **7** was entered accidentally, and the question was whether a max flow can be computed in time $O(m)$ provided that we have a max flow already, and simply increase all capacities by one.

The answer is that the best max flow algorithm is $\omega(m)$ for graphs of unit capacities, which means that if you start out with only capacity $0$ for your graph, the empty flow $f \colon e \mapsto 0$ is a max flow. Then if you increase all capacities with 1, you have a unit capacity flow network. An algorithm with time $O(m)$ would be a ground-breaking achievement at this time (but still possible).

---
Tags: graphs, algorithm-analysis, network-flow, dag
---


# Question
Title: Traveling salesman problem on an incomplete graph
In the standard framing of the traveling salesman problem, we're given a complete graph, meaning every pair of vertices has an edge in between them. And this might be close to accurate when the salesman is flying between cities. If he's driving however, road networks tend not to be dense. You can drive from any city to any other city, but often you'll be hitting other cities on the way.

As an example, the picture below shows the graph of the road network for Ukraine. If you drive from Chernihiv (way North) to Odesa (way South), you will hit Kyiv and other cities on the way.

So, what if a salesman wants a driving tour that visits all cities in Ukraine? One thought is to construct the transitive closure of the road network graph and then apply standard traveling salesman algorithms to it.

But, this will include tours that are obviously sub-optimal because they'll (for example) go from Chernihiv to Odesa and then back to Kyiv, instead of simply stopping at Kyiv on the way.

Is there a way to take the structure of the graph into account while devising a tour that covers all cities? Of course, we can't guarantee that a Hamiltonian tour exists and we could be forced to visit some cities multiple times.

# Answer
> 1 votes
Let $G$ be your original graph and let $G'$ be its transitive closure.

Let $C'$ be an optimal tour in $G'$, and let $C$ be the tour in which you replace each edge $(u,v)$ of $C'$ with a shortest path between $u$ and $v$ in $G$. The tour $C$ is optimal in $G$ (even if it visits a city more than once).

To see this, let $w(C')$ (resp. $w(C)$) denote the cost of $C'$ (resp. $C'$). Let $w^\*$ be the cost of an optimal tour of $G$. Clearly $w(C) \ge w^\*$. Since all tour in $G$ are also tours in $G'$, we have $w(C') \le w^\*$. Finally the cost of $C$ is at most the cost of $C'$ by construction. Therefore: $$ w^\* \le w(C) = w(C') \le w^\*. $$

---
Tags: graphs, np, approximation, traveling-salesman
---


# Question
Title: is there an O(n^2) approach to this problem?
Given an array of N elements, I need to split it into k subarrays, where k can be between 2 \<= k \<= N. A sub-array's score is determined by:

(left boundary point - right boundary point of the subarray)^2 + max(subarray).

Left boundary point would be the index of the element and right boundary point would be the (index of the element + 1) if that makes sense. You can think of them as points where you split the array

Find an algorithm in O(n^2) that calculates the sum of the scores of all subarrays such that it is the lowest possible score obtained.

For example:

array = \[5,3,4,9,2,8\]

subarrays = \[5,3\], \[4,9,2\], \[8\]

score of the first subarray = (2-0)^2 + (5) = 9

score of the second subarray = (5-2)^2 + (9) = 18

score of the third subarray = (6-5)^2 + (8) = 9

sum of all the scores of all the subarrays = 36.

What I tried to do:

I tried to choose the partitions of the array such that: (left boundary point - right boundary point of the subarray)^2 \< max(subarray) but also avoid k = N as they wont give me the lowest score (something i observed through trial and error).

but I am not sure if that is right way to go about it. Thanks!

# Answer
> 0 votes
Dynamic programming gives an $O(n^2)$ solution. Consider partitioning the array recursively to compute the scores of each possible partition. In particular, notice that

$$ OPT(\[a\_1, ..., a\_n\]) = \min\_t \text{score}(\[a\_1, ..., a\_t\]) + OPT(\[a\_{t+1}, ..., a\_n\]) $$

This naturally leads us to a recursive approach.

```
min_partition(arr, index):
    if index == len(arr) - 1:
        return 1 + arr[-1]
    if dp[index] != max_int:
        return dp[index]
    score = max_int
    for i in range(index+1, len(arr)):
        score = min(score, (index-i)**2 + max(arr[index:i]) + min_partition(arr, i))
    dp[index] = score
    return score

```

As a slight optimization to Nathaniel's answer, a pre-processed data structure such as a sparse table can be created in $O(n \log(n))$ time and queried in $O(1)$ time to obtain $\max$ of any range. Asymptotically, however, the algorithm is still $O(n^2)$ since we solve each subproblem exactly once and each subproblem takes $O(n)$ time to solve. In particular,

$$T(n) = \sum\_{i=1}^n i = \frac{n(n+1)}{2} = O(n^2)$$ (p.s. this is my first post, so I'd love feedback on how I can improve as a contributor!)

# Answer
> 0 votes
Given an array $A = \[a\_0, …, a\_{N-1}\]$, let us define some notations:

* for $0\leqslant i \< j \leqslant N$, $M\_{ij}$ is the maximum element in $\[a\_i, a\_{i+1}, …, a\_{j-1}\]$;
* for $0 \< j \leqslant N$, $S(j)$ is the minimum total score of a splitting of $\[a\_0, …, a\_{j-1}\]$ into subarrays (with no condition on the number of subarrays);
* for $0 \leqslant i \< j \leqslant N$, $T(i, j)$ is the minimum total score of a splitting of $\[a\_0, …, a\_{j-1}\]$ into subarrays, with the last subarray being $\[a\_i, …, a\_{j-1}\]$.

First, notice that a matrix containing the values $M\_{ij}$ can be computed in $\mathcal{O}(N^2)$ time. Then, find relations to compute:

* $T(j, j+1)$ given $S(j)$;
* $T(i, j + 1)$ given $T(i, j)$, for $i \< j$;
* $S(j+1)$ given $T(0, j+1)$, $T(1, j+1)$, …, $T(j, j+1)$

And then find a way to compute all this in $\mathcal{O}(N^2)$ time. The minimum possible score can be expressed using the above values, can you see how?

After that, an algorithm computing this score can be easily modified to find the splitting to obtain this score.

# Answer
> 0 votes
Very simple via dynamic programming (which is just a big name for a very simple principle).

If you have one single array element, you have no choice but taking that element as the only subarray.

If you have k ≥ 2 array elements, then you can take all k elements as the only subarray. Or you take 1 element as the last subarray and the first k-1 elements optimally arranged into subarrays. Or you take 2 elements as the last subarray and the first k-2 elements optimally arranged into subarrays. Or you take 3 elements as the last subarray and the first k-3 elements optimally arranged into subarrays. And so on until you try taking the last k-1 elements as the last subarray and the first element optimally arranged into subarrays.

There are k choices, and you take the best choice. You do this for k = 2, k = 3, k = 4, and so on until k = n, and then you are done. For each k, you store the total cost of the optimal split into subarrays, and the length of the last subarray in the optimal split, so you can easily output the total cost of all items and how to split them.

Since calculating the best cost for each of these cases is constant in time, and there are about n^2/2 cases to consider, the time is quadratic.

However, in many cases you can do a lot better than O(n^2). For example, if you try to find out how to best arrange the k first items when you know how to do the k-1 first, and item #k has a value of 10, then you won't make that item part of a subarray with six or more elements: If you did, then turning it into a one-item subarray (cost 10 + 1^2 = 11) and reducing the size of a six item subarray by one (savings 6^2 - 5^2 = 11) means you never use a six item subarray at the end, and only check 5 cases instead of k. For item #k calculate min (k, value / 2), let s be the sum of all these values, and you can solve the problem in O(s).

You will probably be able to make similar savings if you have very large values, except instead of splitting subarrays you will try to join them, because that way a very large second-largest value doesn’t count anymore. Say you have thousand items, and two items with largest values 2,000,000 and 1,500,000. They must be in the same subarray, because then the total cost is at most 2,000,000 + 1000^2 instead of at least 2,000,000 + 1,500,000.

---
Tags: dynamic-programming, recursion, arrays
---


title: Manchester encoding

text:
# Question
Title: Manchester encoding
How clock rate is doubled in the Manchester encoding? clock cycle depends on bit interval time . In NRZ , Manchester encoding and every other Encoding the clock cycle time is same as bit interval is same.

How it is doubled clock rate?

ISRO | ISRO CS 2020 | Question 67 To send same bit sequence, NRZ encoding require (A) Same clock frequency as Manchester encoding (B) Half the clock frequency as Manchester encoding (C) Twice the clock frequency as Manchester encoding (D) A clock frequency which depend on number of zeros and ones in the bit sequence

Some one please tell why clockrate is doubled in Manchester encoding, and band width also..

NRZ, Manchester and others maintain same clock cycle time as in all bit interval time is same ??

Why?

Why?

Why?

# Answer
> 1 votes
Sorry, your question is not very clear, but if I'm reading it correctly, you're asking why the clock rate of Manchester encoding is double that of the bit rate.

It depends on what you mean by "clock rate".

If you understand a full clock cycle as "high followed by low", or "low followed by high", then the bit rate of Manchester encoding is the same as the clock rate, in the sense that one bit is transmitted per clock cycle. Transmitting a `0` (using the IEEE 802.3 convention) is a high followed by a low, and transmitting a `1` is a low followed by a high.

However, if you understand the "high followed by a low" to be two symbols corresponding to one bit, then the *baud* rate (i.e. the number of *symbols* transmitted per second) is twice that of the *bit* rate.

Any circuitry that encodes or decodes Manchester encoding needs to be able to work at this higher frequency (propagation delay, switching speed, etc), and any accurate reconstruction of the signal requires at least one sample per symbol. I think that's why electronics engineers and signal processing people tend to think in terms of this higher frequency.

It's also why Manchester encoding is not used for modern high-speed communication; compare with 8b/10b for which the baud rate is only 25% higher than the bit rate. Still, Manchester encoding is still used. Its robustness and simplicity makes it popular for medium-speed and low-power protocols such as RFID and NFC.

---
Tags: computer-networks
---


# Question
Title: For a logic gate to be universal, must it necessarily be able to perform duplication?
It is said that a gate that can simulate AND and NOT is universal and able to recreate any classical circuit. I was looking at some of the circuits simulated by NAND, and for some of them, we need to split the output of a gate and direct each of the splits to other NAND gates (see the area circled in red):

If we make the restriction that all gates are reversible (in particular, we require fixed input/output size), does the AND/NOT criterion still hold? Is the ability to "split" outputs (i.e., a gate that can do AND, NOT, *and* duplicate a $0$ or $1$, e.g. $(0,0,1) \rightarrow (0,1,1)$ ) a necessary/sufficient condition for universality?

# Answer
I'm not sure what you're asking, precisely, but it's certainly not true that a reversible universal gate requires the number of set bits in the output to be the same as in the input. Toffoli gates do not have that property, for example.

**EDIT**

Thanks for the clarification. The answer to your question is that any reversible circuit must have at least as many output lines as input lines. As an exercise, prove this. Try using the pigeonhole principle.

So what happens if you need a reversible circuit with fewer output lines than input lines? You just add output lines, the values of which are irrelevant. The circuit still computes what you need it to, it also happens to compute more stuff that you don't care about.

So what I think you're asking about duplication is can there be *more* output bits than input bits? The answer is "kind of", and it comes down to what model of reversibility you care about.

Such a circuit can clearly be *logically* reversible. But can it be *physically* reversible? I'm not a hardware designer, and I don't know.
> 2 votes

# Answer
### "AND NOT" Criterion

> If we make the restriction that all gates are reversible (in particular, we require fixed input/output size), does the AND/NOT criterion still hold?

Yes (well sort of).

Sort of, because AND is not reversible. To simulate it with a reversible circuit you would have to implement a function F such that F(q0,q1,q2) = (q0,q1, q0^q1 XOR q2) where qs are the input bits. q2 then must be restricted to be 0 to run a proper computation.

Yes, because every gate (whether reversible or irreversible) can be constructed from and and not. That implies all the subset of reversible gates can be constructed.

### Splitting

> Is the ability to "split" outputs (i.e., a gate that can do AND, NOT, and duplicate a 0 or 1, e.g. (0,0,1)→(0,1,1) ) a necessary/sufficient condition for universality?

It's neither necessary nor sufficient.

First, just wanted to clarify: For reversible computing, any particular function must be reversible. AND is not reversible, so you must adjust it (such as the F that I described above). This adjustment is a splitting of both inputs along with an XOR operation. Splitting alone will not make it reversible.

Once AND has been adjusted that way, AND + Not are (I think) universal. What makes me think that? The TOFFOLI gate

###### Splitting is Not necessary

The TOFFOLI gate is universal, reversible, and doesn't require any splitting operations.

###### Splitting is Not Sufficient

The Identity gate is not universal, no matter how many splittings you do.
> 0 votes

---
Tags: logic, circuits, boolean-algebra
---


# Question
Title: Function which describes an optimal data structure for a bounded number of query operations?
Given an ordered sequence of $n$ elements, you have to choose a family $A$ of subsets of consecutive elements, such that each subset of consecutive elements (not necessairly in $A$) can be represented as a disjoint union of at most $k$ elements of $A$. Let $A$ be the minimal set with this property, define the function $f(n, k):=|A|$. Now I am really interested in how this function behaves. Notice that $A$ actually describes a data structure which is capable of answering most kinds of interval queries (the sequence of elements have to be elements of a monoid) in $k$ "operations". I've discussed it with some of my colleagues and we have noticed the following:

Obviously $f(n, 1) = {n \choose2}$.

Now more interestingly, $f(n, 2) = O(n \\; log(n))$, and the structure of $|A|$ vaguely resembles the standard implementation of a sparse table.

Some also interesting upper bounds are $f(n, log(log(n))) = O(n \\; log(log(n)))$, you can build a tree which resembles the van Emde Boas data structure.

And for $f(n, 2log(n) - 2)$ = $O(n)$ you can use the segment tree data structure. Asymptotically, $f(n, O(log(n))) = O(n)$, this is tight.

Now, I am interested in whether anyone has seen something resembling this function anywhere before? Seems like many data structures can be viewed of as optimal constructions of $A$ for different values of $k$? It would be really helpful if someone could just point me to a reference.

# Answer
> 5 votes
This question is answered by Alon and Schieber \[1\]. For a constant $k \geq 2$, the asymptotic bound is $f(n,k) = \Theta(n \lambda(k,n))$ where $\lambda(k,\cdot)$ is a certain slowly growing function. Concrete values are:

$ \begin{equation} f(n,2) = \Theta(n \log n) \\ f(n,3) = \Theta(n \log \log n) \\ f(n,4) = \Theta(n \log^\ast n) \end{equation} $

The upper bound is proven by a simple recursive algorithm.

For non-constant $k$, it is proven that $f(n,O(\alpha(n))) = \Theta(n)$ where $\alpha(n)$ is the inverse Ackermann function. This is best possible for the linear number of subsets.

* \[1\] Alon, Noga, and Baruch Schieber. “Optimal Preprocessing for Answering On-Line Product Queries,” 1987.

---
Tags: complexity-theory, data-structures
---


# Question
Title: Finding the power of a number without a library pow function
I am solving a problem that involves finding a `pow(x, n)` without using a `pow` library function.

Following is the algorithm that works (apart from negative `n` and some edge cases) but trying to understand the math logic behind it.

```
2^5 -> x = 2, n = 5 (101)

```

The idea is to multiply the answer with `2 ^ (2 ^ i)` such that `i` is ith bit of the exponent `n`.

So we can say: `2^5 = 2 ^ (2 ^ 0) * 2 ^ (2 ^ 2)`. Means: we need to multiply the answer with when the ith bit is 0, and 2 (set bits in `101`)

```
n = 101, i = 0: ans = 2 * 1 = 2, x = 2 * 2 = 2 ^ 2 = 4
n = 010, i = 1: ans = 2, x = 4 * 4 = 2 ^ (2 ^ 2) = 16
n = 001, i = 2: ans = 2 * 16 = 32, x = 16 * 16 === 2 ^ (2 ^ 0) * 2 ^ (2 ^ 2)

```

This seems to work however the following example doesn't

```
2^8 -> x = 2, n = 8 (1000)

```

So we can say: `2^8 = 2 ^ 4 * 2 ^ 4 == 2 ^ (2 ^ 2) * 2 ^ (2 ^ 2)`. Means: we need to multiply the answer with when the ith bit is 2, and 2, however there's only ONE set bit at i = 3.

The algo

```
  double foo()
  {
    double ret = 1;

    while (n)
    {
        if (n & 1)
        {
            ret *= x;
        }

        x *= x;
        n >>= 1;

    }

      return ret;
   }

```

also is the time complexity going to be O(logN)?

# Answer
> 0 votes
Let $k$ be the number of binary digits of $n$ and let $n\_i$ denote the $i$-th least significant digit in the binary representation of $n$, counting from $1$.

$$n = \sum\_{i=1}^{k} n\_i 2^{i-1}$$

Therefore: $x^n = x^{\sum\_{i=1}^{k} n\_i 2^{i-1}} = \prod\_{i=1}^{k} x^{n\_i 2^{i-1}}$.

At the beginning of the $j$-th iteration of the algorithm `x` is equal to $x^{2^{j-1}}$ and `res` is equal to $\prod\_{i=1}^{j-1} x^{n\_i 2^{i-1}}$.

At the end of the $j$-th iteration of the algorithm:

* `res` is equal to $\prod\_{i=1}^{j} x^{n\_i 2^{i-1}}$, which is obtained by multiplying `x` with the current value of `res` when $n\_j=1$. This the same as unconditionally performing the following product: $$ x^{n\_j 2^{j-1}} \cdot\prod\_{i=1}^{j-1} x^{n\_i 2^{i-1}}. $$
* `x` is equal to $x^{2^j}$ and is obtained by multiplying `x` with itself, i.e., $x^{2^j} = x^{2^{j-1}} \cdot x^{2^{j-1}}$.

# Answer
> 0 votes
Calculating powers with integer exponents: You use these formulas: x^0 = 1. x^(k+1) = x^k * x. x^(2k) = (x^k)^2. x^(-k) = 1 / x^k.

Then you implement via recursion:

```
if (k == 0) return 1.0;
if (k < 0) return 1.0 / myPower (x, -k);
if (k % 2 == 1) return myPower (x, k-1) * x;
/* if (k % 2 == 0) */ { tmp = myPower (x, k/2); return tmp * tmp; }

```

That may be a bit slow due to recursion so you then refactor your code to make it fast.

---
Tags: algorithms
---


# Question
Title: Language to regular expression to prove it is regular
I'm trying to find a regular expression to describe the following language:

$\\{a^n xa^n | n≥1,x ∈ Σ^\* \\}$

where $Σ$ = {a,b}

So far I've come up with

$aa^\* (aUb)^\* aa^\*$

but I don't think that accounts for $n$ being the same.

# Answer
> 2 votes
Your language consists of all words that start with $a$ and end with a different $a$, which yields the regular expression $a(a+b)^\ast a$. Note that every word that at first seems *unbalanced*, e.g. $a^n y a^{n+k}$ for some $y \in \Sigma^\ast$ and $k \> 0$ (analogously too many $a$ on the left) can be regrouped to $a^n (ya^k) a^n$ or $a (a^{n-1} y a^{n-1+k}) a$, the middle part in parenthesis being always a suitable choice for your infix $x \in \Sigma^\ast$ in the definition of your language.

# Answer
> -1 votes
Your problem is that your language is not a regular language, so you are not going to find a regular expression, whatever you try. Neither is anyone else.

To see very easily that it is not regular: A regular language has a finite state machine. Now take the strings a^n b for every possible integer n. What is the shortest string to add to create a string from your language? Obviously you have to add a^n to get a^n b a^n which is in the language. Since there are infinitely many different answers, your state machine has infinitely many different states.

(In general, the rule is: For every prefix w, calculate the set of suffixes x such that wx is in the language L. If the number of different suffix sets is finite, then your language is regular, otherwise it isn't. I looked at "the shortest string in each suffix set" instead. If there are infinitely many different such shortest strings, then there are infinitely many suffix sets, so the language is irregular as well. )

PS. I read your "x" as a single symbol. Instead it is any sequence of symbols. Which makes your question a trick question, because every single sentence of at least two characters starting and ending in a belongs to the language. Say you have a^20 x a^19 - just take n = 1, and the *string* x is a^19 x a^18. The "n ≥ 1" is irrelevant. So a regular expression is trivial:

```
a (a|b)* a

```

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


# Question
Title: Finding a family of graphs that displays a certain characteristic
I've read that the number of distinct paths in a graph can be exponential in relation to the number of vertices, later I encountered a problem which I spent some time trying to solve on my own.

The problem asks to find a family of undirected graphs in such a manner that every graph has a pair of vertices $s$ and $t$ such that the number of simple paths from $s$ to $t$ is at least $\Omega(2^n)$, where $n = |V|$.

I've tried applying this to a clique and a circular graph, but didn't really manage to find two (different) vertices that have this characteristic.

Not sure how to direct my thoughts from here.

# Answer
> 4 votes
Consider a clique $G=(V,E)$ on $n$ vertices and any two distinct nodes $s$ and $t$.

Any permutation $v\_1, v\_2, \dots, v\_{n-2}$ of the vertices in $V \setminus \\{s,t\\}$ induces a simple path from $s$ to $t$, namely $\langle s, v\_1, v\_2, \dots, v\_{n-2}, t \rangle$. Therefore the numebr of paths from $s$ to $t$ is at least: $$ (n-2)! = \Omega\left(\sqrt{n} \cdot \left( \frac{n-2}{e}\right)^{n-2}\right) = \omega(2^n), $$ where we used Stirling's inequality and, for $n \ge 14$: $$ \left( \frac{n-2}{e}\right)^{n-2}= 2^{(n-2) \log \frac{n-2}{e} } \> 2^{(n-2) \log \frac{12}{3} } = 2^{2(n-2)} \> 2^n. $$

As Pål GD points out, you can use an easier argument to get a weaker bound which is still enough for you needs. Fix an arbitrary order of vertices in $V \setminus \\{s,t\\}$ and notice that any subset $X$ of $V \setminus \\{s,t\\}$ induces a path from $s$ to $t$ that traverses the vertices in $X$ according the chosen order. Therefore there are at least $2^{n-2} = \Omega(2^n)$ paths from $s$ to $t$.

---
Tags: graphs, path
---


# Question
Title: Understanding this verifier runs in plynomial time
I'm self studying complexity theory and want to prove that SAT is in NP, so I came up with this verifier for SAT:

\begin{align\*} V &= \text{"On input $w = \langle \phi, c \rangle$}:\\ & \quad \text{1. Test whether $c$ is an assignment for $\phi$} \\ & \quad \text{2. Test whether $c$ satisfies $\phi$}\\ & \quad \text{3. If both pass, accept; otherwise, reject."} \end{align\*}

It seems that this is supposed to be an easy question but how can I show that this runs in polynomial time in the size of the input, i.e., $|\langle \phi, c\rangle|$?

# Answer
> 1 votes
You just need to show that you can evaluate $\phi$ in polynomial-time. This is clearly true for any reasonable encoding of $\phi$ and $c$, but the details depend on the specific encoding you choose.

One of the many possible "natural" encodings could be as follows: $\phi$ is encoded by specifying the number of variables $n$, the number of clauses $m$, and list of clauses, where each clause is a list of literals. Each literal is just a pair whose first element is the index (between $1$ and $n$) of a variable and the second elements is a boolean that encodes whether the variable is negated. The assignment $c$ is an array of $n$ boolean values, the $i$-th value is the truth value of the $i$-th variable.

Assume that you already checked that the input is a valid encoding.

Then you can just scan the list of clauses. For each clause, scan the list of literals. For each literal check whether the literal is positive and the corresponding variable is set to true in $c$, or the literal is negated and the variable is set to false. If no literal in the clause satisfies the above conditions, reject. If you run of clauses without rejecting, accept.

This takes time proportional to $m+n$ on the RAM model. If you want to use a Turing machine, describing the algorithm is more annoying and depends on even more fine-grained details of the encoding, but it can be done.

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Split matrix by groups of columns but *capture all combinations of X columns* for some X
Say I have a big matrix, ~50000 rows, ~80000 columns. I want to split it up and solve subproblems on different machines (horizontal scaling).

But I need to make sure every column can be combined with every other column.

Thinking about, I can't really think of an efficient algorithm that could split the matrix up and still do all combinations, without the cost of i/o overcoming the benefits of splitting the problem up. I am sure this is a solved problem, does anyone know how to do this?

# Answer
I am not sure what you mean by "combining" exactly. I assume you want the parallel threads to have read and write access to all data without maintaining multiple copies.

I have dealt with a similar problem while working with large networks in a GPU environment (for doing multi-device scaling), this answer will be apt for CUDA environment, but I am sure OMP and MPI have similar mechanisms.

CUDA supports unified memory where the i/o overhead is managed at the backend. So, a simple solution is to use `cudaMallocManaged` to initiate unified memory and allocate the whole matrix in it. Now each GPU connected to the CPU can access all of the data available at this location. Naturally, lesser the amount of conflicted accesses (resulting in race conditions and page faults), better the performance. There are also some `cudaMemAdvice` flags to tell the compiler if the shared data is going to be read mostly or written mostly.

Source: https://docs.nvidia.com/cuda/cuda-runtime-api/group\__CUDART\__MEMORY.html
> 1 votes

---
Tags: algorithms, distributed-systems, matrices
---


# Question
Title: Question about a proof of the existence of unsatisfiable linear k-CNFs for any k
Today I am reading paper Unsatisfiable Linear k-CNFs Exist, for every k by *Dominik Scheder*, 2007. But I have some problem to understand the proof of Theorem $3.2$.

I don't know how to understand the underlined part:

1. How do we create variable-disjoint copies of $F$?
2. Why is the number $2^m$?

> **Theorem 3.2.** For any $k\in\Bbb N\_0$, there are unsatisfiable linear $k$-CNFs.
>
> **Proof.** We prove this by induction on $k$. For $k=0$, the formula $F=\\{\\{\\}\\}$ containing only the empty clause is linear and unsatisfiable. For the induction step, let $F=\\{C\_1,\cdots, C\_2\\}$ be an unsatisfiable linear $k$-CNF. We will construct an unsatisfiable linear $(k+1)$-CNF formula $F'$. Created $m$ new variables $x\_x, \cdots, x\_m$. For a clause $D=\\{u1, \cdots, u\_m\\}$ with $u\_i\in\\{x\_i, \bar x\_i\\}$, define $$F\otimes D := \\{C\_i\cup\\{u\_i\\}\mid i=1,\cdots, m\\}\ .$$ $F'$ is a linear $(k+1)$-CNF formula, and every assignment satisfying $F\otimes D$ satisfies $D$. Create $2^m$ variable-disjoint copies $F\_1, \cdots, F\_{2^m}$ of $F$, i.e., $\text{vbl}(F\_i)\cap\text{vbl}(F\_j)=\emptyset$ for $i\not=j$. By choosing $2^m$ different sign patterns, we create $2^m$ distinct $m$-clauses $D\_1, \cdots, D\_{2^m}$ over the variables $x\_i$. The formula $\\{D\_1, \cdots, D\_{2^m}\\}$ is unsatisfiable. Hence, $$ F' := \bigcup\_{i=1}^{2^m}F\_i\otimes D\_i$$ is unsatisfiable, as well. Clearly, $F'$ is a linear $(k+1)$-CNF. $\Box$

Here is the image of the quotation above in the original paper.

# Answer
> 1 votes
Suppose $\text{vbl}(F)=\\{y\_1,\cdots, y\_v\\}$, i.e., $F$ is a CNF over variables in $\text{vbl}(F)$.

Let $\\{y\_{i,j}\mid 1\le i\le 2^m, 1\le j\le v\\}$ be a set of distinct $2^mv$ variables.
For each $i=1,\cdots, 2^m$, let $F\_i$ be $F$ with every appearance of $y\_j$ replaced with $y\_{i,j}$ and every appearance of $\bar y\_j$ replaced by $\bar y\_{i,j}$. Then $F\_i$ is a copy of $F$ over variables in $\text{vbl}(F\_i)=\\{y\_{i,j}\mid 1\le j\le v\\}$.

---

The number of all $m$-clauses $c$ such that $\text{vbl}(c)=\\{x\_1,\cdots, x\_m\\}$ is $2^m$. They are, for example if $m=3$, $\\{x\_1,x\_2,x\_3\\}$,$\\{x\_1,x\_2,\bar x\_3\\}$, $\\{x\_1,\bar x\_2,x\_3\\}$, $\\{x\_1,\bar x\_2,\bar x\_3\\}$, $\\{\bar x\_1,x\_2,x\_3\\}$, $\\{\bar x\_1,x\_2,\bar x\_3\\}$, $\\{\bar x\_1,\bar x\_2,x\_3\\}$, $\\{\bar x\_1,\bar x\_2,\bar x\_3\\}$. List these $2^m$ clauses as $D\_1, \cdots, D\_{2^m}$.

What is important is that the formula $\\{D\_1, \cdots, D\_{2^m}\\}$ is unsatisfiable. For example, given an assignment $u\_1\mapsto1$, $u\_2\mapsto0$, $u\_3\mapsto0$, the clause $\\{\bar u\_1,u\_2,u\_3\\}$ is not satisfied.

---
Tags: np-complete, satisfiability
---


title: MInimum Spanning Tree and Combinatorics

text:
# Question
Title: MInimum Spanning Tree and Combinatorics
I just got a small confusion here, I have a graph for which i need to get number of minimum spanning tree,

So, in graph i have 3 edges with weight 2 and 4 edges with weight 3, in such a way that AE = AB = BE = 2 and ED = DC = EC = BC = 3. The solution provided is 3C2\*(2+3C2).

Initially taking any 2 edges from edges with weight 2 and then if BC is choosen then we can only take two edges ED and DC or else we can take edges from 3 weightes edges in 3C2 way respectively.

So, total number of MST possible is 15, but my doubt is, will the above solution include the possibility of forming a closed form from, AE-ED-DC-BC-AB ? as here i can see 2 edges from 2 weighted edges and 2 edges from 3 weighted edges, i am assuming BC is there as i cant see any condition stopping it.

# Answer
> 0 votes
AE-ED-DC-BC-AB contains $5$ edges, when the solutions you counted contained $4$ edges (rightly so), so there is indeed $15$ solutions, and AE-ED-DC-BC-AB is not one of them.

# Answer
> 0 votes
I think you may be mis-understanding the interpretation of the solution. ${3 \choose 2} (2 + {3 \choose 2})$ is the sum of the two distinct cases you cases you pointed out.

In both cases, 2 edges from $\\{AB, AE, BE\\}$ are chosen. This is in accordance with algorithms such as Prim's for greedily constructing MSTs. This can be done in ${3 \choose 2}$ ways. After this step, vertices $A, B, E$ are connected. We then move on to selecting edges of weight 3.

**Case 1**

If $BC$ is part of the MST, we must choose one last edge to connect vertex $D$ to the tree. There are only two options - $ED$ and $DC$. Thus, there are ${3 \choose 2} \cdot 2$ possibilities.

**Case 2**

If $BC$ is not part of the MST, there are 3 viable edges of which any two will connect $D$ and $E$ to the tree without creating a cycle. Thus, there are ${3 \choose 2} \cdot {3 \choose 2}$ possibilities.

In total, we then get the expected ${3 \choose 2} (2 + {3 \choose 2})$ number of MSTs. In particular, receiving an MST given by $\\{AE, ED, DC, BC, AB\\}$ is not possible because both cases we covered above only choose 4 edges. In general, a tree on $n$ vertices has exactly $n-1$ edges. Case 1 above considers $BC$ to be part of the MST then considers the possibilities where $\\{BC, DE\\}$ or $\\{BC, CD\\}$ are added to the existing MST, not $\\{BC, DE, CD\\}$.

Hope this helps!

---
Tags: weighted-graphs, minimum-spanning-tree
---


# Question
Title: Algorithm for farthest point Voronoi diagram?
I am looking for an algorithm to compute the furthest point Voronoi diagram and I don't seem to be able to find anything decent. The most complete one I have found are these slides and this terribly written wordpress site with a cool tool:

But I am not finding any well written text explaining and proving an algorithm to get the voronoi diagram, keyword being proving.

# Answer
> 4 votes
There are linear-time algorithms to construct a farthest-point Voronoi diagram given a sorted list of vertices of a convex polygon. For a general set of points, first computing the convex hull results in $O(n \log n)$-time algorithms.

First algorithm \[1\] is deterministic. Second algorithm \[2\] is randomized but much simpler than the first algorithm.

* \[1\] Aggarwal, Alok, et al. "A linear-time algorithm for computing the Voronoi diagram of a convex polygon." Discrete & Computational Geometry 4.6 (1989): 591-604.
* \[2\] Chew, L. Paul. "Building Voronoi diagrams for convex polygons in linear expected time." (1990).

# Answer
> 2 votes
It's published in *Journal of Computational Geometry: Theory and Applications*, DOI 10.1016/j.comgeo.2010.11.004 by Cheong, Otfried and Everett, Hazel and Glisse, Marc and Gudmundsson, Joachim and Hornus, Samuel and Lazard, Sylvain and Lee, Mira and Na, Hyeon-Suk.

The result you are looking for is:

> **Theorem 11.** The farthest-polygon Voronoi diagram $\mathfrak{F}( \cal S )$ of a family $\cal S$ of disjoint polygonal sites of total complexity $n$ can be computed in time $O(n \log^3 n)$.

---
Tags: algorithms, graphs, planar-graphs, voronoi-diagrams
---


# Question
Title: Prove that $L = \{a^rb^qc^q\}$ where $q > 0$, $r \geq 0$ is not a regular language
I've been working on this question for a few hours now and I've been trying to figure out the question above. My biggest problem is that I don't know what to do with the $\>$ and $\geq$ symbols when determining the language. My current work is below. Also, if you have any resources on how to adequately learn pumping lemma it would be really appreciated, I'm trying to find examples that don't set specific values to $p$ because it's an arbitrary number.

https://cdn.discordapp.com/attachments/451092252396224516/1038268572750856263/20221104\_214824.jpg

# Answer
> 0 votes
In case you haven't worked it out yet, here's my best explanation.

---

Firstly, notice how we can have any number of $a$ characters at the start. So, to make life easy let's assume we have none. If we then let $w=b^pc^p$, we can see that this is part of $L$ (when $r=0$ and $q=p$).

We then take a look at the conditions for a regular language under the pumping lemma. If the language is regular, we can take any $w\in L$ and decompose it into $xyz$ where:

* $|y|\geq1$
* $|xy|\<p$
* $xy^nz\in L\forall n\in\mathbb{N}\_0$

If we go back to $w=b^pc^p$, we can see that because $|xy|\leq p$, $xy$ has to be made up of entirely the character $b$ otherwise $|xy|\>p$. This means that $y$ must be made up of at least 1 $b$ (because $|y|\geq1$) and at most $p$ repetitions of $b$.

We then have a look at the last condition of the pumping lemma; $xy^nz\in L\forall n\in\mathbb{N}\_0$. Since $y$ is made up of only repetitions of $b$, any repetition of $y$ will add more of the character $b$ into this new word. This means that $xy^nz\notin L$ when $n\neq 1$ and therefore the last condition of the pumping lemma is not met so $L$ is not a regular language.

Hope this was helpful in some way

---
Tags: formal-languages, computability, pumping-lemma
---


# Question
Title: How to prove this variant of set partition problem is NP hard?
The problem is: split the given array with $L$ elements, $A$, into $K$ subsets such that maximum sum of all subsets is minimum. I have known that the problem that partitioning the multiset $S$ into two subsets $S\_1$, $S\_2$ such that the difference between the sum of elements in $S\_1$ and the sum of elements in $S\_2$ is minimized is NP-hard. It seems that the aforementioned problem is harder that the known NP-hard problem.
Could anyone explain why my questioned problem is NP-hard? It will be very appreciated that you could offer some formal references or paper.
FYI: I have read this post, but it doesn't offer any reliable reference or papers. I urgently want to konw how to prove it or whether there are any publications to verify its NP-hard. Thanks in advance.

# Answer
> 0 votes
Here is a proof that the problem is weakly NP-hard. I don't know if you'll find it in any paper since it is quite simple.

Consider the decision version of your problem: given a (multi-)set $A=\\{a\_1, \dots, a\_L\\}$ of $L$ elements, a positive integer $K$, and an integer $z$ decide whether there exists a partition of $A$ into $K$ sets $S\_1, \dots, S\_K$ such that $\max\_{i=1, \dots, K} \sum\_{x \in S\_i} x \le z$.

To show that your problem is NP-hard we reduce PARTITION to the decision version your problem. Let $X = \\{x\_1, \dots, x\_n\\}$ be an instance of partition. Consider the instance with $L=n$, $a\_i = x\_i$, $K=2$, and $z=\frac{1}{2} \sum\_{i=1}^L a\_i$.

If the PARTITION instance is a yes-instance, then there is a partition $X\_1, X\_2$ of $X$ such that $\sum\_{x \in X\_1} x = \sum\_{x \in X\_2} x = \frac{1}{2} \sum\_{x \in X} x = z$. Then choosing $S\_1 = X\_1$ and $S\_2 = X\_2$ yields a solution with $\max\left\\{ \sum\_{x \in S\_1} x, \sum\_{x \in S\_2} x \right\\} = z$, showing that the instance of your problem is a yes-instance.

If the instance to your problem is a yes-instance, then there must be some partition $S\_1, S\_2$ of $A$ such that $\max\left\\{ \sum\_{x \in S\_1} x, \sum\_{x \in S\_2} x \right\\} x \le z$ which implies $\sum\_{x \in S\_1} x = \sum\_{x \in S\_2} x = z = \frac{1}{2} \sum\_{i=1}^L a\_i = \frac{1}{2} \sum\_{x \in X} x$. Therefore the PARTITION instance is a yes-instance.

---

You can also show that the problem is strongly NP-hard by reducing from a variant of 3-PARTITION.

Consider an instance of $3$-partition $S=\\{x\_1, x\_2, \dots, x\_{3n}\\}$ with the additional constraint $\frac{T}{4} \< x\_i \< \frac{T}{2}$, where $T = \frac{1}{n} \sum\_{i=1}^{3n} x\_i \> 0$. The problem is known to be strongly NP-hard also in this case (see, e.g., the Wikipedia page for a reduction from the general case).

You can get an instance of (the decision version of) your problem by choosing $L=3n$, $a\_i = x\_i$, $K=n$, and $z=T$.

If there is a solution to the 3-PARTITION instance, then there is a partition $X\_1, \dots, X\_n$ of $X$ such that $\sum\_{x \in X\_i} x = T$ for all $i = 1, \dots, n$. Choosing $S\_i = X\_i$ yields a solution to your problem with $\max\_{i=1, \dots, K} \sum\_{x \in S\_i} x = T = z$.

If there is a solution $S\_1, \dots, S\_n$ to the instance of your problem, then each set $S\_i$ must contain at most $3$ elements, since otherwise we would have $\sum\_{x \in S\_i} x \> |S\_i| \cdot \frac{T}{4} \ge 4 \cdot \frac{T}{4} = T = z$. Consequently, all sets must have *exactly* $3$ elements (if at least one set $S\_i$ had at most $2$ elements, then there would be some other set with at least $4$ elements). Since this is a yes instance, we have $\sum\_{x \in S\_i} x \le z = T$ for all $i=1,\dots,n$, which implies $\sum\_{x \in S\_i} x = T$ (if at least one set $S\_i$ had $\sum\_{x \in S\_i} x \< T$ then there would be some other set $S\_j$ with $\sum\_{x \in S\_j} x \> T$). This shows that the 3-PARTITION instance is a yes-instance.

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


# Question
Title: Algorithm to alternaly order elements in a list
So, I have N sets of objects of various sizes. I want to put them in order, in a way that's as much "alternative" as possible.

For example, if I have 5 A, and 6 b, that's easy: B A B A B A B A B A B

If I have 5 A, 6 B, and 2 C, it could be something like that: B A B A C B A B C A B A B

Any idea how I could compute that? It does not have to be that efficient, I'll have maybe 8 sets maximum, of maximum size 100. I do not have a specific criteria to evaluate how "alternative" the list is, but anything that looks good enough will do the trick. Thanks

# Answer
If you have no real criteria, you could do something like:

```
Input: couples (a1, n1), (a2, n2), …, (ak, nk)
Output: alternating array containing n1 occurrences of a1,
        n2 occurrences of a2, …, nk occurrences of ak

for i = 1 to k:
    mi ← ni
A ← empty array
while not all mi = 0:
    let i ∈ {1, …, k} such that mi / (ni + 1) is maximal
    append ai to A
    mi ← mi - 1
return A

```

With your example, the order would be B A B A C B A B A C B A B.
> 1 votes

---
Tags: algorithms, sorting
---


# Question
Title: Is there an efficient way to solve this problem?
Given a series of n numbers, I need an algorithm that runs in worst case **O(n\*k)** to figure out how many arrangements of those n numbers will give me a score of exactly k.

**Note that the series does not contain duplicate elements.**

The score of a series of numbers is calculated by the number of smaller numbers an element in the series has before it.

For example, The score of the below series would be:

series = \[5,3,6\]

5 has no smaller number before it, so 0

3 has no smaller number before it, so 0

6 has 2 smaller numbers before it (5,3) so 2

Adding all of this, we get a total score for the series as 2.

What I have tried to do:

I have tried to find all possible arrangements of the series -\> (n! many arrangements)

and count the ones that have a score of k.

But this has a worst case time complexity of O(n!). Any help/ideas will be much appreciated. Thanks!

# Answer
Note that the values contained in the series are not important, and you can consider those values are exactly $1, 2, …, n$ (because only relative order is important).

Denote $A(n, k)$ the number of arrangements of $n$ values to reach score $k$.

Given an arrangement of $n$ values of score $k$, if you add the value $n+1$, you can:

* put it in first position and not change the score;
* put it in second position and add one to the score;
*
* put it in last position and add $n$ to the score.

Considering all this, we get the induction formula: $$A(n+1, k) = \sum\limits\_{i = 0}^n A(n, k - i)$$ The base cases are:

* $A(1, 0) = 1$;
* $A(n, k) = 0$ if $k \< 0$.

The total runtime of dynamic programming algorithm computing this would be $\mathcal{O}(n^2k) = \mathcal{O}(n^2)$ if $k$ is considered a constant.

There may be a closed formula that could be used to compute this in $\mathcal{O}(1)$, but I don't know it.
> 2 votes

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