# Question
Title: Path in digraph passing through given set of vertices
Suppose we have digraph G, set of its vertices W and two (possibly equal) vertices s and f. I'm looking for an algorithm which will solve the following problem: whether there is path from s to f passing through all vertices from W; if yes, return any of such paths. By "path" i mean path in the most general sense: repetitions of edges and vertices are allowed.

Unfortunately no information about graph is known: it needn't be connected in any sense, it might have oriented cycles, etc.

My idea was to modificate DFS somehow but i didn't manage to proceed. Any ideas and hints will be highly appreciated. Thanks in advance.

# Answer
Decompose the graph into strongly connected components. You get a DAG, each vertex of which represents a strongly connected component. Let $S,F$ be the strongly connected components containing $s,f$. There is a path from $s$ to $f$ if there is a path from $S$ to $F$ in the decomposition (this includes the case $S=F$). Any such path can only pass through (genuine) vertices in the connected components that appear on the path from $S$ to $F$ in the decomposition, and conversely we can arrange it to pass through all of them (since you allow the paths not to be simple). This leads to a simple criterion for your problem – can you state it?
> 2 votes

---
Tags: graphs, graph-traversal
---


# Question
Title: What's the difference between all these terms?
What's the difference between them - Physically based simulation, Physically based animation, Physical simulation for computer animation, Physically based animation for Computer graphics, Physically based modelling for interactive simulation and games and Cognitive modelling ?

# Answer
These terms are not precisely defined and may overlap, but I think the following are both useful and non-controversial:

* Physically based simulation: Simulation of some physical process, generally employing the laws of physics, for instance modeling of some combustion equations to find the temperature of a gas versus time.
* Physically based animation: Simulation of some physical process, generally employing the laws of physics, in order to render a visual image of some process, such as creating a movie sequence of the bursting of a water balloon as it is pierced by a pin.
* Physical simulation for computer animation: I believe this term is synonymous with "Physically based animation."
* Physically based animation for computer graphics: I believe this term is synonymous with "Physically based animation."
* Physically based modelling for interactive simulation and games and cognitive modelling: I believe this means the same as "Physically based animation," but is applied to computer games, not movies.
> 0 votes

---
Tags: terminology, graphics
---


# Question
Title: What is the use of finding minimum number of straight lines to cover a set of points?
There is that popular problem \[1\] \[2\] in the computer science that is finding minimum number of straight lines that covers a given set of points in 2D.

Even though I have scanned many papers, none of them has a clear motivation for the problem.

What is the use of solving this problem? Is there a paper that explains this?

# Answer
Although many papers in theoretical computer science claims practical applications for their work, this is unfortunately often simply not the case. Usually, either the problems are too far away from being something useful (too simplified), or the algorithms are too far away from being practical (e.g. hiding big constants in the O-notation).

However, you can look at the papers

They claim, e.g.

> The problem of hitting objects in the plane with a minimum number of straight lines has a military application. In many cases when a bomber attempts to destroy targets on the ground, protected by anti-aircraft missiles, it has to spend as little time as possible close to the targets. Thus, careful planning of an air raid on a multi-target site (for example, a cluster of fuel tanks) calls for a minimum number of times a bomber has to fly across the site. Moreover, each pass has to be carried out as fast as possible, hence for each dive into the site there exists a straight line (a "stick") along which targets are destroyed. Another application (in three dimensions) is in medicine where radiotherapy is administered by inserting a minimum number of radioactive needles into a certain area of the body so as to achieve a required level of radiation.

And also:

> For example, we may view the problems faced by a planner who has to locate r (linear) segments of a new railroad system so as to minimize the average cost to the users who have to reach the tracks from a number of different small communities. Thus, a straight line or a line segment is of natural importance in this context. Sometimes such problems are easier than those with point facilities. For example, it is much easier to find a line, so as to minimize the sum of distances to it from a set of given points, than to find a single point with the same objective.
> 15 votes

---
Tags: reference-request, computational-geometry, applied-theory
---


# Question
Title: Flags register in an out-of-order processor
```
LW R2, 0(R1)
CMP R3, R2
CMP R7, R5

```

the LW instruction stalls the first CMP so the second one will execute first. Wouldn't this cause the flags register to contain the wrong value since it expects the second CMP to be the last one that updates the flags register?

I'm not sure about this one: does an ADD instruction ALWAYS update the overflow flag (1 if overflow and 0 if no overflow).

```
LW R2, 0(R1)
ADD R4, R3, R2
ADD R7, R5, R6

```

Same thing here: will the overflow flag be wrong if the first ADD wouldn't overflow but the second one will. The second ADD executes firsts and sets the overflow flag. After that the first ADD executes, doesn't overflow and sets the overflow flag to 0?

# Answer
The flags register is handled using one of the standard techniques for dealing with dependencies in out-of-order processors. Either

1. the registers are *renamed* (there are multiple physical flags registers, and the renaming and retirement mechanisms make sure the correct physical flags register is being used by each instruction) or
2. the scheduler respects anti- and output- dependencies, in which case the two `CMP` instructions execute in-order because the second is output-dependent on the first.

Same thing with `ADD` instructions. In a machine with `ADD`s that set an overflow flag, the overflow flag needs to be handled either by renaming or by stalling on anti- and output- dependencies.
> 5 votes

---
Tags: computer-architecture
---


# Question
Title: Does $P \neq NP$ imply $NP \neq PSPACE$?
Is it true that $\mathsf{P} \neq \mathsf{NP}$ implies $\mathsf{NP} \neq \mathsf{PSPACE}$?

I have here some problem that is in $\mathsf{PSPACE} \setminus \mathsf{NP}$ if $\mathsf{P} \neq \mathsf{NP}$. Since I cannot find a fault in my proof, I wanted to be sure, if the upper implication holds or not.

# Answer
> 10 votes
We know that $\mathrm{L}\subseteq\mathrm{NL}\subseteq\mathrm{P}\subseteq\mathrm{NP}\subseteq\mathrm{PSPACE}$ and at least one of those inclusions is strict, since $\mathrm{L}\subsetneq\mathrm{PSPACE}$ by the space hierarchy theorem. As far as I'm aware, any nonempty subset of the inclusions being strict would be consistent with our current state of knowledge so, in particular, it is not known that $\mathrm{P}\neq\mathrm{NP}$ implies $\mathrm{NP}\neq\mathrm{PSPACE}$.

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


# Question
Title: How is a 2-bit predictor better than a 1-bit predictor at determining loop iterations
I have read various explanations why a 1-bit branch predictor is wrong twice per loop, once at the beginning when it wrongly predicts against entering the loop and once at the end when it wrongly predicts against leaving the loop. Makes sense.

What I don't understand is why the 2-bit predictor is better. It seems it could even be worse, since it might well predict against entering the loop in the first place, hold to that prediction for a second time before beginning to be "right," and then still wrongly predict against leaving the loop at the end.

I could live with "in practice it turns out to not happen that way all that often," but most of these explanations don't seem to be based on such. Rather, they seem (to me) to begin with a demonstration how the 1-bit predictor fails twice, and then merely state that the 2-bit predictor does better without demonstrating that it does.

So...what am I missing?

# Answer
> 4 votes
The assumption is that destructive aliasing (or really any aliasing) is rare. That is, the branch predictor entry is unique to that static branch or at least not shared with another branch that is generally not taken.

If there is no aliasing, a later encounter of the loop will still predict taken for the 2-bit predictor but will mispredict for the 1-bit predictor. (A 1-bit predictor will also lack constructive aliasing with other loops since the previous encounter with the other loop will set the predictor entry to not-taken.)

(The common technique of BTB filtering "never" taken branches (i.e., a BTB miss for a branch that is not taken does not update the predictor and behaves as if no branch was present) can reduce destructive aliasing for taken branches.)

For loop dominated workloads a loop branch is both less likely to alias (fewer static branch instructions, one static branch accounts for multiple dynamic branches) and less likely to have destructively aliasing (*constructive* aliasing with other loop branches is more likely).

If aliasing were common, branch prediction would not work well because the prediction would not apply to the branch being predicted. (A 1-bit predictor can reduce aliasing by providing twice the number of entries compared to a 2-bit predictor of the same storage capacity. For certain workloads with high static branch count, the tradeoff of number of entries/aliasing and hysteresis may be justified.)

---
Tags: computer-architecture
---


title: O(2^n) runs in P... Is this true?

text:
# Question
Title: O(2^n) runs in P... Is this true?
My professor doesn't always know what's actually correct or wrong - he always has to think about it for a very long time and get back to the book and read the book for a long time to answer any of our questions.

He says that

**I tell you that an algorithm runs in $O(2^n)$ but yet is in $\mathsf{P}$. How can this be?** Ans -\> The big-$O$ notation is not a tight bound. Thus any algorithm that runs in polynomial time (e.g., $O(n^2)$) will also run in exponential time, such as $O(2^n)$. Thus, an algorithm that runs in $O(2^n)$ could be in $\mathsf{P}$.

Is he correct?

I cannot fully comprehend this answer. Could anyone please elaborate on his answer Please?

# Answer
> 3 votes
His answer is indeed correct. Like with most questions about big-oh notation, the key is to go back to the definitions.

Suppose we have an algorithm $\mathcal{A}$ that runs in $O(n^{2})$ time, this means:

> There exists two constants $c$ and $n\_{0}$ such that for all instances of size $n \geq n\_{0}$, the time $T\_{\mathcal{A}}(n)$ taken by $\mathcal{A}$ is at most $c\cdot n^{2}$. That is, $\exists c, n\_{0} \forall n \geq n\_{0} (T\_{\mathcal{A}}(n) \leq c\cdot n^{2})$.

Note that it says $T\_{\mathcal{A}}(n) \leq c\cdot n^{2}$. So for any function $f(n)$ that's 'bigger' than $n^{2}$ (i.e. $n^{2} \leq f(n)$, at least for large enough $n$), by the transitivity of $\leq$, we can also then state that $T\_{\mathcal{A}}(n) \leq c\cdot f(n)$. But then we have the defintion of $T\_{\mathcal{A}}(n) \in O(f(n))$.

So as $n^2 \leq 2^n$ for $n \geq 4$, and $T\_{\mathcal{A}}(n) \leq c\cdot n^{2}$ we get $T\_{\mathcal{A}}(n) \leq c\cdot 2^{n}$ (for all $n \geq \max\\{n\_{0},4\\}$), and hence $T\_{\mathcal{A}}(n) \in O(2^{n})$.

So giving a big-oh bound for an algorithm, only gives you an upper bound, there's nothing that says it has to be tight. Of course in practice we strive to make them as tight as possible.

---
Tags: asymptotics, landau-notation
---


# Question
Title: An n-dimensional index where the search key specifies an exact match on certain dimensions?
I'm working on a project where I want to to search for vectors in the form (x1, x2, x3,...xn), and be able to search for them by specifying a specific x value and getting all vectors with that x value for that dimension. The value n, the number of dimensions, will be 4 or 5 in most cases.

For example, if I have a vector (1, 5, 9, 3, 7), I would want to be able to find such a vector by searching in the index with a search key specified as (\*, \*, 9, \*, \*), where * is a wildcard, and finding that vector and all other vectors with the value 9 in the 3rd position.

The reason for doing this is that I am building a path index for a graph database, where I precompute a large number of paths in a graph of length 4 or 5. These paths I store as vectors, where the first index in the vector specifies which path this is, and the remaining items specify the id of the nodes along that path. You can you use this to quickly answer graph queries such as:

"MATCH (person)--\[likes\]--\>(food)--\[madeBy\]--\>(company),

RETURN person, food, company".

You determine what ID you assigned the \[likes\],\[madeBy\] path, search in the B+tree for this ID, and now you have all the nodes on that path.

However, if you delete a specific food node from the graph, finding the relevant nodes in the B+Tree is not possible, since you don't know which paths it could be in. Therefore, finding it is O(n) in the index. You can also look at that node in the graph and compute all the paths it is in, which is another option I am looking in to, but it would be nice if there was a way to do this in the index itself. Such as, if you deleted a node with ID 5, for a 5-dimensional index you could perform deletions: (\*, 5, \*, \*, * ), (\*, \*, 5, \*, * ), (\*, \*, \*, 5, * ), (\*, \*, \*, \*, 5).

I appreciate any insight anyone has. Multi-dimensional indexing is new to me, and I have limited time to complete the project.

# Answer
> 1 votes
If you only want to be able to search on a single dimension at a time (as in your example), this is readily solved by precomputing an index. Basically, you scan the entire database and build up an index for each dimension. For instance, an index for the first dimension is a hashtable that maps from the value of $x\_1$ to the tuple $(x\_1,\dots,x\_n)$, for each tuple. You then build an index for the second dimension, for the third dimension, etc. You do this once, in advance. Once you have the index, it's easy to answer queries. Also, it's easy to update the index when you insert or delete vectors.

A simple way to program this would be to insert your data into a database. Most databases will automatically build indices and update them as you change the data in the database. This will spare you having to implement that logic yourself.

---
Tags: graphs, search-algorithms, search-trees
---


# Question
Title: Limiting memory usage while keeping score
For an assignment we are asked the following(simplified) :

> A function F(a) has a non-negative integer as a result. This result is reused in the function itself. Like this, and where the first a is given:
>
> new\_a = (c1 * (previous\_a or first\_a) + c2) mod c3
>
> Write, in C#, a sufficiently fast and memory efficient algorithm that tells how many iterations of the function does it take before new\_a is within a specified range of any previous ones?

Now I have already made a "naive" solution as follows: I create an array of size c3 and for every new\_a I check whether its corresponding index is set to true. If so, the number of iterations is returned. If not, the index and the given range around it is set to true. This goes on until there is a hit.
This solution is very fast but the downsize is that for large enough sizes of c3 there is just not enough memory available.

I have been thinking about a week now on how to solve the memory problem, but I just am stuck figuring out how to do it? The only thing I can think of is that given the function there is some kind of assumption I should/can make about the distribution of its outcomes but I just am stuck.

Any ideas on the direction I should take?

# Answer
Your idea of an array of size $c\_3$ is a good one. But you can do better. First, since you need only be withing a range $r$, you can use an array of size $c\_3/r$, rounding upward, and just mark the entry corresponding to the integer segment you fall in (there may be some details to work out).

Then, rather than using an array, if it is still too large, you can build a binary structure, so that you create only the array entries you need. Each node of the binary structure corresponds to a range of consecutive entries.

> Then, you can reduce the memory requirement further by merging contiguous ranges where all entries have been hit, and rebalance the tree.
> Of course, there is a $\log\_2 c\_3/r$ price in access time. But this cost is limited by the tree shrinking as it gets full.
> 2 votes

# Answer
While babou offers one possible solution, that one depends on $c\_3/r$ not being too large. If it is large, then you might approach the problem like this:

A data structure for solving this problem would need to provide us with 3 (or 5) operations: we need to be able to *add* numbers, given a number we need to find the *predecessor* (next smaller number) and the *successor* (next larger number).

One possible data structure that supports these operations is a binary search tree, and this gives a quite straightforward algorithm: generate the numbers $\\{a\_n\\}$ one-by-one, and insert them in to the tree, and after each insertion query for the successor and predecessor values of the newly inserted number to see if they are in the specified range. If you use a balanced binary search tree (such as an AVL tree or red-black tree) each operation takes $O(\log n)$ and you obtain an $O(n \log n)$ algorithm where $n$ is the number of iterations before $\\{a\_n\\}$ comes in to the specified range. Using a Van Emde Boas tree you could improve this to $O(n \log \log n)$. This approach uses only $O(n)$ memory so it is much more efficient than babou's approach if $c\_3/r$ is large.

Another approach that is remarkably simple and might work very well in practice is based off insertion sort: if you could keep the elements of $\\{a\_n\\}$ generated so far in a sorted array, given a new value $a\_n$ you could find its position in the array using binary search and find the next larger and smaller values just by looking one position to the left and right. The problem with this approach is of course *inserting* new elements, since that requires expanding the array, and moving over all of the elements larger than the newly generated one one spot to the right.

However, you could store $n$ elements in an array of size $2n$, doubling up every element. You could still use binary search to find a new element's position, but inserting it becomes possible without extra work: you can simply have it take the place of a duplicated element. Of course, as the array gets fuller (with less duplicates) collisions might happen where you need to insert an element at a position where there are no more duplicates. This can be resolved in a similar manner to insertion sort, you can push elements to the right to make space for the newly generated element. Unlike insertion sort, this pushing stops much earlier: as soon as a duplicate element is encountered.

If the elements of $\\{a\_n\\}$ are distributed somewhat evenly (which they are, by virtue of the way they are generated) then the chances of needing a long (and expensive) move step are small, and most insertions will be dealt with quickly. As the array becomes too full such collisions will become more frequent. When you get to the point where (say) the number of distinct elements stored becomes $1.5n$ you might double up the size of the array to $4n$. Even though this is a very expensive step (it requires moving all of the elements to a new array) it only happens very infrequently (since you double the size of the array each time, you only do this expensive step $O(\log n)$ times).

As I mentioned before, babou has already provided a hint in the right direction of how you can make the array smaller, this answer is just to offer a more complete solution to the problem (in case somebody ever comes along and needs guidance on how to solve this problem in a more practical setting without bounds on $c\_3/r$). It's not the one you are intended to use, though if you managed to implement either one you would probably really impress the course staff and really get me in trouble :-)
> 1 votes

---
Tags: efficiency
---


# Question
Title: Double ended queue data abstraction and axioms
I am trying to show the data abstraction for a double ended queue along with the axioms. A double ended queue is a queue where items can be added to and remove from either end of the queue. I have already got the abstraction and axioms for a normal queue but looking at it, it looks to me like it would also work for a double ended queue. If this isn't the case what changes need to be made to make it work for a double ended queue?

```
Specification Queue:
Provides: Queue
Other abstractions used: Item, Boolean

Operations: NewQ: -> Queue
AddQ: Queue, Item -> Queue
RearQ: Queue -> Queue
FrontQ: Queue -> Item
IsEmptyQ: Queue -> Boolean

Axioms:
RearQ(NewQ) := NewQ
RearQ(AddQ(q, i)) := If IsEmptyQ(q) then NewQ
           otherwise AddQ(RearQ(q), i)
FrontQ(NewQ) := Error
FrontQ(AddQ(q, i)) := If IsEmptyQ(q) then i
           otherwise FrontQ(q)
IsEmptyQ(NewQ) :- True
IsEmptyQ(AddQ(q, i)) := False

Where:
   i is of type Item,
   q is of type Queue

```

# Answer
> 1 votes
Like you say items can be added to a double ended queue on both sides, yet you have only a single `AddQ` operator. More substantial is the change to the axioms. An item added at the end can (after several operations) be retrieved from the front.

---
Tags: data-structures, formal-methods, software-verification
---


# Question
Title: Interval scheduling scheduling problem with minimal workers
I am writing a greedy algorithm for a variation of the interval scheduling problem that I haven't seen before.

I have a set of jobs, each with start and finish time. All jobs in set must be assigned to a worker, workers cannot have overlapping jobs. My greedy algorithm should minimise workers - use the least number of workers possible to complete all jobs.

Does this algorithm accomplish this? It seems too simple to me and I have probably neglected to think of something.

```
sort(jobs) //earliest starting time first

w = 0 //number of allocated workers

for i = 1 to n {
    if (worker w has no job with finish time later than starting time of job i)
        schedule(worker w, job i)
    else
        schedule(worker w+1, job i)
        w++

```

# Answer
This is called *Interval Partitioning Problem* or *Interval Coloring Problem* in this lecture note, as well as in Section 4.1 of the book \[1\].

> Given intervals $(s\_i, f\_i)$, assign them to processors/workers so that you schedule every interval and use the smallest number of processors/workers.

The greedy algorithm is a simple one-pass strategy that orders intervals by their starting times, goes through the intervals in this order, and tries to assign to each interval it encounters a processor/worker that has not already been assigned to any previous interval that *overlaps* it.

---

\[1\] Algorithm Design. By Jon Kleinberg and Eva Tardos.
> 3 votes

---
Tags: greedy-algorithms, intervals
---


title: Sensitivity versus degree

text:
# Question
Title: Sensitivity versus degree
Given boolean function $f$, let $F$ denote the unique multiaffine real polynomial representing $f$.

Sensitivity of $f$ at input $x$ is $$S\_x(f) = |\\{i:f(x)\neq f(x^i)\\}|$$ where $x^i=x\oplus\Bbb 1\_i$ where $\oplus$ is $XOR$ operation.

Sensitivity of $f$ is $$S(f)=\max\_xS\_x(f)$$

Is there an easy proof to show $S(f)\leq \mathsf{deg}(F)$?

# Answer
There is a function with degree $3^n$ and maximum sensitivity $6^n$, known as Kushilevitz's function. See page 14 of this survey.

We do know that *average sensitivity* is bounded by the degree. This is because average sensitivity is the same as total influence, and an easy computation shows that total influence is at most the degree.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Is the language of all $a^n$ for which $n$ has an even number of digits in 10-base system regular?
Is the language $ L = \\{a^n ~| ~n \text{ has even number of digits in 10-base system}\\} $ regular?

My approach: let the $ p $ be from the Pumping Lemma. Chose the smallest $ n $ which has even number of digits in 10-base system, but bigger or equal to $ p $, that is $ n = 10^{2m - 1} $ for appropriate $ m $.

According to the Lemma, $ z = a^n = a^{10^{2m - 1}} = uvw $, and $ |uv| \leq p $, with $ v\neq \varepsilon $. So, we pump down $ v $, and we got the $ z' $ which should be in $ L $ (by the Lemma). That is $ uw $ should be in the language. If $ |v| $ is smaller than $ 10^{2m-1} - 10^{2m-3} $, than we reach a contradiction. If $ |v| $ is bigger, than we pump it up 10 times, to reach a contradiction again. I hope this is alright.

# Answer
> 1 votes
A slightly simpler way is to say that if you consider a string $x\in L$ of size $p$, then there is a non-empty substring $v$ of $x$ that you can pump without getting out of the language, if it is regular. Then you can pump it in $x$ until it exceeds a size $10^{2m}$, which has to be greater than $p$, such that $10^{2m+1}-10^{2m} \> |v|$. And you necessarily get the wrong number of digits.

In other words, you try to find in the sequence of possible sizes a gap that is too wide to be jumped by pumping a constant pumping size $|v|$.

This very simple reasonning also works with the context-free pumping lemma.

Wide gaps, that cannot be pumped exist as soon as empty gaps can increase in size beyond any bound. This depends on the definition of the language.

But using the pumping lemma is often a bit more sophisticated.

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


# Question
Title: Can you write a program that alters another program semantically?
It is definitely possible to write a program that takes another program as an input and changes it *syntactically*, but does not alter the meaning.

But is it possible to write a general program $alter$ that alters the output of a given program $P$ for *some* input, i.e. $\exists x: P(x) \neq alter(P)(x)$? Edit: Let's add the assumption that $\exists k: P(k) \neq \bot$.

---

I was thinking about doing something simple like this:

```
alter(Program P)(x):
   k = findSomeInputWhereHalts(P)
   y = P(k)

   if (x == k)
     return y+1 // or something else except y
   else
     return P(x)

```

This requires that $P$ does halt for some input $x$, which is an OK requirement for me. But it seems that there is probably some other counterexample to this specific algorithm or it might be generally uncomputable, but I failed to figure it out.

Edit: How I imagined implementing findSomeInputWhereHalts:

```
findSomeInputWhereHalts(P):
    for each int n:
        for each int k <= n:
            y = run P(k) for n steps
            if (y is defined)
                return k

```

But this obviously never halts if $\nexists k: P(k) \neq \bot$ .

# Answer
Your idea fails (assuming all `P` are allowed), and that's not by accident.

1. You can not find an input for with `P` halts in finite time. `P` may *never* halt, in which case that line in your program loops; thus, the program behaves exactly the same as `P`.
2. You can skip finding `k` and do

```
alter(P, x) =
  P(x) + 1

```

This is the same idea as you have (note how it alters the semantics on *all* inputs on which `P` halts) but does not require us to find an input on which `P` halts.

However, it's still fails for the never-halting program -- but, at least, only that one!
3. What if we just output `1` or any other value sometimes? That takes care of never-halting `P`, but for each such hack with a static, computable "abort and output `c`"-criterion -- that includes runtime bounds! -- we can build easy counterexamples.
Idea: `if ( criterion ) then c else something`.

So that looks bad; we can't compute uncomputable criteria! And we have to "decide" after finite time for any fixed `x` (otherwise the never-halting `P` skrews us).

When prospects are this bleak, it's sometimes wise to try the other direction. What if the problem *can not* be solved, that is `alter` does not exist? In fact, given sufficient background in computability, it is clear that such a function can not exist.

Assume any computable, total function $\mathtt{alter} : \mathbb{N} \to \mathbb{N}$. We understand natural numbers as (the numbers of) programs in some Turing-complete programming language $\phi$. More specifically, let $\phi$ be a suitable numbering of all (partially) computable functions; we then denote by $\phi\_i$ the function computed by program $i$.

Now, by Kleene's recursion theorem there is some index (program) $i^\*$ so that $\varphi\_{i^\*} = \varphi\_{\mathtt{alter}(i^\*)}$, that is $\mathtt{alter}$ *has no effect* on $i^\*$, semantically. Stronger versions show that there are *infinitely many* such $i^\*$ so there's no hope fixing this.

In summary, no such program `alter` that works on all input programs can exist.

If you allow only `P` that halt for at least some `x`, your approach works; the proof is elementary (show that `alter` is computable, and that `alter(P)(k) != P(k)` for some `k`).
> 2 votes

---
Tags: computability
---


# Question
Title: What additional expressivity does polyvariance give in pushdown CFA?
I'm reading through Pushdown Control-Flow Analysis of Higher-Order Programs, which presents a synthesis of the Abstracting Abstract Machines technique and pushdown automata to get static analysis which perfectly matches call and return sites. The paper presents a monovariant and two polyvariant forms of the system.

I can't seem to get my head around what additional expressive power polyvariance (e.g. 1CFA) grants when return-flow merging is already eliminated in the monovariant case by the pushdown methods.

Could someone provide an example program in which polyvariance helps?

# Answer
After playing with an implementation (found here), I believe I've figured it out.

Although 0PDCFA technically entirely eliminates return-flow merging, this isn't a very strong result in the absence of any polyvariance: if the same function is called in two different contexts, the analysis must end up merging flows within the body of the function, since multiple values are bound to the same variable and the variable's abstract address is identified with its name. 1PDCFA provides a different set of addresses to each syntactically distinct call of each function (I might be either under- or over-selling here), eliminating much of the merging.
> 1 votes

---
Tags: programming-languages, pushdown-automata, functional-programming
---


# Question
Title: What features should a critical section have to maximize performance?
Critical sections limit performance by constraining parallel execution and adding overhead. What features should a critical section have for improving performance?

# Answer
> 2 votes
As noted in the question, the performance impact of critical sections has two components: the limiting of parallelism and the overhead in providing the isolation guarantees.

The limiting of parallelism can be addressed by minimizing the context, frequency, and duration of the critical section. Using finer-grained locking or transactional memory allows independent operations to be executed in parallel by reducing the context in which isolation must be guaranteed.

Reducing coupling of operations can reduce the context and frequency of critical sections. The use of redundant data structures can provide localization of data such that critical sections can be avoided (reducing their frequency) or the potential contention reduced. For example, instead of updating a single accumulator a tree of accumulators could be used.

(While the fastest critical section is the one that does not exist, one must be careful that overheads in avoiding critical sections are not higher than the cost of using a critical section.)

The duration of a critical section can be reduced by keeping work out of the critical section. While this is relatively obvious, moving work before or after the critical section may require that more work be done (at least in some cases) or may interfere with other design considerations. *Speculatively* performing work before a critical section can shorten a critical section at the cost of detecting and handling incorrect speculation.

One subtle form of work is the handling of cache misses and state updates (primarily acquiring ownership of a cache block). Avoiding false sharing is a well-known technique, but somewhat less commonly mentioned (in part because of tradeoffs of complexity and runtime overheads with the performance benefit) are localization of true sharing and prefetching. Temporal localization of sharing exploits patterns of reading and updating to use warm data. In some cases, it may even be worthwhile to *increase* the duration of a critical section to reduce the amount of work within critical sections by taking advantage of a warmed-up cache.

Sharing can also be localized within the memory system. Not all communication between threads has equal cost. Physical proximity of communication and read-sharing can exploit sharing of a level of cache to keep warm data in cache (incidentally avoiding replication), to prefetch data (if cross-thread accesses can have temporal locality either naturally or by clever scheduling), or to reduce the bandwidth or latency of communication. NUMA-optimizations can also reduce bandwidth and latency by locating users, especially modifiers, of data near the home of the data. NUMA-optimizations can even apply to last level cache slices when a cache block has a single home partition within the last level cache which can be accessed with less overhead by one or more processing elements.

Using finer-grained locking can also reduce the isolation overhead by avoiding cache line ping-pong. The ultimate in fine-grained locking is lockless updating using atomic operations. Knowing what facilities the targeted hardware provides and the tradeoffs in their use can also be helpful in reducing isolation overhead. For example, if the targeted hardware transactional memory system supports low overhead retry under certain conditions, it may be less important to avoid contention leading to a transient transaction failure than to make sure those conditions are satisfied.

Approximation can also exploited in some cases to reduce overhead. Statistical information such as software performance counters can often tolerate losing some updates, allowing removal from the critical section and the use of less expensive non-atomic operations. Similarly, some information only needs to be conservatively maintained for correctness. For example, a reference counter could afford to lose a decrement if the information is only used for earliest release of a resource (another layer of resource management might handle such leaks).

The basic principle for critical sections is that they should be as small (context and duration) and as infrequent as possible.

---
Tags: operating-systems, performance, synchronization, os-kernel
---


# Question
Title: Difference between time complexity and computational complexity
For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them? I used to calculate the maximum (worst) count of basic (most costing) operation in the algorithm.

# Answer
Computational complexity is the general subject of using complexity measures to compare programs or algorithms. Time complexity and space complexity are two measures that are commonly used when talking about computational complexity, but there are others.

For example, it's common to look at the number of comparisons performed in a sorting algorithm.
> 10 votes

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


# Question
Title: Right equivalent elements arising in the proof of the Schützenberger Theorem
As a part of my Bachelor thesis in computer science I should review the proof of the Schützenberger Theorem (which was given by M.P. Schützenberger himself $^{\[1\]}$). My question arises on page 193 in line 11, namely in the equation: $$" \gamma ( f x ) M ( = mM = mM \cdot M)"$$ But I will break this down in my own words to make this understandable (hopefully).

Let $M$ be an aperiodic monoid, $\Sigma$ a finite alphabet and $\gamma : \Sigma^\* \to M$ a surjective monoid-homomorphism. Fix an element of $m \in M$, whose generated right ideal satisfies $m M \neq MmM$ and $mM \neq M$.
With these define the language $L = \gamma^{-1}(mM)$ and $\hat{L} = L \setminus (L\Sigma^+)$ (one can prove that $\hat{L}$ is the smallest set satisfying $L = \hat{L}\Sigma^\*$) and $M'' = \\{m'\in M \mid \gamma^{-1}(m')\Sigma \cap \hat{L} \neq \varnothing\\}$.
For a fixed $m' \in M''$ one can find a $w \in \gamma^{-1}(\\{m'\\})$ and a $\sigma \in \Sigma$, such that $w \sigma \in \hat{L}$. Now one has to show, that $mM = \gamma(w \sigma) M$.

Well in my opinion $\gamma(w \sigma)M \subseteq mM$ is rather easy, because $w\sigma \in \hat{L} \subseteq L$, therefore $\gamma(w\sigma) \in mM$, which implies ($M \cdot M = M$) this direction.

But I have trouble proving the opposite direction. I gladly appreciate every hint you give me, because I seem to have some kind of blockade in thinking about this. My guess is that the special property of $\hat{L}$ (above in parentheses) is somehow involved.

**Reference:**
$^{\[1\]}$ M.P. Schützenberger. On finite Monoids having only trivial subgroups. Inform. and Computation, 8:190-194, 1965.
A copy can be obtained here: Schützenberger Theorem

# Answer
As suggested by J.-E. Pin in the comments, this claim is wrong in the general case. To prove this statement a counter-example shall be constructed, but this will be done by a Haskell-program (at the bottom of this answer). But first I want to explain what it should do. The program looks onto a special kind of maps that map Maybe \[-2,-1,0,1,-2\] to itself. It suffices to look at maps that only go from \[-2,...,2\] to Maybe \[-2,...,2\]. The set of maps that this program looks at is even more limited, because it shall only be those maps, that can be generated by `a` and `b` only. The function `calculateAll` should calculate the all the elements in the monoid generated by these two functions and the identity (this is a rather large monoid with 56 Elements). `isAperiodic` does what the name suggests, but it does not fail, therefore it is unsafe. Next this program can calculate all the "interesting" candidates, that are those elements of the monoid, whose principal right ideal does not equal the whole monoid and not the principal two-sided ideal. This is done by `getCandidates`. Then `testForOneCandidate` generates all the counterexamples for the claim for a fixed element $m$, where only completion with the letter $a$ is considered. This is done as follows: An element in $m''$, which does not lie in $mM$, but $m''\ast a \in mM$, is in $M''$. For such an element one only needs to test if $m'' M \neq mM$. This is what `testForOneCandidate` does. Retranslating the first result of the call `testForOneCandidate (head getCandidates)` into potencies of `a` and `b` one gets the following in `ghci` testable counter-example (after loading the code):

```
*Main> let ba = b `mappend` a
*Main> ba `elem` rightPrincipalIdeal a
False
*Main> let ba2 = ba `mappend` a
*Main> ba2 `elem` rightPrincipalIdeal a
True
*Main> (fromList $ rightPrincipalIdeal ba2) < (fromList
    $ rightPrincipalIdeal a)
True

```

That is a rather complicated example, but I'm sure that there are simpler ones, it's just the first that I encountered.

Here is the code:

```
import Data.List (nub,(\\))
import Data.Set (fromList)

data Element = Element (Int -> Maybe Int)

instance Show Element where
  show (Element f) = show (map f [-2..2])

instance Eq Element where
  (==) (Element f) (Element g) = (map f [-2..2]) == (map g [-2..2])

instance Ord Element where
  (<=) (Element f) (Element g) = (map f [-2..2]) <= (map g [-2..2])

instance Monoid Element where
  mempty = Element dropOutside
  mappend (Element f) (Element g) = Element $ \i -> ((f i) >>= g)

-- Helper function
dropOutside :: Int -> Maybe Int
dropOutside i
  | abs (i) <= 2 = Just i
  | otherwise = Nothing

-- First elements that "generate" the monoid
a :: Element
a = Element $ \i -> dropOutside (i+1)

b :: Element
b = Element $ \i -> dropOutside (i-1)

nullElement :: Element
nullElement = Element $ \_ -> Nothing

-- Generates the monoid by the neutral element, a and b.
calculateAll :: [Element]
calculateAll =
  let
      calculateAllRec :: [Element] -> [Element]
      calculateAllRec acc =
          let
              newEs = nub [z| x <- acc, y <- acc,let z = x `mappend` y,z `notElem` acc]
          in case newEs of
               [] -> acc
               _ -> calculateAllRec (acc ++ newEs)
in calculateAllRec [mempty,a,b]

-- Checks whether a given element is aperiodic. (Unsafe)
isAperiodicElement :: Element -> Bool
isAperiodicElement x = isApElRec x x where
  isApElRec x' y'
      | y' == (x' `mappend` y') = True
      | otherwise = isApElRec x' (x' `mappend` y')

-- Checks if the whole monoid is aperiodic. (Unsafe)
isAperiodic :: Bool
isAperiodic = all isAperiodicElement calculateAll

-- Calculates the right ideal generated by a given element.
rightPrincipalIdeal :: Element -> [Element]
rightPrincipalIdeal x = nub [x `mappend` y | y <- calculateAll]

-- Calculates the twosided ideal generated by a given element.
twoSidedPrincipalIdeal :: Element -> [Element]
twoSidedPrincipalIdeal x = nub [z `mappend` x `mappend` y | z <- calculateAll , y <- calculateAll]

-- Calculates all those elements, that generate a right ideal, which is not
-- equal to the whole monoid and the twosided ideal generated by that same element.
-- Results in all elements besides the neutral and the null element.
getCandidates :: [Element]
getCandidates =
  let
      fLcA = fromList calculateAll
  in [x| x <- calculateAll,
         let z = fromList $ rightPrincipalIdeal x,
         z /= fromList (twoSidedPrincipalIdeal x),
         z /= fLcA]

-- Tests for an element m from getCandidates, if there is an element in M withouth mM
-- that reaches mM by adding an a (which amounts to saying that this element m' is in
-- M''). Therefore m'a is in mM. But also m'aM must not be mM.
testForOneCandidate :: Element -> [Element]
testForOneCandidate m =
  let
     mM = fromList $ rightPrincipalIdeal m
     factorsWithA = [m' | m' <- calculateAll ,
                                m' `notElem` mM,
                                let x = m' `mappend` a,
                                x `elem` mM,
                                fromList (rightPrincipalIdeal x) /= mM ]
  in factorsWithA

```
> 1 votes

---
Tags: formal-languages, regular-languages, mathematical-foundations
---


# Question
Title: How to understand equivalence of indexes of a family of types that are not definitionally equal
So I've been reading things about HoTT and trying to get solid on the foundations before getting too much further into the book. I am confused by a certain point; maybe I just haven't read far enough yet however. I don't think my question is specific to HoTT but just dependent type theory in general.

Say you have a family of types defined by something like $B : Nat \to Set$. There are two fibers/indexed types defined by $B(x + y)$ and $B(y + x)$. These are definitely not definitionally equivalent but maybe they are extensionally equivalent because $x + y = y + x$. However I thought that perhaps indexes behave definitionally in some cases in which case $B(x + y)$ and $B(y + x)$ might be extensionally distinct.

I tried thinking about the case of $Fin : Nat \to Set$ (the integers less than a certain value). I think that both $Fin (x + y)$ and $Fin (y + x)$ have no inhabitants however because the standard constructors for them have no constructors that unify with $x + y$ or $y + x$. So they both have no inhabitants but what does that mean about their equivalence? This seemed like a bad case to think about to me.

My main question is the following: how does one think about the equivalence between these two types?

My subquestions/confusions are: Do these types have the same inhabitants? Are they extensionally equal? Does having the same inhabitants means that types are extensionally equal?

# Answer
> 4 votes
We can prove `(x : Nat) (y : Nat) -> x + y = y + x` (they are propositionally equal). I'm using Agda-ish notation here rather than the notation in the HoTT book because type setting is hard. Note that we can prove this in standard intensional type theory. This gives a function from `Nat` to `Nat` to a proof of equality.

In intensional type theory we don't distinguish between types up to judgmental equality. Almost as though there's a rule

```
     A ≡ B  a : A
     ------------
        a : B

```

Remember that `FZ : Fin 1`, Since `0 + 1 ≡ 1`, this means that `FZ : Fin (0 + 1)`. If we didn't have a rule like this, it'd be kinda pointless to have computation in our types because the minute we actually have some interesting expression in our type we couldn't witness it.

It's important to keep the different types of equality separate in type theory

1. Judgmental equality (a judgement) is something actually embedded in the system. You can't touch it when writing programs but it says that two terms are equal if they have the same value more or less
2. Proposition equality (a proposition) is what we can prove as a programmer. There is one way to prove `A = B` in standard ITT, with `refl : A = A`. This means that we can prove `A = B` if and only if `A` and `B` are judgmentally equal.

Whether `Fin (x + y)` or `Fin (y + x)` for some `x` and `y` have members is dependent on what `x` and `y`. If `x` and `y` are `0`, then `Fin (x + y)` is judgmentally equal to `Fin 0`, which is unoccupied.

We can prove that `Fin (x + y) = Fin (y + x)` though in standard ITT, the proof in a system like Agda looks like

```
eq : (x y : ℕ) → Fin (x + y) ≡ Fin (y + x)
eq x y rewrite +-comm x y = refl

```

So in answer to your question, the two types are propositionally equal using an intensional notion of equality. This isn't enough to say if `e : Fin (x + y)` then `e : Fin (y + x)`, for that we'd need judgmental equality. We can easily construct invertible maps between the two though by pattern matching on the result of `eq` for example.

Finally, in answer to your last question. In extensional type theory this is the case, in intensional type theory we need some extra tools. HoTT in particular provides us with univalence which is even more flexible: two types can be propositionally equivalent if they're isomorphic.

---
Tags: programming-languages, type-theory, dependent-types, inductive-datatypes, homotopy-type-theory
---


# Question
Title: How does one change the probability bounds in probabilistic complexity classes without changing the class?
I see this theorem whose proof is not clear to me :

"Let $L \subseteq \\{0,1\\}^\*$ be a language and suppose that there exists a polynomial time PTM M such that for every $x \in \\{0,1\\}^\*$ and $Pr\[ M(x) = L(x) \] \geq 1/2 + \vert x \vert ^{-c}$ Then for every constant $d \>0$ there exists a polynomial-time PTM M' such that for every $x \in \\{0,1\\}^\*$, $Pr\[M(x)=L(x)\] \geq 1 - 2^{-\vert x \vert ^d}$"

* Even if I assume this above theorem how does this help convert the $2/3$ probability guarantee in the definition of BPP , RP and coRP into $1-2^{-\vert x \vert ^d }$ without changing the class?
* I understand that the above theorem is proven by doing a $8\vert x \vert ^{2c +d}$ iterations of the PTM's run and then taking the majority vote and somehow Chernoff bound helps get the exact numbers. But I can't understand the intermediate argument. It would be helpful if someone can help fill in!

# Answer
> 2 votes
Suppose that $\Pr\[M(x) = L(x)\] \geq 1/2 + \epsilon$. Run $M$ repeatedly $m$ times (for $m$ odd), and take the majority vote. Let $x\_i$ be the indicator for the event that the $i$th run of $M$ gives the correct solution. The success probability of the majority vote algorithm is $$ \Pr\[x\_1+\cdots+x\_m \> m/2\] \geq \Pr\[\operatorname{Bin}(m,1/2+\epsilon)\>m/2\]. $$ At this point you apply the Chernoff–Hoeffding bound. You take it from here.

---
Tags: complexity-theory, time-complexity, probability-theory, randomized-algorithms
---


title: Calculate Pagerank of three nodes

text:
# Question
Title: Calculate Pagerank of three nodes
Soon I will have an exam where I will be asked to calculate pagerank. So far, I have been thought to use power iteration. However, this can be a very expensive operation to do during an exam, especially when most of the times, the number of nodes is just 3.

Is there any better algorithm to calculate the pagerank of only 3 websites involved?

# Answer
There is a formula for the PageRank which involves inverting an $n\times n$ matrix. When $n = 3$ this is not too hard. For inverting the matrix, use the formula given on Wikipedia, which is just a special case of the general formula involving the adjugate matrix.

That said, I see absolutely no reason why you would ever have to calculate PageRank by hand. That's what we have computers for. If you are given such an exercise in an exam, the matrix will probably have some very simple structure which will make it easier to handle by hand.
> 5 votes

# Answer
A less formal answer, but nice step by step strategy is described in this video
> 1 votes

---
Tags: information-retrieval
---


# Question
Title: Meaning of "positive position" and "negative position" in type theory?
What does "in positive position" and "in negative position" mean in the context of type theory?

The only thing I understood from Bob Harper's blog post on the topic is that there is a connection between polarity in this sense in type theory and polarity in logic, but I don't know what that connection is.

# Answer
> 11 votes
Unfortunately "polarity" is a somewhat overloaded concept in type theory. "Positive position" and "negative position" refer to a different notion of polarity than what Bob's talking about with focusing/polarization.

## Your Meaning

When you're defining an inductive type you give a series of rules which correspond to operations for the type you're defining. For example you might say a `Nat` is something with

* a value `zero : Nat`
* a function `suc : Nat -> Nat`

And then expect that `Nat` contains all the values that can be generated from repeatedly applying `suc` to other `Nat`s and includes `zero`. In line with this inductive construction we get an recursion principle across `Nat`s which works based on the fact that any `Nat` is generated by those constructors.

```
rec : A -> (A -> A) -> Nat -> A

```

so that

```
rec Z S zero = zero
rec Z S (suc n) = S (rec Z S n)

```

However, there are some restrictions on what we can write as rules. Otherwise, we can write down a series of rules for which the recursion principle cannot be justified. Consider the "inductive type" `D` with one constructor

* `d : (D -> D) -> D`

Here there isn't a sane recursion principle here. and for good reason! If we had some recursion principle, we could use it to encode a version of self application and with it, nontermination. This means `D` can't be called "inductive" because inductive types are finite constructions generated from repeatedly applying constructors!

In order to deal with this we restrict how inductive types can be recursive in type theory. Specifically, we stop them from appearing in "negative places". This is that notion of polarity you were talking about. The polarity of a position is determined thusly,

1. The argument starts in a positive position
2. Everytime we go to the left an arrow, the polarity flips

So `X` is positive in the first two and negative in the second two

```
X
Int -> X
X -> Int
(Unit -> X) -> Int

```

This idea is justified with a recourse to category theory where an inductive type with whose only recurrences are positive gives rise to a covariant functor. The details of how this works and why its interesting a a bit long.

## Bob Harper's Meaning

In his blogpost Harper was talking about a different meaning of polarity. This polarity is reference to how various connectives in logic are given meaning. In particular, we can classify connectives in two ways

* Positive connectives can be defined by defining how to introduce them (their introduction rules)
* Negative connectives can be defined by defining how to use them (their elimination rules)

In programming language terms, this nicely captures the distinction between lazy and strict types. A strict type is defined by its values. A lazy one is defined by how can pattern match on them. In order to handle this properly, we define a language with 2 main constructs, ways to build up positive types and "spines" to decompose negative types. We can use this to incorporate both strict and lazy computation into one language.

In order to understand this better, I refer you to chapter 38 of Bob Harper's book.

---
Tags: type-theory
---


title: $P \neq NP$ and determinism

text:
# Question
Title: $P \neq NP$ and determinism
Suppose $P \neq NP$. Does it imply that there exists some superpolynomial time bound, such that any $NP$-complete problem, like SAT, can be used to simulate an arbitrary deterministc Turing Machine working in that time bound?

Rephrasing does $P \neq NP$ imply that there exists some class $D$ of languages solvable by a deterministic Turing Machine, such $P \subsetneq\ D \subseteq NP$ and SAT is $D$-hard?

# Answer
This post shows that the answer to your initial question is yes (even if P = NP).

On the other hand, I suspect there is no known proof that if unambiguousGC(polylog, NC) ⊈ coNP/poly then there is a superpolynomial time-constructible function $T$ and a superlogarithmic space-constructible function $S$ such that

DTIME(T(n)) ∩ DSPACE(S(n)) ⊆ NP/poly.
> 1 votes

---
Tags: complexity-theory, turing-machines, p-vs-np
---


# Question
Title: Is set cover still NP-complete if you have a given k?
Set cover is NP-complete given an arbitrary set $U$, a set $S$ of subsets of $U$, and an integer $k$. However, what if $k$ is always a constant 3? Is that problem still NP-complete?

# Answer
> 7 votes
No.

Like many $NP$-complete problems, fixing the solution size gives a polynomial-time algorithm. In this case, we're looking for a group of at most $(k=)3$ sets $s\_{1}$, $s\_{2}$ and $s\_{3}$ from $S$ such that $s\_{1}\cup s\_{2} \cup s\_{3} = U$, so we can simply try *every* set of 3, which gives a $O(|S|^{3})$ algorithm because there's only $\binom{|S|}{3}$ groups of three sets taken from $S$, and in general, for every fixed $k$, an $O(|S|^{k})$ algorithm.

This is true for many other problems, like Dominating Set, Vertex Cover, Independent Set, $k$-Clique etc. etc. These all have $O(n^{k})$ brute force algorithms. Expressed in Parameterized Complexity terms, they're all in the class $XP$ (in fact, for all of these, they're in $W\[P\]$) when the parameter is the solution size1.

Note the contrast with problems like k-Coloring, which is $NP$-complete for every fixed $k \geq 3$. The best algorithms for problems like these have running times more like $O(k^{n})$ - the relationship between $k$ and $n$ is reversed to what we had before. Again in Parameterized Complexity terminology, such things are $para$-$NP$-complete, and don't have (non-uniform $XP$ algorithms unless $P = NP$.

**Footnotes**

1. $XP$ is the class of all parameterized problems that have a polynomial time algorithm for every fixed value of the parameter, also called "slicewise polynomial". $W\[P\]$ is the class of problems that have a nondeterministic algorithm that runs in $f(k)n^{O(1)}$ time with at most $h(k)\log n$ nondeterministic steps for some $h$, where $k$ is the parameter - we can remove the nondeterminism and get a $O(n^{O(h(k))})$ algorithm for some function $g$, through the same approach of trying all possible solution certificates.

---
Tags: np-complete
---


# Question
Title: Difficult Cases for 3MaxSAT and 3SAT Approximation Algorithm
1. Its known that a polynomial time approximation algorithm that satisfies 3MaxSAT in 7/8+e clauses implies P=NP.
2. Its also experimentally known that 3SAT has the most difficult known cases when the clause to literal ratio is approximately 4.2.

Q1. Is there a similar result for 3MaxSAT where the approximation algorithm for satisfying some 7/8+e of clauses becomes almost always difficult if 3MaxSAT has some specific format (like 3SAT in 2.) ?

Q2. Is there a benchmark set available for 3MaxSAT approximation algorithms for such cases?

Q3. Is there a similar approximation hardness result for 3SAT (like 3MaxSAT in 1.) if informed that the given 3SAT is satisfiable? Is just the clause to literal ratio is sufficient to represent completely the hardest cases for such approximation algorithms too?

# Answer
The reason that 3SAT is hardest empirically when the clause-to-literal ratio is 4.2 is because this is the *satisfiability threshold* (the threshold at which a random 3SAT becomes unsatisfiable with high probability). However, this is a very different type of hardness than NP-hardness. First of all, the model is different: you are generating a *random* 3SAT instance with a given clause-to-literal ratio, and hardness applies only on average. Second, there is no formal connection between the satisfiability threshold and computational hardness. There are some properties of the solution space which we think make the problem hard near the satisfiability threshold, but this is just a heuristic.

Now for your actual questions:

1. While there are definitely no formal results, it might be the case that known practical approximation algorithms for MAX-3SAT perform poorly near the satisfiability threshold.
2. No idea.
3. You are asking two questions. Regarding your first question, if you had an algorithm which approximated MAX-3SAT only on satisfiable instances, say achieving 99% performance, you could run it on any given instance, and so determine whether it is satisfiable or less than 99% satisfiable. We know that this is unlikely as long as the performance is larger than 7/8. Regarding your second question, the instances coming out of the hardness proof are not arbitrary, so there is a class of formally "hard instances", but I don't think it has anything to do with the satisfiability threshold.
> 2 votes

# Answer
Regarding a test benchmark: Keep in mind that the 7/8 hardness result is about *worst-case* behavior, not average-case behavior.

Suppose you have an approximation algorithm for MaxSAT. The fraction of clauses your algorithm can satisfy might be different for each different input (i.e., for each SAT formula). The 7/8th hardness result says you should not expect your algorithm to satisfy more than 7/8ths of the clauses on all possible inputs. However, it might be easy to come up with an algorithm that, for many inputs, satisfies more than 7/8ths of the clauses. For instance, maybe you can satisfy 90% of the clauses for many or most inputs: that might be possible. But what you (probably) won't be able to do is achieve this for *all* inputs.

So, if you have an algorithm in mind, testing it on random inputs might not tell you very much about whether you've beat the hardness result you mention. As far I know, it seems possible that it might be easy to build an algorithm that, for a random input, on average satisfies more than 7/8ths of the clauses. This means that testing an algorithm on random inputs won't necessarily tell you very much. Even if you came up with some clever algorithm and found that, on random inputs, on average, the ratio of satisfied clauses is, say, 90%... that wouldn't contradict the NP-hardness results you mentioned. For these reasons, if you think you've got a great approximation algorithm that will do better than the hardness results suggest... it's not enough to test it on random inputs. You'd have to somehow test it on all possible inputs.

Or, to put it another way, the *average* fraction of clauses you can satisfy on *random* inputs might be very different from the *guaranteed minimum* fraction of clauses you can satisfy on *all* inputs.
> 1 votes

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


# Question
Title: How to understand the reduction from 3-Coloring problem to general $k$-Coloring problem?
3-Coloring problem can be proved NP-Complete making use of the reduction from 3SAT Graph Coloring (from 3SAT). As a consequence, 4-Coloring problem is NP-Complete using the reduction from 3-Coloring:

> Reduction from 3-Coloring instance: adding an extra vertex to the graph of 3-Coloring problem, and making it adjacent to all the original vertices.

Following the same reasoning, 5-Coloring, 6-Coloring, and even general $k$-Coloring problem can be proved NP-Complete easily. However, my problem comes out with the underlying mathematical induction:

> My Problem: What if the induction goes on to $n-1$-Coloring and $n$-Coloring problem, where $n$ is the number of vertices in the graph? I certainly know that $n$-Coloring problem can be solved trivially. So, is there something wrong with the reasoning? How to understand the reduction from 3-Coloring problem to the general $k$-Coloring one?

# Answer
The $k$-coloring problem is usually defined only for constant $k$, so $n$-coloring doesn't make sense. For every constant $k \geq 3$, the reduction you mention works. By adding a superconstant number of vertices you can show, for example, that $(n/2+3)$-coloring is NP-complete.
> 7 votes

# Answer
Your apparent contradiction comes from abusing the notation "$n$": its meaning changes as you move through the question.

When you say that $n$-colouring is trivial, what you actually mean is that it's trivial to colour any graph $G$ with $|V(G)|$ colours. But the $n$-colourability problem for any *constant* $n$ is the problem of determining whether an arbitrary input graph, with any number of vertices, has a proper $n$-colouring.

The chain of reductions from $3$-colourability to $n$-colourability adds $n-3$ vertices to the graph. This means that the only way you could end up with a trivial instance of the $n$-colourability problem is if your original input to the $3$-colourability problem had $3$ or fewer vertices – such an instance was already trivially $3$-colourable.

By the way, there's no need to use induction to prove that $k$-colourability is **NP**-complete for every $k\geq 3$ because it's easy to compose the sequence of reductions that would appear in the induction. A graph $G$ is $3$-colourable if, and only if, the graph $G'$ is $k$-colourable, where $G'$ is the disjoint union of $G$ and a copy of $K\_{k-3}$, plus all possible edges between the two parts.
> 3 votes

# Answer
The $k$-coloring problem is to color *any* graph. You can certainly find graphs for which $k$-coloring is trivial as well as formulas for which SAT is trivial or etc. This does not impact the complexity of the problems in general though.
> 1 votes

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


# Question
Title: Covering a graph with non-overlapping cliques
I have a problem where I need to split a graph into subgraphs. The conditions for the splitting is as follows:

* Every subgraph must be a complete graph/clique
* No vertex can be part of two or more subgraphs
* Subgraphs that can be merged with other subgraphs while remaining complete cannot exist
* When multiple possible complete subgraphs/cliques are present, chose the one with highest within-clique edge weight

Below is an obvious example. Multiple maximal cliques exists, but it is very clear to the beholder which two should constitute the subgraphs.

Community detection are not a good fit (at least the algorithms I've looked into) because they don't enforce completeness within the communities. Furthermore the graphs that I'm working with are quite small and dense, and community detection algorithms will often just find one large community.

My main approach now is thus to find all maximal cliques, and then somehow remove unwanted cliques based on edge weights but I'm at a loss as to what the best approach for the latter part is...

**Edit:** This is my current implementation

1. Detect maximal cliques in the graph.
2. Sort the cliques in descending order based on their minimum edge weight within the clique.
3. Iterate over the sorted cliques, adding cliques to my result list if, and only if, its member vertices are not present in any already selected clique.
4. After iteration see if any vertices in the original graph are present in any of the selected cliques.

* If all vertices are present, exit.
    * If not create a subgraph of the original graph containing the missing vertices and repeat 1-4.

This is sort of similar to @kurtosis answer but handles edge weights as well as the case where vertices are left out of the initial iteration.

**Edit 2:** To clarify what I'm asking (because it might be less obvious after the first edit). My problem remains as described in the first part. After posing the question I've developed a solution as described in the first edit, that seems to get the job done, but it is, in my view, not very elegant. It might be the only way to solve the given problem, but I wouldn't know as graph theory is not my main area. Thus I'm still curious if there are other more efficient approaches to solving the problem.

# Answer
> 6 votes
> Thus I'm still curious if there are other more efficient approaches to solving the problem.

If you take the complement graph $\overline{G}$, then your problem corresponds to a coloring problem. Cover by cliques in $G$ is the same as covering by independent set in $\overline{G}$.

The problem is para-NP-hard in the unweighted case and the problem is just hard no matter what you do.

There is an algorithm computing the chromatic number in time $O^\*(2^n)$ using exponential space, and in time $O(2.2461^n)$ using polynomial space.

The fastest algorithm I know to get the coloring runs in time $O^\*((1+\sqrt\[3\] 3)^n) = O(2.4423^n)$.

\[1\] Fomin, F. V., & Kratsch, D. (2010). *Exact exponential algorithms*. An EATCS Series — Texts in Theoretical Computer Science. Springer.

# Answer
> 3 votes
Try out classical Bron-Kerbosch algorithm. It finds all maximal cliques in a graph and is implemented, for example, in well-known python library networkx: http://networkx.lanl.gov/reference/generated/networkx.algorithms.clique.find\_cliques.html

Nevertheless, the cliques still can be overlapping, so the problem of finding the optimal non-overlapping clique set is open. I'm not aware of latest proceedings in the research on this topic. But you can concoct and apply some simple greedy heuristics, like this:

1. Sort all the obtained cliques by the number of participating nodes in descending order, breaking ties with the sum of edge weights
2. Take the first clique as a first community and move to the second
3. If the second clique doesn't overlap the first one, take it as a second community, else move to the third clique, and so on
4. If i-th clique doesn't include any of the nodes taking part in the already selected communities, add i-th clique to the communities, and mark all it's nodes as 'already visited'

---
Tags: graphs, weighted-graphs, clique
---


# Question
Title: Why do these recurrences determine the number of ways of tiling a 3xN rectangle with 2x1 dominoes?
http://www.algorithmist.com/index.php/UVa\_10918

The above link is a solution to UVa 10918 Problem. The problem is based on Dynamic Programming. I am not able to understand this approach to the problem. I have coded the solution but the approach is completely different. I want to understand the given approach. The problem is:

Determine in how many ways can a 3xN rectangle be completely tiled with 2x1 dominoes.

I only want to know how these recurrence relations came:

```
f(n)=f(n-2)+2*g(n-1)
g(n)=f(n-1)+g(n-2)

```

where f(n)=number of tilings of a 3xN rectangle g(n)= number of tilings of a 3xN rectangle with one of its corner squares removed

# Answer
> 8 votes
Suppose that the rectangle to be tiled has 3 rows and $n$ columns.

```
□□□...□
□□□...□
□□□...□
123...n

```

Consider a tiling of this rectangle using 2$\times$1 dominos. There are two basic options:

1. All tiles touching the $n$th column are horizontal. There must be 3 of them, and if you remove them, you get a tiling of a rectangle of size $3\times(n-2)$.

```
□□□...⧆⧆
□□□...■■
□□□...⧆⧆
123....n

```
2. Exactly one tile touching the $n$th column is vertical. It can either touch the top or the bottom. For each of these two options, if you remove it then you get a tiling of a rectangle of size $3\times (n-1)$ with one corner square added. That square must be tiled by a horizontal tile, after whose removal you are left with a tiling of a $3\times(n-1)$ rectangle with one corner square removed added.

```
□□□...⧇⧇      □□□...□⧆
□□□...□⧆      □□□...□⧆
□□□...□⧆      □□□...⧈⧈
123....n      123.....n

    |             |
    V             V

□□□...□□     □□□...□
□□□...□      □□□...□
□□□...□      □□□...□□
123....n     123....n

```

This explains the formula $f(n) = f(n-2) + 2g(n-1)$.

The same sort of analysis yields the formula for $g(n)$, but I leave that one for you.

# Answer
> 10 votes
The picture should say more than words.

---
Tags: recurrence-relation, dynamic-programming, correctness-proof
---


# Question
Title: Is multiprocessing possible on a turing machine?
I recently created a parallel implementation of the Merge Sort, in which the sorting of several groups was accomplished by different processes, and was wondering if this was theoretically possible on Turing Machine?

# Answer
> 5 votes
You can consider two variants of this question.

1. Can a Turing machine simulate parallelism?
2. Can a Turing machine simulate parallelism *efficiently*?

The answer for the first question is a resounding affirmative. Just like your own OS simulates threads on a single-core CPU, so a Turing machine can simulate parallelism.

Regarding the more refined second question, it depends on your definition of efficiency. You can probably simulate parallelism with at most a polynomial blow-up in resources (mainly time).

Turing machines are not a good model if you care about concrete efficiency. The more appropriate model is the *RAM machine*. RAM machines can probably simulate parallelism pretty efficiently, though you should not accept a running time any less that the *combined* running times of the individual threads in your parallel solution.

---
Tags: turing-machines, parallel-computing
---


# Question
Title: What is the difference between the Mogensen-Scott and the Boehm-Berarducci encoding for ADTs on the Lambda Calculus?
On the Lambda Calculus, there are several different ways to represent a list. For example, one can encode it as its right fold:

```
list = (λ (cons nil) (cons 1 (cons 2 (cons 3 nil))))

```

One can, instead, use `pair`, `false`, `fst` and `snd` as aliases to `cons`, `nil`, `head` and `tail`. This way, you will have this:

```
list = (λ (a) (a 1 (λ (b) (b 2 (λ (c) (c 3 0))))))

```

Another way is to use the Mogensen-Scott encoding, which represents a list as the `case` statement required to deconstruct it:

```
list = (λ (c n) (c 1 (λ (c n) (c 2 (λ (c n) (c 3 (λ (c n) n)))))))

```

But there is also another way, called Boehm-Berarducci encoding, which I didn't understand. Supposedly, it allows the same thing that the Scott allows: systematically representing ADTs with lambda terms. So, what is the difference?

# Answer
The Boehm–Berarducci encoding is often mistakenly referred to as the "Church" encoding. They both start from the same general idea (encode data types by their iterator/catamorphism), but differ in subtle ways. In particular, the Church encoding only represents data types in the untyped setting, only covers introduction, and is not tight; whereas, the Boehm–Berarducci encoding works in System F, covers both introduction and elimination, and proves that the encoding is tight.

For an extensive discussion of the differences, see this post by Oleg Kiselyov.
> 10 votes

---
Tags: functional-programming, lambda-calculus
---


title: Lower bound for maxima on 2D plane

text:
# Question
Title: Lower bound for maxima on 2D plane
> Given $n$ points $(x\_1, y\_1), \ldots, (x\_n, y\_n)$ on a 2-dimensional plane.
> A point $(x\_1, y\_1)$ *dominates* $(x\_2, y\_2)$ if $x\_1 \> x\_2 \land y\_1 \> y\_2$.
> A point is called a *maxima* if no other points dominate it.

I can come up with an $O(n \log n)$ algorithm to find all the maxima. However, I failed to solve:

> **Problem:** What is the lower bound for the "finding all 2D maxima" problem (say, on the comparison model)? And how to prove it?

# Answer
When asking for a lower bound, you should let us know what computation model you're interested in. A good first model to prove lower bounds on is the comparison model. In this case, usually you use the fact that given $n$ values $x\_1,\ldots,x\_n$, determining whether all of them are unique takes $\Omega(n\log n)$ comparisons. This problem is known as *element distinctness* or *element uniqueness*.

In your case, the natural candidate reduction is to map $x\_i$ to $(x\_i,-x\_i)$. Note that no pair dominates each other, but if $x\_i = x\_j$ then $(x\_i,-x\_i)$ "weakly dominates" $(x\_j,-x\_j)$. Therefore any algorithm outputting the number of "weak maxima" can be used to decide element uniqueness, and so requires $\Omega(n\log n)$ comparisons.

You are interested in maxima rather than weak maxima, so you need to tweak this idea a bit. Suppose that all $x\_i$ were integers. Then you map $x\_i$ to $p\_i = (x\_i+i/(2n),-x\_i+i/(2n))$. Now $p\_i$ dominates $p\_j$ iff $x\_i = x\_j$ and $i \> j$. So the number of maxima again allows you to decide element uniqueness.

While you can't really assume that the $x\_i$ are integers in the comparison model, you can tweak the reduction even further to implement the same effect: you map $x\_i$ to $p\_i = ((x\_i,i),(-x\_i,i))$, and you compare pairs of the form $(x,i)$ according to the following rule: $(x,i) \> (y,j)$ if $x \> y$ or $x=y$ and $i \> j$. Every algorithm for computing the number of maximas in the comparison model using $m$ comparisons can be converted to an algorithm for deciding element uniqueness using $O(m)$ comparisons, hence requires $\Omega(n\log n)$ comparisons.
> 4 votes

---
Tags: complexity-theory, reference-request, computational-geometry, lower-bounds
---


title: Convert RE to DFA

text:
# Question
Title: Convert RE to DFA
I've been trying to convert a regular expression to a non-deterministic finite automata (NFA) first using Thompson's construction, giving:

, which looks correct.

I am then using subset construction to create the DFA from the NFA, shown here.

But this does not look correct to me, as for example 0 followed by 0 is not valid according to the DFA I have constructed. I was wondering how should I be modelling the epsilon in the original regular expression, as I have simply treated it as a normal epsilon.

# Answer
> 3 votes
I transformed your NFA into a DFA as an exercise for my future test.

$\epsilon-closure\\{S\_0\\}= \\{S\_0,S\_1,S\_3,S\_4,S\_5,S\_6,S\_7,S\_9,S\_{12}\\}= A$

$1)$ From $A$ consuming $0$: $\\{S\_2, S\_8 ,S\_{13}\\}$

$\epsilon-closure\\{S\_2, S\_8 ,S\_{13}\\}= \\{S\_2,S\_5,S\_6,S\_7,S\_8,S\_9,S\_{11},S\_{12},S\_{13}\\}=B$

From $A$ consuming $1$: $\\{S\_{10}\\}$

$\epsilon-closure\\{S\_{10}\\}= \\{S\_6,S\_7,S\_9,S\_{10},S\_{11},S\_{12}\\}=C$

$2)$ From $B$ consuming $0$: $\\{S\_2, S\_8 ,S\_{13}\\}$

$\epsilon-closure\\{S\_2, S\_8 ,S\_{13}\\}= B$

From $B$ consuming $1$: $\\{S\_{10}\\}$

$\epsilon-closure\\{S\_{10}\\}=C$

$3)$ From $C$ consuming $0$: $\\{S\_8 ,S\_{13}\\}$

$\epsilon-closure\\{S\_8 ,S\_{13}\\}= \\{S\_6,S\_7,S\_8,S\_9,S\_{11},S\_{12},S\_{13}\\}=D$

From $C$ consuming $1$: $\\{S\_{10}\\}$

$\epsilon-closure\\{S\_{10}\\}= C$

$4)$ From $D$ consuming $0$: $\\{S\_8 ,S\_{13}\\}$

$\epsilon-closure\\{S\_8 ,S\_{13}\\}= D$

From $D$ consuming $1$: $\\{S\_{10}\\}$

$\epsilon-closure\\{S\_{10}\\}= C$

Then the initial state of the DFA is $A$ because it contain $S\_0$.

The final states of the DFA are $B$ and $D$ because they contain $S\_{13}$.

---
Tags: regular-languages, automata, finite-automata, compilers, regular-expressions
---


# Question
Title: What is the difference between a prime attribute and a proper subset of the candidate key?
I am taking DBMS classes and am currently studying the various normal forms. The following is the definition of a **Prime Attribute** I learned in class:

```
A prime attribute belongs to the set of attributes which compose the candidate keys.

```

For example, if **R(ABCDEF)** is a relation with the functional dependencies given as:

```
F = {AB -> C, D->E, C->F}
then,
Candidate Key will be ABD
and
the Prime attribute set will be {A,B,D}
and
the Prime Attributes are A,B and D.

```

The proper subset of a candidate key defines itself. For the above example, proper subsets of the candidate key for the relation **R(ABCDEF)** is:

```
{{A}, {B}, {D}, {A,B}, {A,D}, {B,D}}

```

From the above definitions, apart from the number of elements in either sets, it seems that a prime attribute and a subset of a candidate key *are pretty much the same*. Both of these terms are being brought up simultaneously while explaining Third Normal Form and Transitive Dependencies, which is confusing me. It would be nice if somebody clears the difference between them.

# Answer
> 2 votes
Prime attributes are, in your example, just **A**, **B**, and **C**. The subsets of the candidate key are combinations of prime attributes. The difference is subtle, but if you read your material carefully, it will become apparent.

---
Tags: database-theory, databases
---


# Question
Title: When did $LR(k)$ acquire the meaning "left-to-right scan, rightmost derivation?"
According to the Wikipedia article, the L in $LR(k)$ means "left-to-right scan", and the "R" means "rightmost derivation." However, in Knuth's original paper on $LR(k)$ grammars, he defines $LR(k)$ (on page 610) as a language that is "translatable from left to right with bound $k$."

I am guessing that this new terminology was chosen to complement $LL(k)$ parsing's "left-to-right scan, leftmost derivation." That said, I don't know when the terminology changed meaning.

Does anyone know where the newer acronym for $LR(k)$ comes from?

# Answer
> 5 votes
I went and asked Don Knuth about this. He mentioned that he first used the new terminology in his 1972 paper *Top-Down Syntax Analysis* (link here) to provide a consistency between the terminology in $LL(k)$ and $LR(k)$ parsing.

Hope this helps!

---
Tags: formal-languages, reference-request, terminology, formal-grammars, parsers
---


# Question
Title: TSP genetic algorithm: what mutation function for adjacency representation?
When implementing TSP GA I decided for adjacency representation (i.e. $j$ value in $i$-th index means that node $j$ goes right after node $i$), as it enables interesting heuristical crossover operation (see Greffenstette, 1985). However this source, like many others, is silent about a sensible option of mutating solutions written in this way.

Traditional approaches (taken from path representation) usually result in incorrect solutions. For example, let's take permutation `5 4 1 3 2` (path rep. `1 5 2 4 3`) and try swapping second and third position, namely giving `5 1 4 3 2`. Path representation would start with `1 5 2 1` and oops, we're stuck. Another methods are similaringly disappointing.

So, is there an elegant and fast (emphasis on the latter) idea to mutate? Of course, I can switch between representations, but it might strongly impact performance (a switch is linear complexity, though I believe there's a chance of finding something with $O(1)$) and it's a worst-case scenario.

# Answer
> 0 votes
The core of your problem is this: you want a simple mutation operator that sends any $n$-cycle to another $n$-cycle.

Recall that every permutation on $n$ symbols can be decomposed into cycles. To count as a TSP tour, you need the permutation to be a single cycle, i.e., it to be a $n$-cycle. So given a TSP tour (a permutation that is a $n$-cycle), you want your mutation operator to give you another TSP tour (another $n$-cycle).

Here are multiple approaches you could take:

1. Don't represent the tour in your adjacency representation. Instead, represent it as a $n$-cycle: represent it as a list of the vertices visited, in the order they are visited. Then, you can swap any two elements in the list and get another tour (another $n$-cycle). For instance, you'd represent your example path as the list `[1,5,2,4,3]`. Swapping the second and third position gives you `[1,2,5,4,3]`, which is another valid path.
2. Represent the path in adjacency representation. Do the same operation as above, but now apply it directly to the adjacency representation: emulate its effect on the adjacency representation. So, given `5 4 1 3 2`, you decide you're going to swap the order that `5` and 2`appear in. This can be done by replacing the`5`with a`2`, and replacing the`2`with the second element (`4`), and replacing the second element with`2\`.
3. Pick a suffix of the path, then splice that into the middle of the path. For instance, suppose you can decompose the path into $A \to \dots \to F \to G \to \dots \to P \to Q \to \dots Z \to A$. Then you could change this to $A \to \dots \to F \to Q \to \dots \to Z \to G \to \dots P \to A$ by splicing the $Q \to \dots \to Z$ part right after $F$. You can take any suffix and splice it in, at an earlier position, like this. This can be done via a not-too-complex transformation on the adjacency representation, by changing only three elements in the adjacency representation (in this example, you change the successor for $F,Z,P$).

---
Tags: traveling-salesman, genetic-algorithms
---


# Question
Title: How would I write a single expression involving count, x and y that has exactly the same effect as shown (below)?
```
count=0
x=7
y=3
while(y<x):
     y+=1
     count+=1

```

I'm having trouble writing this as a single expression.

# Answer
> 1 votes
I'm assuming that you're interested in the following more general situation:

1. Input: $x,y$.
2. Initialize $count$ to $0$.
3. While $y \< x$: Increment both $y$ and $count$.

You want to know the values of $x,y,count$ at the end.

If $y \geq x$ to start with, then the while loop never runs, so nothing happens. If $y \< x$ (and both are integers), then the loop runs $x - y$ times (why?). At this point you should be able to tell what are the values of $x,y,count$ at the end of the code.

# Answer
> 1 votes
As a single expression, the code segment you presented is equivalent to

```
count = 4

```

as long as you're not concerned with the change in $y$ (which will have $x$'s original value, 7, at the end) and $x$ (which will keep its original value, 7).

Trace the execution of the segment: as Yuval said, as long as $x$ and $y$ are integers, this will set $count$ to $x-y$ if $y\<x$ and to zero otherwise. This operation, by the way, is often called **monus**.

Depending on the language features you have available, it could be completely described as three assignments

```
count = 4, x = 7, y = 7

```

and, more generally (if $x$ and $y$ are external to the routine), by a compound conditional

```
y < x ? count = x - y, y = x : count = 0

```

---
Tags: formal-grammars
---


title: How to prove a Double CNF SAT is in NP

text:
# Question
Title: How to prove a Double CNF SAT is in NP
So I've been stuck trying to figure this problem out for a while. I've looked on wikis and all over stack exchange but I'm really stumped. This isn't my best subject, so any sort of explanation would be AMAZING.

```
The Double CNF SAT problem is given a Boolean formula in CNF determine if it
is satisfiable with every clause having at least two literals that are true.
Show that Double CNF SAT is in NP.

```

I'm really not confident in these SAT, NP problems. I know that NP is the class that consists of problems "verifiable" in polynomial times. So is my goal to show that a double CNF SAT can be verified in polynomial time? If so, how would I do this? How am I supposed to verify it in polynomial time. Is it just a generic solution?

Thanks for any contributions/help

# Answer
> 1 votes
In answer to your comment; yes, you can simply iterate through the clauses. If I had given you a certificate like $$ (y\lor w\lor u)\land(x\lor y\lor \overline{u}\lor z); x=T, y=T, z=F, w=T, u=F $$ could you quickly (in time polynomial in the length of the certificate) verify that (1) the CNF expression is satisfied by the assignments and (2) every clause has at least two literals that are true? Bet you could and could see that this verification is always possible. From that, one can conclude that DOUBLE CNF SAT is indeed in NP.

---
Tags: algorithms, np-complete, satisfiability, np, discrete-mathematics
---


# Question
Title: Big Theta Proof: May I chose any constant?
I have the following assignment:

> Prove that $\sum^n\_{i=1} i2^i \in \Theta(n2^n)$

My current approach thus far is the following:

Since we need to prove $k\_1 \cdot n2^n \le \sum^n\_{i=1} i2^i \le k\_2 n2^n$ I chose $k\_1 = 1$ and $k\_2 = 2$. This holds true to my condition. However I'm unsure whether I can just freely decide on using those two.

Therefore my question is:

> Am I allowed to chose any constant factor I want in a $\Theta$ proof (given that the condition holds true)?

# Answer
Yes, as long as the constant conforms to the definition of $\Theta$, that is it

* is positive and
* independent of $n$.

This follows directly from the definition of $\Theta$, which requires only the *existence* of *some $c\_1, c\_2\>0$* (in typical formulations).

You may find our reference questions helpful; in particular, there are more convenient ways to prove such claims besides checking the definition explicitly.
> 4 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Algorithm to find whether there is a path (any path) above length X between two vertices
We all know how to find the shortest path between two vertices, but what if I just want to know the answer to this question - is there a path, (any path), between vertex A and B of length larger than some X?

Should start from the shortest path, and then merge adjacent nodes if its length is less than X? (or extend the search "circle" gradually)

I don't want to first find all possible paths and then filter out those shorter than X, I want to stop the moment I find any path above a certain length between the two vertices, (and stop if I haven't found one after some MAX iterations)

(I assume I first do a shortest paths to find if there is at all any path between the nodes to avoid searching if there isn't)

It somehow feels it should be simpler that what I'm making it, but I can't seem to find a text-book algorithm for it (e.g. BFS / DFS / Dijsktra / Bellman Ford are not really helping here, right?)

I'm sure it's simple, but I need some push in the right direction.

(cross posted from https://softwareengineering.stackexchange.com/questions/283038/algorithm-to-find-whether-there-is-a-path-any-path-above-length-x-between-two based on suggestions in the comments)

# Answer
If you allow duplicate vertices on your path, you can make a network from your graph by giving each edge weight $-1$. Then, use Bellman Ford to find the shortest path and see if it has length $-X$ or less.

If you don't allow repeats, then the problem is NP hard, since finding the longest simple path between two vertices tells you whether there is a Hamiltonian path or not.
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: How to find number of paths between 2 nodes of a certain length
Consider the following adjacency matrix:

```
0 1 1 0 0 0 0 0 0 0
0 1 1 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
1 0 0 1 1 0 0 0 0 0
0 0 0 0 1 1 1 0 1 0
1 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 1 0 1
0 0 0 1 0 0 0 0 0 1

```

I need to find the number of paths (repeated vertices are allowed) from node 8 to node 5 of length 6.

What methods are there? I want to know how to do this by multiplying matrices but no one has given me a good answer.

# Answer
This is done exactly by multiplying the matrix by itself 6 times, and then $A\_6\[i,j\]$ will give you the number of paths. To get the intuition, figure out what a single matrix multiplication does to the adjacency matrix.
> 2 votes

---
Tags: adjacency-matrix
---


# Question
Title: How do I form a parse tree for equations?
I have the following equation

```
if (x > y) {
   if (y < a) {
     x:= a
     y:= b
   } else {
    x:= b;
   }
 }

```

I was thinking of something like this however I've never done it with actual functions so I'm not quite sure how to proceed.

What are the steps to take in creating a parse tree for something like this?

# Answer
> 1 votes
To produce a parse tree you need a string to parse, which you have, but you also need a grammar to tell you how well-formed (legitimate) strings are to be structured.

In your case you did not give a grammar. so that your question makes no sense. Usually this is done with context-free grammars

Furthermore I suspect that what you really want is an abstract syntax tree (AST), which is often very close to parse trees, but is supposed to be defined more abstractedly (for example with a sorted algebra), indpendently of any parsing process, and from which semantics is more easily defined. Note that, while the AST may be defined independently of any arsing process, it is usually associated to textual representation via a parsing process, though other means do exist.

Below is what an AST could look like for your example. But, as for parse trees, an AST can be properly given only if you have defined formally what the abstract syntax is for your language.

To be very complete, you need at least one formal definition that relates tree structures you may be interested in (parse trees or AST) for your text with corresponding textual strutures.

```
              if
     ________/|\________
    /         |         \
   >          if        :=
  / \    ____/|\____   /  \
 x   y  /     |     \ x    b
       <     :=     :=
      / \   /  \   /  \
     y   a x    a y    b

```

*Warning: the referenced wikipedia articles could be much improved, at least on the pedagogical side.*

---
Tags: parsers
---


# Question
Title: Difference between system bus, address bus and data bus?
What is the difference between system bus, address bus and data bus? Are they different wires or they are using same wires but logically different?

# Answer
> 2 votes
The difference is what data they carry. An address bus carries addresses (e.g., which address the CPU wants to load from memory). A data bus carries data (e.g., the value the memory found at that address). A system bus carries addresses, data, and control: see https://en.wikipedia.org/wiki/System\_bus

---
Tags: computer-architecture, operating-systems
---


# Question
Title: Requiring at least one alldiff constraint to be satisfied converted to SAT
For generating certain hard puzzles, I am trying to model a problem (ultimately) in SAT. I don't know how to do that, so I am starting with CSP because it's more expressive. In CSP, there is a global alldiff constraint, which requires all variables to take on different values from their domains. I have a set of alldiff constraints. However, out of this set, I only require at least one of them to be true. That is, not all of them have to be satisfied.

For concreteness, suppose we have 8 variables $x\_1,\ldots,x\_8$. Each take values from the domain $\\{0,1,2\\}$. We want to satisfy the following formula:

$$\text{alldiff}(x\_1,x\_2,x\_3) \lor \text{alldiff}(x\_1,x\_6,x\_7) \lor \text{alldiff}(x\_4,x\_5,x\_6) \lor \text{alldiff}(x\_3,x\_4,x\_8).$$

We are happy if at least one of the 4 alldiff clauses is satisfied, e.g., if $x\_1=0$, $x\_2=1$, and $x\_3=2$, we are already happy.

But how is then modeled in SAT? Specifically, how do we write an alldiff constraint in SAT?

# Answer
If you want to model an alldiff() constraint in SAT, there are several options. Here are two different options you can try:

* One way is to expand $\text{alldiff}(x\_1,\dots,x\_n)$ into $n(n-1)/2$ inequality constraints: $(x\_1 \ne x\_2) \land (x\_1 \ne x\_3) \land \cdots$. Now you can express each inequality constraint $x\_i \ne x\_j$ on $b$-bit values in turn as a boolean formula: $(x\_i\[0\] \ne x\_j\[0\]) \lor (x\_i\[1\] \ne x\_j\[1\]) \lor \cdots$, where $x\_i\[k\]$ is the $k$th bit of $x\_i$. In this way each alldiff constraint on $n$ $b$-bit variables expands into a boolean formula of size $\Theta(n^2 b)$.
* Alternatively, a different way is to use a one-hot encoding. Suppose each $x\_i$ needs to take values from some universe $U$ of $u$ values. Instead of encoding each $x\_i$ as a $\lceil \lg u \rceil$-bit value, encode it as a $u$-bit boolean vector, where $x\_i\[k\]=1$ if $x\_i = k$ and $x\_i\[k\]=0$ otherwise. Now an alldiff constraint on $n$ variables amounts to requiring that there are exactly $n$ ones in the $nu$-bit vector obtained by concatenating the vectors for each of the $n$ variables in the alldiff constraint. Thus, we obtain a $n$-out-of-$nu$ constraint.

This $n$-out-of-$nu$ constraint can be encoded in multiple ways; one way is to use a tree of half-adders to sum up these values. The tree will have $nu$ leaves, and with a $\lceil \lg nu \rceil$-bit output at the root. You can find more about encoding cardinality constraints here: https://cs.stackexchange.com/a/6522/755.

These approaches give you a boolean formula, i.e., a boolean circuit; it's not in CNF form. So, strictly speaking, it's not an instance of SAT. However, there is a standard way to convert any such boolean formula to CNF form: you use the Tseitin transform (equivalently, you use the standard reduction from CircuitSAT to SAT) and then run a SAT solver on the result. There are several SAT front-ends that will do this work for you; STP is one I have used that is quite convenient, but there are others as well.

This gives you at least options you could consider, for converting your problem to SAT. Which one is most efficient might depend on your specific problem and the parameters of your problem (the size of the domain, the number of variables in each alldiff constraint).

Also, if you have a lot of alldiff constraints, it seems likely that a CSP solver might do better than a SAT solver. CSP solvers are designed to handle alldiff constraints well, thus they might perform better than naively bitblasting to SAT, as SAT solvers won't be aware of that structure.

See also When to use SAT vs Constraint Satisfaction? and Converting (math) problems to SAT instances and https://cs.stackexchange.com/a/12153/755.
> 4 votes

---
Tags: modelling, constraint-programming, constraint-satisfaction
---


# Question
Title: People crossing a bridge (a proof for a greedy algorithm)
**The problem**

Some people are crossing a bridge. Each one takes a different time to pass.

Assume the people are sorted by their passing time increasingly.

These are the conditions of crossing the bridge:

1. only 1 or 2 people can cross the bridge at the same time in the same direction;
2. the speed of the two people crossing is the same as the slower one;
3. it is night and there is only one flashlight;
4. the people passing the bridge must carry the flashlight;
5. the flashlight cannot be thrown over the bridge so it must be carried back to the other end of the bridge.

**My greedy solution**

The obvious solution seems to be using the fastest guy to take every one to the other end and come back for the rest.

**The proof**

I tried to prove it like my text book CLRS:

> 1. Cast the optimization problem as one in which we make a choice and are left with one subproblem to solve.
> 2. Prove that there is always an optimal solution to the original problem that makes the greedy choice, so that the greedy choice is always safe.
> 3. Demonstrate optimal substructure by showing that, having made the greedy choice, what remains is a subproblem with the property that if we combine an optimal solution to the subproblem with the greedy choice we have made, we arrive at an optimal solution to the original problem.

I tried something like this:

If we assume the set of all people in the start is $P$ and the set of all people in the destination is $D$ and $O(x)$ is the function that gives the optimum time by getting the set of people and people $p\_i$ and $p\_j$ are chosen to pass the bridge and $d\_k$ is chosen to return the light and $d\_k \in D\cup \\{p\_i , p\_j\\}$ then:

$$O(P) = Max( t(p\_i) , t(p\_j) ) + t(d\_k) + O(P-\\{p\_i , p\_j\\} \cup {d\_k})\\,,$$

where $t(p\_i)$ is the time it takes for person $p\_i$ to pass.

Now I have to assume I have an optimal solution $OS$ and show that I can use the greedy choice instead of the choice the $OS$ has made.

I do not know how to proceed further.

# Answer
> 3 votes
The reason you can't prove that the greedy algorithm is correct is because it isn't.

Suppose the people cross the bridge in times 1, 2, 5 and 10 minutes. The greedy solution involves the one-minute person walking backwards and forwards every time and takes 10+1+5+1+2=19 minutes. The optimal solution is 17 minutes (spoiler, since it's a famous puzzle that people might want to try on their own).

> 1 and 2 cross, 2 returns with the flashlight, then 5 and 10 cross and 1 returns with the flashlight to collect 2: total time 2+2+10+1+2=17 minutes.

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