# Question
Title: Brute force algorithm for "Binary Puzzle"
## Binary puzzle

Binary puzzle is an puzzle played on a $n × n$ grid; intially some of the cells contain a zero or a one (fixed cells); the aim of the game is to fill the remaining empty cells according to the following rules:

* Each cell should contain a zero or a one.
* No more than two similar numbers next to or below each other are allowed.
* Each row and each column should contain an equal number of zeros and ones.
* Each row is unique and each column is unique.

---

**Decision problem:**

> **Input :** A partially filled n×n grid with 0's and 1's.
>
> **Question :** Can we fill the empty cells with a zero or a one in a way that follow the above mention rules ?

For $n \times n $ this problem known to be NP-complete.

**Brute force Algorithm :**

1. If the given $n \times n$ is empty then it is an yes instance ( use the basis set of $ \mathcal{ R^{n\times n}}$).
2. Case I: If only one row is filled and it is an valid row (follow the above mentions rules ) then it is an yes instance. Second row is going to be the complement of first row (make 0 to 1 and 1 to 0).
3. Case II : if $k$ rows are filled and they are valid then I can fill the table upto 2k rows by using trick of complement.

**Question** : How to design a brute force algorithm for the problem stated above ?

# Answer
> 2 votes
For $k$ fixed cells, you try all $2^{n^2-k}$ possibilities of filling the remaining $n^2-k$ cells and check for each fully filled board whether it fulfills all stated constraints.

---
Tags: algorithms
---


# Question
Title: Is possible to prove undecidability of the halting problem in Coq?
I was watching the "Five Stages of Accepting Constructive Mathematics" by Andrej Bauer and he says that there is two kinds of proof by contradiction (or two things that mathematicians call proof by contradiction):

1. Assume $P$ is false... blah blah blah, contradiction. Therefore $P$ is true.
2. Assume $P$ is true... blah blah blah, contradiction. Therefore $P$ is false.

The first one is equivalent to the Law of Excluded Middle (LEM) and the second one is to how prove negation.

The proof of the undecidability of the Halting Problem (HP) is a proof by contradiction: assume there is a machine $D$ that can decide the HP... blah blah blah, contradiction. Therefore $D$ does not exist.

So, let $P$ be "$D$ exists and can decide the HP". Assume $P$ is true... blah blah blah, contradiction. Therefore $P$ is false.

This looks like the second kind of proof by contradiction, so is possible to prove the undecidability of the halting-problem in Coq (without assuming LEM)?

EDIT: I would to see some points about proving this using contradiction. I know that this can also be proved using diagonalization.

# Answer
You're exactly right that the halting problem is an example of the second kind of "proof by contradiction" - it's really just a negative statement.

Suppose `decides_halt(M)` is a predicate that says that machine `M` decides if its input is a machine that halts (that is, `M` is a program that for some machine `m` and input `i`, decides if `m` halts on input `i`).

Forgetting for a moment about how to prove it, the halting problem is the statement that there is no machine that decides the halting problem. We might state this in Coq as `(exists M, decides_halt M) -> False`, or maybe we prefer to say any given machine doesn't solve the halting problem `forall M, decides_halt M -> False`. It turns out that without any axioms these two formalizations are equivalent in Coq. (I've spelled out the proof so you can see how it works, but `firstorder` will do the entire thing!)

```
Parameter machine:Type.
Parameter decides_halt : machine -> Prop.

(* Here are two ways to phrase the halting problem: *)

Definition halting_problem : Prop :=
  (exists M, decides_halt M) -> False.

Definition halting_problem' : Prop :=
  forall M, decides_halt M -> False.

Theorem statements_equivalent :
  halting_problem <-> halting_problem'.
Proof.
  unfold halting_problem, halting_problem'; split; intros.
  - exact (H (ex_intro decides_halt M H0)).
  - destruct H0.
    exact (H x H0).
Qed.

```

I think either statement isn't too difficult to prove as a diagonalization argument, though formalizing machines, computability, and halting is probably reasonably challenging. For a simpler example, it's not too hard to prove Cantor's diagonalization theorem (see https://github.com/bmsherman/finite/blob/master/Iso.v#L277-L291 for a proof that `nat -> nat` and `nat` are not isomorphic).

The diagonalization above gives an example of how you might go about deriving a contradiction from an isomorphism between `nat -> nat` and `nat`. Here's the essence of that proof inlined as a self-contained example:

```
Record bijection A B :=
  {  to   : A -> B
  ; from : B -> A
  ; to_from : forall b, to (from b) = b
  ; from_to : forall a, from (to a) = a
  }.

Theorem cantor :
  bijection nat (nat -> nat) ->
  False.
Proof.
  destruct 1 as [seq index ? ?].
  (* define a function which differs from the nth sequence at the nth index *)
  pose (f := fun n => S (seq n n)).
  (* prove f differs from every sequence *)
  assert (forall n, f <> seq n). {
    unfold not; intros.
    assert (f n = seq n n) by congruence.
    subst f; cbn in H0.
    eapply n_Sn; eauto.
  }
  rewrite <- (to_from0 f) in H.
  apply (H (index f)).
  reflexivity.
Qed.

```

Even without looking at the details, we can see from the statement that this proof takes the mere existence of a bijection and demonstrates it to be impossible. We first give the two sides of the bijection the names `seq` and `index`. The key is that the bijection's behavior at the special sequence `f := fun n => S (seq n n)` and its index `index f` is contradictory. The halting problem's proof would derive a contradiction in a similar way, instantiating its hypothesis about a machine that solves the halting problem with a carefully chosen machine (and in particular one that actually depends on the assumed machine).
> 20 votes

---
Tags: halting-problem, coq
---


title: Time Complexity of a iterative program

text:
# Question
Title: Time Complexity of a iterative program
```
sum = 0;
for (int i = 1; i <= n; i++ )
    for (int j = 1; j <= i*i; j++)
        if (j % i ==0)
            for (int k = 0; k < j k++)
                sum++;

```

I am trying to find out time complexity of this above program.

First "for loop" will run n times.

Second for loop will execute overall n^3 times

The innermost loop will execute when j is multiple of i, that will happen exactly i times.

Please help me to find the overall time complexity of this program.

# Answer
> 1 votes
The number of times that the `if` statement is executed is $$ \sum\_{i=1}^n i^2 = \Theta(n^3). $$ The number of times that `sum` is incremented is $$ \sum\_{i=1}^n \sum\_{j'=1}^i ij' = \sum\_{i=1}^n i \sum\_{j'=1}^i j' = \sum\_{i=1}^n \Theta(i^3) = \Theta(n^4). $$ Here $j' = j/i$, and the reason we are allowed to do this is that the inner loop gets executed only when $j'$ is integral.

We get that overall, the running time is $\Theta(n^4)$.

# Answer
> -1 votes
The rule to calculate time complexity is to measure how many times (at most) will your code run compared to input. in our case, we have the input as *n*

the outermost loop runs *n* times, so this loop has a complexity of *O(n)*, assuming code inside this loop is static.

Then comes next level, a loop that explicitly run *n2* times, that makes an *O(n2)* piece of code.

Then we have an `if` block, that would have a complexity \_O(1) because it would not scale on *n* size

and finally, a loop that runs *j* times; *j* has an upper bound of *n2* , that should make the inner most loop of *O(n2)*

That makes the overall complexity = *n* × *n2* × *n2* = *n5* i.e. *O(n5)* not *O(n4)*

---
Tags: algorithms, algorithm-analysis, runtime-analysis, loops
---


# Question
Title: Is there a programming language that is not a formal language
Are out there, any programming languages that are not defined algorithmically so that we can call them "constructed languages" but not "formal languages"? Are there any discussions or papers on that topic? It seems pretty hard to develop a compiler for this kind of languages.

# Answer
> 4 votes
No, at least not a reasonable programming language by what we commonly understand under that term.

As soon as you have a compiler (or an interpreter), you have an algorithm that decides whether a given string is a valid program. This compiler then defines the language. (Not a *good* way to define a programming language, but a workable one.)

# Answer
> 1 votes
According to this article, MIT did look into the possibility of writing simple programs using natural language, relying somehow on regular expressions.

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


# Question
Title: DFA and equivalence classes: counting odd numbers of b's
I am studying for an exam and found an exercise about finding the equivalence classes for $L=a^\*ba^\*(ba^\*ba^\*)^\*$, the language over $\\{a,b\\}^\*$ with an odd number of b's.

We found three equivalence classes: $\[a^\*\], \[a^\*ba^\*(ba^\*ba^\*)^\*\], \[a^\*ba^\*ba^\*(ba^\*ba^\*)^\*\]$. This means the minimal DFA would have three states, and it was given so:

But it seemed to me that the following DFA with two states would achieve the same result (by merging q0 and q2).

This is a contradiction with having three equivalence classes.

What went wrong here, and where?

# Answer
Your first and third equivalence classes are equivalent to one another. They both contain strings in which there are an even number of $b$s: in the first class, that number is zero; in the third class, it's at least two. For any string in either of those classes, adding a string with an odd number of $b$s gives a string in the language, and adding a string with an even number gives a string not in it.
> 2 votes

---
Tags: formal-languages
---


title: Lower bounds: Detecting a length 2 path

text:
# Question
Title: Lower bounds: Detecting a length 2 path
> Prove that determining if a non-directed graph of $n$ vertices has or doesn't have a length $2$ path requires time $\Omega(n^2)$, assuming that the graph is represented as an adjacency matrix.

# Answer
Suppose the algorithm does less than $\frac{n^2-n}{2}-2(n-1)$ accesses to the matrix, then, there is at least one column (restricted to the upper triangular part of the matrix) such that there are at least two elements the algorithm have never checked.

This can be proved by contradiction, if every column has at most one unchecked element, then the algoritm have done at least $\frac{n^2-n}{2}-(n-1)$, but this contradicts the hypothesis.

Then, supposing every $a\_{ij}$ element the algorithm has checked is equal to $0$, whatever the output of the algorithm, it may be wrong. Indeed, if the algorithm sais there are no paths, then, in the "doublely unchecked" column can happen that $a\_{ij}=a\_{kj}=1$, so there will be a path $i\to j\to k$ whose lenght is two. Otherwise, if the algorithm says there is a path, the matriz could be entirely made of $0$'s.

Note that if the graph is represented with an adjacency list for each vertex the statement does not hold, beacause there is an easy algorithm in $\mathcal{O}(n)$.
> 1 votes

---
Tags: graphs, lower-bounds
---


# Question
Title: How does a nondeterministic Turing machine work?
What is differences between deterministic and nondeterministic Turing machines? Different but equivalent models of NDTM. In particular, what is this frequently used phrase "nondeterministically guess"? How to use it right, and examples of wrong usage. My goal is to create a reference question.

# Answer
> 9 votes
Here are several ways of thinking about non-determinism (copied from this answer).

**The genie.** Whenever the machine has a choice, a genie tells it which way to go. If the input is in the language, then the genie can direct the machine in such a way that it eventually accepts. Conversely, if the input is not in the language, whatever the genie tells the machine to do, it will always reject.

**Hints.** The machine computes a bivariate function. The first input is a word $w$, and the second input is a "hint" $x$. Whenever the machine faces a non-deterministic choice, it consults the next hint symbol, and operates accordingly. We are promised the following:

* *Completeness:* if $w \in L$ then there is some hint $x$ which causes the machine to accept.
* *Soundness:* if $w \notin L$ then the machine rejects on all hints.

**Accepting computations.** An accepting computation is a legal computation (one in which the machine always operates according to one of the choices it is faced with) which ends at an accepting state. A word is in the language iff it has an accepting computation.

We can formalize the notion of accepting computation using *configurations*. A configuration is an instantaneous description of the entire state of the machine. We can define a relation $\sigma \vdash \sigma'$, where $\sigma,\sigma'$ are configurations, which holds when $\sigma$ can lead to $\sigma'$ in one step. In a deterministic machine, there is at most one $\sigma'$ per each $\sigma$, whereas in a nondeterministic machine, there could be more than one. An accepting computation for a word $w$ is one which starts at the initial configuration (the tape contains $w$, the head points at the start of $w$, the state is the initial state) and ends at an accepting configuration.

Another equivalent description is in terms of reachability. Consider a directed graph in which vertices are configurations and there is an edge from $\sigma$ to $\sigma'$ if $\sigma \vdash \sigma'$. An accepting computation is a path from the initial configuration to an accepting configuration.

# Answer
> 7 votes
**Acceptance of input string in NTM**

let me add more about deterministic and non-deterministic Turing machines. Let us consider that for some language $L$, we design a deterministic and non-deterministic Turing machine respectively. On some input $x$, there is going to be only one path of configurations in the case of deterministic Turing machine, i.e $c\_0 \longrightarrow c\_1 \longrightarrow \cdots \longrightarrow c\_k$ (where each $c\_i$ represents a configuration at $i$th step) . Now on the basis of configuration $c\_k$, we can easily accept and reject the input string $x$.

See the image below for better understanding :

In the case of NTM, we need to be careful, because it may happen that on some configuration paths, we get into rejecting state. So for non-deterministic Turing machines, **we say a string is accepted if at least one of the configuration path leads to accepting state**. We will reject the input string if all configuration paths lead to rejecting state.

For example, consider the configuration tree given above for non-deterministic Turing machine on say some input string $x$, In this case we will accept the input string because there is an one accepting path.

**Reference** : http://cs.umw.edu/~finlayson/class/fall14/cpsc326/notes/24-complexity2.html

# Answer
> 6 votes
The difference between deterministic and non-deterministic Turing machines lies in the transition function. In deterministic Turing machines $\delta$ the transition function is a partial function:

$\delta: Q \times B \to Q \times B \times \\{left, right\\} $

which means that given a state and a tape symbol you have one or none state, input symbol to right and direction to move. However in non-deterministic Turing machines this looks like (here $\mathcal{P}$ is the set of subsets of a set):

$\delta: Q \times B \to \mathcal{P}(Q \times B \times \\{left, right\\})$

meaning that you have none or several states, tape symbols to write or direction to move to. This gives to your machine the possibility to effectively choose in such a state and tape symbol between the different "branches" of computation possible.

In practice, this means that we can compute different outputs for the same input. Therefore, the language of a non-deterministic Turing machine is the set of words for which we find a derivation in the defined transitions. An specific run may not find such derivation but the important thing is that it may occur. So when you "guess" you're just choosing one of the possible branches of computation.

**Example of use**

$L = \\{(M\_1,M\_2):\text{there exists at least one word accepted by both TM at the same time}\\}$

In this case one could just "guess" a word $w$ and execute $M\_1$ and $M\_2$ on $w$ checking that if both accept, they accept at the same time. The guessing could work by introducing a state $q$ with transitions that write on some tape $0$s and/or $1$s and that exits by reading any symbol to the general machine.

To be honest I haven't come across any example of bad use of this "guess" but checking that each time this phrase is used is done correctly, reduces to verify that you could build an automata with this structure that simulated the guessing.

# Answer
> 5 votes
**Augmentation with a guessing module.**

I found this model in "*Computers and Intractability*" by M.R. Garey and D.S. Johnson.

> The NDTM has exactly the same structure as a DTM, except that it is augmented with a **guessing module** having it own write-only head. The guessing module provides the means for writing down the "guess" and is used solely for this purpose.

**How it works.**

> The first stage is the guessing stage. Initially, the input string $x$ is written in tape squares $1$ through $|x|$ (while all other squares are blank), the read-write head is scanning square $1$, the write-only head is scanning square $-1$, and the finite state control is "inactive". The guessing module then directs the write-only head, one step at a time, either to write some symbol from the tape alphabet $\Gamma$ in the tape square being scanned and move one square to the left, or to stop, at which point the guessing module becomes inactive and the finite state control is activated in state $q\_0$. The choice of whether to remain active, and, if so, which symbol from $\Gamma$ to write, is made by the guessing module in a totally arbitrary manner. Thus the guessing module can write any string from $\Gamma^\*$ before it halts and, indeed, need never halt.
>
> The "checking" stage begins when the finite state control is activated in state $q\_0$. From this point on, the computation proceeds solely under the direction of the NDTM program according to exactly the same rules as for a DTM. The guessing module and its write-only head are no longer involved, having fulfilled their role by writing the guessed string on the tape. Of course, the guessed string can (and usually will) be examined during the checking stage. The computation ceases when and if the finite state state control enters one of two halts states (either $q\_Y$ or $q\_N$) and is said to be **accepting computation** if it halts in state $q\_Y$. All other computations, halting or not, are classed together simply as **non-accepting computations**.
> Notice that any NDTM program $M$ will have an infinite number of possible computations for a given input string $x$, one for each possible guessed string from $\Gamma^\*$. We say that the NDTM program $M$ **accepts** $x$ if at least one of these is an accepting computation.
>
> The **time** required by an NDTM program $M$ to accept the string $x\in L\_M$ is defined to be the minimum, over all accepting computations of $M$ for $x$ , of the number of steps occurring in the guessing and checking stages up until the halt state $q\_Y$ is entered.
>
> The only point deserving special special mention is that, wheres we usually envision a nondeterministic algorithm as guessing a structure $S$ that in some way depends on the given \[problem\] instance $I$, the guessing module of an NDTM entirely disregards the given input. However, since *every* string from $\Gamma^\*$ is a possible guess, we can always design our NDTM program so that the checking stage begins by checking whether ot not the guessed string corresponds (under the implicit interpretation our program places on strings) to an appropriate guess for the given input. If not, the program can immediately enter the halt state $q\_N$.

. . .

> The class $NP$ is defined informally to be the class of all decision problems $\Pi$ that, under reasonable encoding schemes, can be solved by polynomial time nondeterministic algorithms.
>
> The use of term "solve" in these informal definition should, of course, be taken with a grain of salt. It should be evident that a "polynomial time nondeterministic algorithm" is basically a definitional device for capturing the notion of polynomial time verifiability, rather than a realistic method of solving decision problems. Instead of having just one possible computation on a given input, it has many different ones, one for each possible guess.
>
> It is this notion of polynomial time "verifiability" that the class $NP$ is intended to isolate. Notice that polynomial time verifiability does not imply polynomial solvability.

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


# Question
Title: Shouldn't the "even parity" function map 1101 to 0?
From the book *Computer organization and design* by Patterson&Hennessy:

> **Parity** is a function in which the output depends on the number of 1s in in the input. For an *even* parity function, the output is 1 if the input has an even number of ones. Suppose a ROM is used to implement an even parity function with a 4-bit input. Then the contents of the ROM is $$\text{Address} \ 0 : \ 0 \\ \text{Address} \ 1: \ 1 \\ \text{Address} \ 2 : \ 0 \\ \text{Address} \ 3 : \ 1 \\ \vdots \\ \text{Address} \ 13 : \ 1 \\ \text{Address} \ 14 : \ 0 \\ \text{Address} \ 15 : \ 1$$

As per my understanding, ROM which implements the *even* parity function should store 0 at both the Address 1 and the Address 2, 1 at the Address 3, ... 0 at both the Address 13 and 14, then 1 at the Address 15, for the Address $k$ to represent the map-value of $(k)\_{\text{base}2}$.

According to this the concept defined above is not clear enough, Can someone clarify the doubt?

# Answer
In this context, implementing something as a ROM just means a look-up table. If you want to know the parity of $x$, you put the binary coding of $x$ on the ROM's address wires and the value you read out is the value stored at that memory location within the ROM, which will be either 0 or 1.

And, yes, the contents of the ROM that you've quoted are wrong: they seem to be implementing parity in the sense that the output is 1 if, and only if, the input is an odd number, instead of implementing the even parity function.
> 2 votes

# Answer
While this isn't *exactly* an answer to the question, I will say that the Appendix of this edition is full of errors, including some really silly stuff on page B-12 claiming that an input is an output, and failing to include "+" between the sum of products. While I was able to track down the official errata list (https://booksite.elsevier.com/9780124077263/downloads/COD5e\_errata\_09-2014.pdf), it doesn't look like anything in Appendix B has been listed.
> 2 votes

---
Tags: logic
---


# Question
Title: Maximizing number of selected squares in a grid
We have an $n\times n$ grid of squares, each square has a non-negative integer. Two distinct squares are neighbours if they share a row or column. A selection of squares is good if every selected square has a number of selected neighbours less than or equal to its number.

Is there a known way to find the maximum number of elements in a good selection? Clearly there is a $\mathcal O(2^{n^2}n^2)$ brute force algorithm (we can test for goodness of a selection in time $\mathcal O (n^2)$ by precomputing number of selected squares in each row and column).

# Answer
> 0 votes
There is a dynamic programming algorithm whose running time is $O(2^{4n})$.

Suppose we have already chosen a configuration for the first $i$ columns. Mark a cell in the $i$th column as "red" if the cell to its right cannot be selected (i.e., the number of selected neighbors, not counting its right neighbor, is equal to the number in that cell), or "green" if the cell to its right can be selected.

Let $c \in \\{R,G\\}^n$ be a sequence of $n$ colors, and $x \in \\{0,1\\}^n$ be a sequence of $n$ bits. Define $A\[i,c,x\]$ to be the maximum number of elements in a good selection for the first $i$ columns that induces the coloring $x$ on the $i$th column and where $x$ describes which cells are selected in the $i$th column. Then it is easy to calculate $A\[i+1,c',x'\]$ from $A\[i,c,x\]$: we have

$$A\[i+1,c',x'\] = |x'| + \max\_{c,x} A\[i,c,x\],$$

where the max is taken over all $c,x$ that are consistent with $c',x'$ (i.e., such that it's possible to have a selection for the first $i+1$ columns that has selection $x$ in column $i$, selection $x'$ in column $i+1$, colors $c$ in column $i$, and colors $c'$ in column $i+1$). To be consistent, we must have $c\_j=R \implies x'\_j=0$ for all $j$, and $x\_j + x'\_{j-1} + x'\_{j+1}$ must be at most the number in column $i+1$, row $j$ (and $c'\_j=R$ iff they are equal).

This yields a dynamic programming algorithm with $O(n \times 2^{4n})$ running time: we need to fill in $n \times 2^{2n}$ entries of $A\[\cdot,\cdot,\cdot\]$, and each entry requires us to compute a max over at most $2^{2n}$ numbers.

---
Tags: algorithms, graphs, optimization, square-grid
---


# Question
Title: Mathematics topics or fields that increase computer programming proficiency?
Generally computer programmers who are mathematicians or have mathematics background are very good in terms of algorithms and computer programming in general.

**What I am not saying:**

Mathematics is needed to be a good computer programmer. Mathematics is necessary for programming. Good mathematicians are good programmers and vice versa

**What I am saying**

I would like to learn some mathematics because I believe it will make me a better programmer. What areas/topics of mathematics will help me to become a better programmer? Answers of the form `math topic - corresponding cs area` will be appreciated.

**NB:** I asked this on StackOverflow where it was declared off-topic. I want to learn it during my spare time just the way I have been doing with computer programming. Thanks in advance.

# Answer
So, there are many fields of math that are relevant to the Science of CS, but for programming specifically:

* **Graph theory**: this is the big one. Graphs and trees are everywhere. Networks, maps, paths in video games. Even things like solving a Rubiks cube can be modelled as a graph algorithm and solved with A\*.
* **Discrete math**: aside from graph theory, knowing this area in general is helpful. It's full of proofs by induction, which are very useful for understanding recursion, which is very useful in programming, particularly with data structures. Knowing about sets, counting, inclusion-exclusion, boolean logic, etc. can come in handy once in a while.
* **Type theory:** unsurprisingly, knowing type theory helps with understanding programming in typed languages, and more broadly, with using types as a way of ensuring certain correctness properties. Knowing about the theory of subtyping helps you to understand covariance and contravariance in Java-like languages. Knowing about things like parametric polymorphism is obviously helpful when learning a type-heavy language like Haskell or Purescript, but langauges like Scala, TypeScript, and Rust are becoming more prevalent in industry, and types are at their cores.

If you take this one to its extreme, you get things like Coq and Agda and Idris, which can be used to prove extremely precise correctness properties about programs.
* **Computability and Complexity Theory**: knowing when a problem is either unsolvable, or NP-hard, is useful, because you won't waste hours racking your brain for a fast way to do it. Likewise, knowing some of the theory behind approximation algorithms, fixed-parameter tractability, or low-base exponential algorithms, can help when you really need to solve an NP-hard problem.
* **Automata theory:** many problems can be modelled with various state machines, so understanding their properties is useful.

There are also some field-specific areas:

* **Statistics:** If you're doing machine learning or big-data, this is a must.
* **Linear algebra/vector calc**: both of these are important for machine learning, graphics, simulations, or image/audio processing.
* **Lattice theory**: if you're doing any work with compilers or program optimization, this one comes up all the time. Fixed points everywhere!
* **Category theory:** not needed to code, but useful for anything deeply drenched in type theory.

Edit: can't believe I forgot:

* **Cryptography**: if you're interested in security, hashing, digital signatures and such, then make sure to learn some number theory, Group Theory, Field theory, elliptical curve Theory, etc.
> 20 votes

---
Tags: mathematical-foundations
---


# Question
Title: Pumping Lemma for single character language
I have a question about the Pumping lemma. Condition $2$ of the pumping lemma for a string division $xyz$ states that the middle portion of the string $y^i$ can be 'pumped' for any $i$ greater than or equal to $0$. This means that y can be the empty string and yet still belong to the language. At the same time, the cardinality $|y|$ has to be at least $1$.

How would I be able to apply this if the regular language is only a single character? i.e. $L = \\{a\\}$. Here, I can set $y = \\{a\\}$ so that the cardinality is greater than zero --- however, it fails to meet the condition that $y$ can be 'pumped down' to the empty string....

But obviously, $L =\\{a\\}$ is a regular language.

And there's also something obvious that I missed ...

# Answer
You interpret the lemma incorrectly. The lemma says that "there is $n$ such that any string $y \in L$, with $|y| \geq n$...". So the lemma does not provide a particular $n$, it only says "there is", not "for all".

If the language is finite then, the pumping length is greater than the longest string in the language. And hence the three conditions of the lemma fails for all strings in the language, meaning there is nothing to "pump". Nevertheless, the lemma holds. Just recall the implication rule $p \implies q$: if $p$ is false then it does not matter if $q$ is true or false, the whole implication is true.

In your example with a single string $a$ take $n$, the pumping length to be $2$. So there is no string of the length greater than or equal to $2$. But it does not mean that the lemma fails.

**Update:**: the following predicate formula expresses the Pumping lemma for regular languages $$\[ L \text{ is regular }\] \implies \[\exists n\forall x\[ \left((x \in L) \land (|x| \geq n) \right) \implies (\exists u \exists uv \exists w(x=uvw \land |uv| \leq n \land |v| \> 0 \land \forall m\[m\>0 \implies uv^mw \in L))\]\]\]$$

and this is antecedent (conclusion) part of the lemma: $$\exists n \forall x\[ \left((x \in L) \land (|x| \geq n) \right) \implies (\exists u \exists uv \exists w(x=uvw \land |uv| \leq n \land |v| \> 0 \land \forall m\[m\>0 \implies uv^mw \in L))\]\]$$

This **premise** of the antecedent $(x \in L) \land (|x| \geq n)$ is false since $|x|$ is less than $n$ (for each $x \in L$) and hence the whole antecedent is true.
> 3 votes

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


title: What is random logic? Why is it needed?

text:
# Question
Title: What is random logic? Why is it needed?
I read now several articles about RISC and CISC architecture. Most are rather exuberant enumerating all the differences between these architecture, but not necessarily why things are the way they are.

One point that struck out to me the most was about the RISC's feature of using hard wired parts in its processor and in particular so called "Random Logic" . According to wikipedia one might best view it as a "simple" decoder from "high level logic" to hardware features like AND and OR gates.

Unfortunately I didn't find more about "Random Logic", so I am a bit at a loss of its concept, design, purpose and why it is needed.

So I hope someone could go into more detail or simply provide references to read up on that topic online.

# Answer
This all deals with one of the major, and complex tasks in any processor. Namely decoding instructions. On a simple conceptual level, this may be viewed as taking the contents of the instruction register and translating this into logic commands to the various functional units of the processor to perform the desired action and then fetch the next instruction into the instruction register and repeat.

Traditionally there are two competing camps called Random Logic and Microcode.

The random logic camp tends to look at the task as a sort of huge logic problem. Given an input (the instruction set), what outputs are needed (the instruction implementation). The result tends to look like a huge array of gates, flip-flops etc arranged in a non-intuitive (looking random, but no actual randomness here). Needless to say, for any non-trivial processor, this can be really complex.

The microcode camp on the other hand, maps each instruction to a stored program for a very simple but fast processor. Often, the microcode program is stored in very wide memory so that many program units can be simply connected to fields in the microcode with little or no additional decoding. In a sense, the microcode is implementing the random logic's output by table lookup.

These views are a gross simplification. Almost all random logic designs have small memory elements in them to simplify the state machines that are part of all processors, like the instruction fetch, operand decoding, or responding to interrupts. Likewise, almost all microcode machines employ some logic to speed up the decoding of the microcode to avoid needing insanely wide microcode memory. In addition, logic is often employed to allow the microcode to loop or branch to create more complex behaviour.

While microcode is extremely difficult to write, when an error is found, the code "simply" needs to be updated (assuming that you don't run out of microcode space, then well, problems) When a bug is found in the random logic decoder, it is not uncommon for the whole logic formulation to be affected. This can make random logic designs very hard to get right. The Z-8000 used random logic and its design was plagued by bugs in the instruction decoder. On the other hand, the simpler MC6809 also used random logic decoding and was highly successful.

The advantage of random logic is that it avoids the overhead of fetching the microcode from it's storage. In simpler processors avoiding this overhead can result in savings of silicon (that is money) and clock cycles (that is time).

RISC computers have much simpler instruction sets than CISC machines. This is a major reason why the random logic decoder is so often associated with RISC chips. CISC chips have intricate, complex instruction sets, so microcode is highly favoured for those designs.

I understand that most modern processors use a hybrid approach. Random logic for the simple and/or highly time critical stuff and microcode for the more complex behaviour and/or exception handling.
> 3 votes

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


title: NP-completeness

text:
# Question
Title: NP-completeness
Q: Suppose a language A is NP-complete. Is this following statement correct?:

A: If there is a polynomial algorithm to solve A, then it can be used to all the problems in NP.

My (and some others) first thoughts were that this answer is correct. But if you look at the following picture you can see that there exist problems which are only! NP. So let's take such a problem which is not NP-complete but NP. Thus a polynomial algorithm which can be used to solve any problem which is NP-complete can not be used to solve this problem which is only! NP. Is this correct?

# Answer
> 2 votes
Check the definition of **NP**-complete: a problem is **NP**-complete if it is in **NP** and every problem in **NP** reduces to it. So, if you have a polynomial-time algorithm for any **NP**-complete problem, you have a polynomial-time algorithm for every problem in **NP**. First, do the reduction; second, solve the complete problem.

---
Tags: np-complete, np, decision-problem
---


# Question
Title: Does "in-place" for $n$ items imply space dominated by $n$?
Does the characterisation of an algorithm for $n$ items as *in-place* imply space ∊ $ο(n)$

1. formally
2. informally ("among coders")?

# Answer
There are two common ways to analyze computation, corresponding to two different machine models. One model is the one taught in classes on computability and complexity theory: it is the Turing machine model. In this model, the machine has a read-only input tape, a write-only output tape, and several work tapes, and we only measure space on the work tapes.

A different (and more realistic) model is used in classes on algorithms and data structures: it is the word RAM model. There are several ways to define space usage in this model - one obvious way is the number of memory cells accessed beyond the input cells. In this model, one could define an in-place algorithm as one which uses $O(1)$ space (in this model we measure space in machine words of length $O(\log n)$, where $n$ is the length of the input), though this ignores stack usage (which will be simulated in the RAM model using a stack whose memory usage counts).

You haven't defined what *in-place* means for you, and you haven't defined how you measure space. Without such definitions, it is impossible to answer your question. However, I have outlined above definitions of both concepts for which in-place implies sub-linear (even constant) space.
> 4 votes

# Answer
In practice, algorithms such as quick sort or bubble sort are considered in-place, though they use $O(\log^2{n})$ and $O(\log{n})$ space ($O(1)$ if to use RAM model), just for storing indices to input array. These algorithms does not use extra space, only constant amount of memory may be used. However, unlike the quick sort and bubble sort algorithms MergeSort is not in-place algorithm which uses extra array to merge two sorted arrays.

Formally, there are different approaches. One approach is using logarithmic space to do computation. Problems that belong to the class $L$ (logarithmic space) are decided using $O(\log{n})$ space. This is because solving the problem of size $O(n)$ using $O(\log{n})$, in some sense, is in-place since we cannot write the whole input on the work-tape and then do computation. Another approach, which is more restricted, is to use $O(1)$ space. In this case a TM behaves as a finite state automaton.
> 2 votes

---
Tags: terminology, asymptotics
---


# Question
Title: Estimate complexity of integer sequence enumeration
I would like to seek help on the complexity of the following problem. Given positive integers $m$, $n$, $D\_1$ and $D\_2$, find all sequences $a\_1\lt a\_2 \lt \dots \lt a\_n$ are there such that:

1. each $a\_i\in\\{1, \dots, m\\}$
2. $\sum\_{i=1}^n a\_i = D\_1$
3. $\sum\_{i=1}^n a\_i^2 = D\_2$.

I want to know the complexity with respect to $m$, $n$, $D\_1$ and $D\_2$.

For example, when $m=12$, $n=4$, $D\_1=26$ and $D\_2=214$ the solutions are

$$ 3,5, 6, 12\qquad 2, 5, 8, 11\qquad 1, 7, 8, 10$$

# Answer
> 1 votes
Here is a simple recursive solution that runs in exponential time.

Geometrically you want to enumerate the lattice points which lies inside the first quadrant of the $n$-hypercube of height $m$ and on the intersection of the $D\_1$-radius $L\_1$ sphere and the $D\_2$-radius $L\_2$ sphere (let call them respectively $S\_1$ and $S\_2$), up to reordering of the coefficients.

Denoting by $V\_n$ the volume of the $n$ unit dimensional ball, we have :

* $m^n/n!$ points in the intersection of the hypercube and the quadrant (let's call it $D$) with the ordering ,
* $\alpha = O\left(m^n e^{\frac{-(D\_1-nm/6)^2}{3nm}}\right)$ in $S\_1\cap D$ (see theorem 1.3 of http://www.doiserbia.nb.rs/img/doi/1452-8630/2008/1452-86300802222R.pdf), considering the ordering condition.
* $\beta = \frac{1}{n!2^{n}}V\_n D\_2^{n/2} + O\left(D\_2^{n/2-1+\epsilon}\right)$ in $S\_2$ (Generalized Gauss circle problem+quadrant condition+order condition). I'm not considering intersection with the hypercube here, so the global complexity will be an overestimation.

Depending on your parameters choose the minimum of $\alpha$ or $\beta$. If its $\alpha$ perform a recursive enumeration of the integers partitions of length $n$ with the restriction on $m$ and use early abort to discard solutions which are getting out $S\_2$. In the other case, enumerate the lattice point on $S\_2$ ( with recursive orthogonal projections for instance) and check for the appartenance in $S\_1$ for each returned vector.

Hence the global complexity will be dominated by $min(\alpha, \beta)$.

---
Tags: integer-programming
---


# Question
Title: Basic question on intermediate code generation
In this diagram, I have a doubt in the 2nd picture. How can different languages have same independent code optimizer ?

I think that different languages will have their own code optimizer(different) and then the optimized code will be converted to target machine code based on different machines.

So the arrow should be from one independent code optimizer (for each language) to many target machines.

Am I correct ?

# Answer
> 3 votes
The intermediate language is a relatively normal programming language and as such you can write an optimizer for it. Optimization passes like common subexpression elimination, constant propagation, or strength reductions are fairly independent of the programming language.

As long as the intermediate language can express all concepts from the source language reasonably well, there is little loss in just optimizing the intermediate representation. For example LLVM's intermediate language is well suited for representing C-like imperative languages. It also comes with a type system, so not much information is lost when translating from C, or Ada, or Java to LLVM.

There is of course a problem if the source language contains information that can't be encoded in the intermediate language. For example you could think about just optimizing x86 assembly instead of first translating to something like LLVMs IR. However assembly lacks many high level constructs that make it easier for the compiler to optimize things. For example it lacks a type system. If your Ada code restricted the value of a variable to be less than five, the compiler could use that information to optimize some conditionals. Such information would be lost when translating to Assembly.

Because of this mismatch it is not uncommon to first do some high level optimizations in the target language and then translate to the intermediate language to leverage all the work that went into the optimization passes that are suitable for many languages. This article about Rust's Mid-Level IR provides an example of this. But this step is not strictly necessary (For example Rust didn't do this at first), you just lose some optimization opportunities if you skip it.

In the end it's probably an engineering tradeoff. You lose a few opportunities for optimization by using an intermediate language. But you save enormous amounts of developer time by reusing existing optimization passes.

---
Tags: compilers
---


# Question
Title: How can we get a Las Vegas algorithm from a Monte Carlo one?
I am trying to solve some exercises on random algorithms from this book, randomized algorithms. This is not a homework. I am only trying to improve my skills.

Here is the exercise:

**Exercise 1.3:** Consider a Monte Carlo algorithm $A$ for a problem $\Pi$ whose expected running time $T(n)$ on any instance of size $n$ and that produces a correct solution with probability $\gamma(n)$. Suppose further that given a solution to $\Pi$, we can verify its correctness in time $t(n)$. Show how to obtain a Las Vegas algorithm that always gives a correct answer to $\Pi$ and runs in time at most $(T(n)+t(n))/\gamma(n)$.

My attempt to solve this exercise is:

```
Algorithm LA
1) for i = 1 to 1/gamma(n) do
2)     solMC = MC(n)
3)     if solMC is correct
4)         return solMC
5)     else
6)         solMC = MC(n)
7)     end
8) end

```

The idea of my Las Vegas algorithm LV was to re-run the Monte Carlo algorithm, `MC` in my code, some iterations until the correct answer is given.

I found that $\Pr\[MC(n) \text{ is called at iteration } i\]=(1-\gamma(n))^i$. So I choose the iterations from `1` to `1/gamma(n)`. In this case, $\Pr\[MC(n) \text{ is called at iteration } i\]=(1-\gamma(n))^{1/\gamma(n)}$ which goes either to $0$ or $1/e$ as $\gamma(n)$ goes to either $1$ or to $0$, respectively. I think this does not answer the question.

How would you solve this problem?

# Answer
> 4 votes
First, the algorithm should run forever; since you are going to stop when you have a correct answer. By this way you can guarantee that you never outputs a wrong answer. So, probability of error is zero.

So, the algorithm should be as following:

```
Algorithm LA
1) for i = 1 to infinity do
2)     solMC = MC(n)
3)     if solMC is correct
4)         return solMC
5)     else
6)         solMC = MC(n)
7)     end
8) end

```

Also, verify the solution from MC(n) by the given in the question which takes t(n) running time; because you don't know that monte carlo algorithm outputs correct or not. Also I removed the else condition, I don't see it is important here. So, the algorithm should be edited as following:

```
Algorithm LA
1) for i = 1 to infinity do
2)     solMC = MC(n)
3)     answer_from_verifier = output_Verify(solMC)
3)     if answer_from_verifier is correct
4)         return solMC
7)     end
8) end

```

---

Now, the expected running time is:

$E\[X\]= \sum\_{i=0}^{\infty} (1-\gamma)^i \gamma (i+1) (T(n)+t(n)) $

$= \gamma (T(n) + t(n)) \sum\_{i=0}^{\infty} (1-\gamma)^i (i+1)$

$= \gamma (T(n) + t(n)) . 1/\gamma^2$

$= \frac{T(n)+t(n)}{\gamma} $

---
Tags: algorithms, randomized-algorithms, probabilistic-algorithms, monte-carlo
---


# Question
Title: Difference between Turing machine and Universal Turing machine
I've read what a Turing machine and a UTM are, but I don't get the difference. What can a UTM do which a normal Turing machine can not?

# Answer
> 15 votes
A universal Turing machine is just a Turing machine whose programming simulates other Turing machines. That is, the input to the UTM is a description of a Turing machine $T$ and an input for $T$, and the UTM simulates $T$ on that input.

It's universal in the sense that, for any problem that can be solved by Turing machines, you could either use a Turing machine that directly solves that problem, or you could use a UTM and give it the description of a TM that directly solves the problem.

If you like, a UTM is an interpreter for (all) Turing machines.

# Answer
> 4 votes
A UTM can run any Turing machine on some input.

A Turing machine can be compared to a program. It takes some input and generates some output.

A UTM can be compared to a computer. It can take any program and run it with some input and generates some output.

The UTM is a Turing machine in itself, so the interesting idea here is that any Turing machine can be encoded as input understood by another Turing machine.

# Answer
> 2 votes
Every TM does just *one* task. It sums two input numbers, or it scans the input for some symbol, or it looks for a counterexample of Goldbach's conjecture ...

... or it (let us call it TM#1, since we will have a 2nd one shortly) gets two parts of input, where the first describes a TM, TM#2 (think of a (fixed) TM as a finite number of states and transitions and stuff like head directions) and next to the description of TM#2 a description of input to TM#2.

So TM#1 receives the pair ("TM#2" "input#2") as its input#1. And then TM#1 runs on this input#1 and behaves (to the outside, after termination!) as if it was TM#2 working on input#2. In case TM#2 would not halt, TM#1 won't do either.

Such a TM#1 is called a UTM, since it can behave like/fake/simulate any other TM you give it as TM#2. Think of a virtual machine (TM#1), a simulated program (TM#2), and an input to the simulation (input#2). The VM takes longer, but the results are the same.

Even TM#2 = TM#1 is possible ... then input#2 = ("TM#3" "input#3") and TM#1 is a UTM and now simulates another UTM (TM#2) which in turn meta-behaves as TM#3 on input#3, in symbols:

TM#3(input#3) = TM#2("TM#3 input#3") *since* we took TM#2 to also be a UTM = TM#1("TM#2 'TM#3 input#3'")

Again: Behaviour is in terms of eventual final output, if and when halting, certainly *not* in terms of tape contents at any time, number of time steps etc., simulation takes (much) more time than doing it directly.

---
Tags: turing-machines
---


title: Is my problem NP-Hard?

text:
# Question
Title: Is my problem NP-Hard?
I have a grocery dotted list of pairs which are missing items that I need and I don't have any of them, so I am going to the supermarket.

Each pair in the dotted list is the name of the missing item that I need and a natural number which is the quantity/amount i.e. how many of this item I need.

I am in the supermarket now and I see an array of packages of items standing on shelf.

There are packages that don't contain items that I don't need and there are packages that contain items that I don't need.

I have enough money to buy all the packages, but if I will do this then I will get items that I don't need, so I don't want to do this.

Surely that I won't buy any package that contains an item that I don't need, but note that I don't want to have too many of any item that I need.

I can peek inside each package to see what items it contains and how many of that item it contains.

I cannot buy partial package, i.e. I cannot for each package decide which items from the package I buy and which I don't buy.

My only choice for each package is either buy the package and get all the items inside or don't buy the package and get nothing from the items that this package contains.

I want to know if this is possible to buy the packages so I get all what I need exactly as written in my grocery dotted list without having superfluous items that I don't need.

I will bring my mobile phone to the supermarket and once I can peek inside the packages I will run the application that will solve my problem.

I am programmer and I can program this application for my mobile phone with no problem but I want to use a polynomial time algorithm that solves my problem, because I am not going to wait hours, days, months and years until my phone will return me the answer.

But to know if there is polynomial algorithm or not I need to know first if my problem is NP-Hard or NP-Intermediate that polynomial solution is unknown.

Indeed my problem is decision, because I need to decide which packages I buy and which I don't buy and if I have a solution I can verify it in polynomial time, so my problem is indeed in $\mathbb{NP}$, but I don't know if it is in $\mathbb{P}$.

Do you know?

EDIT:

Mathematically my problem is show either:

$A\subset\mathbb{MULTISETS} \land B\in\mathbb{MULTISETS}\vdash\exists C: C \subseteq A \land \displaystyle \biguplus\_{D \in C}D=B$

OR

$A\subset\mathbb{MULTISETS} \land B\in\mathbb{MULTISETS}\vdash\nexists C: C\subseteq A \land \displaystyle \biguplus\_{D \in C}D=B$

# Answer
> 2 votes
Your problem is **NP**-complete.

It is a multidimensional generalization of the **subset sum** problem. The input to subset sum is a list of integers $a\_1, \dots, a\_n$ and a target $t$. The question is whether there's some sublist of the integers whose total is $t$. This corresponds to the case where your shopping list is just "$t$ apples" and each package on the shelf contains some number of apples.

Having multiple products for sale in the shop certainly can't make the problem any easier. But it doesn't get any harder, either: it's still in **NP** because, as you've observed, if somebody tells you "buy this set of packages", you can easily check in polynomial time that this gives you exactly what you want.

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


# Question
Title: Obtaining Image Measurements of a Known Object
Given the image of an adhesive tape as below, what would be possible method to find the tape radius?

The image sepia toned with artificial background added. The tape itself is partially hidden.

# Answer
> 1 votes
*I think you're looking for a way to approach this problem however I am not sure if the question belongs to this site(Seems more relavant to https://computergraphics.stackexchange.com/ and https://stackoverflow.com)*

A typical approach will be ***canny edge detection , finding Contours*** and then ***Elliptical Curve Fitting***.Then you can find the approximate diameter and divide it by two.

Below are some links that will help you

Documentation from **OpenCV** (*an open source library for image processing*) library will shed a light on finding contours

http://docs.opencv.org/3.2.0/d4/d73/tutorial\_py\_contours\_begin.html

How to find contours in an image using c++ and OpenCV

http://docs.opencv.org/2.4/doc/tutorials/imgproc/shapedescriptors/find\_contours/find\_contours.html

See the following for getting an idea about curve fitting

https://en.wikipedia.org/wiki/Curve\_fitting

How to implement Elliptical Curve fitting using c++ and OpenCV

http://docs.opencv.org/2.4/doc/tutorials/imgproc/shapedescriptors/bounding\_rotated\_ellipses/bounding\_rotated\_ellipses.html

# Answer
> 0 votes
The Hough transform for circles would be appropriate here. It will yield radius as output and thanks to tape being a ring (with some bigger radius) will help, more results with the same center will appear. In fact it will work even with partially visible objects. If you can supply estimated size then runtime can be drastically decreased. But in that case the RANSAC for circles might be even better.

The core problem here is not the circle detection (and measurement) but the image tone. The standard edge detectors yield poor results (I have tested Canny, Roberts, Sobel and Laplacian). The sepia tone is a bit tricky part, but may be ignored. Second tricky part is the second circle in the image. Although the Hough transform gives far greater response for the tape, such situation should be included into pipeline of transforms. In this particular case the shadow removal would suffice (naive thresholding would work). It means that we treat the darkest parts of the image as shadow / background (this comes from very common idea that interesting object should be centered and see some light).

---
Tags: computational-geometry, image-processing, computer-vision
---


# Question
Title: How does MIPS ( or any other multi-byte word arch ) fetch a word?
I've recently been studying MIPS as part of a CS course, but something bugs me. We've seen so far that MIPS increments the PC by 4 each cycle because each word is in fact comprised of 4 bytes (32 bits), each with their own address. I've also seen that a theoretical RISC machine has instructions that should only take a single cycle to execute.

Ignoring memory latency, how does it manage to generate an address for each 4 bytes? It can't have four adders for memory address calculation right? That'd be too expensive! Or am I incorrect in this assumption? I've also seen other architectures that manage to pull multiple bytes from memory (even multiple words) in a single step/cycle/instruction, but how is this achieved if each byte needs an address?

# Answer
MIPS can load a 32-bit (4-byte) word in a single instruction (load word, `LW`). The fact that each byte of the word is individually addressable doesn't affect this. Effectively, the instruction says "Read the four bytes beginning at this address", not "Read the byte at this address. Increment the address by one. Read the byte at that address. Increment the address by one. Read the byte at that address. Increment the address by one. Read the byte at that address."

By way of an analogy, you can photocopy any two facing pages of a book simultaneously, even though each has its own number.
> 1 votes

# Answer
the cpu might have used an integrated circuit to clone one single instruction command to a number that the same number of instruction set executive commands,how for it will always be executed by transistors logic gate.Your question is unclear,i assume the command is a 8 bits so this 8 bits will be parsed and the output will have to be **11111111** and if not,it will be:
example: **10110010** so if the command is available,it will switch circuit to address 8th to send to a i/o another processing circuit to send the next commands to ram or peripheral devices.if not,it will switch to address 4th.
> -4 votes

---
Tags: computer-architecture
---


# Question
Title: Unrolling closures into SAT boolean formula
I need to verify some assertions about the minimalist Turing-complete language Jot.

Many of the assertions I want to investigate are semi-deciable (co-recursively enumerable). So far it's been fairly straightforward to literally enumerate every Jot program via its Goedel number and testing the assertion's complement by running a Jot program with a given space/time bound.

This works great for small programs (\< ~40 bits) and has allowed me to find the shortest known representations of several standard simple functions from lambda calculus.

```
SUCC = J(18400)
CHURCH_0 = J(154)
CHURCH_1 = J(0)
CHURCH_2 = J(588826)
IS_ZERO = J(5)
MUL = J(280)
EXP = J(18108)
S = J(8)
K = J(4)
AND_2 = J(16)
AND_3 = J(139248)
OR_2 = J(9050)

```

However, this is particularly inefficient for larger functions and I'd like to speed up searches using a SAT solver. To do this requires unrolling the recursion of a Jot program J(n) to a predefined hard cut-off depth as a boolean formula.

Technically the formula isn't of polynomial length, but is still practically useful due to the small constants in program length and an already known existing polynomial number of beta reductions in an equivalent (but verbose) implementation of the target J(n).

I'm used to encoding problems in SAT formulae, however the new issue for me is understanding how to encode closures (nested functions) in an efficient manner.

None of the standard tools for bounded model checking that I know of allow nested anonymous functions, so I haven't been able to study any existing encoding methods. I would greatly appreciate any hints about how to encode these closures.

Here's the Jot interpreter written in Python which I'm trying to unroll into a boolean formula:

```
def S(x): return lambda y: lambda z: x(z)(y(z))
def K(x): return lambda y: x
def X(x): return x(S)(K)
def B(x): return lambda y: lambda z: x(y(z))
def I(x): return x
def J(n): return (B if n & 1 else X)(J(n >> 1)) if n else I

```

# Answer
> 1 votes
It's important to remember that SAT can only encode problems that are in $NP$, unless you use more than polynomial-length formulas. I'm not 100% sure, but I'm doubting your problem is in $NP$.

Consider the following function:

$F = \lambda x\ y \ldotp x x (\lambda y . y y)$

Now consider evaluating $F F (\lambda z \ldotp z)$.

This clearly runs forever, but we can also see that the argument given as $y$ will grow exponentially with the number of $\beta$ reductions you do.

Now, some things that aren't clear from the question:

> non-deterministically represented candidate program

What does this mean? Is the program non-deterministic? Or its representation? What even is a non-deterministic representation?

> static once created and have a small number of predefined variables within each combinator

Again, what does this mean? My example doesn't seem to fit this, but if whatever you're dealing with us Turing Complete, my gut says your problem is likely to be $EXPTIME$-hard.

---
Tags: satisfiability, lambda-calculus, kolmogorov-complexity
---


# Question
Title: Simplest complete combinator basis pair for flat expressions
In Chris Okasaki's paper "Flattening Combinators: Surviving Without Parentheses" he shows that two combinators are both sufficient and necessary as a basis to encode Turing-complete expressions without the need for an application operator or parentheses.

Compared to John Trump's encodings of combinatory logic in "Binary Lambda Calculus and Combinatory Logic" through prefix coding S and K combinators with an application operator, only needing two combinators for flat expressions increases the code density to optimality. The resulting Goedel numbering maps every integer to a valid, well-formed closed-term expression unlike most calculi and minimal description length relevant esolangs whose canonical representations usually permit descriptions of syntactically invalid programs.

However Okasaki's encoding was meant to be most helpful in a one-way mapping from lambda calculus terms to bitstrings, not necessarily the other way around as the two combinators used in this reduction are relatively complex when used as practical substitution instructions.

What is the simplest complete combinator basis pair that does not require an application operator?

# Answer
> 6 votes
Coming back to this nearly a year later, I realized I had missed some critical research before posting.

Jot seems to fit the bill of what I was asking for, with two relatively simple combinators B & X that can be represented by a compact Goedel numbering.

I've simplified his reference implementation with Python:

```
def S(x): return lambda y: lambda z: x(z)(y(z))
def K(x): return lambda y: x
def X(x): return x(S)(K)
def B(x): return lambda y: lambda z: x(y(z))
def I(x): return x
def J(n): return (B if n & 1 else X)(J(n >> 1)) if n else I

```

J(n) returns the built up function denoting the program represented by its Goedel number n.

B (equivalent to Church encoded multiply) serves the function of functional application (parentheses), and can isolate the S/K halves of the single-basis Iota combinator X.

There a few important properties of this language that I'm (almost) shamelessly stealing from the website of the language's inventor Chris Barker, circa 2000.

Jot is a regular language in syntax but Turing-complete. You can see from the implementation of J(n) that if a host language supports tail-recursion, there's no stack space required to parse the bitstring program format.

The proof of Turing-completeness comes from Chris's site as well, implementing the already known Turing-complete combinatory logic using the S and K combinators:

```
K  ==> 11100
S  ==> 11111000
AB ==> 1[A][B], where A & B are arbitrary CL combinators built up from K & S

```

Jot has no syntax errors, every program given its Goedel number n is a valid program. This is probably the most important aspect to my own research, as it not only simplifies parsing to triviality, but should also in theory make Jot far more parsimonious than any Turing-complete encoding that has to skip over malformed programs.

I've written a few tools to 'solve' via brute force the semi-decideable problem of finding a function's Kolmogorov complexity in Jot. It works by relying on the programmer to specify some very characteristic training examples of a function's mapping, then enumerates all Jot programs until all training examples are matched, and lastly attempts a proof of equality of a found function with the original verbose implementation.

It currently only works for up to ~40 bits with my limited resources. I'm attempting a rewrite with a SAT solver to learn much larger programs. If you know how to unroll bounded nested closures as a boolean formula, please help out with my new question.

Now for some interesting comparisons to John Tromp's Binary Lambda Calculus, which is known for its conciseness, but does have the problem of possible syntax errors. The following programs were generated by my learning program in a few seconds.

```
Function    Jot       Binary Lambda Calculus   |J| |B|
--------|----------|--------------------------|---|---
SUCC      J(18400)  "000000011100101111011010" 15  24
CHURCH_0  J(154)    "000010"                    8   6
CHURCH_1  J(0)      "00000111010"               1  11
CHURCH_2  J(588826) "0000011100111010"         20  16
IS_ZERO   J(5)      "00010110000000100000110"   3  23
MUL       J(280)    "0000000111100111010"       9  19
EXP       J(18108)  "00000110110"              15  11
S         J(8)      "00000001011110100111010"   4  23
K         J(4)      "0000110"                   3   7
AND       J(16)     "0000010111010000010"       5  19
OR        J(9050)   "00000101110000011010"     14  20

```

From my own experiments, the hypothesis that Jot leads to smaller programs is slowly being confirmed as my program learns simple functions, composes them, then learns larger functions from an improved ceiling.

---
Tags: lambda-calculus, combinatory-logic
---


# Question
Title: Pumping lemma for simple finite regular languages
Wikipedia has the following definition of the pumping lemma for regular langauges...

> Let $L$ be a regular language. Then there exists an integer $p$ ≥ 1 depending only on $L$ such that every string $w$ in $L$ of length at least $p$ ($p$ is called the "pumping length") can be written as $w$ = $xyz$ (i.e., $w$ can be divided into three substrings), satisfying the following conditions:
>
> 1. |$y$| ≥ 1
> 2. |$xy$| ≤ $p$
> 3. for all $i$ ≥ 0, $xy^iz$ ∈ $L$

I do not see how this is satisfied for a simple finite regular language. If I have an alphabet of {$a,b$} and regular expression $ab$ then $L$ consists of just the one word which is $a$ followed by $b$. I now want to see if my regular language satisfies the pumping lemma...

As nothing repeats in my regular expression the value of $y$ must be empty so that condition 3 is satisifed for all $i$. But if so then it fails condition 1 which says $y$ must be at least 1 in length!

If instead I let $y$ be either $a$, $b$ or $ab$ then it will satisfy condition 1 but fail condition 3 because it never actually repeats itself.

I am obviously missing something mind blowingly obvious. Which is?

# Answer
You are right - we cannot allow "pumping" words of a finite $L$. The thing you are missing is that the lemma says **there exists** a number $p$, but does not tell us the number.

All words **longer** than $p$ can be pumped, by the lemma. For a finite $L$, it happens so that $p$ is larger than the length of the longest word in $L$. Thus, the lemma only holds vacuously, and cannot be applied to any word in $L$, i.e., any word in $L$ does not satisfy the condition of "having length at least $p$" as the lemma requires.

*A corollary:* if $L$ has pumping length $p$, and there exists some word $w\in L$ of length at least $p$, then $L$ is infinite.
> 46 votes

# Answer
Pumping lemma is usually used on infinite languages, i.e. languages that contain infinite number of word. For any finite language $L$, since it can always be accepted by an DFA with finite number of state, $L$ must be regular.

According to wikipedia (http://en.wikipedia.org/wiki/Pumping\_lemma\_for\_regular\_languages#Formal\_statement), pumping lemma says: $\begin{array}{l} (\forall L\subseteq \Sigma^\*) \\ \quad (\mbox{regular}(L) \Rightarrow \\ \quad ((\exists p\geq 1) ( (\forall w\in L) ((|w|\geq p) \Rightarrow \\ \quad\quad ((\exists x,y,z \in \Sigma^\*) (w=xyz \land (|y|\geq 1 \land |xy|\leq p \land (\forall i\geq 0)(xy^iz\in L)))))))) \end{array}$

For any finite language $L$, let $l\_{max}$ be the max length of words in $L$, and let $p$ in pumping lemma be $l\_{max}+1$. The pumping lemma holds since there are no words in $L$ whose length $\geq l\_{max}+1$.
> 9 votes

# Answer
One way to formalize the core part of the Pumping lemma is this, using $L^{\geq k} = \\{ w \in L \mid |w| \geq k\\}$:

> If $L$ is regular, there exists $p \in \mathbb{N}$ so that
>
> $\qquad \displaystyle \forall w \in L^{\geq p}.\ \exists x,y,z \dots$ (\*).

For all finite $L$ and $p \> \max \\{ |w| \mid w \in L\\}$, we have obviously that $L^{\geq p} = \emptyset$. Therefore (\*) is (vacuously) true for such $p$.
> 3 votes

---
Tags: formal-languages, regular-languages, pumping-lemma, finite-sets
---


# Question
Title: Is it an open problem if generalized resolution is always possible?
Let we have a 3CNF under following restriction: each variable occurs 3 times.

Then I apply generalized resolution (GR) (I don't know which name would fit more) technique (number of clauses can be arbitrary large, just an example):

$(x\lor A)\land(x\lor B)\land(\overline x\lor C)=(A\lor C)\land(B\lor C)$. Here $A,B,C$ are some clauses. Neither $A$ and $C$ nor $B$ and $C$ have opposing literals (like in original resolution, the reason is not to exponentially increase length of formula).

Is it an open problem if there is such a sequence of choices (which variable to choose for GR) that will return 'NO' if formula is unsatisfiable? Or there is a proof that some unsatisfiable formulas (with given restrictions) have no such sequences? Meaning that for every pair of literals $x,y$ on some step it will be possible to find a clause $(A\lor x\lor y)\land(B\lor\overline x\lor\overline y)$.

We assume that we can use any known polynomial technique such as unit propagation, absorption rules $(x\lor A)\land(\overline x\lor A)=A; A\land(x\lor A)=A$, pure literal rule (if variable always occur as positive or negative, remove all clauses where it is contained), changing equal literals, finding strongly connected components in a graph for 2-clauses, etc.

# Answer
Resolution is refutation-complete. This means that if $S$ is a set of unsatisfiable clauses, then you can use resolution to derive the empty clause. Moreover, Resolution is sound, so you can only derive the empty clause if $S$ is unsatisfiable. Summarizing, given a set $S$ of clauses, you can use Resolution to derive the empty clause if and only if $S$ is unsatisfiable.

Unfortunately, sometimes generating the empty clause takes an exponential number of steps. Let $G$ be a random 4-regular graph on an odd number of vertices $n$, and let us associate with each of the $2n$ edges a variable. Consider the set of $\Theta(n)$ clauses stating that for every vertex, the XOR of the four variables corresponding to edges touching the vertex is 1. Since the number of vertices is odd, this set of clauses, known as a *Tseitin contradiction*, is unsatisfiable. Urquhart showed that with high probability, any Resolution refutation of this set of clauses has $2^{\Omega(n)}$ many lines (i.e., clauses); see Jakob Nordström's lecture notes.
> 2 votes

---
Tags: algorithms, logic, satisfiability
---


# Question
Title: Is this graph problem NP-hard / NP-complete?
I have a certain kind of graphs. They are DAGs similar to dependency graphs but strictly hierarchical, that is, each node belong to a certain level in the hierarchy and cannot be moved up or down when the graph is laid out onto a plane. The nodes can be arbitrarily exchanged with others in the same level.

Here's an example:

**The problem:**

Find an ordering (permutation) of the nodes in each level of the hierarchy such that the total number of edge crossings is minimal.

The problem could be, I suppose, rephrased as a decision problem: Given an ordering of nodes in each level, decide whether that ordering is minimal in terms of number of edge crossings.

For example, in the above graph embedding there are 3 edge crossings, however, by reordering the nodes in a certain way we obtain an embedding that only has 1 edge crossing (I believe this is minimum for this particular graph):

(Nodes that have been moved are highlighted.)

**The question**:

Is this problem NP-hard? I'm having a hard time finding correspondence to one of the more well-known NP-hard/NP-complete problems but at the same time I'm having a hard time finding a polytime solution.

# Answer
> 4 votes
Turns out this is indeed an NP-complete/NP-hard problem according to wikipedia and Eades et al.

---
Tags: complexity-theory, graphs, complexity-classes
---


title: How is PowerPoint Turing complete?

text:
# Question
Title: How is PowerPoint Turing complete?
From my understanding, Turing complete means that the program or machine can complete any computation that a Turing machine can complete, which to me means any computation. So how can something like HTML or PowerPoint be Turing complete?

# Answer
Some system is Turing complete if you can simulate every Turing machine inside of it. Powerpoint is Turing complete because its animation features can be used to simulate a Turing machine. This video explains the proof for Powerpoint. You can read the proceedings from the 2017 SIGBOVIK for a written explanation.
> 15 votes

---
Tags: computability, turing-completeness
---


# Question
Title: Proof that locality is sufficient in showing two graphs are isomorphic
Using the graph representation with (node, \[list of neighbours\]), to show that two graphs are isomorphic it is sufficient to:

* show that the vertices have the same degree and
* for every pair of vertices with the same degree, the degrees of the nodes in their adjacency list must be the same.

The last point was a bit ambiguous, in the sense that in two graphs many vertices could have the same degree, but between two isomorphic graphs their is a bijective function (an exact one to one mapping) between them such that their adjacency list maps correctly.

My question is what's the proof behind this? Why is this sufficient? For me, this is not clear at all, because this is, overall, a local property and I can't understand how this generalizes to the whole graph.

If it's easier to track what I said on code...Prolog it's pretty verbose at this part.

```
:- dynamic p/2.
graph1([n(1,[2,3,4]),n(2,[1,3]),n(3,[1,2,4]),n(4,[1,3])]).
graph2([n(a,[b,d]),n(b,[a,d,c]),n(c,[d,b]),n(d,[a,b,c])]).
eq_perm([H1|T1],L2,EQ):-
    delete(H2,L2,T2), % we generate a solution here
    P = ..[EQ, H1, H2],
    P,
    eq_perm(T1,T2,EQ).
eq_node(N1,N2):-
    p(N1,N2).
eq_node(N1,_):-
    p(N1,_), !, fail.
eq_node(_,N2):-
    p(_,N2), !, fail.
eq_node(N1,N2):-
    asserta(p(N1,N2)).
eq_node(N1,N2):-
    retract(p(N1,N2)).
iso_graph(G1,G2):-
    eq_perm(G1,G2,eq_neighb).
eq_neighb(n(N1,L1),n(N2,L2)):-
    eq_node(N1,N2),
    eq_perm(L1,L2,eq_node).

```

# Answer
This method fails on regular graphs. For example, it fails on the following two graphs: the hexagon, and two disconnected triangles.

More generally, if you continue to explore neighbors' neighbors and so on, you get the 1-dimensional Weisfeiler–Lehman method. If you start with $k$-tuples of vertices, you get the $k$-dimensional Weisfeiler–Lehman method. Cai, Fürer and Immerman proved in An optimal lower bound on the number of variables for graph identification that there exist non-isomorphic graphs on $n$ vertices which fail to be distinguished by the $k$-dimensional Weisfeiler–Lehman method unless $k = \Omega(n)$. Since the running time of the method in the worst case is asymptotically $n^{k+1}$, this shows that the Weisfeiler–Lehman method doesn't yield a subexponential time algorithm for graph isomorphism.

For more on the Weisfeiler–Lehman method, check a paper of Douglas, or the recent work of Neuen and Schweitzer.
> 0 votes

---
Tags: algorithms, graphs, correctness-proof, graph-isomorphism
---


title: What is the definition of a property?

text:
# Question
Title: What is the definition of a property?
I have seen 2 answers in stackoverflow:

1. A "trivial" property is one that holds either for all languages or for none.
2. The property is trivial if it contains every TM, or if it is empty.

My problem is: Saying that a property is trivial if it contains every TM is not the same as saying that a property is trivial if it contain all the languages (including non `RE` languages).

Same as for: Saying that a property is trivial if it is does not contain any TM languages is not the same as saying that a property is trivial if it is empty.

# Answer
We call a set of languages, $P\subseteq 2^{\Sigma^\*}$, a property. If you think of this subset as the set of languages who satisfy some property, then we can simply say that a language $L$ satisfies the property iff $L\in P$.

Rice theorem tells you that you can't, given a Turing machine $M$, check if $L(M)$ satisfies some non trivial property $P$, i.e. $P\neq \emptyset$, $P\nsupseteq RE$. Note that Shaull makes a distinction between semantic and syntactic properties in the comments. To the best of my knowledge, the standard definition of a property in the context of Rice's theorem is a set of languages.
> 2 votes

---
Tags: computability, rice-theorem
---


# Question
Title: Where does LL parser belong in the top-down parsers classification
There are four types of top-down parsers according to this answer:

* recursive descent backtracking
* recursive descent predictive
* table-driven with backtracking
* table-driven predictive.

Also the author says that:

> All top down parsers are LL

However, in this answer the author seem to associate the LL parser with table-driven parsers:

> LL is usually a more efficient parsing technique than recursive-descent.

And the OP:

> \[one category\]... seem to be the LL parser (using stack/parse table)

Also this article states:

> LL parsers are also called predictive, because it's possible predict the exact path to take by a certain amount of lookup symbols, without backtracking.

which associates LL parsers with predictive parsers, which can be either recursive descent or table-driven.

So I'm at loss here. Can you guys help?

# Answer
> 2 votes
First let's make some general remarks about nomenclature. They are not all relevant here, but they may help you in the future.

1. not all authors are using the same precise definition. Sometimes the differences are irrelevant for the current points, sometimes one wonder way such different things are named in the same way by different authors. Sometimes authors give the definition they are using, but that's not always true. Sometimes there are well accepted definition that you can take for granted in about any context, sometimes every group tend to have its own and you have to know of which group the author is a member. (Ask a Java and a ML programmer what polymorphism is)
2. Nomenclature are about classification. Classification is emphasizing some aspects while ignoring other, even if you think it should be (For instance L. Cardelli and P. Wegner do not consider the static or dynamic aspect in their analysis of polymorphism)

Now you are somewhat lucky, as some of the terms here have quasi-universal definitions (that is not that some are not using other one, especially in blogs and QA sites, but they are trying to intuit a definition from the terms instead of looking at the definitions given by text books).

A *top-down parser* is a parser which start from the *start symbol*, guess which *production* to use, and then repeat the process for a *non terminal symbol*. If it is able to second guess its choice, it is also a *back-tracking parser*. If it never second guess its choice, it is a *deterministic parser*.

A *LL(k) parser* is a deterministic top-down parser which will always determine the production to use for the left-most non-terminal not yet determined (that's what the second L means) and will consider only the text from left to right (that's what the first L means) and will never use more than $k$ terminal symbols not predicted.

Thus

> There are four types of top-down parsers:
>
> * recursive descent backtracking
> * recursive descent predictive
> * table-driven with backtracking
> * table-driven predictive.

*deterministic* seems more common than predictive but that division seems correct. I'll emphasize the fact that the division backtracking/predictive characterizes the algorithm, while the division recursive/table-driven characterizes the implementation. So although the classification is correct, it is mixing different aspects something which tend to introduce confusion.

> All top down parsers are LL

That is false. Some are not deterministic (the recursive descent backtracking one of your first list). Some are scanning the text from right to left (AFAIK, the only interest is academic here but it would not surprise me that there is someone somewhere which found a use for it). Some are trying to determine the production to use for another non-terminal than the next one (it's a formalization of the good old find the next matching parenthesis before trying to parse what is between them).

> LL is usually a more efficient parsing technique than recursive-descent.

LL can be implemented as recursive-descent (and is the easiest way to do so), opposing the two does not really make sense to me. Recursive/table driven is an implementation choice. (I've written both, I'd use the table driven approach only as part of a parser generator but I'll never say they are different algorithms).

> LL parsers are also called predictive

This could be misleading. They are not the only class of parser which could be called predictive.

---
Tags: formal-grammars, compilers, parsers, syntax-trees
---


# Question
Title: Classes of outer totalistic cellular automata
I'm wondering if anyone knows of any place where the Wolfram classifications of many outer totalistic cellular automata have been catalogued. The classes of a few examples are given in *A New Kind of Science*, famously that of Rule 224 (Life) or more simply ones like Rule 0 which kills all of the cells. I'm wondering if there's any place where these classes have been collected, for a research project. Thanks!

# Answer
> 1 votes
Here is a fairly old link, which only lists a few classes specifically, but it might be a place to start.

I'd agree with David Eppstein that a longer list might not be all that useful. There's no quick way to tell for sure whether a given CA rule is Class 4, except in the really simple cases. In many cases, with enough work you may be able to design persistent structures that could support universal computation.

---
Tags: cellular-automata, data-sets
---


# Question
Title: Complexity of ANOTHER HAMILTONIAN CIRCUIT problem
All references I find about the ANOTHER HAMILTONIAN CIRCUIT problem:

> Given a graph and a hamiltonian circuit on it, is there another hamiltonian circuit on it?

I was trying to reduce it to the hamiltonian circuit problem but I always need to add too many or too few circuits to the original one.

Am I going through the good direction? It seems to be very simple...

**Edit**

Papadimitriou's complexity book refers to its theorem 17.5 for the inspiration for this problem.

I think that a good way for the solution is to consider the graph proposed in Papadimitrious'

One can for each node of the original graph, transform to the graph shown at the left image. Then, one can connect all these new graphs using the poles N and S and thus obtains a hamiltonian circuit. Then, one uses W and E to connect vertex that were connected in the original graph. In principle, one could connect W with W and E with E.

I only have one more doubt, what happens if the original graph is just a segment, that is, two vertex with a edge between them. My construction would give an extra hamiltonian circuit going from W1-\>E1-\>E2-\>W2-\>W1 even if the original one didn't have one!

Can you find any other counterexample? This was the solution given in my course and it seems to be partly wrong...

# Answer
This result is proved in the senior thesis The complexities of puzzles, cross sum and their another solution problems (ASP) by Takahiro Seta.

The systematic study of ASPs was initiated by Ueda and Nagao in their paper NP-completeness Results for NONOGRAM via Parsimonious Reductions. See also Takayuki Yato's master thesis, Complexity and completeness of finding another solution and its application to puzzles.
> 4 votes

---
Tags: complexity-theory, graphs, np-complete, hamiltonian-circuit
---


title: Find the Context Free Grammar

text:
# Question
Title: Find the Context Free Grammar
Let $\Sigma = \\{a, b\\}$. For each of the following languages, find a grammar that generates it.

(a) $L\_1 = \\{a^n b^m : n\geq 0, m\>n\\}$

(b) $L\_1^3$

(C) $L\_1^\*$

I know the grammar for the language $L\_1$, that is

$S \rightarrow aSb \mid bA$
$A \rightarrow bA \mid \epsilon$

please help me to find the grammars for another two languages.

# Answer
b) Introduce a new start symbol $S\_1$ and a new production rule $S\_1 \rightarrow SSS$

c) Introduce a new start symbol $S\_2$ and a new production rule $S\_2 \rightarrow S\_2S \mid \epsilon$
> 0 votes

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


title: Find the grammar for the given language

text:
# Question
Title: Find the grammar for the given language
$L = \\{ w: |w| \bmod 3 \geq |w| \bmod 2 \\}$

I know, when the length of strings is not $3, 9, 15, 21,\dots,$ they will be members of the given language but unable to write a grammar for this language.

Please confirm one more thing, that this given language is regular?

# Answer
Note that this language excludes all strings of length divisible by 3 but not by 2, i.e., of length $3, 9, 15, 21,\dots$.

Consider languages $$L\_1 = \\{w\mid |w|=2k, k\geq 0\\}$$ and $$L\_2 = \\{w\mid |w|=3k, k\geq 0\\}$$ They are regular, since it is very easy to design DFA for both languages; the first has three states, the second has four states. The complement of the language $L$ is equal to $L\_2-L\_1$, and by the closure properties of regular languages $L=\overline{L\_2-L\_1}$ is also regular.
> 1 votes

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


# Question
Title: What is the difference between Big-O and worst-case run time?
Big-O describes an upper bound on run time. Is that not the definition of "worst-case"?

For example, how can we say that a hash table insertion require O(1) time on average? Constant time is the best case, *n* time is the worst case. How can an upper bound describe an average run time? In what sense is that bound "upper"?

# Answer
> 2 votes
Wikipedia says:

> Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

So it is not the definition of the "worst case".

Wikipedia defines best, **worst**, and average cases as

> In computer science, best, worst, and average cases of a given algorithm express what the resource usage is at least, **at most** and on average, respectively.

By resource we usually refer to time or/and space (memory) required to solve a certain problem.

It also says:

> Big O notation is a convenient way to express the worst-case scenario for a given algorithm, although it can also be used to express the average-case - for example, the worst-case scenario for quicksort is $O(n^2)$, but the average-case run-time is $O(n\log{n})$.

To sum up: Big-O notation is a pure mathematical concept and notation, which is used in Computer science to express the worst-case scenario for a given algorithm.

Here we have some useful posts:

---
Tags: algorithm-analysis
---


title: 2CNF with 3 variable occurences

text:
# Question
Title: 2CNF with 3 variable occurences
If we do not allow unit clauses, can 2CNF containing 3 occurences per variable be unsatisfiable?

Every time I try to connect opposing variables to a cycle, I need to draw 4 edges for at least one variable (2 per positive and negative occurences).

So, is it even possible?

# Answer
> 2 votes
The following is unsatisfiable: $$ (x \lor y) \land (x \lor \lnot y) \land (\lnot x \lor z) \land (\lnot z \lor w) \land (\lnot z \lor \lnot w) \land (y \lor w). $$ This contains every variable exactly three times, not all of them of the same polarity. If you allow variables to appear less than three times, you can drop the last clause $y \lor w$.

---
Tags: boolean-algebra, 2-sat
---