# Question
Title: Draw a graph of DFA for a regular language
I'm trying to draw a DFA graph for the regular language where every chain:

```
* consists of symbols from the set {1,a,b}.
* starts with the subchain '1a'.
* includes at least one subchain 'aa'.

```

Output chains: $1aa, 1abaa, 1aaba, 1aaa, 1aaab, 1aab1a, \space ..., \space etc.$

There's no problem with checking the $'1a'$ subchain, but there's a problem with the double repeating action for an $'a'$ terminal in any part of the chain for getting at least one $'aa'$ subchain. The shortest chain here is $'1aa'$ and graph states change from $q\_0$ to $q\_3$ (which will possibly be the DFA's end state). If I draw a $(1,b)$-cycle for the $q\_2$ state, the DFA might come to the end state $q\_3$ on reading the wrong chain like $1aba$. From the other side, my DFA will only allow chains starting from $1aa$ (not $1a$) and that is not correct either.

My attempts leaded to this:

What should I correct here to add "at least one $'aa'$ check" feature? Or offer your version of this DFA graph.

# Answer
$T$ is a 'trap state' $q\_3$ is final accepting state. From state $T$ all inputs $a$, $b$, $1$ will direct to $T$ itself. There's a self loop over state $q\_4$ for inputs $1$ and $b$.
> 1 votes

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


title: Top Down Insertion in a B Tree

text:
# Question
Title: Top Down Insertion in a B Tree
I have a B-Tree of order 5. So the keys are between $\lceil n/2 \rceil- 1 \leq keys \leq n - 1$ and children are between $\lceil n/2 \rceil \leq children \leq n $. Am I doing it right? So a full node would be of 4 keys, how do I split that, because when I split that full node, I get uneven keys in any of the children.

Example: $\\{G\\}$ at level $0$, $\\{A, C, E\\}$ and $\\{H, K, N, Q\\}$ at level $1$

Here $\\{H, K, N, Q\\}$ is a full node, when I insert T, I must pre-split $\\{H, K, N, Q\\}$, I get one key in either of the subtree which is wrong as the selection of keys suggest that they must be between 2 and 4.

What am I doing wrong?

# Answer
> 1 votes
It seems you are doing nothing wrong. Like you say, for a B-tree of order $n$ the number of children is between $\lceil n/2 \rceil$ and $n$, the number of keys is one less. For $n=5$, keys are between $2$ and $4$. When you add a key to a node of size $4$, you get two new nodes of size $2$ and one new key which is pushed upwards. When this happens at the root, a new root with a single key is formed.

Your example. Add $T$ to the tree. At the root $G$ go right, to $\\{H,K,N,Q\\}$. With $T$ this becomes $\\{H,K,N,Q,T\\}$ which is too heavy and we split into $\\{H,K\\}$ and $\\{Q,T\\}$. Middle key $N$ is pushed upwards to the root. In the new configuration the root $\\{G,N\\}$ with two keys has three children $\\{A,C,E\\}$, $\\{H,K\\}$ and $\\{Q,T\\}$.

---
Tags: data-structures, search-trees
---


# Question
Title: Is everything in CS either a numeric method or a symbolic method?
Or maybe also a combination of the two, but not something else, whether numeric, nor symbolic. Do they cover the whole field?

# Answer
> 7 votes
No. You could make a decent argument that every algorithm is in some sense a symbolic manipulation, though not in the sense normally used for symbolic computation - they are not explicitly algebraic, and more naturally find expression as logic and set theory (unsurprisingly). Taking the wider view of symbolic manipulation though, even numerical analysis is just symbolic calculation, it's only at the external semantic level that we recognise it as an approximation of what we actually want to do. The computer is still just pushing bits around.

However Computer Science extends beyond algorithms, even though they are central to CS. It includes complexity, computability, plus practical subfields like networking, machine intelligence, compiler and language design &c. which involve more than just designing algorithms.

Just to pick a few illustrations of this: designing a programming language is not a computation of any sort (the compiler is of course), but it is certainly computer science; the construction of a complexity reduction is not a computation (but the reduction itself is; the choice of processor layout in parallel computing is a choice made by the designer.

---
Tags: terminology, computer-algebra, numerical-algorithms
---


# Question
Title: Is it possible to accurately determine the number of instructions required to multiply or add two integers in a modern processor?
I'm not nearly at the experience level in computer science to be able to properly determine the number of instructions involved in basic ALU calculations, and I'm interested in a certain software concept where the difference is important.

**Multiplication**

---

```
       1011   (this is 11 in decimal)
     x 1110   (this is 14 in decimal)
     ======
       0000   (this is 1011 x 0)
      1011    (this is 1011 x 1, shifted one position to the left)
     1011     (this is 1011 x 1, shifted two positions to the left)
  + 1011      (this is 1011 x 1, shifted three positions to the left)
  =========
   10011010   (this is 154 in decimal)

```

I've been studying the binary multiplier, which seems to calculate **partial products** with binary, and then shifts them to the left, the *very same way that we do* with base-10 multiplication in grade school. It would seem to me that this would require **2 instructions per digit**, but that's merely a barely-educated guess.

**Addition**

I've found Wiki's explanation of an adder-subtractor to be far more advanced, (in description, not operation, surely), and I've had less luck interpreting it thus far.

**Purpose**

My goal is to determine the number of instructions required to compute the addition / multiplication (respectively) of number sets. Basically, I want to figure:

```
5 x 5 = 10 --> 5 instructions //example
5,000,000,001 x 456892 --> 50 instructions //example

1 + 1 = 2 --> 4 instructions //example
1,000,042,569 + 1,491 = 1,000,044,060 --> 45 instructions //example

```

---

**Tl;dr - My Question:**

* Is it possible to accurately determine the number of instructions required to multiply or add two (whole number) integers in a modern processor?
* **If so, how is this figured (in both addition and multiplication, based on the size of the number)?**

# Answer
> 8 votes
Yes and no.

“Instructions” isn't the right unit of measure: most processors include an ALU and require a single instruction to perform addition or multiplication on a number of a certain size (usually 8, 16, 32 or 64 bits, often with several possible sizes). A more relevant measure is the number of clock cycles required by this instruction. Counting instructions only comes into play when talking about bignums.

The number of clock cycles is determined by the depth of the circuit. A signal can traverse many gates in the same clock cycle, but more gates means a longer path which can be a limiting factor when trying to increase the clock frequency. It doesn't depend on the input values, only on the circuit that is being used (of course the values have to fit within the width of the circuit). For example a 32-bit adder will take the same number of cycles to calculate 1 + 1 and 1,000,042,569 + 1,491.

There are many possible designs for an adder or multiplier circuit. One of the design parameters is using more transistors or more complex connections to achieve faster operations. For example, addition the way we usually perform it requires adding the lowest-order bits, then adding their carry to the bits of order 1, and so on: the carry is propagated linearly, which means that the depth of the circuit is proportional to the word size. There are more sophisticated adders which parallelize the additions to reduce the depth.

The depth of the circuit tells you how many clock cycles the arithmetic operation requires inside the ALU. On a typical complex processor, going from there to the time it takes to perform instructions can be very complex, because you need to consider how the ALU fits in the processor. In order to actually add two values, the CPU must do many things:

* Fetch the addition instruction from memory.
* Decode the instruction to find that it is an addition, where its inputs are and where its output is.
* Fetch the inputs — this can take different number of cycles depending on the width of the operation and whether the inputs are immediates, in registers, in memory, etc.
* Make the arithmetic calculation.
* Write the result into the output register or memory.

Most processors are very heavily pipelined: all of these steps are performed in parallel for different instructions. For example, at any given clock cycle, there are typically instructions in various stages of being fetched and decoded, different arithmetic operations in various stages of being carried out, etc. Advanced processors often have multiple ALUs so as to be able to make computations in parallel. For these reasons, the time it takes to perform $N$ successive additions is often not $N$ times the time it takes to perform one addition. Though in practice, the biggest variability comes from memory access — accessing an inner cache is dramatically faster than accessing RAM.

# Answer
> 1 votes
Multiplication is one instruction, in most instruction sets, for 64 or 32 bit integers. You can find reference manuals for various instruction sets by Googling -- look for "MIPS" for a relatively easy-to-understand version.

If you want to multiply integers of arbitrary size (\>64 bits), it gets more complicated. Good algorithms exist.

# Answer
> 1 votes
Yes, one (most of the time).

But that is useless, depending on the instructions before/after this one, the *sequence* of instructions will take wildly varying times on modern CPUs that execute instructions in paralell, execute them out of order, and do other funky rearrangements. Add to that that on modern CPUs an access to RAM can cost the same as *hundreds* of instructions, so previous memory accesses will be crucial (cache effects).

---
Tags: computer-architecture, binary-arithmetic, mathematical-programming
---


# Question
Title: Effective computation on linear data without random access
recently I've started thinking about caching problems in modern CPUs, where they struggle to adequately fetch program data (not instructions) in time, so that it can be computed further.
So then I came up with the idea, why don't we restrict random access on program data and make it all as a continuous stream (input and all eventual locals), which moves strictly in one direction through some "processing head", where you only have a possibility to read in some x amount of symols, write, let through and append symbols at the head position (this is a data stream, not an instruction stream).
The question is, whether you can **effectively** run computations in that system:
Is it possible to order all functions and allocate all local data/variables at compile time in such order that they will produce usable stream of data for all further functions, so that you will never need to "loop" the tape to access some particular element? (thus, emulating random access, by waiting for desired element to come by)
I've tried to look up this topic on the internet and found nothing. And maybe it is because this idea is obviously stupid, so no one bothers with it :)
Thank you for your help!

# Answer
No. Consider an algorithm on a graph (e.g., network flow). It fundamentally requires random access to memory. The restriction you propose would be painful and make many standard algorithms impossible.
> 0 votes

---
Tags: compilers, cpu-cache, cpu-pipelines
---


title: Quicksort implementation unclear

text:
# Question
Title: Quicksort implementation unclear
This code is taken from wikipedia:

```
// left is the index of the leftmost element of the subarray
  // right is the index of the rightmost element of the subarray (inclusive)
  // number of elements in subarray = right-left+1
  function partition(array, left, right, pivotIndex)
     pivotValue := array[pivotIndex]
     swap array[pivotIndex] and array[right]
     storeIndex := left
     for i from left to right - 1
         if array[i] ≤ pivotValue
             swap array[i] and array[storeIndex]
             storeIndex := storeIndex + 1
     swap array[storeIndex] and array[right]  // Move pivot to its final place
     return storeIndex

```

It is not clear for me why it is true, every iteration storeIndex and i index are pointing to the same place as I see it.

Where am I wrong?
Lets Take for example the array 9,8,6,5
1.pivotIndex I chosen is 0, hence pivot value is 9.
2.After first swap out array is : 5,8,6,9 (storeIndex point to 0)
3. entering loop left pointing to 0 index, condition happens that is why we swaping on the same cell.
4. i is incremented and pointing to 1, also store index is 1 and so on.

# Answer
Consider $A = \[5,2,7,6,3,4\]$ and $pivotValue=5$. After pushing $5$ to end we get $A=\[4,2,7,6,3,5\]$. Now when $i=2$, the $storeIndex$ is not changed. Similar is the case for $i=3$. When $i=4$, $A\[4\]$ and $A\[storeIndex\]$ get swapped. Note that $storeIndex=2$. So we get $A=\[4,2,3,6,7,5\]$. You can think $storeIndex$ as a 'marker'. After each iteration of $for$ loop, all values upto 'marker' index are smaller than $pivotValue$.
> 0 votes

---
Tags: algorithms, sorting, quicksort
---


# Question
Title: For a flow network, is it possible to show that there always exists a maximum flow which would assign integer values to all the edges?
Is it possible to prove that for a flow network, there always exists a maximum flow which assigns an integer value to every edge?

# Answer
If edges have real valued capacities, there may not exist a maximum flow which assigns an integer value to every edge. For example consider a single edged $s-t$ network with $c(s,t)=0.1$ where $c$ is capacity function. However if edges have integer valued capacity, there exists a maximum flow which assigns integer value to every edge because in each iteration of ford-fulkerson algorithm, each edge in residual graph is assigned an integer value. So the result is an integer.
> 3 votes

---
Tags: graphs, network-flow
---


# Question
Title: Set of $\mathsf{NP}$-hard languages closed under set inclusion?
As the title says, my question is whether the set of $\mathsf{NP}$-hard languages is closed under set inclusion, i.e. whether for any $\mathsf{NP}$-hard language $L$, all subsets of $L$ are also $\mathsf{NP}$-hard. This question is related since $\emptyset$ is not $\mathsf{NP}$-hard as there is nothing we could map "yes"-instances to and $\emptyset \subseteq L$ for all $\mathsf{NP}$-hard $L$.

However, what about non-trivial subsets, i.e. languages $L'$ of the form $\emptyset \neq L' \subsetneq L$ for $\mathsf{NP}$-hard $L$? We know that $\emptyset \neq 2SAT \subsetneq SAT$ and while $SAT$ is $\mathsf{NP}$-hard, $2SAT$ is in $\mathsf{P}$. This suggests to me that whether the set of $\mathsf{NP}$-hard is closed under "non-trivial" inclusions depends on whether $\mathsf{P} = \mathsf{NP}$. Am I mistaken here?

In one sentence, my question is this: is the set of $\mathsf{NP}$-hard languages closed under nontrivial set inclusion (1) assuming $\mathsf{P} = \mathsf{NP}$ and (2) assuming $\mathsf{P} \neq \mathsf{NP}$?

# Answer
> 4 votes
Indeed, if NP=P then every nontrivial problem is NP-hard, and in particular every nontrivial subset of an NP-hard problem (thus closing it to inclusion).

---
Tags: complexity-theory, np-hard, closure-properties
---


# Question
Title: Access control matrices: who are the subjects: users or processes?
I'm studying the basics of security in computers. The doubt I have is that the access control matrix is presented as a matrix whose rows are the subjects and the columns are the objects. Also subjects are defined both in Windows and Unix (and Multics for that matter) as processes, threads, not users, but processes.

My question is why then, when I check the Windows ACLs, I get the permissions that each user has instead of the permissions that each process under each user has.

It seems to me that more than a matrix a cube is needed, because the subject permissions, i.e. the processes permissions, are bound to the identity of the user logged in.

From what I've read it seems ambiguous: in some cases subjects are processes, and in others subjects are user accounts. Which one is the correct form?

# Answer
Short answer: both.

My answer is based on knowledge of Unix, but as far as I know the same principle applies to Multics and Windows.

Runtime permission checks are performed by the kernel in system calls (such as the call to open a file). They are based on a matrix where the subjects are processes — the kernel determines the content of the cell for the calling process and for the object under concern (e.g. the file whose opening is requested).

The row for each process in that matrix is computed from data that is stored in a kernel data structure for that process. It is inherited from parent process to child process, all the way from login time. At login time, this data is initialized from the user database; it includes the information of which user the process is running as.

A file's access control list is stored on disk (if the file is a disk file). It could not reference processes: these have a too short lifetime — on a reboot, not information about processes would be meaningful. In access control lists stored on the filesystem, the subjects are users (and groups).

You can draw a cube, but that cube doesn't correspond to anything tangible in the operating system design. The user/object matrix corresponds to file ACLs, and the process/object matrix corresponds to runtime checks in the kernel.
> 1 votes

---
Tags: operating-systems, security, access-control
---


# Question
Title: Simplest argument that language decidable in constant time cannot be $\mathsf{NP}$-hard?
My question is specifically about $\emptyset$, but more generally about any language that can be decided in (deterministic or nondeterministic doesn't really make a difference here) constant time. Obviously, $\emptyset$ cannot be $\mathsf{NP}$-hard since there is nothing to map "yes"-instances to, but I'd prefer a one line argument using a time hierarchy theorem, ideally. Currently I'm arguing (very informally speaking) that since constant time is $\subsetneq \mathbb{o}(n \log n)$, constant time is strictly "less powerful" than any deterministic polynomial time due to the deterministic time hierarchy theorem and thus - since $$\mathsf{Polytime}(f(n)) \subseteq \mathsf{NPolytime}(f(n))$$ - also strictly less powerful than nondeterministic polynomial time. So, constant time languages can't be $\mathsf{NP}$-hard.

This doesn't sound elegant to me at all (although it should be correct I hope, even if not phrased as formally as I'd write it down for something to hand in). What's the most elegant argument you can come up with, preferably using not-too-advanced complexity theory?

# Answer
> 5 votes
Let $L \in P$ be non-trivial (not empty and not containing everything). If $L$ is NP-hard then $P=NP$. Indeed, given any language $L' \in NP$, by definition of NP-hardness there is a polytime reduction $f$ such that $x \in L'$ iff $f(x) \in L$. Since $L \in P$, this gives a polytime algorithm for $L'$, showing that $L' \in P$.

Conversely, if $P=NP$ then $L$ is NP-hard. Indeed, given $L' \in NP$, we can decide $L'$ in polynomial time using some algorithm $A$. Fix some yes instance and some no instance of $L$, and use $A$ to come up with a polytime reduction from $L'$ to $L$, which always returns one of the two fixed instances. This shows that $L$ is NP-hard.

Summarizing, if $L \in P$ is non-trivial then $L$ is NP-hard iff $P=NP$.

---
Tags: complexity-theory, np-hard, constant-time
---


title: KMP Algorithm Example

text:
# Question
Title: KMP Algorithm Example
I'm studying KMP algorithm and I'm stuck on an example.

Suppose my text is "I am queen." and my pattern is "q".

The sp table will have only **one** value, **q** and it's **sp index** will be **0**. Mismatch will occur at the very first index.

According to the formula: **i - ( spi-1 \+ 1)** ; the right shift will be **0**.

And so the algorithm will get stuck and move nowhere.

What am I doing wrong?

# Answer
> 1 votes
The formula for shifting is **i - spi \+ 1** if you start indexing from 0 and **i - spi** if you start indexing from 1.

---
Tags: algorithms, strings
---


title: Time cost of thread creation

text:
# Question
Title: Time cost of thread creation
While creating an algorithm, the following question came up:

> In uniform cost, what is the time cost of a process that creates a thread?

Is there a difference between creating a thread in a thread pool vs creating a thread in runtime?

I know these questions should be self-explanatory, but I cannot seem to find an answer.

# Answer
> 2 votes
The cost of thread creation is constant but large on most real systems. (Think approximately the same cost as doing 1000 function calls of a function that does nothing but return a small constant. On most systems it requires a call into the kernel, which is pretty expensive.)

The point of a thread pool is to try to amortize this large constant cost over multiple thread creation/destruction requests. A thread pool is an abstraction that caches threads that are currently not in use, thus can be allocated relatively quickly instead of going through the enormous cost of creating a new thread. A typical thread pool might work as follows:

* starts out empty
* if a request is made for a thread from the pool and the pool is currently empty, then create a new thread and return it to the requester.
* if a request is made to "exit" a thread, then instead of really shutting the thread down you insert a pointer to the thread into the thread pool and put the thread to sleep.
* if a request is made for a thread from the pool and the pool contains a sleeping thread, then wake the thread up, give it the requested work, and return the pointer to the thread to the requester.

# Answer
> 2 votes
Every model of computation has a supported list of instructions, each associated with its time complexity. Thread handling is not a basic instruction in any model I'm aware of, but probably for practitioners of parallel computation, it is. The time complexity really depends on your viewpoint. If you're interested in optimizing the inner working of the operating system, then thread creation is not a basic operation at all, and its cost is associated with the algorithms implementing it. If you're interested in parallel computation, then probably thread creation is a primitive operation of unit cost. It all depends on the context.

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


title: Session Memory in the Windows Kernel

text:
# Question
Title: Session Memory in the Windows Kernel
While reading the paper Effective Data-Race Detection for the Kernel by John Erickson and Madanlal Musuvathi. I was stuck on a slightly tricky sentence.

"Similarly, a range of kernel-address space, called session memory, is mapped to different address spaces based on the session the process belongs to. When a sampled access lies in the session memory space, DataCollider sets a data breakpoint but checks if the conflicting accesses belong to the same session before reporting the conflict to the user."

I can not figure out in practice what the session memory is at process level. Is the session related to the user owning the process? Or is it something more specific of the Kernel?

I know that I am probably missing something important but this is not basically my field of study so, although I tried, I couldn't find substantial answers. Is there someone who can explain me briefly what I am missing?

Cheers

# Answer
> 5 votes
I *think* that what is going on here is this.

In most operating systems, including Windows, there are lots of data structures inside the kernel that the kernel "shares" between all the processes running on the machine. In early versions of Win32 (starting maybe with Windows 95?) there are some kernel data structures, specifically those having to do with the graphics device interface (GDI)) that are shared by all the processes that are using the same desktop. In early versions of the OS there was only one desktop, so only one session, so these data structures were just shared like all the others. In the Server versions of Windows each remote login gets a "terminal" which, I think, is sort of a virtual desktop. So now they needed to "virtualize" those GDI data structures inside the kernel that weren't previously virtualized. I think that a "session" is that set of virtualized GDI datastructures. They are shared by all processes running on the same "terminal", and each "terminal" has its own version of the data structures.

The reason this matters in the DataCollider paper you referenced is that they are using data breakpoints, which are set on virtual addresses rather than physical addresses. But race detection (in the kernel) really makes more sense from the physical address perspective. For most kernel data structures there is a one-to-one mapping from virtual addresses to physical addresses. You set a data-breakpoint on a particular virtual address and when it "fires" you know that the *physical* address corresponding to that virtual address is still the same. All processes, from all users, from all "terminals" are really sharing those data structures, and if there is a race, there is a race.

The problem, for DataCollider is that in "session memory" this one-to-one mapping doesn't hold. In the case of session memory the *virtual* addresses are the same for every process, but the *physical* address that virtual address is mapped to is different when the kernel is working on behalf of processes from different terminals. So when the data breakpoint fires you need to do some extra bookkeeping to figure out whether the virtual address is pointing to the same physical address that you intended when you set the breakpoint.

---
Tags: concurrency, memory-management, os-kernel
---


# Question
Title: Why can I look at a graph and immediately find the closest point to another point, but it takes me O(n) time through programming?
Let me clarify:

Given a scatterplot of some given number of points n, if I want to find the closest point to any point in the plot mentally, I can immediately ignore most points in the graph, narrowing my choices down to some small, constant number of points nearby.

Yet, in programming, given a set of points n, in order to find the closest point to any one, it requires checking every other point, which is ${\cal O}(n)$ time.

I am guessing that the visual sight of a graph is likely the equivalent of some data structure I am incapable of understanding; because with programming, by converting the points to a more structured method such as a quadtree, one can find the closest points to $k$ points in $n$ in $k\cdot\log(n)$ time, or ammortized ${\cal O}(\log n)$ time.

But there is still no known ${\cal O}(1)$ ammortized algorithms (that I can find) for point-finding after data restructuring.

So why does this appear to be possible with mere visual inspection?

# Answer
Your model of what you do mentally is incorrect. In fact, you operate in two steps:

1. Eliminate all points that are too far, in $O(1)$ time.
2. Measure the $m$ points that are about as close, in $\Theta(m)$ time.

If you've played games like pétanque (bowls) or curling, this should be familiar — you don't need to examine the objects that are very far from the target, but you may need to measure the closest contenders.

To illustrate this point, which green dot is closest to the red dot? (Only by a little over 1 pixel, but there is one that's closest.) To make things easier, the dots have even been color-coded by distance.

This picture contains $m=10$ points which are nearly on a circle, and $n \gg 10$ green points in total. Step 1 lets you eliminate all but about $m$ points, but step 2 requires checking each of the $m$ points. There is no a priori bound for $m$.

A physical observation lets you shrink the problem size from the whole set of $n$ points to a restricted candidate set of $m$ points. This step is not a computation step as commonly understood, because it is based on a continuous process. Continuous processes are not subject to the usual intuitions about computational complexity and in particular to asymptotic analysis.

Now, you may ask, why can't a continuous process completely solve the problem? How does it come to these $m$ points, why can't we refine the process to get $m=1$?

The answer is that I cheated a bit: I presented a set of points which is generated to consists of $m$ almost-closest points and $n-m$ points which are further. In general, determining which points lie within a precise boundary requires a precise observation which has to be performed point by point. A coarse process of elimination lets you exclude many obvious non-candidates, but merely deciding which candidates are left requires enumerating them.

You can model this system in a discrete, computational world. Assume that the points are represented in a data structure that sorts them into cells on a grid, i.e. the point $(x,y)$ is stored in a list for the cell $(\lfloor x \rfloor, \lfloor y \rfloor)$. If you're looking for the points that are closest to $(x\_0, y\_0)$ and the cell that contains this point contains at most one other point, then it is sufficient to check the containing cell and the 8 neighboring cells. The total number of points in these 9 cells is $m$. This model respects some key properties of the human model:

* $m$ is potentially unbounded — a degenerate worse case of e.g. points lying almost on a circle is always possible.
* The practical efficiency depends on having selected a scale that matches the data (e.g. you'll save nothing if your dots are on a piece of paper and your cells are 1 km wide).
> 123 votes

# Answer
The reason is that the data has been put in a "data structure" optimized for this query and that the preprocessing time in preparing the graph should be included in your measured times which is proportional to the number of dots, giving a O(n) complexity right there.

If you put the coordinates in a table listing X and Y coordinates of each point you would require a much larger mental effort to calculate the distances between points, sort the list of distances and choose the smallest.

As an example of a query not working well visually, would be to look at the night sky and - based on your view only and a table of coordinates of each star - locate the closest star to Earth or which astrological sign has the smallest distance between the stars it consists of. Here you would need a zoomable and turnable 3D model in order to determine this visually, where a computer would consider this to be essentially the same problem as your original.
> 46 votes

# Answer
This question starts from a faulty premise. You just think you can mentally find the nearest point in $O(1)$ point, but in fact, if you can't. It feels like that because you're used to dealing with very small graphs, but small examples can be misleading, when we're dealing with asymptotic complexity. If you tried to do this with a scatter plot with one billion points, you'd quickly discover that you can't do it in $O(1)$ time.
> 23 votes

# Answer
1. **The computer is solving a different problem.** It takes a *list* of points, not a rasterized image of points. Converting from a list to an image, i.e. "plotting" the points, takes `O(n)` time.

Quick! Which is closest to (1,2):

* (9, 9)
    * (5, 2)
    * (3,-2)
    * (4, 3)
    * (0, 4)
    * (1, 9)

A lot harder, right? I bet if I made the list twice as long you'd have to do twice as much work.
2. **You're not aware of how much work your brain is doing.** You don't "just know" which point is closer. Your brain is doing computational work to figure out that answer and make it available. The brain works on each point in parallel, so the time to finish stays roughly the same, but the amount of required work still increases with the number of points.
> 17 votes

# Answer
The superiority of the visual inspection hinges on crucial premises which cannot be guaranteed in general:

* *scaling*: You focus on the graphical representation of the area of interest. this means, the geometry has been scaled down to fit into your field of vision. in the general setting this already requires $O(n)$ time for preprocessing.
* *count*: (cf. comment of Nick Alger on the answer given by D.W.) assume a point count exceeding the number of your retinal cells - you will not even identify all points involved.
* *variance*: (cf. comment of Nick Alger on the answer given by D.W.) assume a set of points on a regular (e.g. hexagonal) grid being subjected to small random perturbations. if these perturbations become less than the resolution of your retina (or any other overlaid grid), you will not only be hard-pressed to detect the actual minimum distance but pick the wrong pairs of points with a high probability.

assuming that the mental processes involve some rasterization of a geometrical representation (vs. let's say a distance matrix), these processes do not scale arbitrarily with the size of the problem instance. put in different terms, for a general setting, a preprocessing sampling procedure would be required running in $O(n)$. in human visual inspection, the parameters of this preprocessing are hardwired in the perception apparatus (number of retinal cells, retinal area) which makes this processing stage appear to be $O(1)$.
> 16 votes

# Answer
For the same reason when you look at a triangle and know it is a triangle you are forgetting the many millions of calculations you do without noticing it.

# Neural networks

In effect you are a neural network that has been trained and loaded with masses upon masses of data.

Take the infant shape sorting game as an example:

When a child first interacts with this it is likely they will attempt to insert shapes into the wrong holes, this is because they have not yet trained their brain or encountered enough data to build networks. They can't make assumptions about edges, size, .etc to determine which shape fits the hole.

This seems obvious to you (I hope) because you have built these connections, you may even think it is intuitive and not have to break it down, for example you just know the triangle fits the triangle and don't need to approximate the size, count the edges, .etc. This is not true, you have done all that in your subconscious, the only conscious thought you had was that it is a triangle. Many millions of computations happened from taking a visual representation, understanding what it was representing, understanding what the individual elements are and then estimating their distances, the fact that you had a large database of information to poll against made this simpler.

# Your brain isn't binary

The data your brain works on isn't binary (As far as we know), isn't true or false, it holds many states that we use to interpret the data, we also get things wrong often, even when we follow the correct process, this is because the data changes often. I would hazard a guess that our brains function a lot more like a quantum computer would where the bits are in an approximate state until read. That is, if our brain works like a computer at all, it really is not known.

Hence an algorithm for working with binary data will not work the same. You can't compare the two. In your head you are using concepts to perform, rich data types that hold far more information, you have the ability to craft links where they are not explicitly defined; upon seeing a triangle you may think of Pink Floyd's Dark side of the moon cover.

Back to the scatter graph, there is no reason you couldn't do this on a computer using a bitmap and measuring the distance from a point in increasing radii until you encountered another point. It is possibly the closest you could get to a human's approximation. It is likely to be much slower because of the data limitation and because our brains don't necessarily care about computation complexity and take a complex route to do things.

It wouldn't be O(1), or even O(n) if n is the number of points, instead its complexity now depends on the maximum linear distance from the point selected to a bound of the image.

# tl;dr

Your brain is not a binary computer.

---
> 13 votes

# Answer
you are forgetting one important step: **plotting all those points** on the graph you are looking at.

this is by necessity a O(n) operation.

after this a computer can use image recognition software to find the approximate points closest to the center in much the same way the human eye can. This is a O(sizeOfImage) operation worst case.

for a human to do the same as the computer remember that the computer gets a list of coordinates and can only look at one at the time.
> 8 votes

# Answer
**My interpretation of the question:**

*I do not believe this question is to be taken simplistically as a a computational geometry complexity issue. It should be better understood as saying: we perceive an ability to find the answer in constant time, when we can. What explains this perception, and up to this explanation and to human limitations, can a computer do as well.*

Thus the question should probably be seen first as **a question for a psychologist**. The issue is probably related to your perception of time and effort. Can you brain really perceive a difference between $O(1)$ time and $O(log( n))$ time? Specific counter examples do not really matter, as in issues of perception we tend to think instinctively of average cost (complexity being probably to precise a concept psychologically). More accurately, we are more interested in the common case, than in special cases when we feel we cannot readily answer the question.

This may be reinforced by the Weber-Fechner laws, that states that our perception is to be measured on a logarithmic scale of the actual physical measure. In other words, we perceive relative variations rather than absolute variations. This is for example why sound intensity is measured in decibels.

If you apply this to the perception of the time we use to find the closest point, this is no longer $O(log (n))$ but $O\_\psi(log (log (n)))$, where $O\_\psi$ is my *just invented* Landau notation for "*psychological complexity*".

Actually I am cheating, because the psychological perception of the scatterplot graph size also obeys the logarithmic law, which should compensate in this simple complexity relation. Still, it means that a scatterplot will alsways seem much simpler to us than it really is, especially for very large ones. But whatever the size we perceive, if we have a built-in logarithmic algorithm to find a closest point (such as neuronal quadtrees), then the perceived processing time is to be mesured by $O\_\psi(log (log (n)))$ which for all practical purposes is probably perceptually undistinguishable from a constant, and ther is necessarily some constant time added to it to start the recognition process and acknowledge the result.

**Taking into account the physiological limitations**

The above conclusion is further sustained when considering the image acquisition steps.

The OP was careful to separate the construction of a proper data structure, "such as a quadtree", which is amortized on several queries.

This does not work for most people who do not memorize the image. I think the image is scanned for each query, but that does not imply scanning all points: not the first time, and not for later queries.

**The eyes scans a raster image, in constant time** $T\_{scan}$, idenpendently of the size of the scene taken in, and **with a fixed resolution** defined by the retina structure (see below). Thus it gets a constant amount of information, possibly not distinguishing all points. It can then focus on the relevant part of the image, to distinguish relevant points in another time $T\_{scan}$, plus possibly the time to change the orientation and focus of the eye. Theoretically, this operation could have to be repeated, leading to logarithmic focussing, but I believe that in perceptual practice, there is at most one additional step for focussing vision.

Scanning probably results in a structure in the brain that can be analyzed to find the answer. It may still contain a very large number of points. Though I do not know how the brain proceeds, It is not unreasonable to think that it is some kind of focussing process that takes *at worst logarithmic time, possibly even less*. This process is applied to the perceived image, that has a bounded size. This implies of course a bounded number of points, though it can be quite large. Thus there is a fixed upperbound $m$ to the information to be processed. Assuming logarithmic processing, and reusing the above analysis, the perceived processing time is $O\_\psi(log (log (m)))$.

The resolution of the human eye is fixed by the number of rods, which is about 125 millions. That is about $2^{27}$. Using base 2 for the logs, that gives for the processing an upperbound of about $log\_2(27)$, i.e. about 5 steps of whatever cost there is for a step. Using instead the estimated value of the eye resolution which is on the order of 500 megapixels does not change the final result.

Without knowing the actual units to be used, this simply shows that the variation for processing is at worst on the same order as other constant time operations. Hence, it is quite natural that the perceived time for finding the closest point feels constant . . . whether we determine the closest point or only a set of the closer points.

**About counter-examples and a possible solution**

It is of course easy to build counter-examples that make eyes determination of the closest point very difficult among a small collection of the closer points. This is why the OP is actually asking for an algorithm that eliminate quickly most of the points, except for the closest ones. This issue of the possible difficulty of chosing among several close points is adressed in many answers, with the paradigmatic example of closest points being almost on a circle around the reference point. Typically the Weber-Fechner laws precludes being able to distinguish small distance variations over long enough distances. This effect may actually be increased by the presence of other points which, though eliminated, may distort the perception of distances. So trying to identify the closest point will be a harder task, and may well require specific examination steps, such as using instruments, that will completely destroy the feeling of constant time. But it seems clearly outside the range of experiments considered by the OP, hence not very relevant.

**The question to answer**, which is the question actually asked by the OP, is whether there is a way to eliminate most of the points, except possibly for the remaining few which seem to have very similar distances to the reference point.

Following our analysis of what may be hidden behind a perceived constant time, a computer solution that does it in $O(log(n))$ time could be considered satisfactory. On the other hand, relying on amortized cost should not really be acceptable, since the brain does not do it that way, afaik.

Rejecting amortized cost does not allow for a computer solution, since all points have to be looked at. This underscores a major difference in the computing power of the brain and of human perception: it can use **analog computation with properties that are quite different from digital computation**. This is typically the case when billions of points are not distinguishable by the eye, which does not have the resolution to see anything but a big cloud with various shades of dark. But the eye can then focus on relevant smaller part, and see a bounded number of points, containing the relevant ones. It does not have to know of all points individually. For a computer to do the same, you would have to give it a similar sensor, rather than the precise numerical coordinates of each point. It is a very different problem.

**"Mere visual inspection" is in some respects a lot more powerful than digital computation.** And it is due also to the physics of sensors, not just to a possibly greater computing power of the brain.
> 7 votes

# Answer
We had students in exams who, when asked how fast you can sort an array, would claim that computers are stupid, and need n\*log(n) (or worse), while humans can do it faster.

The reply of my professor was always: I will give a list of 10.000 items. Let's see if you can come up with a method that is faster than what a computer would do.

And then: how many processing cores are involved when you try to find the closest point? You are not a single-processor machine, you have a neural network, that has some flexibility when it comes to tasks like this.
> 4 votes

# Answer
I believe @Patrick87 gave you the clue: your eyes and brain are a massively parallel computing machine. Some argued that this does not explain the issue, because for arbitrarily large problems a finite number of parallel processors makes no difference.

But it does here: as hinted by many, your eyes (and brain) have a limited capacity to solve this problem; and this is because one cannot fit any number of points within the span of a normal human gaze. Your eyes need to be able to distinguish them for a start, and if there are too many, then they will be so close than your eyes won't notice the difference. Bottom line: it is fast for well enough points that fit in your normal sight, i.e. very few. In other cases it will fail.

So, you can solve this problem in O(1) for small and simple cases that your brain can process in a breeze. Beyond that, it can't and therefore, it is not even O(*anything*) because it most likely fails.
> 3 votes

# Answer
Nobody has mentioned that this problem can be solved very quickly on a computer with a spatial index. This is the equivalent of plotting out the points in an image for your eyes to scan quickly and eliminate most of the points.

There is a very good indexing algorithm used by Google and others to find the nearest point(s) called a Geohash. http://en.wikipedia.org/wiki/Geohash.

I think that this will even up the contest in favour of the computer. I was not impressed with some of the answers that used linear thinking.
> 1 votes

# Answer
If we consider the case of finding a nearest neighbours in a point set of n-dimensions in Euclidean space, the complexity is typically bounded by the number of dimensions as it grows large (i.e. larger than the size of the dataset).

P. Agrawal in a survey on range searching lists a few logarithmic solutions for the problem. However, as dimension grows large, the complexity of a query is then $O(\log^{d-2} n)$. We do not consider the time to read the data or build the data structure but only the time to query it.

The problem of finding a closest point to a node in a graph has a Euclidean expression whenever the graph can be embedded into Euclidean space with a distortion small enough. And using a adjacency list with weights, we still need to build the adjacency list.

Now your question effectively has a psychological aspect. The closest answer that has been studied is the "neural network" gestaltist perspective on the subject. If you build a neural network that can recognize the closest point to an element, if all the neurons of the network run in parallel, as is usual, then you effectively have an $O(1)$ complexity. If our brain effectively functions "like" a neural network, then this may explain why we have the impression of a "gestalt".
> 1 votes

# Answer
other answers are good but how about a zen counter question that stretches the basic reasoning/premise of the original question to extremes to show some faultiness \[but is also the paradox at the core of AI research\]:

> if I can think with human intelligence, why cant I create a computer that thinks as well as a human?

there are multiple ways to answer your question, but basically, our thought processes and brain perceptual capabilities are not necessarily accessible to introspection, and the introspection we do apply to them can be misleading. for example we can recognize objects but we have no way to perceive/explain the quasi-algorithmic process that goes on to allow this. also there are many psychology experiments that show there are subtle distortions in our perceptions of reality and in particular time perception, see eg time perception.

it is generally thought/conjectured by scientists that the human brain does in fact employ *algorithms* but they function differently than computerized ones, and also there is a very large amount of *parallel processing* going on in the brain via *neural networks* that cannot be compared sensibly to *sequential* computer algorithms. in mammals, a significant percentage of the entire brain volume is dedicated to visual processing.

in other words human brains are in many ways highly optimized visual computers, and they do in fact in many ways have a capability that exceeds the worlds greatest supercomputers currently, such as in object recognition etcetera, and that is due to deficiencies (in comparison) in human-constructed software/hardware in comparison to biology that has been highly tuned/evolved/optimized over millions of years.
> -1 votes

# Answer
Generally speaking you are solving two different problems and if you compete in the same competition, complexity will be O(1) for both of you. Why? Let's make situation a bit simpler - assume that you have a line with one red point and n green points. Your task is to find green point which is closest to red point. Everything is on the graph. Now what you do and what you program is doing is basically the same - just "walk away"(in both directions) from red point and check whether the pixel you are looking at is white/black(background) or green. Now the complexity is O(1).

What's interesting is that some data presentation methods gives answers to some questions immediately(O(1)). Basic example is extremely simple - just count white pixels on black image(each pixel value is 0 = black or 1 = white). What you need to do is just add all pixels values - complexity is the same for 1 white pixel and for 1000, but it depends on image size - O(m), m=image.width\*image.height. Is it possible to do it faster? Of course, all we need to do is use different method of storing images which is integral image: Now calculating the result is O(1) (if you have integral image already calculated). Another way is just store all white pixels in array/vector/list/... and just count it size - O(1).
> -2 votes

---
Tags: algorithms, computer-vs-human, human-computing
---


# Question
Title: Showing that a Particular Word Problem is Decidable
I need to give an algorithm to show that the word problem in the group $\langle x,y \mid \mid x^{1984} = y^{2014} = 1 \rangle$ is decidable. How do I show this? I'm not too sure where to start.

# Answer
> 3 votes
Hint: Come up with a normal form for words in this group.

---
Tags: algorithms, computability, logic
---


title: Are Lie theoretic codes impractical?

text:
# Question
Title: Are Lie theoretic codes impractical?
I have been recently studying Lie theory. I discovered that there is a family of Lie theoretic error correcting codes. I did not find any information except this paper:

So, my question is: why isn't there a further development of this research? Are these codes considered inefficient or impractical?

# Answer
There are zillions of papers in coding theory, proposing zillions of codes. Most of them are not used, due to several reasons:

1. Some of the codes are non-constructive.
2. Some of the codes don't have efficient decoding procedures.
3. Some of the codes have bad parameters.

The main reason, however, is that practitioners don't spend their time reading the coding theory literature and thinking up applications of the various codes. Rather, given a concrete problem, they first look up the "standard" solutions they know of. I'm putting "standard" in quotes since different people probably use different types of codes — whatever they are used to. There are many reasons for this:

1. Known codes are the easier to find out about — they are already familiar.
2. Code (and sometimes hardware) is already available.
3. Bosses prefer using known and proven tools.
4. Practitioners are often interested in properties which are either hard to prove or are simply not completely formal, but could be tested experimentally (for example, recovery from burst errors). These are found in their own literature rather than the theoretical coding theory literature.

If none of the standard codes seem to work, then they are in trouble and probably ask an expert. The expert probably knows some other standard codes which do work.

For a new code or type of code to reach the mainstream requires a lot of publicity to make the community aware of it. Mathematicians working in coding theory don't usually care about the practical side, and indeed, often their constructions have theoretical aims which are not important in practice (this is especially common for researchers in theoretical computer science). Even if a particular code is practical, the researcher is usually not interested enough in promoting it for it to become widely known among the practitioners.

Engineers, on the other hand, might publish new practical codes, and rarely one of them does change the mainstream paradigm. Most papers are, however, small variations on known techniques, and are important mostly for people's resumes, or for the particular project they were developed for.

In your particular case, the paper you are linking to is theoretical, and ignores one of the main questions in coding theory, namely how to efficiently decode. This shows that it's a theoretical paper. The motivation behind the paper is to construct *orthogonal codes* with good parameters. It mentions that orthogonal codes have applications in mathematics, but not necessarily in "real life". Furthermore, as you mention, the construction seems novel, which makes it more interesting mathematically. Practically speaking, the novelty is not as important as the "usability" of the code in terms of parameters and ease of encoding and decoding, an issue not mentioned at all.
> 8 votes

---
Tags: coding-theory
---


# Question
Title: What is the name of this prime number algorithm?
Does the following recursive algorithm have a name? If so, what is it?

```
procedure main():
 myFilter = new Filter( myPrime = 2 ) //first prime number
 print 2 //since it would not otherwise be printed
 for each n in 3 to MAX:
  if myFilter.isPrime(n):
   print n

object Filter:
 integer myPrime
 PrimeFilter nextFilter = NULL

 procedure isPrime(integer n):
  if n is multiple of myPrime:
   return FALSE
  else if nextFilter is not NULL:
   return nextFilter.isPrime(n)
  else
   nextFilter = new PrimeFilter(myPrime = n)
   return TRUE

```

Sample implementation in Java here

This is similar to the Sieve of Eratosthenes though after some discussion in the CS chat, we decided that it is subtly different.

# Answer
> 9 votes
O'Neil \[1\] call this the "unfaithful sieve". It's much slower than the sieve of Eratosthenes.

For each prime $p$ you do work $\sim p/\log p$ and so the total number of divisions up to $x$ is roughly $x^2/(2\log^2 x)$ if you assume composites are free. (That's essentially true: they take at most $2\sqrt x/\log x$ divisions each for a total of at most $2x^{3/2}/\log x$ divisions.)

Divisions take longer than unit time, so the total bit complexity is about $O(x^2\log\log x/\log x)$.

\[1\] Melissa E. O’Neill, The Genuine Sieve of Eratosthenes

# Answer
> 4 votes
Let me rephrase your algorithm (starting at a different base case):

```
Initialize P to be the empty list.
for n from 2 to MAX:
  if no integer in P divides n:
    add n to P
return P

```

Let $p\_1,p\_2,\ldots $ be an enumeration of the primes. The probability that $p\_1,\ldots,p\_i$ do not divide a number $n$ is roughly $$ \prod\_{j=1}^i \left(1 - \frac{1}{p\_j}\right) \approx e^{-\sum\_{j=1}^i p\_j} \approx e^{-\sum\_{j=1}^i j\log j} \approx e^{-\frac{1}{2} i^2 \log i}.$$ Therefore the inner loop runs for roughly this many iterations: $$ \sum\_{i=1}^\infty e^{-\frac{1}{2} i^2\log i} = O(1). $$ In total, the complexity is $O(n)$ divisions. In contrast, the Eratosthenes sieve requires $O(n\log\log n)$ additions.

For a fair comparison, we also need to factor it the computational complexity of operations on large numbers. Assuming that division can be done in time $O(m\log m)$ (which is the conjectured running time), where in our case $m = \log n$, your algorithm has bit complexity $O(n\log n\log\log n)$, matching the bit complexity of the sieve. However, the best known division algorithms are somewhat slower, both asymptotically and in practice, and so I expect your algorithm to be somewhat slower than the sieve.

Atkin's sieve uses only $O(n/\log\log n)$ additions and so is faster than both your algorithm and the Eratosthenes sieve. It also uses only $\tilde{O}(\sqrt{n})$ memory, compared to your $\sum\_{p\_i \leq n} \log p\_i \approx \sum\_{m=1}^{n/\log n} \log(m\log m) = \Theta(n)$, also shared by the Eratosthenes sieve.

---
Tags: algorithms, reference-request, primes
---


# Question
Title: Finding a set of maximally different solutions using linear programming or other optimization technique
Traditionally, linear programming is used to find the one optimal solution to a set of constraints, variables and a goal (all described as linear relationships). Sometimes, when the objective is parallel to a constraint, there are infinite or many equally good optimal solutions. I am not asking about this latter case.

I am more interested in finding many solutions that are in the feasible region generated by my set of constraints. But I would like the solutions I find to be 'scattered' around the feasible region in the sense that they are maximally far from one another. Is there a known way to, without running a solver multiple times, generate multiple solutions and use the objective function to enforce that the solutions should be separated?

For example, any linear program with decisions a and b and constraints w \<= a \<= x and y \<= b \<= z can be 'duplicated' to find two solutions. Our new linear program has variables a1, a2, b1, and b2 and the constraints w \<= a1 \<= x and w \<= a2 \<= x and similar for b1, b2. However, when it comes to forming an objective function we run into trouble as we can not use norms other than the L1-norm without discarding linearity and we can not truly even use the L1 norm because it is not possible (so far as I know) to encode absolute values.

Perhaps I should look into convex optimization or semidefinite programming or something?

Is there a known way to generate a set of solutions to a linear program, and using an objective that enforces "distance" between the solutions?

# Answer
## A heuristic, using linear programming

One approach might be to pick a random objective function, and maximize it. Then repeat, with a different set of objective functions each time.

In other words, suppose the unknowns are $x\_1,x\_2,\dots,x\_n$, and you have some constraints $\mathcal{C}$. In each iteration you pick $c\_1,c\_2,\dots,c\_n \in \mathbb{R}$ randomly, then search for a solution that maximizes $c\_1 x\_1 + \dots + c\_n x\_n$ subject to the constraints $\mathcal{C}$.

I would expect this heuristic might often find a somewhat scattered set of solutions -- not necessarily maximally scattered (maximally far from each other), but probably not too close to each other, either.

## Maximizing the average pairwise L2 distance, using quadratic programming

Alternatively, use quadratic programming. For simplicity, let's look at the problem of finding two solutions. Suppose you want two solutions $x,y$ that are as far apart from each other as possible, under the $L\_2$ norm (Euclidean distance). Then this can be formulated as a quadratic programming problem.

Basically, you want to maximize the squared distance $d(x,y)^2 = (x\_1-y\_1)^2+\cdots+(x\_n-y\_n)^2$ between $x$ and $y$, subject to the requirement that both $x$ and $y$ must satisfy the constraints. This is the problem of maximizing a quadratic objective function, with linear constraints -- i.e., quadratic programming.

If you want $k$ points that are maximally scattered, this is also possible. Say the points are $x^1,\dots,x^k \in \mathbb{R}^n$. Then you could maximize the objective function

$$\sum\_{i\<j} d(x^i,x^j)^2,$$

i.e., the function

$$\sum\_{i\<j} \sum\_\ell (x^i\_\ell - x^j\_\ell)^2.$$

This is a quadratic function, and you have linear constraints $\mathcal{C}$ on each of the points $x^i$, so this is a quadratic programming instance. It finds you points that are maximally scattered in the sense that the average pairwise distance is maximized.

You can also formulate a greedy variant of this algorithm, where you already have $k$ solutions, and you want to find a $k+1$th solution that satisfies all the linear inequalities and also maximizes the average L2 distance from it to the other $k$ solutions. That too can be formulated as a quadratic programming problem.

Quadratic programming is harder than linear programming, but there are off-the-self solvers that will solve quadratic programming problems for you.

## Maximizing the minimal pairwise L2 distance, using QCQP

Finally, let's say you want your $k$ points to be scattered in the sense that you want to maximize the minimum pairwise distance. In other words, let's say you want to find the largest possible threshold $t$ such that it is possible to find $k$ points $x^1,\dots,x^k \in \mathbb{R}^n$ that each satisfy the linear constraints, and such that each pair of points is at distance $t$ away from each other: $d(x^i,x^j) \ge t$ for all $i\<j$. Then this can be formulated as a quadratic optimization program with quadratic constraints, i.e., QCQP. QCQP is even harder, but there are off-the-shelf solvers for QCQP you could try out, too.
> 2 votes

# Answer
I found an approach to generating absolute values.

Suppose we have the variables $a\_1$, $a\_2$, $b\_1$ and $b\_2$ and a bunch of constraints. Our objective functions looks something like: maximize $|a\_1 - a\_2| + |b\_1 - b\_2|$; the idea being we want to maximize the L1 norm of these two solutions (as per the original question).

We can introduce "slack variables" abs\_a and abs\_b and the constraints:

$$\mathrm{abs\_a} + a\_1 - a\_2 \leq 0$$

$$\mathrm{abs\_a} - a\_1 + a\_2 \leq 0$$

and similarly for $b\_1$ and $b\_2$. These constraints force $\mathrm{abs\_a}$ to be at most the difference between $a\_1$ and $a\_2$, and possibly less. In other words $\mathrm{abs\_a}$ can not be larger than the maximum difference between $a\_1$ and $a\_2$.

Then what is left is replace the objective function: maximize $\mathrm{abs\_a} + \mathrm{abs\_b}$.
> 1 votes

---
Tags: optimization, linear-programming
---


# Question
Title: Understanding an algorithm for the gas station problem
In the *gas station problem* we are given $n$ cities $\\{ 0, \ldots, n-1 \\}$ and roads between them. Each road has length and each city defines price of the fuel. One unit of road costs one unit of fuel. Our goal is to go from a source to a destination in the cheapest possible way. Our tank is limited by some value.

I try to understand the algorithm, so I manually wrote down steps to calculate the solution. Unfortunately I got stuck - at some point there are no edges to consider, I don't know why, maybe I'm missing something.

**Example:**
road:
0 ----------- 1 ------------ 2 -------------- 3
*(it doesn't have to be that simple, it could be any graph i.e. there could be roads between 0-\>2, 0-\>3, 1-\>3 etc.)*

Source: 0, Destination: 3, Tank: 10 units
Fuel prices: **0**: 10 units, **1**: 10 units, **2**: 20 units, **3**: 12 units
Lengths: **0-\>1**: 9 units, **1-\>2**: 1 unit, **2-\>3**: 7 units
*Optimal solution:* fill 9 units at 0 and 8 units at 1. Total cost then is 170 units (9 * 10 + 8 * 10).

So I tried to calculate it as shown here (paragraph 2.2)

```
GV[u] is defined as:
GV[u] = { TankCapacity - length[w][u] | w in Cities and fuelPrice[w] < fuelPrice[v] and length[w][u] <= TankCapacity } U {0}

so in my case:
GV[0] = {0}
GV[1] = {0}
GV[2] = {0, 3, 9}
GV[3] = {0}

D(u,g) - minimum cost to get from u to t starting with g units of fuel in tank:
D(t,0) = 0, otherwise:
D(u,g) = min (foreach length[u][v] <= TankCapacity)
         {
           D(v,0) + (length[u][v] - g) * fuelPrice[u]                             : if  fuelPrice[v] <= fuelPrice[u] and g <= length[u][v]
           D(v, TankCapacity - length[u][v]) + (TankCapacity - g) * fuelPrice[u]  : if  fuelPrice[v] > fuelPrice[u]
         }

so in my case:
D(0,0) = min { D(1,0) + 9*10 }  - D(0,0) should contain minimum cost from 0->3
D(1,0) = min { D(2,9) + 10*10 } - in OPT we should tank here only 8 units :(
D(2,9) = min { ??? - no edges which follows the condition from the reccurence

Nevertheless D(0,0) = 90 + 100 + smth, so it's already too much.

To achieve the optimal solution algorithm should calculate D(2,7) because the optimal route is:
(0,0) -> (1,0) -> (2, 7) -> (3, 0) [(v, g): v - city, g - fuel in tank].
If we look at G[2] there is no "7", so algorithm doesn't even assume to calculate D(2,7),
so how can it return optimal solutions?

```

Recurrence from the document doesn't seem to work or what's more likely I do something wrong.

Could anybody help me with this?

# Answer
The problem is in the condition for the first argument to `min()` in Equation (4) on p. 7. It's currently

```
c(v) <= c(u) and g < d[u][v]

```

but it should be

```
(c(v) <= c(u) or v = t) and g < d[u][v]

```

to force arrival at t to have no gas left. (Just as with my explanation below for the bug in Fill-Row(u, q), we are *never* interested in the cost of gas at t. And as with there, another way to fix the problem would be to overwrite c(t) with 0 at the start of the algorithm.)

Fixing this mistake (in the published algorithm), combined with adding in the missing edges as I describe below (your mistake :-P), should be enough to get everything working.

---

One thing you're missing is that the graph G must be *complete* (first sentence of section 2, p. 4) -- and if it's not complete, any missing edges must be added, with the weights found by taking minimum path lengths in the graph. So e.g. in your example graph, there should be (among others) an edge from 1 to 3 with weight 8 (corresponding to the path via 2), so that in fact GV\[3\] = { 0, 2 }.

I'm not sure whether that will completely solve the problem for you, but it should help.

Separately, I think there's a bug in the Fill-Row(u, q) algorithm on p. 6: this algorithm should treat the case q=1 specially, but it doesn't. I believe it could be fixed by changing

```
if c(v) <= c(u)

```

on line 3 to

```
if c(v) <= c(u) or q = 1

```

to force any final leg to arrive at the destination empty. (Intuitively, we should always disregard the price of gas at the final destination, t.) Another way around this would be to overwrite c(t) with 0 at the outset.
> 8 votes

# Answer
Using @j\_random\_hacker solution we need to transform our graph to a complete graph and change the condition from equation (4) to:

```
(c(v) <= c(u) or v = t) and g < d[u][v]

```

Complete graph should look like this:

and final calculations:

```
GV[0] = {0}, GV[1] = {0}, GV[2] = {0, 3, 9}, GV[3] = {0, 2}

D(0,0) = min { D(1,0) + 9 * 10 }
D(1,0) = min { D(2,9) + 10 * 10, D(3,0) + 8*10 }
D(3,0) = 0
... etc

so D(0,0) = 170

```

Path through 0 -\> 1 -\> 3 \[total cost 170$\] is the solution. That's what we expected :-). If we need a route, then we should be able to transform those extra edges from the solution to the given edges at the beginning (it shouldn't be very difficulty).

I only wonder how we should avoid deadloops in this recurrence. For example there can be deadloop between 0 \<-\> 1 , because c(0) \<= c(1) and c(1) \<= c(0).
> 2 votes

# Answer
The idea is to get the fuel as required in cheapest rate wherever you get (greedy algorithm paradigm)

Take some examples. in your example

Source: 0, Destination: 3, Tank: 10 units Fuel prices: 0: 10 units, 1: 10 units, 2: 20 units, 3: 12 units Lengths: 0-\>1: 9 units, 1-\>2: 1 unit, 2-\>3: 7 units

I have to travel 9 units at first, so I need to fill up my tank at 0 with \>= 9 units (capacity \>= 9). Now, I can see at 1,2,3 the fuel rate is \>= fuel rate at 0. As, I want to buy my needed fuel in cheapest rate I'll try to fill up 9+1+7=17 units at city 0 only. But, the capacity of tank might be \< 17, say 10. So, I will fill up till 10. Then at 1 I have 1 units fuel left and I have to traverse 8 units more, so at 1 I'll fill up 7 units more. I can't fill up at 2 because the rate would be higher. My, total cost = 10\*10+7\*10 =170.

The greedy algorithm follows the idea mentioned above. $C\_i$ fuel cost at city i. $d\_{ij}$ distance between two cities $i$ and $j$. "full" is unit of fuel with which tank is filled up. "capacity" is max tank capacity.

i) full = 0

ii) for $i=0$ to $n-1$, let $l$ be the first city after $i$ such that $C\_i \> C\_l$ (if no such $l$ exists then $l=n-1$). $d\_l$= more\_distance\_need\_to\_travel\_till\_city\_$l$ = $\sum\_{k=i+1}^l d\_{k,k+1}$. Buy $\min${$d\_l - $ full, capacity} unit fuel at city $i$. full = $\min${$d\_l - $ full, capacity}. Set $i=l$.
> 1 votes

---
Tags: algorithms, graphs, recurrence-relation
---


# Question
Title: LR(0) parsing: how can I know sets of items corresponding to states?
I'm studying LR(0) parser. But I don't understand how sets of items corresponding to states can be calculated. I think The author would miss some information readers must know. Given the following LR(0) automaton, How the set of items corresponding to I1, I2, I3, ... , and I11 can be calculated?

In addition, is closure of item sets related to with calculating them? If so, what exactly every item in I1, I2, ... , and I11 is?

# Answer
An item is a rule with dot marker in it. Think of the dot marker as what you've seen so far and what you are hoping to see in the future. Itemsets are sets of items. In the diagram above they are the boxes with all the items (nodes in the graph). The *kernel* (or *core*) of an itemset are the rules that are in white. Those items are given to us (rule 1) in CLOSURE from a different part of the table building algorithm. Taking closure of all the kernel items gives you the full itemset and includes non-kernel items (the darker ones in your diagram). The CLOSURE(*I*) operation is this expansion algorithm.

Take *I7* for example. We start with only one kernel item.

```
T -> T * . F

```

Step 2 of CLOSURE is saying that since *F* is in front of the dot we have to expand it, adding those items to the itemset. Hence, we add items the following items.

```
F -> . ( E )
F -> . id

```

This is everything that F can expand to. So the full itemset is now:

```
T -> T * . F
F -> . ( E )
F -> . id

```

We reapply rule (2), but see that the . is not in front of any new non-terminals that we haven't expanded, we are done. The itemset is now *closed*.

The other half of the parse table building algorithm generates new itemsets. This involves moving the dot across each symbol of each item. For example, moving the dot over the 'F' gives you the itemset with the kernel item below.

```
T- > T * F .

```

This is *I10* in your diagram. Note, that edges from *I7* to *I10* is labeled *F* (since the dot crossed that symbol). You'd reapply the same closure algorithm here and loop this process.

See the Wikipedia entry on this for more information.
> 2 votes

---
Tags: context-free, parsers
---


# Question
Title: Construct grammar given the following language
**Construct grammar given the following language!**

$ L = \\{(ab)^{n+1}u(ba)^n|n\>0, l\_c(u) = 1, u\in\\{a,c,d\\}^\* \\}$

My interpretation in a less accurate way:

1. $(ab)^{n+1}$ says we need to concatenate $(ab)$ at leat one time with itself (since $n \> 0$)
2. $u$ represents one word from the set of $\\{a,c,d\\}^\*$, (except the words, that contain the letter $c$ more than once). The set $\\{a,c,d\\}^\*$ is equivalent to $\bigcup \limits \_{i=0}^\infty \\{a,c,d\\}^i$
3. $(ba)^n$ means we need to use $(ba)$ at least once.

My soloution for the rules so far:

$S\to abA$
$A\to abB|abA$
$B\to aB|dB|c|cC$
$C\to baD$
$D\to baD|ε$

Notations:

* $S$ - start variable
* $ε$ - null string, end of the word
* $l\_c(u)$ - the exact numbers of $c$'s in $u$

I'm having difficulties figuring out the rule(s) for the part $l\_c(u) = 1$. I need clarification on my interpretation of the given $L$ language and thoughs how to construct the rule(s) for the part $l\_c(u) = 1$.
In addition, I'm a bit unconfortable on this field, so there might be other issues too.

# Answer
> 1 votes
Your grammar is wrong. Note that your grammar can generate the word $(ab)^3c$ which is clearly not in $L$. (More over, you don't handle the request of the number of $ab$ and $ba$. a word in $L$ must have at least $(ab)^2$ as prefix and $ba$ as suffix (as $n\>0$).

Note that we could write $L$ in the following way:

$L=\left \\{ (ab)^{n+1} xcy(ba)^n | n\>0, x,y \in \left \\{ a ,d \right \\} ^\* \right \\} $

A grammar for this language:

$S \rightarrow ababAba$

$A \rightarrow abAba \\, | \\, B$

$B \rightarrow DCD $

$C \rightarrow c$

$D \rightarrow aD \\, |\\, dD \\, |\\, \epsilon$

The grammar works as follow: First, using the first and second rules we generate $(ab)^{n+1}A(ba)^n$ for $n\>0$ . Then we replace $A$ with $B$. $C$ is responsible to generate $c$ (and by that promising that $l\_c = 1$ , and $D$ generates the language $\left \\{ a ,d \right \\} ^\*$

---
Tags: formal-languages, formal-grammars
---


# Question
Title: A variant of the set cover problem: Is that a known problem?
Can this problem be solved in poly time?

> **Input:** $S\_i \subset \\{1,\cdots,n\\}$ for $i=1,\cdots, n$.
>
> **Question:** Is it possible to select an $a\_i \in S\_i$ for each $i=1,\cdots,n$, such that $\\{a\_1,\cdots,a\_n\\}=\\{1,\cdots,n\\}$?

Informally, the problem asks for selecting one element from each subset $S\_i$ such that the selected elements cover the set $\\{1, \cdots, n\\}$.

# Answer
Hint: Form a bipartite graph which has the sets $S\_1,\ldots,S\_n$ on one side and the numbers $1,\ldots,n$ on the other. Connect $S\_i$ to $a$ if $S\_i$ contains $a$. You are looking for a perfect matching in this graph.
> 2 votes

---
Tags: algorithms, complexity-theory, decision-problem, polynomial-time
---


# Question
Title: Why are dependently typed languages such as Agda used for proofs, if supercompilers for simpler typed languages can do the same?
Proof assistants such as Agda can be used to assert properties about programs, such as "the double of a number is even". Interestingly, supercompilers can be used for the same purpose, creating typeless proofs. Even more interestingly, macro tree transducers can, too. My question is: what is the relationship between those? What does a dependently typed language have that makes it more powerful than other type systems as far as theorem proving goes, considering proofs can be done without types?

# Answer
I think you're confusing two things: dependently typed languages are convenient for **specifying** properties and **giving proofs** about functional programs. The techniques you mention are possible **decision procedures** for certain properties of functional programs.

The ability to specify program properties usually takes place within a *logic*. Dependent types are a kind of logic, when viewed through the propositions-as-types lens. The nice thing about this logic is that it is naturally suited to talk about functional programs, which also can be used as a proof language. But there are other logics as well capable of doing this, and some are not based on dependent types.

Supercompilation type proofs are essentially a way to prove that two functions are *observationally equal* i.e. send identical inputs to outputs. But the fact that a supercompiled function $\mathrm{S}(f)$ is observationally equal to $f$ is not obvious: it has to be *proven*. Usually this is done with pen and paper, but of course Agda could be used for such a purpose.

Some things to note:

1. Agda is sufficiently powerful to prove (almost) all the program equivalences you could be interested in. The drawback is that you have to *supply* the proof yourself.
2. The things that can be proven automatically using SC or transducers are nice, but they only cover a tiny percent of what people want to prove about their functional programs. In particular, these techniques will fail with any slightly complex property (say, always returning a prime number) and even expressing the desired property may be hard (e.g. always returning a prime number).
3. There are a number of decision procedures for functional programs which are well-studied and offer similar or additional power as the techniques you mention. In particular ACL2 has been around for quite some time and is (I hear) quite powerful for these kinds of things.
4. *In theory*, we could integrate these kinds of procedures to help the user produce a proof in a system like Agda or Coq. There are a number of technical and social reasons for which this hasn't happened yet. There's still hope though! Note also that Coq has a fair number of automated techniques already.
> 10 votes

---
Tags: type-theory, functional-programming, dependent-types, proof-assistants
---


# Question
Title: Computational complexity vs. Chomsky hierarchy
I'm wondering about the relationship between computational complexity and the Chomsky hierarchy, in general.

In particular, if I know that some problem is NP-complete, does it follow that the *language* of that problem is not context-free?

For example, the clique problem is NP-complete. Does it follow that the language corresponding to models with cliques is of some minimal complexity in the Chomsky hierarchy (for all/some ways of encoding models as strings?)

# Answer
There are four classes of language in the Chomsky hierarchy:

1. Regular languages — this class is the same as $\mathrm{TIME}(n)$ or $\mathrm{TIME}(o(n\log n))$ (defined using single-tape machines, see Emil's comment), or $\mathrm{SPACE}(0)$ or $\mathrm{SPACE}(o(\log\log n))$ (per Emil's comment).
2. Context-free languages — this class doesn't have nice closure properties, so instead one usually considers $\mathrm{LOGCFL}$, the class of languages logspace-reducible to context-free languages. It is known that $\mathrm{LOGCFL}$ lies in $\mathrm{AC}^1$ (and so, in particular, in $\mathrm{P}$), and it has nice complete problems detailed in the linked article.
3. Context-sensitive languages — this class corresponds to $\mathrm{NSPACE}(n)$.
4. Unrestricted grammars — this class consists of all recursively enumerable languages.

If a language in NP-complete then assuming P$\neq$NP, it is not context-free. However, it could be context-sensitive (clique and SAT both are). Any language in NP is described by some unrestricted grammar.
> 11 votes

---
Tags: complexity-theory, formal-languages
---


title: Partition area using test function

text:
# Question
Title: Partition area using test function
I am looking for an efficient algorithm that can partition an area $B \subset \mathbb{R}^2$ into disjoint subsets $B = \bigoplus\_i U\_i$ such that a test function is constant on each of the subsets, $f \vert\_{U\_i} = \mathrm{const.}$

For example, consider the following partitioning:

The indicated numbers are the return values of the test function in each cell. I want to recover the partitioning, given area error bounds, with the least number of function calls.

My current approach uses a recursive grid-based method that tests at each vertex of an intial $n \times n$ grid. If not all vertices of a grid cell have the same function value, the cell is subdivided and the process repeats. This needs many subdivisions, and the initial grid must be "fine enough".

I am curious if a specialized approach exists, and if there is a common name for this problem.

# Answer
The discrete version of your problem has a close resemblance with the classical Clustering problem. In Clustering given a finite set of points you have to divide the set such that points belong to a partition (cluster) iff they have similar properties.

We consider the continuous version, i.e, your problem. Let $2\epsilon \< 1$ is error bound. And, we have a bounding box of size $n\*n$ which we would like to partition based on functional values.

We divide the bounding box into $n/\epsilon\*n/\epsilon$ grid cells, each cell has $\epsilon$ length side. Here we apply bottom up approach where the consecutive cells having same functional values are merged together. The partitioning algorithm is as follows.

i) For each grid cell $c$, compute function values in its four corner points. Let $x$ be the function value occurring most frequently among those four values (in case of tie choose one arbitrarily). Assign $x$ as a label to $c$.

ii) Start with the left and topmost grid cell. Iterate over cells from top to bottom and in a single row from left to right. In each cell $c$ if the cell on left and above (if exists) have same labels add $c$ to the cluster (partition) correspond to those cells (merging). Else if one of the left or above cell has same label add $c$ to the cluster (partition) of that cell. Otherwise start a new cluster with $c$.

You can see that the error may occur in boundary regions (between two partitions) of the partitioning and the merging procedure will give correct partitions. But, as the boundary consists of $\epsilon$ side length boxes the error is within tolerance limit.

Time complexity is $O((\frac{n}{\epsilon})^2)$.
> 1 votes

# Answer
As stated, this problem is not solvable. Your problem is analogous to: "given the sequence 1,3,5,7,9, what is the next number in the sequence?" The answer that puzzle is: "without further information, it could be anything (you can always find a degree-5 polynomial that will make the answer anything you want)".

You have not given us any restrictions on the test function, nor have you given us any regularity conditions on it. If we don't know anything about it, then as j\_random\_hacker says, your problem is not solvable: if you query the test function $n$ times and construct a partitioning that is consistent with the responses from the test function, an adversary can always come up with a $n+1$th query and a response to that query that demonstrates that your partitioning is wrong. Thus, no finite number of queries ever suffices, if you don't narrow down the set or structure of possible test functions in some way.

To make this solvable, you need some structure on the set of possible test functions: say, that test functions are known to be convex, or something.
> 0 votes

---
Tags: algorithms, computational-geometry, partitions
---


# Question
Title: Quickly pruning edges below average weight for a membership-based weighting
I have points represented as sparse high-dimensional binary vectors, or put another way, I have a list of groups that each point belongs to. For two points, the edge weight between them is $\sum\_i 1/|B\_i|$ where $|B\_i|$ is the number of points that belong to group $i$, and the summation is over all shared groups that both points belong to.

My distribution on group size is very skewed where there are a few large groups that contain about 5 million points and many small groups that contain 2-10 points. Each point belongs to about 5 groups on average and there are roughly a million groups. Also there are roughly 10 million points total. The goal is to identify all edges that have weight above some pretty high threshold, e.g. the mean edge weight.

Currently the best algorithm I have in hand is to check all pairs of points within each group and compute the edge weight between them. However there are groups that give rise to on the order of $10^{13}$ pairs, which is too high. I was thinking of maybe going through groups from smallest to largest and somehow eliminating a lot of pairs to check once the larger groups are reached, since after all the overall edge weight has to be above a pretty high threshold. But I'm not 100% sure how to formalize that, or whether it would really help. Any help would be greatly appreciated, either advice on how to make my pruning idea effective, or even completely fresh ways to approach the problem.

# Answer
> 2 votes
Yes, we can make your idea work. I'll show how below, and prove that it is correct (it does not miss any edges).

The first step will be to sort the groups by decreasing size. Say their sizes are $s\_1 \ge s\_2 \ge s\_3 \ge \dots$. Say $t$ is your threshold. Find the smallest $k$ such that

$$1/s\_1 + 1/s\_2 + \dots + 1/s\_k \ge t.$$

**Lemma.** No edge can have weight above the threshold $t$ based only upon membership in groups $1,2,\dots,k-1$. In other words, every edge with above-threshold weight must be in at least one of the groups $k,k+1,k+2,\dots$.

This observation lets you apply your idea, to optimize the performance of the algorithm.

**Algorithm.** Sort the groups by decreasing size and find $k$, as above. For each of groups $k,k+1,k+2,\dots$, look at all pairs of points within the same group, and compute the edge weight of each such edge. Output the ones whose edge weight is above the threshold $t$.

This algorithm can be proven to output all above-threshold edges, thanks to the lemma above.

---
Tags: algorithms, heuristics
---


title: How to show that FPATH is in NL?

text:
# Question
Title: How to show that FPATH is in NL?
Consider this problem:

$\qquad\displaystyle \mathsf{FPATH} = \\{\langle G, a\_1,\dots,a\_n\rangle \mid G \text{ is a digraph with directed path } (a\_1,\dots,a\_n)\\}$

It's allowed to visit nodes outside the sequence, but a1 must be visited before a2 and so on.

I am having big trouble trying to show that this language is NL-complete. I have tried finding an algorithm for a TM that decides this problem in NSPACE(log n), but I can't seem to find a good solution. I know that PATH is NL-complete, so I guess I can use that fact. My problem is finding an algorithm that somehow has to know that is has been through the sequence $a\_1$ to $a\_n$, but how can I do this when the worktape only can use $\log n$ space?

# Answer
> 0 votes
Turning my comment into an answer for the question in the title, the Immerman-Szelepcsényi Theorem says that NL = coNL. This means it's enough to show that FPATH is in coNL. For that, observe that the path $a\_1,a\_2,\ldots, a\_n$ is not in $G$ if and only if some edge $a\_ia\_{i+1}$ is not present. Since you just need to guess $i$, that's all you need to write down.

---
Tags: algorithms, complexity-theory, space-complexity
---


title: Fast Consequence FInders

text:
# Question
Title: Fast Consequence FInders
I have been struggling in the search for a modern fast "consequence finder". That is, an implementation based on state-of-the-art theory; things of the ilk of Z3, Prover9, OTTER, etc.

To describe what I mean by "consequence finding" (and please correct my term usage if it's inappropriate):

Given a satisfiable and consistent set of clauses C, where a clause is a finite disjuction of literals, wherever there is some atom $p$ in some clause $\phi = p \lor \alpha$ and $\lnot p$ in some clause $\psi = \lnot p \lor \beta$, we add the new clause $\alpha \lor \beta$ to C (provided it cannot already be found in C). This is what I understand as the process of performing Resolution.

Assuming we generate all possible new clauses from C, contintually adding generated clauses, and trying to find new clauses again, we will have C'.

As a very small example, on the input:

$(\lnot p \lor q) \land (p \lor r)$

$(\lnot p \lor q) \land (p \lor r) \land (q \lor r)$ would be the output.

If we now remove subsumed clauses from C', i.e. clauses which are of the form $\alpha \lor \beta$ where there exists some other clause of the form $\alpha$, then we have a set of clauses C''.

I want C''. I was under the impression that there would be tools like those mentioned to generate this set since C'' is essentially what would remain when having performed vanilla resolution on a satisfiable set of clauses.

# Answer
> 2 votes
Updated answer, based upon the revised question:

It sounds like resolution does exactly what you want, so I suggest you implement the resolution algorithm (combined with a subsumption test). Implementing this is a straightforward programming exercise which should take you only a few hours.

---

Original answer to an earlier version of the question:

I don't know if there are any dedicated solvers aimed at solving this problem, but one "poor man's approach" might be to implement this using an off-the-shelf SAT solver. The approach will depend on what you are looking for: in particular, from what space consequences are allowed to come from.

## A useful building block

Let me first observe that you can use a SAT solver to determine whether a candidate clause is indeed a consequence or not. This will be a useful building block below.

Suppose $\varphi(x)$ is a formula, on boolean variables $x=(x\_1,\dots,x\_n)$. Let $c(x)$ be a clause. You can easily use a SAT solver to test whether $c(x)$ is a consequence of $\varphi(x)$. In particular, you test whether $\varphi(x) \land \neg c(x)$ is satisfiable; if it is satisfiable, $c(x)$ is not a consequence, otherwise $c(x)$ is a consequence.

## Finding consequences that are conjunctions of literals

If you want each consequence to be a conjunction of literals, you can find the minimal consequence using a SAT solver. In particular, it suffices to use dumb search. Focus on clauses that contain a single literal; there are only $2n$ possibilities for them. Test each of them to see which ones are consequences (if any); this requires $2n$ invocations of the SAT solver. In other words, for each variable $x\_i$, test whether $x\_i$ is a consequence, and also test whether $\neg x\_i$ is a consequence.

Now you have a bunch of consequences, say the literals $\ell\_1,\dots,\ell\_m$. Then $\ell\_1 \land \dots \land \ell\_m$ is also a consequence -- and it turns out it is *the* minimal consequence (minimal, among the space of conjunctions of literals). This procedure requires $O(n)$ invocations of the SAT solver, so it should be pretty efficient.

## Finding consequences that are disjunctions of literals

If you want to consequences to be disjunctions of literals, it's also possible to find all minimal consequences (minimal, among the set of disjunctions of literals), though it is somewhat more complex. Let me build up the ideas step-by-step:

* *Finding a single consequence.* You can use a SAT solver to find a single consequence of $\varphi(x)$ (not necessarily a minimal consequence). Feed $\neg \varphi(x)$ to the SAT solver, and let it find a satisfying assignment, say $x=\alpha$. Then from this it is possible to identify a consequence (not necessarily minimal) of $\varphi(x)$. In particular, the clause $x\ne \alpha$ is a consequence of $\varphi(x)$. To put it another way, consider the clause $c(x) = \ell\_1 \lor \dots \lor \ell\_n$, where $\ell\_i$ is either $x\_i$ or $\neg x\_i$ according to whether $\alpha\_i$ is false or true; then $c(x)$ is a consequence of $\varphi(x)$. This is a somewhat trivial and boring consequence, but it is a valid one.
* *Finding a minimal consequence.* Once you have a single consequence $c(x)= \ell\_1 \lor \dots \lor \ell\_n$, it is now possible to to minimize it. In particular, we will look for a minimal subset $S \subseteq \\{1,2,\dots,n\\}$ such that $c\_I(x) = \lor\_{i \in I} \ell\_i$ is a consequence of $\varphi(x)$. How do we do that? We can simply try removing one literal at a time from $c(x)$ (removing one index at a time from the set $I$), testing at each step whether the result remains a valid consequence. If removing a literal from the disjunction leaves it a valid consequence, go ahead and remove that literal; if after removal, it is no longer a valid consequence, then don't remove it. Each test requires a single invocation to the SAT solver, so this procedure requires $n$ invocations of the SAT solver. When you are done, you have a single minimal consequence $c\_1(x)$ of $\varphi(x)$.
* *Finding another consequence.* Next, I will show to find a second consequence. Let me explain using an example. Suppose that $c^1(x) = x\_1 \lor \neg x\_3 \lor x\_7$ (say), and suppose we know that $c^1(x)$ is a minimal consequence: no literal can be removed from this disjunction while keeping it a consequence. We want to find a second minimal consequence $c^2(x)$ that is a disjunction of literals. What can we say about the set of literals that appear in $c^2(x)$? Well, either $c^2(x)$ does not contain the literal $x\_1$, or it does not contain the literal $\neg x\_3$, or it does not contain the literal $x\_7$ (otherwise it would be a consequence of $c^1(x)$, i.e., subsumed, and thus not minimal).

So let's search for some consequence that satisfies these constraints. One way to do this is to search for a satisfying assignment to $\neg \varphi(x) \land (\neg x\_1 \lor x\_3 \lor \neg x\_7)$, by feeding this to a SAT solver. Suppose the SAT solver gives us a satisfying assignment $x=\alpha$. Then this immediately suggests a consequence that is not subsumed by $c\_1(x)$, namely, the clause $x\ne \alpha$ (expressed as a disjunction of literals). If we want, we can minimize this consequence to get a minimal consequence $c^2(x)$. By construction, $c^2(x)$ will be minimal and different from $c^1(x)$. This gives us a way to find two minimal consequences.
* *Finding all minimal consequences.* Now it should be clear how to find all minimal consequences. Suppose we have found $c^1(x),\dots,c^k(x)$, each of which is a minimal consequence of $\varphi(x)$, where $c^j(x) = \lor\_i \ell^j\_i$. We define the formula

$$\neg \varphi(x) \land (\lor\_i \neg \ell^1\_i) \land \cdots \land (\lor\_i \neg \ell^k\_i).$$

Feed this formula to a SAT solver. If it is unsatisfiable, you are done: you have found all minimal consequences. Otherwise, suppose it finds a satisfying assignment, say $x=\alpha$. Then this immediately supplies a new consequence, which you can then minimize as above, to get a new minimal consequence $c^{k+1}(x)$. Now you can iterate until there are no more to be found.

The running time for this algorithm is best expressed in an output-sensitive measure. If there are $m$ minimal consequence clauses, then this algorithm will complete after making $O(mn)$ queries to the SAT solver. It might even be somewhat efficient, if you use a SAT solver that allows you to make multiple related queries and that remembers state across those queries.

## Finding consequences that are in CNF form

Now suppose you want to allow consequences to be any CNF formula, and you want consequences that are minimal among the set of such consequences. Then the problem becomes trivial.

In particular, $\varphi(x)$ is a trivial consequence of $\varphi(x)$, and it is possible to show that it is a minimal consequence: any other formula that has the same or more satisfying assignments is subsumed by it, and any formula that has fewer satisfying assignments is not a consequence.

## A comment on resolution and on formulating problem statements

Resolution is just a means to an end, not an end goal in itself. Resolution is one technique that is used in some SAT solvers, but SAT solvers also use other techniques as well -- and that combination of techniques is important. What we've seen in practice is that current SAT solvers perform a lot better than vanilla resolution on many problems.

Therefore, my advice to you is to articulate the problem statement clearly, and try to keep clear in your mind the distinction between the goal (the problem statement) vs the way you'll achieve the goal (the algorithm you use). Formulate the goal in a way that describes what you want to achieve, not how you want it to be achieved. Once you articulate your goal clearly, you might find that resolution is not the optimal method.

---
Tags: optimization, sat-solvers
---


title: How to logarithmic interpolation?

text:
# Question
Title: How to logarithmic interpolation?
I'm trying to interpolate a logarithmic function but it always reaches a singularity due to $\log(0)$ being $-\infty$

is there a correct way to interpolate logarithmic functions? (as in correct parameters)

What i'm currently going for is

$y=a+b \log(cx)$

with initial values

$a=0$, $b=1$, $c=0$

# Answer
The general fitting formula for pretty much any function is $F(x)=a\*x+b$

so if you have a function inside a function it would be $F(G(x))=a\*G(c\*x+d)+b$ by virtue of substitution.

You made a tiny error. Instead of $y=a+b \log(cx)$ you probably want $y=a+b \log(cx + d)$

try to fit your function again. a multiplier should never equal to zero, because that would imply you don't have a function of $x$.
> 0 votes

---
Tags: numerical-analysis
---


# Question
Title: Multiple production rules for expressions of the same type?
I often see syntax like

```
expression = term | expression, "+" , term;
term       = factor | term, "*" , factor;
factor     = constant | variable | "(" , expression , ")";
variable   = "x" | "y" | "z";

```

You see, all the rules produce an arithmetic value. Each can replace the other. Why not just declare

```
aexpr = var | num | (expr + expr) | expr * expr;

```

?

Certainly I need different production for expression of different type

```
statements = "if (" bexpr ") body | "while (" bexpr ")" body | a_variable "=" aexpr
bexpr = (bexpr "|" bexpr) | bexpr "&" bexpr | aexpr ">" aexpr

```

Here, I introduce a new production rule (a line per rule) only when I get a new type of expression and see no reason to split them.

I just started to generate random sentences and see that expressions are naturally grouped according their result type (e.g. arithmetic and boolean are different) and that is all. If you need an arithmetic expression, you draw (rewrite) it from arigthmetic pool, if boolean form the boolean pool. Why to split the pools into further groups?

# Answer
In one word - ambiguity.

Sometime you don't want your grammar to be ambiugous.

For example, for parsing. Ambigous grammar can't have a $LR(K)$ grammar (you can think of ambiguity as non determinism). $LR(K)$ parser handle determinstic grammars.

Example for the ambiguity of your grammar:

The sentence a * b + c can be derived in two different ways.
> 2 votes

---
Tags: formal-grammars
---


# Question
Title: is there a sorting algorithm of order $\log n!$
Is there any sorting algorithm that takes order of $\log n!$ in the worst case? I know that this is the lower bound for sorting algorithms using comparison based sorting. I know that there are algorithms of order $n\log n$, but since $n!$ grows much slower than $n^n$, I wish to know of there is any algorithm of this order.

# Answer
By Stirling's approximation, $$\log(n!) = n\log n - n + O(\log n) = \Theta(n\log n)\\,,$$ so, yes, there are lots of sorting algorithms that run in time $O(\log(n!))$.
> 7 votes

---
Tags: algorithms, reference-request, sorting
---