# Question
Title: Every DFA accepting a finite language must contain a dead state?
I came a across a question where there were some statements made on Finite Automata, DFA and their states.

One such statements in the question was that a "Every DFA accepting a finite language must contain a dead state"

And the answer stated the statement to be true, and showed some DFA where there was a dead state following the accepting/final state.

Yes, dead states after the final state is possible but what about languages like $(a+b)^\*$ ? It is a finite language and there is no need for a dead state in it's DFA:

There is no dead state in this DFA. Am I making a mistake somewhere?

# Answer
Yes you are making a mistake. There is an important condition here, which is **finite**.

The language $(a+b)^\*$ is not finite. For $L$ any language, $L^\*$ is finite if and only if $L = \emptyset$ or $L = \\{\varepsilon\\}$.
> 2 votes

# Answer
> "Every DFA accepting a finite language must contain a dead state"

This depends on the definition. If dead state is the same as what some call a garbage state (not accepting, for all letters a loop back to the state) then this statement is *not* true. See the automaton below, which accepts only the empty string. This example can be generalized to other finite languages.

Alternatively, dead state might mean at state from which no accepting state is reachable. In that case the above statement is true.
> 0 votes

---
Tags: finite-automata
---


# Question
Title: How does "+" operator fit into the formal grammar of $\lambda$-calculus?
In Wikipedia I found out that the formal grammar of $\lambda$-calculus is the following:

```
<λexp> ::= <var>
  | λ<var> . <λexp>
  | ( <λexp> <λexp> )

```

Then, a few lines later they say that this is a valid $\lambda$-expression:

$$\lambda x.x^{2}+2$$

How does one matches with the other? Where is the "+" operator in the formal grammar? Where is the integer 2?

# Answer
From the Wikipedia article:

> An abstraction $\lambda x.t$ denotes an anonymous function that takes a single input $x$ and returns $t$. For example, $\lambda x.x^{2}+2$ is an abstraction for the function $f(x)=x^{2}+2$ using the term $x^{2}+2$ for $t$.

It doesn't claim $\lambda x. x^2 + 2$ is a $\lambda$-expression. Rather, it is an example of a general concept of *abstraction*.

In other words, a syntax rule for a lambda expression `λ<var> . <λexp>` is an abstraction, but not every abstraction is a lambda expression.

Similarly, *application* is a syntax rule for a lambda expression but this concept is used for other formalities, such as combinatorial calculus.
> 1 votes

---
Tags: lambda-calculus
---


# Question
Title: What Complexity Class Contains $QSAT_{\log n}$?
It is known that $QSAT$ is $PSPACE$ complete, and it is known that $QSAT\_i$ is $\Sigma\_i$ complete for any constant $i$. However, what if we had $QSAT\_{\log n}$? That is, $QSAT$ where the quantifiers can alternate $\omega(1)$ times, but still $o(n)$. Would this be enough to make the problem $PSPACE$ complete, or are all $O(n)$ alternations necessary? If this is not $PSPACE$ hard, would it fit somewhere in $PH$?

# Answer
Let $\Sigma\_{O(\log n)} \mathrm{P}$ be the class of languages accepted by a polynomial-time alternative Turing machine with $O(\log n)$ alternations. Then, $QSAT\_{\log n}$ is complete for this complexity class (under polynomial-time many-one reduction, for example). This question in TCS.SE Quantified Boolean Formulas with logarithmic alternations has some more discussions of this complexity class.

> If this is not PSPACE hard, would it fit somewhere in PH?

The problem is $PH$-hard because $QSAT\_i$ is $\Sigma\_{i+1}$-complete for every $i$ and we have $i \in O(\log n)$ for all constant $i$.
> 1 votes

---
Tags: complexity-theory, complexity-classes, oracle-machines
---


# Question
Title: How can we analyze the procedure Product: multiply two n-bits binary numbers x and y?
I am trying to analyze the algorithm *Product*: multiply two n-bits binary numbers x and y.

```
function Product(x, y);
 1. prod = 0;
 2. while y not eq 0
 3.     y = y -1;
 4.     prod = prod + x;
    return prod;

```

Assume: n = |x| = |y|
Give the worst case time T(n) function for algorithm Product.
Express T(n) in terms of a big-Θ function in n.
Analysis:

T(n) = c1 + n + c2 + c3

I would appreciate it if someone could explain how to use big-Θ to express T(n).

# Answer
Answer these two questions: How many iterations when n = 1 billion? How many iterations when n = -1?

With that you should have no problem answering your question.
> 0 votes

# Answer
line 1: c1 line 2: n line 3: c2 line 4: c3 line 5: c4

T(n) = c1 + n + c2n + c3n + c4n T(n) = theta(n)
> 0 votes

---
Tags: algorithms
---


title: Confused on Bellman Ford

text:
# Question
Title: Confused on Bellman Ford
We have a graph where we want to get from node u to v in the shortest path possible.

I understand how Bellman-Ford works when we have exactly i edges to go from u to v or at most i edges to get from u to v. But how does this work when you have to go from u to v with at least k number of edges?

Is this a simple variation of bellman-ford or is there more to this problem?

So far my reading material has been: DPV, Wikipedia, and online publications

Would someone be able to shed some light on this topic?

Thanks.

# Answer
> 1 votes
Consider the following problem:

Given an undirected, weighted graph $G=(V,E)$, and a pair of vertices $s,t$, we wish to find a lowest cost path from $s$ to $t$ with length exactly $k$. That is, out of all paths from $s$ to $t$ with length $k$, we wish to find the one with the lowest cost.

As D.W tried to direct you towards, Hamiltonian Path is reducible to this problem. w.l.g, we can set all weights to be 1, and set $k$ to be $n-1$ (assuming the length $k$ defines the number of edges in the path), then if we have a solution to the problem above, the same solution with these properties would find a Hamiltonian path, thus the problem is NP-Hard.

For completeness, and since you articulated that you are interested in a path with at least $t$ edges, we can also find the necessary reduction by solving this problem for all $k$ between $t\dots n-1$.

---

Note that, if you don't require the path to be $\mathit{simple}$, you can find the answer in polynomial time by some form of DP or duplicating the graph $k$ times.

---
Tags: graphs, dynamic-programming
---


# Question
Title: What is the right name for a "map" data structure?
I'm trying to say this in my paper: "$M$ is a key-value store, where 1) all keys are unique, 2) $k \in M$ means that the $k$ key exists in the store, 3) $M + (k, v)$ is a new store equal to $M$ but the key $k$ is assigned to $v$, 4) $M - k$ is a new store equal to $M$ but without the $k$ key.

Is it possible to omit all this text and just say that "$M$ is something," referring to some well-known definition of such structures?

# Answer
> 2 votes
You might be looking for a dictionary. Common implementations are hash tables and binary search trees.

# Answer
> 4 votes
Another common name for such a "map" data structure is *Map*. That's what it is called in C++, Java, ECMAScript, PHP, Go, Matlab, Rust, Scala, Clojure, Elixir, OCaml, F#, Racket, Kotlin, Dart, Ada, and Haskell, to name just a few.

The name *Map* is also used in Computer Science.

Yet another common name is *Associative Array*.

A slightly less common name is *Table*. That's what it is called in *Lua*. The term *Table* also appears in terms like *Hash Table*.

---
Tags: definitions
---


title: Min-cut with maximal number of edges

text:
# Question
Title: Min-cut with maximal number of edges
I’ve searched for a solution for this problem for some time now, it is out of an algorithm question sheet.

We know that in order to find the minimal amount of edges in a flow graph’s min-cut we need to find the maximal flow, $c\_o$,set the capacity of the edges of the min-cut to $1$ and for for the rest $e\in E$ set $c(e)=c(e)\cdot (|E|+1)+1$ and find the max flow $c\_n$ in the new graph such that $c\_n=c\_o\cdot (|E|+1)+k$, in which $k$ is the minimal number of edges in the graph’s min-cut.

Our problem is about finding the maximal number of edges in a graph’s min-cut.

Deducting one instead of adding would have the same effect, hence I’ve thought that perhaps if we add some number $\epsilon \in \mathbb{R} $ until the max flow increases, that could tell us something.

However I got stuck in that thought, unable to find ways on how to progress.

# Answer
Here is a simple algorithm that is based on your idea to reduce the capacity function.

---

Suppose the given flow network is directed graph $G=(V,E)$ with source $s$, sink $t$ and capacity function $c$.

Let $\epsilon\>0$ be a constant that is small enough. Consider a new capacity function $c^-$ that is $\epsilon $ less than $c$, i.e., $c^-(e)=c(e)-\epsilon$ for each edge $e$.

Let $\mathcal C\_1$ and $\mathcal C\_2$ be two $s$-$t$ cuts of $G$. Abusing the notations $c$ and $c^-$, let

* $c(\mathcal C\_1)$ and $c^-(\mathcal C\_1)$ be the capacity of $\mathcal C\_1$ wrt to $c$ and $c^-$ respectively.
* $c(\mathcal C\_2)$ and $c^-(\mathcal C\_2)$ be the capacity of $\mathcal C\_2$ wrt to $c$ and $c^-$ respectively.

Let $\\|\mathcal C\_1\\|$ be the number of edges in $\mathcal C\_1$ i.e. in the cut-set of the $s$-$t$ cut $\mathcal C\_1$ (which are the edges that start with nodes in the part of $\\|\mathcal C\_1$ that contains $s$ and end with nodes in the other part of $\\|\mathcal C\_2\\|$ that contains $t$). We have $\\|\mathcal C\_2\\|$ similarly.

**Claim**: $c^-(\mathcal C\_1)\<c^-(\mathcal C\_2)$ $\iff$ either $c(\mathcal C\_1)\<c(\mathcal C\_2)$ or $c(\mathcal C\_1)=c(\mathcal C\_2)$ and $\\|\mathcal C\_1\\|=\\|\mathcal C\_2\\|$.
Proof: $c^-(\mathcal C\_1)=c(\mathcal C\_1)-\\|\mathcal C\_1\\|\epsilon$.
$c^-(\mathcal C\_2)=c(\mathcal C\_2)-\\|\mathcal C\_2\\|\epsilon$.
$$c^-(\mathcal C\_1)-c^-(\mathcal C\_2)= c(\mathcal C\_1)-c(\mathcal C\_2)-(\\|\mathcal C\_1\\|-\\|\mathcal C\_2\\|)\epsilon.$$ Since $\epsilon\>0$ is small enough and $-|E|\<\\|\mathcal C\_1\\|-\\|\mathcal C\_2\\|\<|E|$, the claim is true.

---

The claim means *any* min-$s$-$t$-cut wrt to $c^-$ must be a min-$s$-$t$-cut wrt to $c$ with the maximum number of edges. In other words, the maximum number of edges in *any* min-$s$-$t$-cut of the flow network $(G,c)$ is the number of edges in a min-$s$-$t$-cut of the flow network $(G, c^-)$.

So we have the following algorithm.

1. Construct $c^-$ such that $c^-(e)=c(e)-\epsilon$ for a small-enough constant $\epsilon\>0$.
2. Compute a min-$s$-$t$-cut of $G$ wrt to $c^-$. Return the number of edges in it.

There are two ways to implement step 1.

* If $c$ is integer valued, we can choose $\epsilon=\frac1{|E|}$.
* In all cases, we can represent the scalar capacity $c(e)$ as vector $(c(e),0)$. Let $\epsilon=(0,1)$. $c^-(e)=(c(e),-1)$. Use the natural arithmetic and comparison order for the vectors. In this way, $\epsilon$ is realized as an "infinitesimal positive" capacity.

The time-complexity of the algorithm is about the same as the time-complexity to compute a max-flow of a flow network, such as $O(VE^2)$ for Dinic's algorithm.
> 1 votes

---
Tags: network-flow, max-cut
---


# Question
Title: Is checking whether a 3-SAT is satsifiable if and only if every clause has at least 2 or all three literal set to true an NP-complete problem?
I want to know if checking whether a 3-SAT is satsifiable if and only if every clause has at least 2 or all three literal set to true NP-complete?

It seems similar to Exact-3SAT but it differs from it as the version of this problem which we'll call Exact2or3-3SAT ,where all literals are positive is trivial as its always true .That's why I want to know if its NP-complete or not ?

# Answer
It is not currently known whether your problem is $\mathsf{NP}$-complete, but it can definitely be solved in polynomial time since it can be reduced to 2-SAT. If we assume $\mathsf{P} \neq \mathsf{NP}$, then your problem is not $\mathsf{NP}$-complete.

The reduction is as follows: a clause $(\ell\_1, \ell\_2, \ell\_3)$ of your problem is satisfied iff there does not exist a pair of distinct literals $\ell\_i, \ell\_j$ that are both false. Equivalently, for all pairs $\ell\_i, \ell\_j$ of literals you must have that at least one of $\ell\_i$ and $\ell\_j$ is true.

This shows that you can replace each clause $(\ell\_1, \ell\_2, \ell\_3)$ with: $$ (\ell\_1 \vee \ell\_2) \wedge (\ell\_1 \vee \ell\_3) \wedge (\ell\_2 \vee \ell\_3), $$ to obtain an equivalent 2-SAT instance.

As a note, there is also a straightforward reduction from 2-SAT to your problem: add a new variable $x$ and replace each 2-SAT clause $(\ell\_1 \vee \ell\_2)$ with $(\ell\_1, \ell\_2, x)$.
> 2 votes

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


# Question
Title: Logic for Computer Science - How to define msort, merge and split functions inductively?
In "Modelling Computing Systems: Mathematics for Computer Science", I came across a logic exercise to inductively define a merge sort function 'mergeSort', with a hint to first define auxillary functions 'split' and 'merge'. The style of the logic so far looks like this for inductively defined sets Odd and Even, and some other functions that manipulate lists (isort, insert, length, append):

```
1 ∈ Odd;
if n ∈ Odd then (n+2) ∈ Odd;
0 ∈ Even;
if n ∈ Even then (n+2) ∈ Even;

isort([]) = [];
isort(a:L) = (insert a)(isort(L));

(insert a)[] = [a];
(insert a)(b:L) = if a < b then a:(b:L) else b:((insert a)L);

length([]) = 0;
length(n:L) = 1 + length(L);

L1 ++ [] = L1;
(a:L1) ++ L2 = a:(L1 ++ L2);

```

I have tried, but I can't figure out how to define the first auxillary function 'split', which should split a list in roughly the same size. So far, I've defined the base cases for empty list and list with single element, but I don't know how to define the inductive case. I am not sure about the logic, the notation and also not about how I could make sure that the function doesn't use the same tail of the list L?

```
split([]) = ([],[]);
split(a:[]) = ([a],[]);
split(a : b : L) = if length(a : b : L) ∈ Even
                     (a : (split(L)), b : (split(L)));
                   else
                     (a : (split(L)), b : (split(b : L)));

```

How can I inductively call the split function again, without repeating the same split?

I have defined the merge function like this, and am pretty sure that should work:

```
merge(L1,[]) = L1;
merge([],L2) = L2;
merge(a:L1, b:L2) = if a < b
                      (a:(merge(L1, b:L2)));
                    else
                      (b:(merge(a:L1, L2)));

```

As for the final function mergeSort, I've gotten this far:

```
mergeSort([]) = [];
mergeSort(a:[]) = [a];
mergeSort(L) = merge("firstResultOf"(split(L)), "secondResultOf"(split(L)));

```

I don't know how to make it clear in the function that merge should use the first and second output lists of split. And I am unsure how to call mergeSort inductively..

How would you do it, using this type of notation?

# Answer
You can avoid odd and even by considering one more case in `split`. Any you need recursive calls in `mergeSort`. Here's a working Haskell solution.

```
    split :: [a] -> ([a], [a])
    split [] = ([], [])
    split [x] = ([x], [])
    split [x,y] = ([x], [y])
    split (x : y : l) = (x:xs, y:ys) where (xs,ys) = split l

    merge :: Ord a => ([a], [a]) -> [a]
    merge (xs, []) = xs
    merge ([], ys) = ys
    merge (x:xs, y:ys) | x <= y    = x : merge (xs, y:ys)
                       | otherwise = y : merge (x:xs, ys)

    mergeSort :: Ord a => [a] -> [a]
    mergeSort [] = []
    mergeSort [x] = [x]
    mergeSort xs = merge (mergeSort ys, mergeSort zs) where (ys, zs) = split xs

```
> 0 votes

---
Tags: logic, induction, lists
---


# Question
Title: Complexity of deciding the satisfiability of quasi-monotone 3-SAT?
This question:Complexity of deciding the satisfiability of a quasi-monotone CNF formula asked whether quasi-monotone SAT is NP-complete or not ?

I want to know if the restricted version of this SAT that is quasi-monotone 3-SAT is NP-complete or not, in this restricted quasi-monotone 3-SAT each clause has exactly 3 literal ?

# Answer
> 1 votes
The answer to the question you linked already shows how to transform a quasi-monotone 3-SAT formula into a quasi-monotone formula in which each clause has either $2$ or $3$ literals.

To get a formula in which each clause has exactly 3 literals, we just need to "pad" each clause with $2$ literals while preserving quasi-monotonicity property.

To do so, we repeat the following procedure for each clause $(\ell\_1 \vee \ell\_2)$ with $2$ literals:

* Introduce the new variables $a,b,c,d,x,y,z$
* Add the clauses $(\overline{a} \vee \overline{b} \vee \overline{x}) \wedge (\overline{a} \vee \overline{b} \vee x)$. This forces at least one of $a$ and $b$ to be set to false.
* Add the clauses $(\overline{a} \vee \overline{c} \vee \overline{y}) \wedge (\overline{a} \vee \overline{c} \vee y)$. This forces at least one of $a$ and $c$ to be set to false.
* Add the clauses $(\overline{a} \vee \overline{d} \vee \overline{z}) \wedge (\overline{a} \vee \overline{d} \vee z)$. This forces at least one of $a$ and $d$ to be set to false.
* Add the clause $(b, c, d)$. This forces at least one of $b,c,d$ to be set to true, which implies that $a$ must be set to false.
* Replace $(\ell\_1 \vee \ell\_2)$ with the equivalent clause $(\ell\_1 \vee \ell\_2 \vee a)$.

Therefore the quasi-monotone 3-SAT problem (with *exactly* 3 literal per clause) is also NP-complete.

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


# Question
Title: How does the linker know where to look for a function implementation in C++?
I am currently learning about how the compilation and linking works in C++. I think I kinda get how the compiler works, and that for a file to fully compile you don't need to have function implementations, but only declarations. It is the linker's job to link the function declaration to its implementation.

But now I have this weird question, for example if I have a `.cpp` file in which I am using 1000 different functions, and each of those functions has its own separate `.cpp` and `.h` file, how does the linker know which of the cpp files to scan to find that specific function? I mean does the linker know where the function is located or does the linker every time for every function scan the whole project to find that specific function?

# Answer
The compiler compiles from a .cpp file to an object file (.o) with the binary code.

The linker combines all of the object files together into a single binary.

So, the linker doesn't need to know which cpp to look at, because the linker doesn't look at cpp files. Instead, the linker looks at all of the .o files, figures out where all the functions are, and combines them together.
> 10 votes

# Answer
The linker is given explicitly the list of files to use, in the command line of the linker. They can be object files (.obj / .o) - compiled code - or libraries (.lib / .a) - object files structured in a single one.

Part of the job of the linker is to establish a list of the available functions and assign them an address in memory. This is enough to generate the calls where needed.

Note that the linker does not see the source code itself.
> 13 votes

# Answer
> It is the linker's job to link the function declaration to its implementation

This is not true. This is the compiler's job. Essentially the declaration (I'm assuming you mean the prototype, as in `return_type function_name (arguments...)`) is part of the language to allow you to tell the compiler what the function looks like before the compiler finds its implementation (the code body between `{` and `}`).

A lot of functions in fact are declared at the same place they are implemented. However it is also common to declare function prototypes without an implementation in headers or in virtual classes. This basically tells the compiler "hey, this is what the function looks like, but you will find the implementation later or somewhere else".

By the time you run the linker it is no longer processing things like declarations. Instead, linkers deal only with compiled code and some of that code consists of functions.

The final binary code does not actually contain any function definitions. Instead, code is simply a long list of machine instructions. A function is simply an address to somewhere in the code. For example a function like `add()` may be located at the 12566th byte of the binary code (or 0x00003116 in hex which is a more common way to look at addresses). The code that calls that function will simply be the instruction `call 0x00003116`. At this stage there is no information that that location contains a function.

However linkers work with object (or library) files that contain metadata, not just pure binary code. The actual format of these files depend on a lot of things - the language you use, the operating system you are on, the type of file etc. (for example, obj files in C/C++, lib files on Linux, dll files on Windows, etc.). However, what these files must contain is a list of what is sometimes called "symbols" and what addresses those symbols point to. These symbols are basically the function signature which tells the linker things like what the function's name is in the source code, how many arguments the function accepts, etc. This list of symbols is usually called the symbol table.

Actually, during compilation the compiler keeps a data structure called the symbol table in RAM in order to remember what it has compiled. Once the code is compiled, the compiler will format this symbol table appropriately and insert it in the object or library file.

When the linker sees that some code is calling `add()` it scans the list of files it is working on (or it looks up the database/array that it stored all the scanned files) and checks their symbol table to find `add()`. Once found, it will replace the caller's symbol with the address of the `add()` function (eg, 0x00003116). There is another step called the fixup which recalculates the address in RAM depending on how the executable or library file is loaded into RAM but I'll leave the details of that process as further research. It's enough to know that the linker's job is to load all the files you pass to it, remember all their symbol tables, and then replace symbols in code with actual addresses in memory.
> 8 votes

# Answer
For C and C++, the linker's job is the same, ignoring template classes/functions.

The .o / .obj files are split into Sections, each of which has a Symbol Table.

The Symbol Table has the offset into this Section of each exported Symbol (function, global variable), and a set of relations. These are the function calls, and references to global variables. The linker will determine which Object file contains \_main, and add it to the .exe it is building. It will then scan the relocations for the Section, and determine that \_add is being used. It then finds the .obj file that provides \_add, and adds it to the .exe. It then patches the Section that has \_main at the offset given in the Relocation Table, and writes the Absolute or Relative address of \_add here. It then locates all the Symbols that the Section that \_add requires, and processes them in the same way.

A .a / .lib file is a collection of Object files, optionally with an Index that lists all the Symbols the Library contains, for MS Visual Studio, this Index file is processed once, and the object files are added to the .exe as needed. UNIX traditionally only scans Library files when needed, and if a Library needs another Library, then this must be listed before the requiring Library.

A worked example may be helpful. Assuming that the linker is looking for \_main, and it finds it in foo.obj, at offset 100 in the .DATA Section. This Section is added to the .DATA Section of the .exe, and the caller is updated to have the address of \_main. A C or C++ program does not start at \_main - there is a function the initialises the C run time, any global variables, and then calls \_main. In MSVC command-line programs this is \_mainCRTStartup, but will have other names for other compilers.

The linker then finds \_add in bar.c in Section .DATA, and adds it to the .DATA section. Assume that foo.c .DATA Section was 500 bytes longs, this means that bar.c .DATA section is now at 500 bytes in. \_add is 200 bytes into bar.obj .DATA setion, so \_add is 700 bytes into the .exe .DATA section. Thus 700 is written into the .exe .DATA section at location 100 - which is where \_add is called. The process repeats until all Relocations have had their Sections added to the .exec.
> 3 votes

---
Tags: compilers, c, c++
---


# Question
Title: How to prove this because if we consider big-oh than logn^2 <= log n + 5 can never happen if n grows?
f(n) = log n^2; g(n) = log n + 5 =\> f(n) = Θ (g(n))

I think we can prove this for omega but how can we prove it for Big oh ?

because if we simplify it to logn + logn \<= logn +5 =\> logn\<=5 is not true !

# Answer
To show $f(n) = O(g(n))$ pick $n\_0 = 1$ and $c=2$. Then, for any $n \ge n\_0$, $$ f(n) = \log n^2 = 2 \log n \< 2 \log n + 10 = 2(\log n+5) = c g(n). $$

For the opposite direction (i.e., $g(n) = O(f(n))$) pick $n\_0 = 2^5$ and $c=1$. For any $n \ge n\_0$: $$ g(n) = \log n +5 = \log n + \log 2^5 = \log 2^5n \le \log n^2 = c f(n). $$
> 0 votes

# Answer
Obviously, $$2\log(n)\le 2(\log(n)+5)$$ for all $n$, so

$$\log(n^2)=O(\log(n)+5).$$

---

The $\Omega$ bound is slightly more difficult, as it does not hold for all $n$:

$$\log(n)+5\le2\log(n)$$ only for $n\ge e^5$.

(More generally, $c(\log(n)+5)\le 2\log(n)\iff n\ge e^{ 5c/(2-c)}\land c\<2$.)
> 0 votes

---
Tags: algorithms, time-complexity, data-structures, asymptotics, big-o-notation
---


# Question
Title: Optimum placement of zigzag trees in order to minimize the makespan
Suppose we have some trees of the following forms:

We want to place these trees in a linear fashion in a way such that the last node has the minimum distance to the first node. For instance, if we have the following trees:

Then an optimal placement will be like the following:

The minimum distance between the first node and the last node (which could be called "the makespan") is 5.

Note that we can stretch an edge, but we can't make an oblique edge straight or change its direction. The nodes have to be placed in a maximum of two rows (Like the trees themselves).

What would be the optimal placement strategy? We have all the trees upfront (this is an offline problem).

Motivation: I was trying to find an optimal schedule for a jobshop problem with two machines in presence of some form of recirculation. My modeling led to this problem.

# Answer
> 1 votes
The given trees are, in fact, paths. They can be encoded/given as a multiset of pairs $(\ell, \text{direction})$ where $\ell$ is the length of the path and $\text{direction}$ is either $\text{top}$ or $\text{bottom}$ that indicates whether the path should start at the top row or at the bottom row. For instance, the trees in the question are given by $(2,\textrm{top})$, $(2,\text{top})$, $(4,\text{bottom})$, $(3,\text{bottom})$.

Here is a simple greedy algorithm. The idea is to arrange to the top row earlier for the remaining part of a path scheduled for the top row if it has the most nodes not arranged yet. Ditto for the bottom row.

1. $column \leftarrow 0$
2. Initialize two empty priority queues, $top\\\_queue$ and $bottom\\\_queue$. A bigger number in the queue has higher priority.
Insert $\ell$ into $top\\\_queue$ for all $(\ell, \text{ top})$.
Insert $\ell$ into $bottom\\\_queue$ for all $(\ell, \text{ bottom})$.
3. While either $top\\\_queue$ or $bottom\\\_queue$ is not empty:

1. Add $column$ by $1$.
    2. If $top\\\_queue$ is not empty, pop an element. Let it be $t$.
    3. If $bottom\\\_queue$ is not empty, pop an element. Let it be $b$.
    4. If $t\>1$, insert $t-1$ to $bottom\\\_queue$.
    5. If $b\>1$, insert $b-1$ to $top\\\_queue$.

When an element is popped from a queue, imagine the current node of the corresponding path is put onto column $column$. The remaining part of the path, which is $1$ shorter, is then inserted to the other queue.
4. Return $column$, which is the minimum makespan possible.

If we add steps that track the identities of the numbers and the elements popped in order, the algorithm can return the optimum placement as well.

---
Tags: algorithms, graphs, trees, scheduling
---


# Question
Title: Hoare Triple Derivation Example (Precondition False)
How can i derive this Hoare Tripel?

{false} x := x + 1; {x = 0}

I do not know which rule should i use on this. I am confused on this wrong precondition.

# Answer
> 1 votes
Hoare triple derivations use axioms and rules of Hoare logic. In this case, one would use (1) an instance of the assigment axiom followed by (2) an instance of the consequence rule. Yves Daoust's comment spells out the relevant premise (2).

---
Tags: software-verification, hoare-logic
---


# Question
Title: Operation of non-regular with regular language
Would it be correct to say that on a operation with a Non-regular language (L) with a Regular language will always return the language L?

I'm came across a property that when we intersect a non-regular language (say L) with Regular Language the resultant result will always remain in Language L.

$L \cap Reg = L$

Does this property extent to other operations too?

# Answer
> 2 votes
For most of the time one can't make sweeping statements about operations between any non-regular language and any regular language. The intuitive reasoning is that regular languages are a very broad collection of languages. Every non-regular language is the subset of a regular language, and every non-regular language has a regular subset (though for some, all regular subsets are finite). Given a regular language $A$ and a non-regular language $B$, you can't eg. know if any of the following are regular or not, without further information on the languages:

* $A \cap B$ (intersection)
* $A \cup B$ (union)
* $A \cdot B$ or $B \cdot A$ (concatenation)
* $A \setminus B$ or $B \setminus A$ (set difference)
* Any of the above with either or both languages' complement
* \[countless other operations\]

Symmetric difference, as pointed out by HendrikJan in the comments, is one of the few set operations that provably results in a non-regular language when applied between a regular $A$ and a non-regular $B$.

---
Tags: regular-languages
---


# Question
Title: Parameterized complexity of Weighted Satisfiability with few variable occurrences
Given an integer $k$ and a Boolean CNF Formula $\phi$, Weighted Satisfiability asks whether $\phi$ is satisfiable by a model of weight $k$, i.e., a model that sets at most $k$ variables to true. This problem is W\[2\]-complete with respect to the parameter $k$.

Let $l$ be the maximum number of clauses that share a common variable, i.e., how often a variable occurs at most in $\phi$. My question is the following: **What is the complexity of Weighted Satisfiability parameterized by both $k$ and $l$?** Is anyone aware of work in this regard?

Note that this problem is NP-complete in classical complexity even if we fix $l$ to be 3, as we can introduce add copies of the variables and make them equivalent ($a\leftrightarrow a'$). This idea does not help in the parameterized setting with $k$ and $l$ as parameters, as it would require unbounded $k$ (all copies have to be set to true).

This problem seems to be connected to the model checking problem p-MC with bounded degree: Given a first-order logic $\psi$ formula and a labelled graph $G$, decide if G is a model of $\psi$. (See Logic, Graphs and Algorithms by Martin Grohe pdf)

This problem is fixed-parameter tractable with respect to the parameters length of $\psi$ and maximum degree of $G$. In principle, Weighted Satisfiability (with bounded occurrences) can be translated to a p-MC instance, but I do not see how to achieve this with bounded degree. Vertices corresponding to variables would have bounded degree (they are only connected to a bounded number of clauses), but vertices corresponding to clauses could have unbounded degree (they may contain a large number of variables).

# Answer
> 1 votes
As I stumbled upon this today and found after some further research out that this has been solved, I want to mention this here.

By this, the asked problem is FPT (so $t=0$ for the last sentence in the abstract).

The paper is "On the parameterized complexity of (k,s)-SAT" by Paulusma and Szeider, Inf. Proc. Letter, Volume 143, March 2019, Pages 34-36.

https://www.sciencedirect.com/science/article/abs/pii/S002001901830228X?via%3Dihub

Here is also a version not behind the Elsevier-paywall: https://www.ac.tuwien.ac.at/files/tr/ac-tr-18-008.pdf

---
Tags: logic, satisfiability, parameterized-complexity
---


# Question
Title: Decidability of the minimum number of states a Turing Machine needs to accept a language
I'm reading some old notes from a course on Turing Machines and I've bumped into the following question:

> Is the following language decidable? The language formed by the set of all Turing Machines whose languages can be accepted by a Turing Machine with at most 37 states

My assumption is that the question boils to whether, for a given Turing Machine, there exists an algorithm to minimise its number of states. In that case, we could run the algorithm against a given machine M, and if the number of states is greater than 37, it doesn't belong to the language; otherwise, it does.

The question then boils to whether such an algorithm exists. I have not found anything about that in the notes nor online.

# Answer
> 1 votes
The language is undecidable, and is proven immediately by Rice's Theorem.

These languages are recursively enumerable (since they are the languages of Turing machines), and being accepted by a Turing Machine of at most 37 states is a property of those languages; furthermore some languages will fit the criteria (being accepted by a Turing Machine of at most 37 states) while others won't, so it is a non-trivial property. Hence, by Rice's Theorem it is an undecidable property.

# Answer
> 0 votes
Hint:

> How many states does it take to recognize the language $\Sigma^\*$?

A further hint:

> Is it easy or hard to test whether a given Turing machine accepts $\Sigma^\*$?

---
Tags: turing-machines, undecidability, rice-theorem
---


# Question
Title: Tweaking traditional quicksort worst cases
All the sources I find on the internet say the time complexity of quick sort is worse if:

> * input array is sorted and we choose the leftmost element as the pivot
> * input array is sorted reversely and we choose the rightmost element as the pivot

I am wondering if time complexity is still $O(n^2)$ if we do the following instead.

* input array is sorted and we choose the rightmost element as the pivot
* input array is sorted reversely and we choose the leftmost element as the pivot

Does it even matter at the end of the day, we are choosing two extreme-sized partitions?

# Answer
> 1 votes
Quicksort's behavior is bad when every partition is imbalanced (instead of splitting $m$ elements in two, the split is like $1$ vs. $m-1$), leading to $O(n^2)$. A good pivot is one which has a rank close to the median ($O(n\log n)$). In case of an already sorted array, the middle element would be a good choice.

---
Tags: algorithm-analysis
---


# Question
Title: Is "Bitwise Complement Operator" (~ tilde) distributive?
To be more precise, Is `~(a+b) = ~a + ~b`? Here, `"~"` bitwise NOT operator.

I ran into this question while thinking about the 2's complement, which adds `1` to `~x` (i.e., `-x = ~x + 1`).

Suppose we are given `-x` (in binary), and we need to find `x` (in binary). We can do this by computing `x = ~(-x-1)`, but computing `-x-1` (by hand) is a bit of a hassle when compared to computing `~(-x)` (easy to flip bits directly). So, I wanted to find some relation between `~(-x)` and `x` that can help me calculate `x`.

It turns out that `~(-x) = x-1`. I found this relation by taking some examples.

But I wanted to derive this relation. This was my derivation approach:

```
-x = ~x + 1        # from 2's complement definition
~(-x) = ~(~x + 1)  # applying bitwise NOT on both sides
~(-x) = x + ~1     # taking bitwise NOT into the brackets: ~(~x) = x.
~(-x) = x - 2      # ~1 = -2

```

This above result is incorrect (it should be `x-1` instead of `x-2`).

What mistake did I make? Can we take "~" within the brackets (step 3)? If not, what would correct derivational steps look like?

# Answer
> 1 votes
Certainly not. By De Morgan's law,

$$\lnot(a\lor b)=(\lnot a)\land(\lnot b)\\\ne(\lnot a)\lor(\lnot b)$$

and this carries to the bitwise case.

---

Adding one to a binary number is virtually as easy as flipping: start from the right, flip the bit and if was a $1$, carry to the next.

---
Tags: logic, propositional-logic, mathematical-foundations, mathematical-analysis, bit-manipulation
---


# Question
Title: Where does the FLP impossibility proof depend on allowing a single process failure?
# Question

I'm reading the FLP impossibility paper. I think I understand the idea of the proof, and I don't have questions about it.

However, **it seems like the assumption of having *at most, a single faulty process* is not used in the proof**. Put another way, if we remove this assumption and forbid process failure, the proof still seems to hold.

This can't be correct, because then it wouldn't be possible to construct a protocol that succeeds with no faulty processes. However, it *is* possible, and a protocol meeting this criterion is supplied in section 4.

My question is therefore: **which part of the proof relies on the condition that one process can fail?**

# My best effort at an answer

## Definitions

For reference, the assumption in question appears in the definition below:

> A run is *admissible* provided that **at most one process is faulty** and that all messages sent to nonfaulty processes are eventually received.

Also relevant is the definition of a deciding run:

> A run is a *deciding* run provided that some process reaches a decision state in that run.

I'll also use my own definition, below:

> A run is *0-admissible* provided that **no processes are faulty** and that all messages sent to nonfaulty processes are eventually received.

## Approach

I want to show that, by changing the definition of *admissible* to that of *0-admissible*, the proof is no longer correct. Therefore, it would rely on the *at most one failure* part of the *admissible* assumption.

## Lemma 2

Lemma 2 ("*P has a bivalent initial configuration*") references this assumption. In particular:

$C\_0$ and $C\_1$ are $0$-valent and $1$-valent initial configurations, respectively. They differ only in the initial value $x\_p$, of a single process $p$.

> Now consider some **admissible deciding run** from $C\_O$ in which process $p$ takes no steps, and let $\sigma$ be the associated schedule.
>
> Then $\sigma$ can be applied to $C\_1$, also, and corresponding configurations in the two runs are identical except for the internal state of process $p$. It is easily shown that both runs eventually reach the same decision value. If the value is $1$, then $C\_0$ is bivalent; otherwise, $C\_1$ is bivalent.

Both cases above being a contradiction, proving the lemma.

### Replacing *admissible* with *0-admissible* in Lemma 2

I'd hoped that replacing *admissible* with *0-admissible* would show the proof no longer works.

For simplicity, I'll only consider the case where $N = 2$.

Now consider the (modified) line of the proof:

> Now consider some *0-admissible deciding run* from $C\_O$ in which process $p$ takes no steps.

*0-admissibility* implies the following:

1. Process $p$ cannot be faulty
2. Process $p$ must have received all messages sent to it
3. A decision state is reached

By non-triviality, the schedule $\sigma$ must not initially be in a deciding state.

Now, we know from (1) and (2) that no messages can have been sent to process $p$: Either it would have taken steps to receive them (violates assumptions), or it didn't receive them (violates 0-admissibility).

Therefore, we can ignore process $p$ and focus on the remaining process. I had assumed that it being deterministic implies the configuration must be univalent, but I can see a problem.

Namely, the deterministic process can introduce nondeterminism by sending a message to itself, and measuring the time taken to receive it. This effectively generates a random integer, which can be used to randomly choose an answer.

Even if it were right, this seems like a very complex answer to a simple question - have I missed something obvious? Is there another part of the proof where the assumption of faultiness is required more explicitly?

# Answer
The part of the original paper's proof that requires node failure to prove the impossibility is case 2 of lemma 3. This case assumes that there is a "finite deciding run from C0 in which p takes no steps". p taking no step means it has died/failed.

From case 1 of lemma 3, we know that there exists a pair of messages, called e and e' which affect the decision process, and if they are received by different nodes (p and p') the nodes will decide on different values. This means that these "important messages" must be received by a single node p only.

Case 2 tests this further with the possibility that node p, the recipient of the "important messages", fails (or "takes no steps"). If a "totally correct in spite of one fault" algorithm exists, it needs to tolerate the scenario where node p fails after configuration C0. Of course, p might just not fail, and the algorithm must be correct in both scenarios: p failing and p not failing.

Since the algorithm *must* decide on some value, if p is failing it has to proceed through some run called sigma and arrive at a deciding configuration A.

The problem here is that if p is actually still functional, it will accept e and e' and decide on its own. As we know from case 1, node p can decide on 0 (e arriving before e') or decide on 1 (e' arriving before e). So node p is making a decision on its own with no regard for what the rest of the nodes (through sigma) are deciding and ultimately there will be a case where the 2 set of nodes decide on different values.

As for your proof, since p takes no steps (it dies after C0), it invalidates your definition of a 0-admissible run.
> 4 votes

# Answer
\[Well, I am no expert, but here we go.\]

The assumption of at most a single faulty process is used twice.

First, it is used to establish that there is one bivalent starting configuration. (FLP Lemma 2)

\[Assume not. Then all starting configurations are monovalent, and by the need to avoid triviality, at least one must be 0-valent and at least one must be 1-valent. This then means that a 0-valent start must be ‘next’ to a 1-valent start. ‘Next’ here means differs only in the input value of one process. For example, with just two processes we might have

```
p1 input=1 p2 input=1 say… 0-valent

p1 input=1 p2 input=0 say… 1-valent

```

Now, assume the system is ‘fault tolerant’ and can work with a single faulty process and p2 dies immediately.

So, from the first line

```
p1 input=1 p2 input=1 p2 dead but supposed to be 0-valent

```

there must be a schedule (=sequence) of events such that p 1 leads the whole system to a 0-valent configuration. Schedules are produced by processes asking the message buffer for their messages and the buffer firing back a single message, essentially event(process i, message m). Process 2 is dead, we may imagine, so never asks the buffer for anything. So, this schedule, say s, that produces a 0-valent configuration involves only events requested by, and processed by, process 1. The schedule looks like this

```
< event(process 1, message ?), event(process 1, message ?), event(process 1,
message ?), etc. >.

```

Now, focus attention on the second input configuration

```
p1 input=1 p2 input=0 say… 1-valent

```

and apply schedule s to it. Schedule s is perfectly good. It is quite possible for the message buffer to hold the relevant messages, and quite possible for it to produce schedule s (since there is a randomness to what it supplies to process 1 and process 2 in response to their requests). Schedule s will run exactly the same with input

```
p1 input=1 p2 input=0

```

as it does with input

```
p1 input=1 p2 input=1

```

since all the events go to p1 and all the processing is deterministic. So, the resulting configuration will be 0-valent. But the second configuration is supposed to be 1-valent. So, this is a contradiction.

Notice here, that in the running from the second input configuration, process 2 does not have to be dead. It can be alive and well, but the situation is that no events, or no configuration changing events, go to it.

Second, in case 2, of the ‘bivalent has a later bivalent’ lemma, process death is invoked (or imagined). (FLP Lemma 3 case 2.)

Here we can imagine a horizontal tree, the nodes of the tree are configurations, and the branches are sequences of configurations. Sequences of configurations can be thought of as sequences of events (whose application to previous configurations produce configurations) i.e. the sequences of configurations are schedules. Events can be understood as labels on the branch segments. We are also interested here in partial branches i.e. from root to node but not necessarily out to leaf. These partial branches are also schedules (sequences of events). Now, we are going to hang from each node an additional applicable event, say e, and these hang down vertically like baubles on a Xmas tree. Effectively, e, is appended to every schedule, being a leaf on new branches and longer schedules. We are also going to insist that e did not appear in any schedule in the tree before we added it (so, had it been there we would delay it until it ends up as a leaf). The event e can be called a ‘critical event’. Every leaf in the tree has now been produced by the application of e to the penultimate node in its branch. The root configuration of the tree is bivalent (for that is what we are starting from). In part, this means that one leaf is 0-valent and one leaf is 1-valent. But the question is: are any of the leaves bivalent? \[We are trying to prove that at least one is.\] Assume not. So, all leaves are monovalent. We will say that one leaf is ‘next’ to another, if the node that the first hangs from is ‘next’ to the node that the second hangs from. And one node (= configuration) is next to another node (= configuration) if the second can be obtained from the first by the application of a single event, say e\* i.e. c2= e\* (c1) . Now, somewhere in the tree a 0-valent leaf is next to a 1-valent leaf (FLP prove this). So

```
c2= e* (c1)

l1= e (c1)

l2= e (c2)

l1= 0-valent, say

l2= 1-valent, say

```

But this turns out to be contradictory. We need to look in more detail at the events and their processes, say

```
e= event(process1, message?)

e*= event(process*, message*?)

```

Case 1. process1 and process\* are different processes, in which case disjoint schedules (events) involving them commute, so

```
l2 is 1-valent

l2= e ( e* (c1)) = e* (e (c1)) = e* (l1)

But if l2 is e* (l1) it is a child of l1 and thus is 0-valent

So, l2 is both 0-valent and 1-valent (a contradiction).

```

Case 2 process1 and process\* are the same process, say p1 (FLP Figure 3)

We will want to have a second process, say p2 (the proof holds only for two or more processes)

focus now on the configuration (i.e. node) c1. There will be a schedule, say, s, which both transforms c1 into a determinate state (i.e. 0-valent or 1-valent), say node A, and does not involve the process p1. The system as a whole is assumed to be fault tolerant and so can run to determinate states when a single process say p1 is dead. And also, all configurations have schedules which take them to determinate states. This schedule s is disjoint with the schedule

```
<e>

```

and also with the schedule

```
<e*, e>,

```

this means that it will commute with both of these. (Basically, s runs on p2 and e\* and e on p1.)

```
l1= e (c1)

define E0 to be the configuration

E0= s(l1) so E is 0-valent (it is a child of the first leaf)

E0= s(e (c1))= e (s (c1)) by commutativity

A= s(c1)

E0= e(A)

So E0 is a child of A and so A is 0-valent

But

l2= <e*, e> (c1)

define E1 to be the configuration

E1= s(l2) so E is 1-valent (it is a child of the second leaf)

E1= s(<e*, e> (c1)) = <e*, e>  (s (c1)) by commutativity

A= s(c1)

E1= <e*, e> (A)

So E1 is a child of A and so A is 1-valent

A is both 0-valent and 1-valent, which is a contradiction.

```

So…. Every bivalent has a later bivalent (assuming asynchronous messaging and a possible single faulty process).

What about the schedule s? It was constructed from fault tolerance and the need to run to determinate states when a single process, say p1 is dead. But having got s, which does not involve p1 at all, p1 can be alive and well and yet the system runs from one bivalent state to another (and then it is possible for the system to do this over and over).

Hope this helps. Sorry for any typos or blunders.
> 1 votes

# Answer
In the PROOF of LEMMA 2:

> Now consider some admissible deciding run from $C\_0$ in which process p takes no steps, and let u be the associated schedule.

The protocol can become deciding without talking to p. This requires the protocol can tolerate one fault. In other words, if the protocol tolerates no fault, it requires every process to participate to eventually become deciding.
> 1 votes

---
Tags: distributed-systems, consensus
---


# Question
Title: Linear algebra matrix coding to solve specific formula
I have a formula which cannot be expressed in terms of y.

```
fv = (p (1 + r) (-1 + (1 + r)^m) ((1 + r)^(m y) - (1 + x)^y))/
      (r (-1 + (1 + r)^m - x)) + c (1 + r)^(m y)

```

I'd like to solve it numerically with some kind of matrix operation.

For example

with

```
r = 0.05/12
m = 12
p = 1000
x = 0.03
c = 2000
fv = 92988.93

```

Can this be done with linear algebra, or is an iterative approach necessary?

Wolfram Alpha is not giving any clues for a matrix solution. Maybe some gradient descent program is required.

# Answer
> 1 votes
Linear algebra and matrices are not relevant here. Roughly speaking, they are useful when you have a system of linear equations. Here, you have a single equation, not a system of equations; and it is nonlinear.

If I understand correctly, given $p,m,\dots$, you are trying to find a value of $y$ that satisfies the equation. This equation can be written in the form

$$f(y) = 0$$

where $f$ is a function of $y$ (it also depends on $p,m,\dots$ but those are considered known constants). Here $f(y) = (p(1+r)\cdots) - fv$.

You can find an approximate solution to such an equation using an iterative algorithm, such as Newton's method. See https://en.wikipedia.org/wiki/Root-finding\_algorithms.

# Answer
> 2 votes
From what I see, your equation has the form

$$A(1+a)^y+B(1+b)^y+C=0$$ where $a,b$ are small. Such a nonlinear equation cannot be solved analytically.

To find an approximate solution, you can write

$$0=A(1+a)^y+B(1+b)^y+C\approx A(1+ay)+B(1+by)+C$$ and solve for $y$. An even better approximation comes from

$$0=A(1+a)^y+B(1+b)^y+C\\\approx A\left(1+ay+a^2\frac{y(y-1)}2\right)+B\left(1+by+b^2\frac{y(y-1)}2\right)+C$$

which is quadratic in $y$ (by the generalized binomial formula).

Then you can refine with Newton's method. Few iterations will be needed.

$$y\leftarrow y-\frac{A(1+a)^y+B(1+b)^y+C}{A\log(1+a)(1+a)^y+B\log(1+b)(1+b)^y}.$$

# Answer
> 0 votes
***Newton-Raphson solution for n***

Need to find a root for this formula with one unknown, n

```
(p ((1 + r)^n - (1 + x)^n))/(r - x) + c (1 + r)^n - fv = 0

```

Using the algorithm here: https://en.wikipedia.org/wiki/Newton%27s\_method#Code

This method requires the derivative of the formula.

---
Tags: linear-algebra
---


# Question
Title: Check array in linear time with a constant space complexity
Given an array of integers I have to return true if all the elements in the array are different or all the elements are the same. Otherwise, I have to return false.

E.g.

`[1, 1, 1, 1]` \- all the elements are the same, so it is `true`

`[12, 20, 1, 23]` \- all the elements are different, so it is also `true`

`[12, 20, 1, 1]` \- we have just two `1`, so it is `false`

The easy thing I was able to come up with is to use a hashmap to map an integer to a number of occurrences of that integer in the array. And then to iterate over the hashmap and check if there is at least one entry whose value is greater than 1 and is not equal to the length of the array, then I return false. Otherwise, I return true after the iteration.

The problem with my solution is that it has a linear space complexity and I feel that it should be possible to somehow solve the problem using a constant space complexity and linear time complexity.

So, could someone help me come up with an `O(1)` space complexity and `O(n)` linear complexity with respect to the array size solution, please?

I am working on this problem just for fun.

# Answer
> 3 votes
The problem does not have any $O(n)$ time algorithm. Note that it is easy to check in linear time if all the elements in the array are the same or not. However, to check if all the elements are district, the problem is known as Element distinctness problem. And, this problem has an $\Omega(n \log n)$ lower bound complexity (for comparison based models). More technically, your problem can be reduced to *element distinctness problem* in linear time.

Therefore, the best possible solution here is $O(n \log n)$ time algorithm. For that, you can employ merge sort algorithm using a linked list. It also has an $O(1)$ space complexity.

---

**Note:** Since the input is a set of integers, you can employ Radix sort to solve the problem in linear time.

# Answer
> -1 votes
I have just started to look into time and space complexity and it is all a mess for me atm, but this particular problem can be solved with converting the list of integers into a set, then comparing lenghts. Would that be linear in time? Sample function:

```
def same_diff(a_list):
    a_list.sort()
    temp_set = set(a_list)
    if len(temp_set) <= 1 or len(temp_set) == len(a_list):
        return True
    return False

```

Sorting is not required, but neater I guess?

Thanks :)

---
Tags: arrays, space-complexity, communication-complexity
---


# Question
Title: Question about $L$ = { $ww$ | $w$ ∊ $ca^*c$}
I found a grammar for this language.

$S-\>caZac |cccc $.

$Z-\>aZa | cc$

But if I try to use pumping lemma for context-free languages on $L$ with the word: $ca^ncca^nc$ I obtain it's not context-free. How is it possible?

# Answer
The pumping lemma is verified with a pumping length $n=6$. Indeed, let $ww\in L$, $|ww| \geqslant n$. Then $ww =ca^kcca^kc$ with $k\geqslant 1$.

Then $ww = uvxyz$ with $u = ca^{k-1}$, $v = a$, $x=cc$, $y=a$ and $z=a^{k-1}c$, and:

1. $|vxy| = 4 \leqslant n$;
2. $|vy| = 2 \> 0$;
3. for $i\geqslant 0$, $uv^ixyv^iz = ca^{k-1+i}cca^{k-1+i}c\in L$.
> 1 votes

---
Tags: context-free, pumping-lemma
---


# Question
Title: Simulating Halt Decider Applied to the Halting Theorem
> A key breakthrough is that the author of the best selling book on the theory of computation MIT professor Michael Sipser has agreed that the following verbatim paragraph is correct:
>
> If simulating halt decider H correctly simulates its input D until H correctly determines that its simulated D would never stop running unless aborted then H can abort its simulation of D and correctly report that D specifies a non-halting sequence of configurations.

**Complete halt deciding system (Visual Studio Project)**

> **Halting problem:** In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. https://en.wikipedia.org/wiki/Halting\_problem

**Can anyone point out any error in the following conclusion? (or affirm that it is correct)**

A simulating halt decider is a UTM that has been adapted to decide whether or not its input halts. It does this on the basis of the dynamic behavior of this input. Behavior that matches a non-halting pattern is recognized. When it determines that its input would not halt it aborts the simulation of its input and reports that is input is not a halting computation.

The key notion that must be expressed is **infinitely nested simulation.** In the language of Turing machines this would seem quite tedious. I could use the Linz approach and express this as state transition diagrams.

**Infinitely nested simulation is expressed as a cycle from qx to q0.**
**Figure 12.3 Turing Machine Ĥ** (Linz:1990:319)

# Key halt deciding criteria overcomes self-referential inputs

**When-so-ever a simulating halt decider must abort the simulation of its input to prevent the infinite execution of this input, this input is always correctly decided as not a halting computation.**

The simple concrete examples that can be fully understood by any expert C programmer. The x86utm operating system was created to investigate the following examples in the high-level language of C.

H examines the behavior of the x86 emulation of its input. As soon as a non-halting behavior pattern is matched H aborts the simulation of its input and decides that its input is not a halting computation.

**This understanding is a mandatory prerequisite:**
A bench check of the first line of main() can be understood by any expert C programmer to specify infinite recursion that never reaches the second line of H\_Hat2(). If you can't see this then you will not understand the rest.

```
int Simulate(u32 P, u32 I) {
  ((void(*)(u32))P)(I);
  return 1;
}

// Simplified Linz Ĥ (Linz:1990:319)
void H_Hat(u32 P) {
  // Linz H as a simulating partial halt decider
  u32 Input_Halts = H(P, P);
  if (Input_Halts)
    HERE: goto HERE;
}

void H_Hat2(u32 P) {
  u32 Input_Halts = Simulate(P, P);
  if (Input_Halts)
    HERE: goto HERE;
}

int main() {
  Simulate((u32)H_Hat2, (u32)H_Hat2);
  H((u32)H_Hat, (u32)H_Hat);
}

```

Anyone that knows C programming very well will know that line 1 of main() won't halt and line 2 of main() will only halt if simulating partial halt decider H() stops simulating H\_Hat(). A simulating halt decider that never stops simulating its input is simply a simulator on this input.

When we know that the UTM simulation of TM Description P on input I would never halt we know that the execution of TM P(I) would never halt.

**Conclusion:** On this basis we know that any computation that must have its simulation aborted to prevent its otherwise infinite execution is not a halting computation, H stops simulating its input and reports that its input is not a halting computation.

**Linz, Peter 1990.** An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company.

# Answer
This updated dialogue is complete and can be replicated in ChatGPT. ChatGPT confirms that the halt status criteria that I use in my rebuttal of the halting theorem is correct.

```
olcott
void D(void (*x)())
{
  int Halt_Status = H(x, x);
  if (Halt_Status)
    HERE: goto HERE;
  return;
}

int main()
{
  Output("Input_Halts = ", H(D, D));
}

```

When H(D,D) correctly simulates its input the execution trace of this simulated input proves that it would never stop running because D continues to call H in recursive simulation. Then H aborts its simulation of D and returns 0 to main, indicating that D would never stop running unless aborted. Is H correct?

ChatGPT
Yes, H is correct if it correctly simulates its input and the execution trace of the simulated input shows that D never stops running unless aborted.
> -4 votes

# Answer
**The following concrete example shows that the confounding input is aborted before it ever receives any return value from the halt decider. The simulating halt decider H aborts its input because this input specifies infinite invocations comparable to infinite recursion.**

When a simulating halt decider must abort the simulation of its input to prevent the infinite execution of this input, this input is correctly decided as not a halting computation even though it has been forced to halt and thus halts.

> Now Ĥ is a Turing machine, so that it will have some description in Σ\*, say ŵ. This string, in addition to being the description of Ĥ can also be used as input string. We can therefore legitimately ask what would happen if Ĥ is applied to ŵ. (Linz:1990:320)

When we assume that the actual the Linz halt decider H bases its halting decision on simulating its input the same infinitely nested simulation is derived.

This provides the basis for the halt decider embedded in Ĥ to decide that its input is not a computation that halts.

Because the halt decider must abort the simulation of its input to prevent its infinite execution it correctly transitions to its final state of Ĥ.qn indicting that its input is not a computation that halts.

```
// Simplified Linz Ĥ (Linz:1990:319)
void H_Hat(u32 P) {
  u32 Input_Halts = H(P, P);
  if (Input_Halts)
    HERE: goto HERE;
}

int main() {
  u32 Input_Would_Halt6 = H((u32)H_Hat, (u32)H_Hat);
  Output("Input_Would_Halt6 = ", Input_Would_Halt6);
}

```

Because the input to H() on the first line of H\_Hat() must be aborted to prevent its infinite execution this input is correctly decided as not a halting computation.

**Linz, Peter 1990.** An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company.

```
_H_Hat()
[00000b10](01)  55              push ebp
[00000b11](02)  8bec            mov ebp,esp
[00000b13](01)  51              push ecx
[00000b14](03)  8b4508          mov eax,[ebp+08]
[00000b17](01)  50              push eax
[00000b18](03)  8b4d08          mov ecx,[ebp+08]
[00000b1b](01)  51              push ecx
[00000b1c](05)  e81ffeffff      call 00000940
[00000b21](03)  83c408          add esp,+08
[00000b24](03)  8945fc          mov [ebp-04],eax
[00000b27](04)  837dfc00        cmp dword [ebp-04],+00
[00000b2b](02)  7402            jz 00000b2f
[00000b2d](02)  ebfe            jmp 00000b2d
[00000b2f](02)  8be5            mov esp,ebp
[00000b31](01)  5d              pop ebp
[00000b32](01)  c3              ret
Size in bytes:(0035) [00000b32]

_main()
[00000b40](01)  55              push ebp
[00000b41](02)  8bec            mov ebp,esp
[00000b43](01)  51              push ecx
[00000b44](05)  68100b0000      push 00000b10
[00000b49](05)  68100b0000      push 00000b10
[00000b4e](05)  e8edfdffff      call 00000940
[00000b53](03)  83c408          add esp,+08
[00000b56](03)  8945fc          mov [ebp-04],eax
[00000b59](03)  8b45fc          mov eax,[ebp-04]
[00000b5c](01)  50              push eax
[00000b5d](05)  682b030000      push 0000032b
[00000b62](05)  e8f9f7ffff      call 00000360
[00000b67](03)  83c408          add esp,+08
[00000b6a](02)  33c0            xor eax,eax
[00000b6c](02)  8be5            mov esp,ebp
[00000b6e](01)  5d              pop ebp
[00000b6f](01)  c3              ret
Size in bytes:(0048) [00000b6f]

Columns
(1) Machine address of instruction
(2) Machine address of top of stack
(3) Value of top of stack after instruction executed
(4) Number of bytes of machine code
(5) Machine language bytes
(6) Assembly language text
===============================
...[00000b40][00101533][00000000](01)  55              push ebp
...[00000b41][00101533][00000000](02)  8bec            mov ebp,esp
...[00000b43][0010152f][00000000](01)  51              push ecx
...[00000b44][0010152b][00000b10](05)  68100b0000      push 00000b10
...[00000b49][00101527][00000b10](05)  68100b0000      push 00000b10
...[00000b4e][00101523][00000b53](05)  e8edfdffff      call 00000940
Begin Local Halt Decider Simulation at Machine Address:b10
...[00000b10][002115d3][002115d7](01)  55              push ebp
...[00000b11][002115d3][002115d7](02)  8bec            mov ebp,esp
...[00000b13][002115cf][002015a3](01)  51              push ecx
...[00000b14][002115cf][002015a3](03)  8b4508          mov eax,[ebp+08]
...[00000b17][002115cb][00000b10](01)  50              push eax
...[00000b18][002115cb][00000b10](03)  8b4d08          mov ecx,[ebp+08]
...[00000b1b][002115c7][00000b10](01)  51              push ecx
...[00000b1c][002115c3][00000b21](05)  e81ffeffff      call 00000940
...[00000b10][0025bffb][0025bfff](01)  55              push ebp
...[00000b11][0025bffb][0025bfff](02)  8bec            mov ebp,esp
...[00000b13][0025bff7][0024bfcb](01)  51              push ecx
...[00000b14][0025bff7][0024bfcb](03)  8b4508          mov eax,[ebp+08]
...[00000b17][0025bff3][00000b10](01)  50              push eax
...[00000b18][0025bff3][00000b10](03)  8b4d08          mov ecx,[ebp+08]
...[00000b1b][0025bfef][00000b10](01)  51              push ecx
...[00000b1c][0025bfeb][00000b21](05)  e81ffeffff      call 00000940
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
...[00000b53][0010152f][00000000](03)  83c408          add esp,+08
...[00000b56][0010152f][00000000](03)  8945fc          mov [ebp-04],eax
...[00000b59][0010152f][00000000](03)  8b45fc          mov eax,[ebp-04]
...[00000b5c][0010152b][00000000](01)  50              push eax
...[00000b5d][00101527][0000032b](05)  682b030000      push 0000032b
---[00000b62][00101527][0000032b](05)  e8f9f7ffff      call 00000360
Input_Would_Halt6 = 0
...[00000b67][0010152f][00000000](03)  83c408          add esp,+08
...[00000b6a][0010152f][00000000](02)  33c0            xor eax,eax
...[00000b6c][00101533][00000000](02)  8be5            mov esp,ebp
...[00000b6e][00101537][00100000](01)  5d              pop ebp
...[00000b6f][0010153b][00000080](01)  c3              ret
Number_of_User_Instructions(33)
Number of Instructions Executed(26452)

```

**Halting problem proofs refuted on the basis of software engineering**
> -6 votes

---
Tags: computability, halting-problem, c
---


# Question
Title: Is $\{ w_1cw_2 \mid w_1 ≠ w_2 \}$ a context-free language?
Is the language $L\_1 = \\{w\_1cw\_2 ~|~ w\_1,w\_2 \in \\{a,b\\}^{\ast} \text{ and } w\_1 \neq w\_2\\}$ a context-free language?

It certainly isn't regular, but is it context free?

I'm having trouble creating a grammar that creates terminal symbols from the outside-in; Is there anything to look for explicitly that tells me it is/isn't CF?

And if it was in fact context-free, how would I go about proving that?

# Answer
The idea is that $w\_1 \neq w\_2$ if and only if either (1) $|w\_1| \neq |w\_2|$ or (2) the $i$th letters of $w\_1,w\_2$ are different. This leads to the following partition of $L\_1$: $$ \begin{align\*} L\_1 &= (a+b)^+(a+b)^nc(a+b)^n \\ &\cup (a+b)^nc(a+b)^n(a+b)^+ \\ &\cup (a+b)^na(a+b)^\*c(a+b)^nb(a+b)^\* \\ &\cup (a+b)^nb(a+b)^\*c(a+b)^na(a+b)^\* \end{align\*} $$ Each of the summands is clearly context-free, hence so is their union.
> 6 votes

# Answer
Grammar for this language based on @Yuval Filmus's answer:

$S \rightarrow X\_{1}$| $X\_{2}$|$X\_{3}b \Sigma^{\*}$|$X\_{4}a \Sigma^{\*}$

$X\_{1} \rightarrow \Sigma X\_{1} \Sigma$|$\Sigma^{+} c$

$X\_{2} \rightarrow \Sigma X\_{2} \Sigma$|$c \Sigma^{+}$

$X\_{3} \rightarrow \Sigma X\_{3} \Sigma$|$a \Sigma^{\*} c$

$X\_{4} \rightarrow \Sigma X\_{4} \Sigma$|$b \Sigma^{\*} c$

$\Sigma^{+} \rightarrow \Sigma \Sigma^{\*}$

$\Sigma^{\*} \rightarrow a \Sigma^{\*}$|$b \Sigma^{\*}$|$\epsilon$

$\Sigma \rightarrow a$|$b$
> 0 votes

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


title: maximum span between two numbers

text:
# Question
Title: maximum span between two numbers
We have an array of `n` measurements: `(m_0, m_1, ..., m_n-1)`. The measurements are voltages, but that's not important, so let's say they are just numbers. The measurements can be positive, negative or zero. There are no NaNs or infinites, only "regular" numbers. We are given a certain non-negative `threshold`.

We want to find two indices `(i, j)` in `[0, n-1]` such that:

* `j >= i`
* `m_j >= m_i`
* `m_j - m_i` does not exceed `threshold`
* `j - i` is maximum
* if there are several pairs which satisfy the above conditions and for which `j - i` is equal, any of those pairs is OK

Examples:

* the measurements are `(-1.5, -3.6, 2.2, 0, 3.0)`, `threshold` = 3.8 =\> return `(0, 3)`
* the measurements are `(1.1, 0, -1.5, -1.7)`, `threshold` = 1 (or any number \>= 0) =\> return `(0, 0)`, or `(1, 1)`, or `(2, 2)`, or `(3, 3)`

We can easily come up with a brute force solution: for each `i` in `[0, n-1]`, examine each `j` in `[i+1, n-1]`, and remember the best answer. This is `O(n^2)`. We currently have no more than tens of thousands of measurements, so `O(n^2)` is kind of OK, but the maximum number of measurements is expected to grow up to millions, perhaps tens of millions. Then, `O(n^2)` will no longer be OK.

We are wondering whether there's a better algorithm. I doubt one can do this in `O(n)`, but perhaps in `O(n*long(n))` by sorting the measurements in some clever way?

# Answer
> 1 votes
I think you can solve this problem in $O(n \log n)$ time. I'll list two solutions.

# Pareto optimality + binary search

In a preliminary stage, find the Pareto front, where a pair $(j,m\_j)$ is better (dominates another pair) if $j$ is larger and $m\_j$ is smaller. This can be done in $O(n \log n)$ time: see How do you compute the Pareto Front of a set?, minimum subset of dominating 2D points.

Put the Pareto optimal solutions in an array $P$. This array will be sorted by increasing $j$ and decreasing $m\_j$.

Now repeat the following, for each $i := 0,1,\dots,n-1$:

* Use binary search in $P$ to find the largest $j$ such that $j \ge i$ and $m\_j \le m\_i + \text{threshold}$. This can be done by binary search in $P$, by finding the location of index $i$ in $P$, then using binary search on the subsequent $m\_j$ values.
* If $j-i$ is larger than any previously remembered pair, remember the pair $i,j$.

Finally, output the best pair $i,j$ seen during this procedure (i.e., the one where $j-i$ is largest).

Each binary search takes $O(\log n)$ time, and you do $n$ of them, so the total running time is $O(n \log n)$.

Please check the details on this, to be sure whether it actually works. I have not checked it carefully.

# Self-balancing binary search tree

Alternatively, store all the $(j,m\_j)$ values in a self-balancing binary search tree, keyed on $m\_j$, with each $(j,m\_j)$ value stored in a leaf, so the leaves are sorted by the value of $m\_j$. Augment this tree so that each internal node $x$ stores the maximum of all $m\_j$ values in the leaves under $x$, and also stores the maximum of all $j$ values in the leaves under $x$.

Now, for $i=0$, let's find the largest $j$ such that $m\_j-m\_i \le \text{threshold}$. You can do this as follows: there is a set of $O(\log n)$ subtrees whose union contains all the leaves with $m\_j$ values satisfying $m\_j \le m\_i + \text{threshold}$ (and no other leaves); use the augmentations in the parent nodes for those subtrees to find the largest value of $j$ among all of those subtrees; and output $j-i$.

Next, delete $m\_i$ from the tree, set $i:=1$, and repeat.

In each step, we delete one element from the tree, increment $i$, and examine $O(\log n)$ subtrees.

Finally, we keep the best pair that was outputted (i.e., the pair with the largest value of $j-i$).

Since all operations on a self-balancing binary search tree can be done in $O(\log n)$ time, and you can find the $O(\log n)$ subtrees in $O(\log n)$ time, the total running time for this algorithm is $O(n \log n)$.

---
Tags: maximum-subarray
---


title: Competitiveness of online algorithm

text:
# Question
Title: Competitiveness of online algorithm
Is it possible for an online algorithm to perform better than the optimal solution for the offline version of a problem, and if so, in what circumstances?

Doesn't competitive ratio rely on the fact that online algorithm can only reach at most the same performance as the optimal offline solution ?

# Answer
Say there exists some optimal online algorithm $A$ that is better than any offline algorithm. We can create an offline algorithm $A'$ such that when $A'$ receives the input sequence, it will not perform any preprocessing; instead it will feed each request to $A$ one at a time. This offline algorithm must be optimal, given that $A$ is optimal and better than any other offline algorithm.

With this, the performance of the online can never be better than the optimal offline one.
> 1 votes

# Answer
If you have an online algorithm, you can always execute it offline by feeding the elements one at a time, and there's no loss of efficiency. So offline can beat online, and not conversely.
> 1 votes

---
Tags: online-algorithms
---


# Question
Title: Whether the class of languages with time complexity between polynomial and exponential is an NP language？
We know that the P language class is a polynomial-time solvable language class, and the NP language class can be determined in exponential time. And there exist some languages that can be decided only in exponential time and no polynomial time solution has been found yet, such as SAT language.

My question is whether the class of languages with time complexity between polynomial and exponential is an NP language？i.e., whether it can be determined in polynomial time by non-deterministic Turing machines？

# Answer
> 1 votes
This problem is open. In fact, we cannot even rule out the stronger claim that NP = EXP. This is almost certainly false but proving it is beyond what current techniques can do.

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


# Question
Title: If an array is stored from higher region of memory to lower region, how'll the indexing formula look like?
If an array is stored from lower region of memory to higher region, we've this indexing formula.

$$ Address (A\[i\]) = M+(i-L)\*w$$

Where:

M = memory location where first element is to be stored.

L= Lower bound for index

i = index

w = word length

But for the case in question, we have:

$$L\<i\<U$$

$$A\_i \> A\_{i+1}$$

# Answer
If the array grows from a higher address to lower address, you need to subtract the offset from base address $$Address(A\[i\])=M-(i−L)∗w$$
> 0 votes

# Answer
From the formula,

$$ \text{Address} (A\[L\]) = M+(L-L)\*w=M$$ and $$ \text{Address}(A\[U\]) = M+(U-L)\*w$$

If $\text{Address} (A\[L\])\>\text{Address} (A\[U\])$, you conclude that $w\<0$.
> 0 votes

---
Tags: data-structures
---


# Question
Title: Building the minimal automaton from the syntactic monoid of a language
I'm studying the algebraic view of automata theory. One of the basic results is that the **syntactic monoid** of a language $L$ is the transition monoid $M(A)$ of the **minimal automaton** $A(L)$ accepting $L$. It is also very easy, from a monoid $M$ and a morphism $\mu:\Sigma^\*\to M$, to build an equivalent deterministic automaton $A(M)$ by using the monoid itself as the set of states and the morphism to build the transition function.

However, if I understand well, $A(M(L))\ne A(L)$, *i.e.* the syntactic monoid is the transition monoid of the minimal automaton, but the automaton I trivially get from the syntactic monoid is not the minimal automaton. Of course, to get $A(L)$ one could minimize $A(M(L))$, but I wonder if there is a more direct definition or construction.

So if the above is correct, is there a way to get the actual minimal automaton $A(L)$ from the syntactic monoid $M(L)$, without building $A(M(L))$ and then minimize it?

# Answer
> 4 votes
No, we cannot compute $A(L)$ from $M(L)$ without first building $A(M(L))$, essentially because $A(M(L))$ is obtained from $M(L)$ by forgetting some information; in other words, if you are given $M(L)$, then, you know $A(M(L))$ without having to do any computation.

---
Tags: finite-automata, reference-request
---


# Question
Title: Detecting if three Turing Machines halt given a magic oracle that is only used twice
We were given a question in class as follows:

You have a "magic oracle" that can decide if a Turing Machine halts. You have three TMs $T\_1, T\_2, T\_3$. Device an algorithm that decides which of the TMs halt and which do not by asking the oracle at most twice.

The sketch of the solution given was

Construct a new TM $T\_A$ that terminates if at least 2 TMs (from $T\_1, T\_2, T\_3$) halts. Construct a new TM $T\_B$ that terminates if one TM halts.

First call oracle on $T\_A$. If $T\_A$ halts: Run $T\_1, T\_2, T\_3$ in parallel until two of them halt, then call the oracle on the last TM that does not finish running.

If $T\_A$ doesn’t halt:

Call oracle on $T\_B$, If $T\_B$ halts: Then run $T\_1, T\_2, T\_3$ in parallel until one of them halts. That TM is the only one that halts

If $T\_B$ does not halt: then $T\_1, T\_2, T\_3$ all do not halt.

---

I did not agree with this solution, as formalising the proof would mean $T\_A$ and $T\_B$ are Oracle Turing Machines that must ask the oracle about the termination of $T\_1, T\_2, T\_3$. The professor replied

> They don't use magic oracles internally, because they are not claimed to detect termination, they just terminate if and only if other machines terminate, which can be achieved through concurrent interpretation of that machines.

Is this right? How would you go about formalising this? Thanks.

# Answer
One way to built $T\_A$ works is roughly as follows:

```
While (true) {
   run $T_1$ for 10 steps, if $T_1$ halts during that time, $i := 1$, break;
   run $T_2$ for 10 steps, if $T_2$ halts during that time, $i := 2$, break;
   run $T_3$ for 10 steps, if $T_3$ halts during that time, $i := 3$, break;
}

While (true) {
   if not $i = 1$
       run $T_1$ for 10 steps, if $T_1$ halts during that time, break;
   if not $i = 2$
       run $T_2$ for 10 steps, if $T_2$ halts during that time, break;
   if not $i = 3$
       run $T_3$ for 10 steps, if $T_3$ halts during that time, break;
}

halt

```

As you see, there is no magic involved.
> 18 votes

# Answer
As Arno shows in the other answer, you can easily write a program that halts if and only if at least $k$ out of $n$ given Turing machines halt, by running the $n$ machines in parallel until $k$ of them have halted. As a bonus, if you actually run this program (instead of just asking the oracle about it), it will tell you *which ones* were the $k$ it found to halt.

So if someone gives you $2^{n}-1$ Turing machines, and an oracle that will tell you whether a given TM will halt, you can do a binary search with the oracle, using it just $n$ times, to determine exactly how many of the TM's halt. Once you know this number, then you can actually run the program for this $k$ to figure out which ones halt.

If $k=2$, this solves the stated problem, only slightly differently from the provided solution.

Although it might sound like this is a general procedure that reduces $2^n-1$ oracle queries down to just $n$ oracle queries, and so by repeating the reduction you could arbitrarily reduce the number of queries, that doesn't actually work, because each of the $n$ queries you make depends on the results of the previous queries, whereas the $2^n-1$ machines do not depend on each other.
> 8 votes

# Answer
The key point here is that $T\_A$ and $T\_B$ does not know whether any of the TMs will halt. It just simulates all TMs, and it will halt if 2 of them (1 for $T\_B$) halt. If none of them halt, then $T\_A$ also won't halt, which is why $T\_A$ and $T\_B$ are not oracle, since they are not guaranteed to halt, unlike the actual oracle, which is guaranteed to halt and give an answer.
> 0 votes

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


# Question
Title: What is this question actually asking for me to solve?
(15 marks) Suppose a ray comes from a point (2, 8) and hits at mirror point (6, 6). Assume that perpendicular vector a point (6, 6) is ̅= (0, 3). Find the reflection emitting point from (6, 6).

\[Assume 2-D coordinate system, you must draw the appropriate diagram of your solution\]

I'm pretty sure I can figure out the diagram, but I can't figure out what information I've been given and what is left for me to calculate. I can't draw a diagram that makes sense with what is being described. Does anyone know what I'm being asked here?

# Answer
> 0 votes
IMO the question is about a trick to handle reflections: rather than computing the direction of the incoming ray and deriving the direction of the outgoing ray, you can construct the symmetric of the emission point wrt the mirror. Then the reflected ray is the line from the reflected point through the hitting point.

---
Tags: graphics, computer-graphics
---


# Question
Title: Show that a problem about permutations is NP-Complete
I want to prove that the following problem is NP-Complete.

> Input: Set $S = \\{s\_1, \dots, s\_n \\}$, set $T \subset S \times S$, that contains ordered pairs $(s\_i, s\_j) : s\_i \neq s\_j$, and an integer $k \geq 1$.
>
> Output: Is there a permutation $p:\\{1, \dots, n\\} \rightarrow \\{1, \dots, n\\}$ for the elements of $S$, so that there are at most $k$ pairs $(s\_i, s\_j) \in T$ such that $p(i) \> p(j)$ (i.e. pairs that are "inconsistent" with the order of the permutation)?

Due to the form of $S$ and $T$, which are reminiscent of vertices and edges, I tried to reduce a known NP-Complete problem with Graphs to the current one, but without success.

I tried using the Vertex Cover and the Sparse Subgraph problems (which may be wrong choices), by setting $S = V$ (vertices) and $T = E$ (edges) and tried to "encode" the presence of an edge as an "inconsistent" pair (as above mentioned). However, I cannot see how to use a property concerning permutations. I was also wondering if it is a wrong idea anyway to use reduction based on graphs.

I would appreciate any help.

# Answer
The decision version of the minimum feedback arc set problem is as follows: given a directed graph $G=(V,E)$ with no self-loops and an integer $k$, decide whether there is a set $F \subseteq E$ of edges such that $|F| \le k$ and the graph $G - F = (V, E \setminus F)$ is acyclic.

This is a well-known NP-Complete problem. To get an instance of the problem in the question pick $S = V$, and $T=E$ (the value of $k$ stays the same).

If there is a solution $F$ to the minimum feedback arc set instance, then $G-F$ is acyclic and hence there is a topological ordering $v\_1, \dots, v\_n$ of the vertices in $V$. Choosing $v\_i$ as the $i$-th element of the permutation $p$ we have that all edges $(v\_i, v\_j) \in E \setminus F$ satisfy $i \< j$, and hence there are at most $|F| \le k$ pairs in $T$ that are "inconsistent" with $p$.

Conversely, if there permutation $p$ with at most $k$ "inconsistencies" for the instance of the problem in the question, then we can choose $F$ as the set of all edges $(u,v)$ such that $u$ follows $v$ in $p$. This ensures that the permutation of $S$ is exactly a topological ordering of $G-F$, i.e., $G-F$ is acyclic. Since $|F| \le k$, $F$ is a solution to the minimum feedback arc set instance.
> 2 votes

---
Tags: complexity-theory, np-complete, decision-problem, polynomial-time-reductions
---


# Question
Title: A string that contains aabb, does this work?
Can you verify this like please bro please tell me the answer to my question

# Answer
> 1 votes
Have 5 states `S`, `Sa`, `Saa`, `Saab`, `Saabb`. Move to a state `Sxxx` after you parsed the first characters `xxx` of `aabb`, except you stay in the accepting state `Saabb` no matter what the input once you reached it.

```
S:     a->Sa,    b->S.
Sa:    a->Saa,   b->Sa.
Saa:   a->Saa,   b->Saab.
Saab:  a->Saab,  b->Saabb.
Saabb: a->Saabb, b->Saabb.

```

# Answer
> -2 votes
This automaton only accepts strings that START with aabb. You also need to accept strings such as baabb, bababaabbabab, aabaabb, etc.

---
Tags: finite-automata
---


title: O(nlogn)-time complexity

text:
# Question
Title: O(nlogn)-time complexity
Is there a $O(nlogn)$ time algorithm for computing $p(x)=\sum\limits\_{i=0}^na\_ix^i$ ?

I think with the method below I get O(n), but I need O(nlogn) Hint: there's a way to calculate $x^i$ more efficiently. This is exactly what I'm doing right ?

```
x = v

total = 0

for coef in coefs:

    total += coef * x
    x *= x

return total

```

# Answer
> 1 votes
Your solution (when fixed) indeed achieves the complexity $O(n)$ by computing the $x^i$ incrementally.

From a numerical standpoint, this is maybe not the best approach because of the accumulation of truncation errors along the multiplies. The power $x^i$ takes $i-1$ multiplies.

It is well-known that you can compute powers by successive squarings and products, and the power $x^i$ can be obtained with $O(\log i)$ multiplies. That will yield a total complexity $\sum O(\log i)=O(n\log n)$.

Now it is possible to combine both advantages, as follows:

* compute $x^0,x^1$;
* square $x^1$ and multiply with the above to obtain $x^2,x^3$;
* square $x^2$ and multiply with the above to obtain $x^4,x^5,x^6,x^7$;
* square $x^4$ and multiply with the above to obtain $x^8,x^9,x^{10},x^{11},x^{12},x^{13},x^{14},x^{15}$;
* and so on.

In total you will be performing $O(n)$ multiplies, and every power involves $O(\log i)$ of them.

---
Tags: time-complexity, polynomials
---


# Question
Title: What set.seed() mean in the Monte Carlo method
I'm trying to learn the implementation of the Monte Carlo method in R language. I am following a course with an example of predicting results for a board game. What I'm not understanding is the usage of a function that was implemented on the top of the code, and that is:

```
set.seed(5678)

```

Do you know what this function is used for and the meaning of the "5678" numbers inside the brackets?

# Answer
> 1 votes
When you wonder what a library function does, you should look it up. Get into the habit of reading the language or library's documentation. This can be more or less helpful depending on the quality of the documentation, but when the quality is good, that's your problem solved.

In this particular case, the reference documentation is admittedly pretty hard to follow. Searching for “`set.seed` R” on the web finds some good articles, e.g.    .

That being said, let me answer the on-topic aspect of the question, which is how **seeding the random generator** (which is what `set.seed` does) relates to the Monte-Carlo method.

A Monte Carlo method is an algorithm that uses random sampling to make approximate calculations. It's used when doing the full calculation with all the data would involve such a high volume of data that the calculation would be impossible in practice. So instead we do the calculation with a small subset of the data. This can only work if the subset is representative of the data.

To get a representative subset, we take data points at random. Statistically, in most physical systems, even a moderate amount of data points (e.g. thousands out of billions) are enough to get reasonably accurate results.

For programming, the downside of a random selection is that if you run the program twice, you'll get different results. The results should be approximately the same if the Monte Carlo method is suitable for the problem that's being solved, but they won't be identical. For example, you can't double-check someone else's calculation.

So instead of using an actual random selection, the program uses a **pseudorandom** selection. A pseudorandom generator (PRNG) is a source of numbers that is reproducible, but when you only look at the numbers, they're indistinguishable from a truly random source. (There are different levels of quality to the indistinguishability — for example cryptography requires a higher level of indistinguishability than Monte Carlo simulations.) The **seed** of a PRNG is an input to the generator, such that if you run the PRNG twice with the same seed, you get the same outputs. But if you run different seeds, you get different, independent outputs. A pseudorandom generator works just as well as a random generator because it's independent (in the probabilistic sense, but I'm not going to formalize this) from anything else, including the phenomenon you're modelling. (It's also independent from the same PRNG with a different seed.)

There is no significance to the value 5678. Any number would do (at least any number within the permissible range for that particular library function). You can use a different value and you'll get results that are different, but statistically equally representative of the phenomenon.

# Answer
> 1 votes
Unless a computer has special hardware to generate truly random numbers, it can only generate pseudo-random numbers. Pseudo-random means that the numbers seem random but are in reality generated by a deterministic algorithm. So they will always follow the same sequence of numbers, periodically (though the period can be absolutely astronomical\*).

To avoid always starting the random numbers at the same point in the period, *seeding* is used, meaning that you supply a number that changes the starting point. The seed is arbitrary, but it is up to you to keep the same or change it every time, depending on your needs.

---

\*In the old days, there were random generators with a period as small as 32767 or so, which is considered tiny. Nowadays, you can find generators with a period longer than the number of quarks in the universe.

# Answer
> 0 votes
A random seed is a number that is used to initialize a pseudorandom number generator. The resulting numbers that are generated will depend on the seed.

---
Tags: statistics, monte-carlo
---


# Question
Title: Given a graph `G`, what is the maximum number of "minimum" cycles it could have?
In graph `G`: a cycle $A$ is a **subcycle** of cycle $B$ if there exists vertices $c$ and $d$ such that:

* $cd$ is an edge of $A$.
* $F$ is the resulting path of $A$ after removing the edge $cd$.
* $E$ is a path from $c$ to $d$ of length at least $2$, and the cycle $B$ consists of the edges in $E$ and $F$

For example:

In the graph consisting of edges: `1,2` `2,3` `3,4` `4,1` `1,3` (with vertices `1`-`4`), then:

`3,4` `4,1` `1,3`

and

`1,2` `2,3` `1,3`

are both subcycles of

`1,2` `2,3` `3,4` `4,1`

---

A cycle is **minimal** if it has no subcycles.

---

**Given a graph `G`, what is the worst-case (maximum) number of minimal cycles it could have???**

My thought is a complete graph would have each triplet of vertices a minimum cycle, therefore about `n^3` but I don't know if that's right

---

The computer science application of this is:

To compute a Hamiltonian cycle, you could first start with a minimum cycle and then see if you can replace an edge in the cycle with a path of length at least `2` (finding a cycle we're a subcycle of). If you do this over and and over get lucky each time, you will end up with a Hamiltonian cycle.

# Answer
> 2 votes
If I understand correctly, you call a cycle "minimum" if it has no chord.

Then the number of minimum cycles can be exponential. As an example, start from a graph containing a single cycle $C$ and replace each edge $e = (u,v)$ with two "split" vertices $x\_e, y\_e$ and the edges $(u, x\_e), (x\_e,v), (u, y\_e), (y\_e,v)$.

Notice that, once you choose one of $x\_e$ and $y\_e$ for each edge $e$, you can build a chordless cycle that traverses exactly all original vertices of $C$ and all the chosen split vertices.

The resulting graph has $3n$ vertices and $2^{n}$ minimum cycles.

Here is an example of one such graph:

---
Tags: graphs
---


# Question
Title: Writing a linear program to model balanced bin packing
Say we want to write a (MI)LP to model the following problem:

> Find a parking plan for a set of cars $K=\\{1, ..., k\\}$ with lengths $\lambda\_i$. Parking is organised in lanes $P=\\{1, ..., p\\}$. The *length* of a lane is the sum of the cars parking there and may not exceed a specified constant $L$. The goal is to **balance the lengths of the parking lanes as well as possible**. More specifically, we want to minimise the difference of the length of a longest and shortest line.

To me, this seems quite akin to some variant of the Bin Packing problem. Usually, however, we want the number used bins to be minimised.

Here, I am quite confused on how I could come up with an objective function that expresses the balance between the lanes/bins. My main problem is that -- as far as I understood it -- the objective function has to be linear. Thus, I couldn't use operations like max, min, absolute value etc.

Can someone help me out here with a hint?

# Answer
> 0 votes
Define a variable $b$ that represents the imbalance between the lengths of the parking lanes. For instance, if $b=5$, that means that the lengths of every pair of parking lanes differs by at most 5. Define other variables to represent the lengths of the parking lanes.

Write constraints to enforce that $b$ is set consistently with your other variables.

Minimize $b$.

# Answer
> 0 votes
Not exactly what you asked, but if you define $b$ as the maximum length reached, you can minimize $b$ and get something similar to what you desire.

Let's say that $X\_p$ is a variable that represents the number of cars parked in lane $p$. So, you could add constraints like:

$b \geq X\_p, \forall p \in P$

If you minimize $b$, and there is no other constraint that avoids that, the minimum value of $b$ is the value than minimizes the difference across lanes.

---
Tags: linear-programming
---


# Question
Title: Is checking whether a a set of 3-literal clause is satisfiable such that every literal in each clause is either all true or all false NP-complete?
I want to know if checking whether a a set of 3-literal clause is satisfiable such that every literal in each clause is either all true or all false NP-complete?

By 3-literal clause, I mean it can have a clause can have at most 3 literals.

I think this problem is NP-complete or co-np complete as it seems like a complement of 3-NAE-SAT?

I want to know if its NP-complete and if it is then does there exist a reduction from 3-NAE-SAT to this variant of SAT which we may call 3-All-Equal-SAT?

# Answer
> 4 votes
The problem can be solved in polynomial time. Construct a new formula as follows:

* The set of variables of the new formula is the set of variables of the original instance plus one variable $x\_c$ for each clause $c$. The idea is that all literals in $c$ will be forced to have the same value of $x\_c$.
* For each clause $(\ell\_1, \ell\_2, \ell\_3)$ of the original instance, and for each $i \in \\{1,2,3\\}$, create the following clauses: $(x\_c \implies\ell\_i) \wedge (\overline{x}\_c \implies \overline{\ell\_i})$, which can be equivalently written as $(\overline{x\_c} \vee \ell\_i) \wedge (x\_c \vee \overline{\ell\_i})$.

Notice that the resulting formula is an instance of 2-SAT, which can be solved using standard algorithms.

---
Tags: complexity-theory, 3-sat, schaefers-dichotomy
---