# Question
Title: Need a practical solution for creating pattern database(5-5-5) for 15-Puzzle
I have asked this exact question on StackOverflow. I did not get the answer that I was looking for. Please read this question fully before answering. Thank You.
For static pattern database(5-5-5), see this(page 290 and 283) OR there is an explanation below. For What is 15-puzzle?
I am creating a static patter database(5-5-5). This code to to fill entries into the first table. I am doing it via the recursive function `insertInDB()`. The first input to the recursive function is this (actually the input puzzle contains it in 1-D array. For better understanding I have represented it as 2-D below)

---

1 2 3 4
0 6 0 0
0 0 0 0
0 0 0 0

---

This is my code :

```
class DBClass
{
    public Connection connection;
     public ResultSet rs;
      public PreparedStatement ps1;
    public PreparedStatement ps2;
    public int k;
      String read_statement,insert_statement;

    public DBClass()
    {
        try {
            Class.forName("com.mysql.jdbc.Driver");
        } catch (ClassNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
            try {
                connection = DriverManager
                    .getConnection("jdbc:mysql://localhost/feedback?"
                        + "user=ashwin&password=ashwin&autoReconnect=true&useUnicode=true&characterEncoding=utf8&validationQuery=Select 1");
                insert_statement="insert into staticpdb1(hash,permutation,cost) values(?,?,?)";
                read_statement="select SQL_NO_CACHE * from staticpdb1 where hash=? and permutation= ? LIMIT 1";
                 ps1=connection.prepareStatement(read_statement, ResultSet.TYPE_SCROLL_SENSITIVE,
                            ResultSet.CONCUR_UPDATABLE);
                ps2=connection.prepareStatement(insert_statement);
                k=0;
            } catch (SQLException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
    }
    public int updateIfNecessary(FifteenPuzzle sub)
       {
           String str=sub.toDBString();
           try
           {

               ps1.setInt(1, sub.hashcode());
               ps1.setString(2,str);
               rs=ps1.executeQuery();
           if(rs.next())
              {
                  //if a row exists, check if the cost is greater than sub's
                  int cost=rs.getInt(3);
                  if(sub.g_n<cost)  //if the cost of sub is less than db row's cost
                  {
                      //replace the cost
                      rs.updateInt(3, sub.g_n);
                      rs.updateRow();
                      return 1;   //only examine - do not insert
                  }
                  else
                      return 0;   //dont examine - return

              }
           else
               return 2;      //insert and examine
           }
           catch(SQLException e)
           {

               System.out.println("here1"+e);
               System.err.println("reported recursion level was "+e.getStackTrace().length);
               return 0;
           }
           finally{

               try{
                   rs.close();}
               catch(final Exception e1)
               {
                   System.out.println("here2"+e1);
               }

           }

       }
    public void insert(FifteenPuzzle sub)
    {

        try{
        String str=sub.toDBString();

         ps2.setInt(1,sub.hashcode());
         ps2.setString(2, str);
         ps2.setInt(3,sub.g_n);
         ps2.executeUpdate();
         ps2.clearParameters();
        }catch(SQLException e)
        {
            System.out.println("here3"+e);
        }
    }

    public void InsertInDB(FifteenPuzzle sub) throws SQLException
       {

           System.out.println(k++);

           int i;

           int p=updateIfNecessary(sub);
          if(p==0)
          {
              System.out.println("returning");
           return;
          }
          if(p==2)
          {
          insert(sub);
          System.out.println("inserted");
          }

           //FifteenPuzzle temp=new FifteenPuzzle(sub.puzzle.clone(),2,sub.g_n);
           for(i=0;i<sub.puzzle.length;i++)
           {
               if(sub.puzzle[i]!=0)
               {

                   //check the positions it can be moved to
                   if(i%4!=0 && sub.puzzle[i-1]==0)  //left
                   {
                       //create another clone and increment the moves
                       FifteenPuzzle temp_inner=new FifteenPuzzle(sub.puzzle.clone(),2,sub.g_n+1);
                       //exchange positions
                        int t=temp_inner.puzzle[i];
                        temp_inner.puzzle[i]=temp_inner.puzzle[i-1];
                        temp_inner.puzzle[i-1]=t;
                        InsertInDB(temp_inner);
                   }
                   if(i%4!=3 && sub.puzzle[i+1]==0)  //right
                   {
                       //create another clone and increment the moves
                       FifteenPuzzle temp_inner=new FifteenPuzzle(sub.puzzle.clone(),2,sub.g_n+1);
                       //exchange positions
                        int t=temp_inner.puzzle[i];
                        temp_inner.puzzle[i]=temp_inner.puzzle[i+1];
                        temp_inner.puzzle[i+1]=t;
                        InsertInDB(temp_inner);
                   }
                   if(i/4!=0 && sub.puzzle[i-4]==0)  //up
                   {
                       //create another clone and increment the moves
                       FifteenPuzzle temp_inner=new FifteenPuzzle(sub.puzzle.clone(),2,sub.g_n+1);
                       //exchange positions
                        int t=temp_inner.puzzle[i];
                        temp_inner.puzzle[i]=temp_inner.puzzle[i-4];
                        temp_inner.puzzle[i-4]=t;
                        InsertInDB(temp_inner);
                   }
                   if(i/4!=3 && sub.puzzle[i+4]==0)  //down
                   {
                       //create another clone and increment the moves
                       FifteenPuzzle temp_inner=new FifteenPuzzle(sub.puzzle.clone(),2,sub.g_n+1);
                       //exchange positions
                        int t=temp_inner.puzzle[i];
                        temp_inner.puzzle[i]=temp_inner.puzzle[i+4];
                        temp_inner.puzzle[i+4]=t;
                        InsertInDB(temp_inner);

                  }
             }
       }

```

The function **insertInDB(FifteenPuzzle fp)** in the class is the recursive function and is called first from the main function with the array for the fifteen puzzle argument(`puzzle` is an integer array field of the Class `FifteenPuzzle`) being - `1,2,3,4,0,6,0,0,0,0,0,0,0,0,0,0`(same as the matrix shown above). Before explaining the other functions I will explain what static pattern database is; briefly(Because of the comments below)

## What is a (5-5-5) static pattern database for 15-Puzzle?

Pattern databases are heuristics used to solve a fifteen puzzle(can be any puzzle. But here I will talk about only 15-Puzzle). A heuristic is a number used to determine which state to be expanded next. I is like cost of each state. Here state is a *permutation* of the 15-Puzzle. For simple puzzles like 8-Puzzle, the heuristic can be **manhattan distance**. It gives the minimum number of moves, for each misplaced tile, to reach **it's** goal position. Then manhattan distances for all the tiles are added up to give the cost for that tile. Manhattan distance gives the lower bound to the estimate of the number of moves required to reach the goal state i.e you cannot reach the goal state with moves, less than the manhattan distance. **BUT** manhattan distance is not a very good heuristic, though admissible, because it does not consider other tiles near by it. If a tile has to be moved to it's goal position, the near by tiles also have to be moved and the number of moves increase. So, clearly for these puzzles, the actual cost is mostly much greater that the manhattan distance.
To **overcome** this(manhattan distance) and take into account the other tiles, pattern databases were introduced. A static patter database holds the heuristics for sub-problems or for a group of tiles to reach for their goal state. Since, you are calculating the number of moves to make these group of tiles reach their goal state, the other tiles in that group will be taken into account when a tiles is being moved. So, this is a better heuristic and mostly will always is greater than manhattan distance.
5-5-5 static pattern is just a form of static pattern database where the number of groups are 3, two of them containing 5 tiles each and the third one contains 6(6th isthe blank tile).

## One of the groups is this matrix :<br>

1 2 3 4
0 6 0 0
0 0 0 0
0 0 0 0

---

I calculating the heuristics/number\_of\_moves for all permutations of this group to reach the above configuration and **inserting them into my database**.
The total number of combinations(also the no of rows in db) possible is

```
16!/(16-5)! = 524160

```

Now, the other functions - `updateIfNecessary(FifteenPuzzle)` \- this function checks if the array of the passed FifteenPuzzle object is already present in the database. If already present in the database, it checks if the current object's cost is less than the cost in DB. If yes, it replaces it with the current cost else does nothing. The function -`insert(FifteenPuzzle)` inserts a new permutaion with the cost.
**NOTE :** `fifteenuzzle.g_n` is the cost for the puzzle. For the initial puzzle that represents the matrix above, the cost is `0` and for each move the cost is `incremented by1`.

I have set the stack size to -`Xss128m`(1024, 512 and 256 were giving a fatal error) for stack size in run configurations.
Currently the recursion number or the depth is **`7,500,000` and counting**(value of `System.out.println(k++);`).
The total number of combinations possible is

```
16!/(16-5)! = 524160

```

But the depth has already reached 7,500,000. This is because of generation of duplicate states. Currently the number of entries in the database is **513423**. You might think that there only 10,000 entries to fill up now. But now the rate at which entries are made has decreased drastically about **1 entry every 30 min**. This will never get over then.
I need a solution that is practical - **with or without recursion**. Is it possible?

# Answer
It seems that you are moving the blocks to get all the permutations. Then, checking each permutation to be present in DB; if yes then updating the number of moves if necessary.

It would generate a tree. You are generating it in DFS style (by recursive calls). If you do it in BFS style, then you will always get the smallest number of moves. The duplicate states generated later would always have larger moves required. So, you don't have to compare it in the DB.

In the following examples, we will shift `6` and then we see the number of moves.

`Priority: Left, Right, Up, Down (as you gave)`

**DFS Style**

```
1 2 3 4    1 2 3 4
0 6 0 0    6 0 0 0
0 0 0 0    0 0 0 0
0 0 0 0    0 0 0 0
  (0)        (1)

```

Left most position reached. Now, check to move to it right (from where it came from). That position is already there in the DB, so carry on. Moreover, it can't even go up. So going down.

```
1 2 3 4    1 2 3 4
0 0 0 0    0 0 0 0
6 0 0 0    0 0 0 0
0 0 0 0    6 0 0 0
  (2)        (3)

```

Now, go right

```
           State-1    State-2    State-3
1 2 3 4    1 2 3 4    1 2 3 4    1 2 3 4
0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0
0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0
6 0 0 0    0 6 0 0    0 0 6 0    0 0 0 6
  (3)        (4)        (5)        (6)

```

Here you can see that, `State-1` can be reached in just 2 (not 4) moves. But that will be revealed later and we'd have to update the DB. So, clearly its a waste of effort.

**BFS Style**

```
1 2 3 4    1 2 3 4
0 6 0 0    6 0 0 0
0 0 0 0    0 0 0 0
0 0 0 0    0 0 0 0
  (0)        (1)

```

Leftmost position reached, now go right

```
1 2 3 4    1 2 3 4
0 0 6 0    0 0 0 0
0 0 0 0    0 6 0 0
0 0 0 0    0 0 0 0
  (1)        (1)

```

You can consider this as `6` spreading all the sides equally. Here also, we would have duplicate states but those would have larger min moves required than the first entry of the DB.

You can use a simple queue to implement this.

**Pseudocode**:

```
Initialize no_of_moves by 0
enqueue(startingPosition)
insertIntoDB(startingPattern, no_of_moves)
while((currentPattern = dequeue()) is not null)
    if(currentPattern is not already traversed)
        insertIntoDB(currentPattern);
        list<Pattern> allPatterns = patterns which can be reached from currentPattern in just 1 move
        no_of_moves++
        enqueue(allPatterns, no_of_moves)
    end if
end while

```

There can be many ways to check if a state has already been traversed besides checking it from the DB. I was thinking of hashing but not able to come up.

You can maintain a boolean list mapped from the pattern string (say `traversed["1234060000000000"] = true or false`). I don't think storing 524160 entries in the main memory would create any problem.
> 2 votes

# Answer
Glad to see someone implemented Pattern Databases!

From your description: "*Since, you are calculating the number of moves to make these group of tiles reach their goal state, **the other tiles in that group** will be taken into account when a tiles is being moved*" it seems to me that you are implementing MAX pattern databases while I would strongly recommend you to implement additive (ADD) pattern databases. While it cannot be assured that the latter is always more informed than the former (for a nice discussion on the subject see Fan Yang et al. A General Theory of Additive State Space Abstractions, Journal of Artificial Intelligence Research, 32, pp 631--662, 2008) they are usually preferred. I am just noting this in passing since this choice really makes a difference in the implementation though I have an implementation which can create any of the two PDBs simultaneously. I do not think that posting here the code might be the more convenient (though I would not mind to do so). Thus, if you want to get the full code, email me (or anyone) at carlos.linares@uc3m.es and I will send it to you. Of course, you can do with it whatever you want.

Now, regarding your question: note that your PDB (implemented usually as a plain binary file with as many entries as different positions might arise which contain just a signed char) serve also as a closed list. At the beginning, initialize your PDB with -1 in all locations. Everytime you generate a new permutation, rank it to get the right entry of your PDB and write down the minimum number of moves it took your algorithm to visit it. Doing so, if you ever generate the same entry again you will easily notice that its content is strictly positive and can be discarded. This works if you fill in your PDB using a *backwards breadth-first search*.

In case you already noted this then you might be suffering from another problem: the blank location. Be aware that the blank should never be taken into consideration (i.e., it should never be mapped or you might end up with inadmissible estimates). Hence, you have to ignore the blank location when ranking your permutation and this way, each entry of your PDB should contain the minimum number of moves to reach that particular permutation in spite of the blank location.

My last recommendation, use a separate file that just encodes the OPEN list used in the backwards breadth-first search, ie., a file which just contains two pointers: one to the next item to pop and another one to the tail with the position where the next item should be pushed. Well, 5 symbols in your PDB is not that big but you will need this when trying to generate PDBs as large as 7-8 which is the preferred configuration for solving the 15-Puzzle.

Again, feel free to e-mail me in case you want to have a look both at the code for generating PDBs and also to solve instances randomly chosen using them.

Hope this helps,
> 2 votes

---
Tags: algorithms, artificial-intelligence, recursion
---


# Question
Title: Relation between interactive proof systems (IP), NP, coNP, PSPACE
I would like to ask you some clarification on the following question: know that ${\sf NP}$ is a subset of ${\sf IP}$ and also ${\sf coNP}$ it is a subset of ${\sf IP}$. So ${\sf IP}$ is a biggest class, but how much it is big?

May i say that ${\sf PSPACE}$ is a subset of ${\sf IP}$? or that they may intersect?

Can you give me a easy clarification about it?

# Answer
> 9 votes
IP = PSPACE is a famous result (and indeed paper) by Adi Shamir in 1992.

Furthermore, we clearly have NP $\subseteq$ PSPACE and coNP $\subseteq$ PSPACE, but we don't know how NP relates to coNP. There are several reasons to believe that determining the relationship between NP and coNP is difficult, some of which are discussed in this recent thread.

---
Tags: complexity-theory, time-complexity, space-complexity, complexity-classes, interactive-proof-systems
---


# Question
Title: Constructing a graph of min-degree k with the smallest diameter possible
I need to build a graph with $N$ vertices such that each vertex has degree at least $k$ and the graph has the smallest diameter. What algorithm can I use?

# Answer
> 4 votes
If $N \> k$ then the complete graph $K\_N$ is regular with degree $N-1 \geq k$, and has the smallest possible diameter $1$. If $N \leq k$ then there the degrees are bounded by $N-1 \< k$, and so no such graph exists.

---
Tags: graphs
---


# Question
Title: What is the difference between abstract and concrete data structures?
I thought associative array (i.e. map, or dictionary) and hashing table were the same concept, until I saw in Wikipedia that

> For dictionaries with very small numbers of bindings, it may make sense to implement the dictionary using an association list, a linked list of bindings. ...
>
> The most frequently used general purpose implementation of an associative array is with a hash table: an array of bindings, together with a hash function that maps each possible key into an array index. ...
>
> Dictionaries may also be stored in binary search trees or in data structures specialized to a particular type of keys such as radix trees, tries, Judy arrays, or van Emde Boas trees. ...

So, I think, my problem lies in that I don't know that associative array (i.e. map, or dictionary) is an abstract data type and hashing table is a concrete data structure, and different concrete data structures can be used to implement the same abstract data type.

My questions would be

* What is the difference and relation between abstract data structures and concrete data structures?
* What examples are for each of them (abstract and concrete data structures)? The more the better.
* Is there a list of what concrete data structures can be used to implement what abstract data structures? It would be nice to have one.

# Answer
The abstract data type (ADT) is essentially an API, and a concrete data structure provides an implementation of that API. For a given ADT, there are often several different choices of concrete data structures which support the query and update operations described by the ADT. Every concrete data structure for a given ADT must support all the operations described by the ADT (possibly with some probability of success in the case of randomized structures), but each concrete structure may make different guarantees of the running times of each operation. The choice of which concrete data structure to implement for a given ADT usually depends on the priorities of efficiency of each operation (including initializing the structure) and the complexity of implementing and maintaining the various data types. Some concrete data structures have excellent theoretical guarantees, but the overhead is such that a slightly less theoretically optimal data structure may be a better choice in practice.

There are far too many ADT and corresponding concrete structures to list in a single answer, but here are a few examples:

* A dictionary supports `Find(x)` queries. For an a key $x$, return the element in the dictionary with key $x$, if such an element exists. A dynamic dictionary also supports `Insert(x)` and `Delete(x)`. Common implementations of a dictionary include different kinds of balanced binary search trees (e.g. red black tree) and various kinds of hash tables.
* In addition to `Find` an ADT may require support of `successor(x)` queries. That is, maintain a set of keys $S$, and given key $x$, find the smallest key $t \in S$ such that $s \< t$. Concrete data structures which support the Successor ADT include various binary search trees, and more complicated structures such as an X-fast trie or van Emde Boas tree (if the keys are integers).
* A Priority Queue is an ADT that requires `insert` and `delete-min` operations (and sometimes other operations as well, such as `find-min` `increase-key` or `delete-key`). Data structures that implement the priority queue ADT include:

1. an unsorted linked list, which has fast `insert` but slow `delete-min`.
    2. a sorted linked list which has fast `delete-min` but slow `insert`
    3. a binary search tree, which has logarithmic `insert` and `delete-min`, and $sort(n)$ initialization time.
    4. a binary heap which has logarithmic `insert` and `delete-min`, and linear time initialization.
    5. There are also other variants of heap implementations.
* An interval stabbing ADT maintains a set of intervals on the real line, and supports a `stabbing(x)` query, which returns the subset of intervals which contain (are stabbed by) the point $x$. Data structures that implement the stabbing query ADT include a Segment Tree and an Interval Tree.
> 19 votes

# Answer
Abstract data type describes *what* operations are available and what laws they obey. E.g. a dictionary allows you to store a value under a given key and to retrieve a value for a key, and promises that if you first store a value and then retrieve it with the same key, you will get the value you stored back. A stack has push and pop operations.

Concrete data type says *how* these operations are actually implemented.
> 9 votes

---
Tags: data-structures, abstract-data-types
---


# Question
Title: Confusion about big-O notation comparison of two functions
On page 16 of this algorithms book, it states:

> For example, suppose we are choosing between two algorithms for a particular computational task. One takes $f\_1(n) = n^2$ steps, while the other takes $f\_2(n) = 2n + 20$ steps (Figure 0.2).

He then goes on to say:

> This superiority ... (of $f\_2$ over $f\_1$) ... is captured by the big-O notation: $f\_2 = O(f\_1)$, because ...

Now my problem is that in the original quote, he said that $f\_1(n) = n^2$ steps and $f\_2(n) = 2n+20$ steps, so thus $f\_1 = O(n^2)$ and $f\_2 = O(n)$ (big-O is defined in Section 0.3). But the second quote above states $f\_2 = O(f\_1)$, which means $f\_2 = O(n^2)$ and contradicts his definition of big-O notation. What have I missed?

# Answer
> 12 votes
The key thing to keep in mind here is that the equals sign in $f = O(g)$ does not behave as an equals sign usually would. The reason is that $O(g)$ is not actually a function but a **set** of functions. For example, you can think of $O(n^2)$ as being a set which, among many other functions, contains the functions $n$, $5 \sqrt n$, $\log^5 n$, etc. So as the appropriate way to think of $f = O(g)$ is not as equality but instead as being an element of a set: $f \in O(g)$.

So the set $O(n)$ is a subset of $O(n^2)$ since any function that is asymptotically bounded above by a multiple of $n$ is also bounded asymptotically above by a multiple of $n^2$.

# Answer
> 4 votes
The big-O denotes an **upper bound**. Since $O(n)\subset O(n^2) $, we have for any function $h$ $$h=O(n)\\; \Rightarrow \\; h= O(n^2).$$

In other words if $g\_1(n)=n$ is an asymptotic upper bound for $f\_2(n)$ then $g\_2(n)=n^2$ is of course also an asymptotic upper bound for $f\_2(n)$. The statement does not contradict the definition of the big-O definition.

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


# Question
Title: How to quickly find a few bisimulations on a given labelled digraph?
We are given a labelled directed graph, where both vertices (or states) and edges (or transitions) have labels. Informally, two states are bisimilar when they have the same label and they can simulate each other's transitions. On the states the two states evolve to, the same again is true.

More formally, a binary relation $R \subseteq S \times S$ is a simulation iff $\forall (p,q) \in R$

* $p$ and $q$ have the same label, and
* if $p \overset{a}{\longrightarrow} p'$ then $\exists q', q \overset{a}{\longrightarrow} q'$ and $(p',q') \in R$.

A relation $R$ is a bisimulation iff $R$ and $R^{-1}$ are simulations. The largest bisimulation on the given system is called the *bisimilarity relation*.

There are algorithms for finding the bisimilarity relation, that run in $O(m \log n)$ time and $O(m+n)$ space, where $n$ is the number of states and $m$ the number of transitions. An example is the Paige-Tarjan RCP algorithm from 1987.

However, consider a simpler problem. Instead of finding all the bisimulations, I just want to find a few of them. Can it be done faster than in loglinear time? If so, how? For example, let's say one is given two states $p,q \in S$ such that they have the same label and they can make the same transitions. What I find problematic is to check that the states they lead to are once again bisimulations. In other words, one could also ask if there is a quick way to decide if two given states are a bisimulation.

# Answer
> 2 votes
You can always return the bisimulation $∅$ in constant time.

You are right about the fact that in order to return $R$, you will have at least some sanity checks.

For example you could think that returning all bisimulations of the form $\\{(p,q)\\}$ when $p$ and $q$ have the same label and such that $p\not→$ and $q\not→$ is easy, but not that much: you need to proceed through $O(m+n)$ time and $O(n)$ space! (Or $O(mn^2)$ time and $O(1)$ space (not counting the output)). Checking that a small relation is a bisimulation is not a lot easier than finding the relation $\sim$.

The computation of $\sim$ uses clever properties specific to $\sim$ and fusing states tricks. These techniques would not be useful for several relations and doing better than $O(m\log n)$ (not loglinear) is hard. Also, computing "a few" bisimulation is of arguable interest.

Another thing: deciding if $p\sim q$ implies computing the relation $\sim$ on the union of the directed graphs $G\_p=\\{x ∣ p \stackrel{a\_1\dots a\_n}{\longrightarrow}x\\}$ and $G\_q=\\{x ∣ q \stackrel{b\_1\dots b\_m}{\longrightarrow}x\\}$ which can be a significant part of the graph. If however you know have information like the size of $G\_p$ and $G\_q$ then you can compute $\sim$ on smaller graphs. Keep in mind that algorithms with Tarjan in their name tend to have very tight bounds. This is not an exception.

---
Tags: algorithms, graphs, process-algebras
---


# Question
Title: Guessing the best choice to maximize returns
There are $N$ number of people and $X$ amount of objects with different values. Each person will choose an object and will obtain that objects value. If multiple people choose the same object then the value of the object is shared among the people. For example, If there are 2 objects and 3 people, one of the objects will be chosen by at least 2 people, thus the value of the object is divided over 2.

Each round the people make their decisions with new objects and new values, how can a person maximize their expected values accumulated from their choices in Q number of rounds, in order to win(i.e accumulated most value)? ($Q$ belongs to \[1, +infinite).

Note that keeping track of other player's decisions and their accumulated values can help in future decision making.

Note: An approximation would be great as well, so far my strategy is to choose a random object at each round, I am looking for ways to maximize this strategy.

# Answer
One simple way, better than random choice, is to use modification of one step ExpectiMax. Each round you will give each Objects Value some new estimated value V(obj).

V(obj)= $\frac{ObjectValue(obj)}{ ( 1+ \sum\limits\_{i=1}^n P\_{i}(obj) )}$

where **$ P\_{i}(obj)$ = probability that person i will chose Object obj**

And every round you will chose the one Object with greatest estimated value V.

You can choose at the beginning **$ P\_{i}(obj)$** to be some function over the Object Value- the bigger the value the greatest probability that it will be picked.

## Learning:

From your question "`Note that keeping track of other player's decisions and their accumulated values can help in future decision making.`" and your comment "`(learning opponent strategy under uncertainty)` " I guess that you need to learn the strategies of your opponents.

One way is after each game to see which Object Value was picked by each of your opponents and how the picked value differs from your expectations (**$ P\_{i}(obj)$**). Using this information you can **slightly** modify the probabilities **$ P\_{i}(obj)$** (decrease or increase them a little for specific Object Values) and use the improved probabilities for each of the opponent in the next rounds s.
> 2 votes

# Answer
First of all, I don't think there is any point in considering rounds, since each round is independent. So if the behavior of the players is not affected by the outcome of the previous rounds, they would play every round as a new round. You probably assume that there is an influence, but then this should be modeled.

Okay but lets come back to a single round. For simplicity assume you have 2 players $A,B$ and two objects with value $6$ and $8$. You can model this as a 2 player game with the following payoff matrix $$ \begin{pmatrix} 3,3 &6,8 \\8,6 & 4,4\end{pmatrix}. $$

This symmetric game has no dominant strategy. So every player should randomize its choice. We have 3 Nash equilibria, shown in the picture

From this I would expect that each players plays the mixed strategy, i.e., pick the item with value 3 with probability $2/7$ and otherwise pick the object with value 4.
> 1 votes

---
Tags: artificial-intelligence, randomized-algorithms
---


title: Floating-Point Binary to Decimal

text:
# Question
Title: Floating-Point Binary to Decimal
I'm having difficulty with the following question:

> Given a bit pattern with mantissa $10110000$ and exponent $0111$, what does the bit pattern represent in denary (i.e decimal / base 10)?

I got the right answer(!) but the wrong (or alternative) work:

1. Convert the exponent to denary: $0111$ is $7$
2. Apply this exponent to the mantissa: $10110000\rightarrow1011000$ after shifting $7$ places
3. Convert the mantissa to denary: $1011000$ is $88$
4. Set the sign: $-88$ (which is correct!)

Using a different method, the mantissa $1.0110000$ is somehow deteremined to be $-11/16$ and then $-11/16 \times 2^7 = - 88$ (I understand this shift with the exponent). However, what I don't understand is:

> **How do you convert 1.0101 (mantissa) to -11/16?** Is this a standard way to do it?

# Answer
I got the answer with a bit of reverse engineering.

1) 0111 is 7 in denary so the exponent is power(2,7)

2) convert 10101000 to a positive number using twos comp

3) you you get: 010110000 which is 1/2 + 1/ 8 + 1/16 using the powers of 2 after the radix point

4) this is 11/16 but we no it is negative from step 2 so it is -11/16!
> 1 votes

---
Tags: terminology, binary-arithmetic
---


# Question
Title: 'Texas Hold Em Poker' Agent Heuristics to help decide whether to fold or bet?
I am designing a poker agent with different heuristics to decide whether to raise, fold or pass (in Texas holdem poker). I am planning to have 4 heuristics with the agent biased to one of them.

The poker game will consist of 10 agents playing against each other.

I have two heuristics now:

1. bluff - Agent would keep betting until all others fold
2. odds\>pot odds - https://www.youtube.com/watch?v=1wux3avg1CM&feature=relmfu

I need to know what other heuristics a poker agent can use to make a decision.

# Answer
Here are some of the heuristics I use when playing online on XBOX live against bots, but the game is so much better with human players, bots are boring and predictable.

1. Obviously, what are you hold cards. Rockets to 7-2 off suite. There are many poker tables that give you the odds for the hold cards.
2. How many players at the table. The more players you have the better your hand has to be because more cards are in play for making better hands. When you get down to one-on-one, even a high card is often good, but with a table of 10, you should be holding at least a high pair after the river.
3. Is the card generator truly random. For the XBOX live games it is rumored they use a card generator named the "Action Engine" because it is designed to generate action on the table by setting up possible flushes and straights. You would not believe how many people chase down the river hoping for a straight or flush, problem is they tend to get it more often than random because of the simulated gambling.
4. Is there a pattern to the players betting? Do they continue to bet on each card? Do they slow play when then have a good hand or the nuts? Do they bet really big when bluffing? Do the bet really big when they have a high card or better? I their betting related to the the cards they have? Do they ever bluff?
5. Are you allowed to keep a database of all hands? This is a big advantage if allowed.
6. Position. Are you the dealer or in the blind? Ever heard the saying that poker is a game of position.
7. Does a player re-raise?
8. Does a player fold before or on the river to hide their cards if they don't believe they have a good hand even if they can check?
9. Do they play most hands or are conservative. A conservative player will bet only on good cards and you can pretty much count on that, while a player who plays most to all hands means that you have to more attentive to them having the nuts from the flop no matter what the flop is.
10. Does the player have a limit they never bet or raise beyond?
11. How many out cards do you have versus all of the possible out cards.
12. Does the player play the heavy? At what level will they play the heavy against another player?
13. Is the player afraid to call an all-in.
14. Is there a level below they will not raise? I.e. only raise if a King or higher in their hold cards, or have a pair or higher with what's on the table?
15. Do they go all in if the best hand can only be made by the cards on the table?
16. Do they bluff more when A's, or possible straights or flushes appear?
17. Is there betting based on money amounts or multiples of the blind?
18. Does there style of play changed based on their money amount? Based on a multiple of the blind? Based on who sits next to them?
19. Can you use the length of time the opponent uses to play a turn to your advantage?
20. Is the player trying to win the game or just play to make it to the money rounds?
21. Are the players susceptible to being pulled into betting wars?
22. Can betting big on the river cause the player to fold more than normal?
23. Can always re-raising a player get them to change their playing style?
24. Are their bet amounts increasing or decreasing as the hand progresses?
25. Is there a minimum amount they always bet no matter what they have in the hold?

These are just the basic ones for playing a bot, if you add a human player the list of heuristics gets much more complicated.
> 3 votes

---
Tags: artificial-intelligence, heuristics
---


# Question
Title: Prove that $2^{(log(n)^{1/2})}$ is $O(n^a)$
Hopefully this is the right section. I need to prove that $2^{(log(n)^{1/2})}$ is $O(n^a)$. From the basic principle of Big-O notation, I know I need to find two numbers $c$ and $N$ so that $f(n) \le c\cdot g(n)$ for all values of $n \ge N$. In this case, $f(n)$ is $2^{(log(n)^{1/2})}$, and $g(n)$ is $n^a$.

The first problem in the set had me prove that $2^{n+a}$ is $O(2^n)$. For this problem, I had separated the $f(n)$ to $2^n \cdot 2^a$. I was guided by another user to set $c = 2^a$. This way, with $g(n) = 2^n$, $cg(n) = 2^a2^n$, which is obviously $\ge f(n)$, $2^{n+a}$, for all values of $n \ge 0$. This problem, however, I don't find as easy.

Could someone point me in the right direction? I've been trying to rearrange the problem and solve it for a while now.

# Answer
> 1 votes
$n^a = \exp(a \ln n) = \exp(a \ln n \frac{\ln 2}{\ln 2}) = 2^{\frac{a \ln n}{\ln 2}}$. Can you prove that if $h(n) = O(k(n))$ then $2^{h(n)} = O(2^{k(n)})$ ?

# Answer
> 1 votes
It holds that $\log x^y=y\log x$. Hence we have $$2^{\log n^{1/2}}=2^{1/2 \log n}=(2^{\log n})^{1/2}=n^{1/2}=O(n^{1/2}).$$

So this is mostly about computing with logarithms, and not so much about the big-O notation.

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


# Question
Title: Finite State Automata for recognising consecutive characters
I'm currently working on this question as part of some homework, it has me stumped.

I'm familiar with finite state automata (FSA), I know how they work and I've read everything I can find on Google, but nothing's helped me come any closer to a solution.

If I don't know the length of the input string, or I'm not searching for a particular pattern, how can I design a machine that will always land on the final state?

I've tried drawing some, but that always end up being a little off.

# Answer
> 2 votes
The FSA should have three states:

* $q\_a$ represents: **last character was not a `b`, and no `bb` yet**
* $q\_b$ represents: **last character was a `b`, and no `bb` yet**
* $q\_{bb}$ represents: **there was already a `bb`**

Clearly, you start with $q\_a$ and you accept in $q\_a$ and $q\_b$. Now try to figure out how to connect the states.

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


title: Runtime analysis of a nested loop

text:
# Question
Title: Runtime analysis of a nested loop
I have some difficulties performing the worst case analysis on this algorithm.
The outermost loop is executed $2N$ times.
The while loop, in the worst case, will increase by $2$ each time, so it performs $i/2$ basic operations ($\*2$ because double call)

```
for (i=1; i<=2*N; i++) {
        j = 0;
        while (j <= i) {
            a[i] = function (function (a[i]));
            if (c[i][j] != 0)
                j = j + 6;
            else
                j = j + 2;
        }
    }

```

`function` is the basic operation.
Am I going the right way?

# Answer
The worst case for the number of `function` calls is (as you already observed)

$$\sum\_{i=1}^{2N}\sum\_{j=1}^{i/2} 2 =\sum\_{i=1}^{2N} i = \frac{2N(2N+1)}{2}=2N^2+N,$$

by Gauß' summation formula.
> 2 votes

# Answer
Let $f(N)$ denote the number of `function` calls within the loop.

Substituting $N+1$ instead of $N$ into the code you can observe that the first $2N$ iterations of the outer loop remain exactly the same and the last two iterations add up to $N+1$ and $N+2$ iterations of the inner loop each. Since each iteration of the inner loop results in two `function` calls, you can arrive to the following estimation $$ f(N+1) \leq f(N) + 4 N + 6 $$

Observe also that $$ f(1) \leq 6$$

Starting from here you can obtain an upper bound $F(N)$ for $f(N)$ by solving the recurrence $$ \begin{eqnarray\*} &&F(N+1) = F(N) + 4 N + 6\\ &&F(1) = 6 \end{eqnarray\*} $$

The solution for this recurrence is a function quadratic in $N$. I will add the exact solution later.
> 1 votes

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


title: coNP and limitation of NDTM

text:
# Question
Title: coNP and limitation of NDTM
I am trying to understand if someone can apply an **NTM** to recognize a $coNP$ language.

From the definition we know that:

$NP$ \- set of languages that can be recognized by NTM in polynomial time.

$coNP$ \- set of all languages that are complement to $NP$ language.

as with $P$ vs. $NP$ question, we have $NP$ versus $coNP$ question.

Unfortunately, is not defined explicitly if can one recognize $coNP$ language with NTM.

However, if we take a look at few examples from the set of $coNP$ languages, few questions emerge.

$TAUTOLOGY$ = {$\varphi$: $\varphi$ is satisfied by every assignment}

$UNSAT$ = {$\varphi$: $\varphi$ is unsatisfiable}

These languages are known to be $coNP$ language and intuitively it seems like one can construct NTM to recognize these languages. On the other hand, if one can construct NTM to recognize them why them not in $NP$ class (by definition)? Maybe not all languages of $coNP$ can be solved by NTM, just few of them which are in $NP\cap coNP$. And if every language from $coNP$ class cannot be solved by NTM, does it mean that limitation of NTM is located in $coNP$. Does NTM have limitation at all?

I am a little bit confused, I would appreciate anyone that is willing to shine the light on this topic.

# Answer
> 4 votes
These complexity classes are not just defined by a machine model but also by the criteria about when a machine accepts a strings. So although $\mathsf{NP}$ and $\mathsf{coNP}$ can be defined using essentially the same underlining machine structure their accepting criteria are different. That is the main point you are missing.

In my experience, generally it is intuitively more clear for people to think about $\mathsf{NP}$ using its verifier-certificate definition and forget about the non-deterministic TM (which can be confusing).

We say a language $L$ is in $\mathsf{NP}$ if there is a polytime DTM with two inputs $V$ (think of $V$ as a certificate verifier) s.t. for all $x$, $ x \in L$ iff there exists a polynomial size certificate $y$ s.t. $V$ accepts $(x,y)$.

In more intuitive terms, $\mathsf{NP}$ is the set of problems that given an instance and a polysize solution/certificate/proof for that instance, we can efficiently *verify* the correctness of the given solution. E.g. given a graph and a list of vertices in it, it is possible in polynomial time to check if the list is a Hamiltonian path in the graph. Therefore Hamiltonian path problem is in $\mathsf{NP}$.

So in intuitive terms, $\mathsf{NP}$ is the set of problems that a given solution can be **confirmed efficiently** and $\mathsf{coNP}$ is the set of problems that a given solution can be **refuted efficiently**. For example, a refutation for a $TAUT$ instance is an assignment that makes the formula false.

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


title: Finding $c$ and $n_0$ for a big-O bound

text:
# Question
Title: Finding $c$ and $n_0$ for a big-O bound
A book I am reading demonstrates how $5n^3 + 2n^2 + 22n + 6 = O(n^3)$, which I believe is true. After all, there exists a value $c$ for which $cn^3$ is always greater than $5n^3 + 2n^2 + 22n + 6$ for all $n$ greater than or equal to some value $n\_0$.

However, the book then casually notes that $c = 5$ and $n\_0 = 10$. Where did these values come from? What algebraic calculations were done (if any) to derive the $c$ and $n\_0$ values?

# Answer
$c=5$ is clearly the wrong answer, since for any $n$, $$cn^3 \< 5n^3 + \text{(positive terms)}$$

However, if we take $c\>5$ then there will exists some $N\_0$ such that for $n\>N\_0$ $$cn^3 \ge 5n^2+2n^2+22n+6$$

If we let $g(n)=(c-5)n^3-2n^2-22n-6$, then Since $\lim\_{n\to\infty} g(n)=\infty$, by the limit definition there always exists $N\_0$ such that for any $n\>N\_0$, $g(n) \>0$. This implies the above claim.

To find that $N\_0(c)$ you can try to find the roots of $g(n)$. $N\_0$ will be the most positive root.
> 5 votes

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


# Question
Title: CFG and PDA for the grammar that has perfectly nested parentheses and brackets
I gotta make a CFG and PDA for the grammar that has perfectly nested parentheses and brackets.

$\qquad\begin{align} S &\to \[S\] \\ S &\to (S) \\ S &\to SS \\ S &\to \varepsilon \end{align}$

Not sure if this is correct, or how to make the PDA from it?

# Answer
The language you study is a classic, the one-sided Dyck language (on two pairs of brackets). You can directly make a PDA by considering the following property of nested strings: every symbol closing bracket you read should match the last unmatched opening bracket. Keep the unmatched $\[$ and $($ on the stack and you are ready to go.
> 3 votes

# Answer
A: your CFG looks good.

B: There is a very well-known method of converting CFGs to PDAs.

Check https://www.youtube.com/watch?v=MJ9xNavURY8

Or the Wikipedia article on Pushdown automata

also this question has some interesting details.

But mainly - google "Converting CFG ro PDA".
> 0 votes

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


# Question
Title: Find an undecidable language that is mapping-reducible to its complement
As the title suggests. Also, such a language must satisfy that neither it nor its complement are semi-decidable. I already know that $All\_{TM}, EQ\_{TM}, T$ (that is the set of all deciders) satisfy this property. But I tried reducing these to their complements directly, and via some sort of intermediate language, but to no avail. Can anyone help?

# Answer
Try the following construction. Given a language $L$, use $$ \\{0x : x \notin L\\} \cup \\{1x : x \in L\\}. $$
> 3 votes

# Answer
Another more advanced answer is to look at a complete problem from a class that is closed under complement. For example, take the arithmetical hierarchy which is closed under complements. Now consider a complete problem for it like:

> Given: a sentence in the language of first-order arithmetic,
> Question: is the sentence true (in the standard model $\mathbb{N}$)?

It is easy that one can reduce this to its complement by negating the sentence.

This works generally for any class that is closed under completion and has a complete problem (w.r.t. many-one reductions).
> 2 votes

---
Tags: computability, reductions
---


# Question
Title: How can P =? NP enhance integer factorization
If ${\sf P}$ does in fact equal ${\sf NP}$, how would this enhance our algorithms to factor integers faster. In other words, what kind of insight would this fact give us in understanding integer factorization better?

# Answer
If $P=NP$, and we have an algorithm that can solve the k-SAT problem in polynomial time, then integer factorization can simply be reduced to k-SAT by describing factoring as a problem in k-SAT.

Essentially it works as follows: You make a bunch of variables each representing the bits of $p$, and $q$, and $n$. Then you formulate the k-SAT problem as $p\*q=n$. Since $n$ is known, you can set those values. Then a satisfying assignment will describe a valid $p$ and $q$. To describe the multiplication in k-SAT, you can use any of the known multiplication algorithms and describe it's logical circuit in k-SAT. For more info on reducing factoring to k-SAT, see here.

As for understanding factoring better, that would probably require more research and analyzing the magic algorithm (that can solve NP-complete problems in deterministic polynomial time), and perhaps specializing it to the integer-factoring formulation of k-SAT problem (which obviously has a very specific structure, depending on the multiplication algorithm used).
> 10 votes

# Answer
The decision problem for factoring is $\mathsf{NP}$ and the factoring can be reduced to it in deterministic polynomial time.

If $\mathsf{P}=\mathsf{NP}$ then then any problem in $\mathsf{NP}$ including factoring will have a polynomial time algorithm.

Note that the best known deterministic/probabilistic algorithms for factoring at the moment take exponential time so a polynomial time algorithm would be a great improvement. To get a feeling of it, consider factoring a 2000 bit number. One may take longer than all the time since the big bang, the other may answer in a few milliseconds.
> 4 votes

---
Tags: complexity-theory, computability, np-complete, p-vs-np, factoring
---


# Question
Title: Proving that if $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$
I'd really like your help with proving the following.

If $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$.

Here, $\mathrm{NTime}(n^{100})$ is the class of all languages which can be decided by nondeterministic Turing machine in polynomial time of $O(n^{100})$ and $\mathrm{DTime}(n^{1000})$ is the class of all languages which can be decided by a deterministic Turing machine in polynomial time of $O(n^{1000})$.

Any help/suggestions?

# Answer
> 3 votes
Here is the solution using padding. Suppose $L \in \mathrm{NTime}(n^{1000})$. Define a new language $L' = \\{x0^{|x|^{10}-|x|} : x \in L\\}$. Each $x \in L$ corresponds to some $y \in L'$ of length $|y| = |x| + (|x|^{10}-|x|) = |x|^{10}$. Therefore we can decide whether $y \in L'$ in non-deterministic time $|x|^{1000} = |y|^{100}$, i.e. $L' \in \mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$. In order to decide whether $x \in L$, form $y = x0^{x^{10}-|x|}$ and run the $|y|^{1000} = |x|^{10000}$-time deterministic algorithm for $L'$. We conclude that $L \in \mathrm{DTime}(n^{10000})$.

# Answer
> 2 votes
Break the problem into two parts:

1. There is a $\mathsf{NP}$-complete language in $\mathsf{NTime}(n^{1000})$.
2. If an $\mathsf{NP}$-complete language is in $\mathsf{DTime}(n^{1000}) \subset \mathsf{P}$ then $\mathsf{P}=\mathsf{NP}$.

# Answer
> -2 votes
This is a near trivial consequence of the definition of NP-completeness. If any language in NP is solvable in polynomial time (which is asserted by the premise), then they all are. Another way to look at this is to look at Cook's theorem for NP-completeness that reduces all NP-complete languages to the recognition of a language involving SAT and the conversion of the nondeterministic Turing machine into SAT.

---
Tags: time-complexity, complexity-classes, p-vs-np
---


title: Why is Relativization a barrier?

text:
# Question
Title: Why is Relativization a barrier?
When I was explaining the Baker-Gill-Solovay proof that there exists an oracle with which we can have, $\mathsf{P} = \mathsf{NP}$, and an oracle with which we can have $\mathsf{P} \neq \mathsf{NP}$ to a friend, a question came up as to why such techniques are ill-suited for proving the $\mathsf{P} \neq \mathsf{NP}$ problem, and I couldn't give a satisfactory answer.

To put it more concretely, if I have an approach to prove $\mathsf{P} \neq \mathsf{NP}$ and if I could construct oracles to make a situation like above happen, why does it make my method invalid?

Any exposition/thoughts on this topic?

# Answer
> To put it more concretely, if I have an approach to prove P≠NP and if I could construct oracles to make a situation like above happen, why does it make my method invalid?

Note that the latter “if” is not a condition, because Baker, Gill, and Solovay already constructed such an oracle. It is just a mathematical truth that (1) there exists an oracle relative to which P=NP, and that (2) there exists an oracle relative to which P≠NP.

This means that if you have an approach to prove P≠NP and the same proof would equally prove a stronger result “P*A*≠NP*A* for all oracles *A*,” then your approach is doomed to fail because it would contradict (1).

In other words, there is some fundamental difference between proving P≠NP and proving e.g. the time hierarchy theorem, because the proof of the latter just uses diagonalization and is equally applicable to any relativized world.

Of course, this does not mean that there is no proof for P≠NP. Such a proof (if one exists) must fail to prove the stronger result mentioned above. In other words, some part of the proof must distinguish the nonrelativizing world from arbitrary relativized worlds.
> 38 votes

# Answer
There are already good answers, but I would like to add a few small points.

Assume that we have a technique to solve problems, e.g. *diagonalization*. Assume that we want to show that the technique cannot solve a specific problem e.g. *$\mathsf{P}$ vs. $\mathsf{NP}$*. How can be show this?

Before going further, note that a technique like diagonalization is not a formal concept here (though we can make it so). Moreover the fact that the technique cannot solve the problem by itself doesn't mean that it is not useful in solving the problem at all, we might be able to modify it and/or combine it with other techniques to solve the problem.

Now, let's get back to the question. One way to show that a technique cannot solve a specific problem is to show that if it could it would also work in a different framework for solving another question, and the answer that we would get in that case would be wrong. This is what happens here. If the diagonalization could separate $\mathsf{NP}$ from $\mathsf{P}$ then the same argument could be used to separate $\mathsf{NP^A}$ from $\mathsf{P^A}$ for all $A$. But we know that there is an oracle such that this is false (take any $\mathsf{PSpace}$-complete problem as the oracle). So diagonalization cannot separate $\mathsf{NP}$ from $\mathsf{P}$.

The essential point in this argument is a kind of *transfer principle*:

> we can transfer a diagonalization argument for TMs without oracle to TMs with oracles.

This is possible here because diagonalization arguments are based on *simulation* of machines, moreover the simulation doesn't depend on the internals of machines but only on the final answers from these simulations. This kind of diagonalization is referred to as *simple diagonalization*. In a simulation it doesn't matter how the machine works, we care only the final answer of the machine. Adding an oracle will not change this so the simulation and the argument will work also in the framework where we have oracles.

More formally, we can think of a diagonalization argument as a function from a class of machines (say $\mathsf{P}$) to instances showing that the machine cannot solve a problem (say $SAT$). This counterexample function is the diagonalization function. A diagonalization is simple if the counterexamples it gives do not depend on the internals of the machines, i.e. if two polynomial time DTMs have the same language then the counterexample showing that they cannot solve $SAT$ given by the diagonalization function is the same.

You may wonder if this is a big restriction? Why would the counterexample need to depend on the internal structure of the machine? Can we prove separations using diagonalization that cannot be proved using simple diagonalization? The answer is yes. In fact Kozen shows in his 1978 paper "Indexing of subrecursive classes" (3 years after BGS result) that if $\mathsf{NP}$ can be separated from $\mathsf{P}$ then there is a general diagonalization argument for it. And in practice such arguments have been found. For example, Fortnow and van Melkebeek's time-space lower-bounds for SAT (2000) use a technique called *indirect diagonalization* that gives a non-simple diagonalization.

So is the claim that diagonalization cannot solve $\mathsf{P}$ vs. $\mathsf{NP}$ incorrect? Well, in general what experts mean by diagonalization here is *simple diagonalization* and there is a good reason for that.

The general diagonalization arguments are so general that it doesn't really make much sense to call them a technique, you can easily turn any separation argument into a diagonalization argument without much insight: If we already have some way of separating two complexity classes, we can pick a function in the larger class not in the smaller one. Take any enumeration of the machines in the smaller class. Let $M$ be any machines in the enumeration. We have to define the counterexample for $M$. But we already know that $M$ cannot solve the problem, so there *exists* instance showing this, define the value of the diagonalization function on $M$ to be that instance. This is the big-picture view, if you want to see the details check Kozen's paper.

### Summary:

* When experts say "diagonalization cannot solve $\mathsf{P}$ vs. $\mathsf{NP}$" what they mean is "*simple* diagonalization cannot solve $\mathsf{P}$ vs. $\mathsf{NP}$" not the general one.
* The reason simple diagonalization cannot separate $\mathsf{NP}$ from $\mathsf{P}$ is that it transfers to the framework with oracles (in the literature it is stated as "diagonalization relativized") and the separation does not hold there.
* The reason this transfer from oracle-less framework to framework with oracles works is that simple diagonalization is based on black-box simulation of TMs and it doesn't matter how machines works, whether it has an oracle or not.

Two good papers to learn more about diagonalization are

* Lance Fortnow's survey paper "Diagonalization", 2001, and
* Russell Impagliazzo, Valentine Kabanets and Antonina Kolokolova's paper "An Axiomatic Approach to Algebrization", 2009. (Note that *algebraization* is an extension of *simple diagonalization*.)
> 24 votes

# Answer
Let $\mathrm{A}$ and $\mathrm{B}$ be two complexity classes. A separation ($\mathrm{A} \neq \mathrm{B}$) or collapse ($\mathrm{A} = \mathrm{B}$) is said to relativize if for all oracles $\mathrm{O}$ we have $\mathrm{A}^\mathrm{O} \neq \mathrm{B}^\mathrm{O}$ or $\mathrm{A}^\mathrm{O} = \mathrm{B}^\mathrm{O}$ respectively. The Baker-Gill-Solovay proof tells us that $P = NP$ or $P \neq NP$ does not relativize.

Why is this a problem? When this proof came out, the majority of techniques and tricks we knew to separate or collapse complexity classes 'relativized', in that they work with respect to any oracle. For instance, the time hierarchy theorem (as well as the space and nondeterministic versions of it) 'relativize': they prove separations for classes for which this separation relativizes, and in fact, they prove the stronger result that the separation holds with respect to any oracle.

If a technique or trick works regardless of whether there is an oracle present, then it cannot possibly prove $P = NP$ or $P \neq NP$ by the above argument. This means that a large number of tricks and techniques that we know of don't work on this problem (or indeed on a lot of open problems). You can also use it as a sanity check for any purported $P \neq NP$ proof: check whether the idea fails to hold in the presence of a $\mathrm{PSPACE}$-complete oracle - if it still works, then it is wrong.
> 18 votes

---
Tags: complexity-theory, proof-techniques, p-vs-np, relativization
---


# Question
Title: Dynamic programming: Knapsack with repetition, Find the number of redundant machines
I have just started to learn Dynamic Programming, and so far I have studied the few basic concepts; longest common subsequent problem, edit distance problem and the knapsack problem. I have attempted to solve the following exercise that is related with this topic, and so far I think I have a way how to approach it , but I am stuck at one point. Please, if you can, read my solution and tell me whether I am doing something wrong. I absolutely do not want you to solve it for me, just give me some help/hints.

A mission-critical production system has n stages that have to be performed sequentially; stage i is performed by machine M\_i. Each machine M\_i has a probability r\_i of functioning reliably and a probability 1-r\_i of failing (and the failures are independent). Therefore, if we implement each stage with a single machine, the probability that the whole system works is r\_1,r\_2,...,r\_n. To improve this probability we add redundancy, by having m\_i copies of the machine M\_i that performs stage i. The probability that all m\_i copies fail simultaneously is only (1-r\_i)^(m\_i), so the probability that stage i is completed correctly is 1-(1-r\_i)^(mi) and the probability that the whole system works is prod(i=1,n){1-(1-r\_i)^(m\_i)}. Each machine M\_i has a cost c\_i, and there is a total budget B to buy machines. (Assume that B and c\_i are positive integers.) Given the probabilities r\_1,...,r\_n, the costs c\_1,...,c\_n, and the budget B, find the redundancies m\_1,...,m\_n that are within the available budget and that maximize the probability that the system works correctly .

**\__*_*\__*_*\__*_*\__*_*\__*_*\__*_*\__*_*\___** MY PROPOSED SOLUTION

1. We need to make sure that all the given probabilities are different from 0, meaning for all r\_1 !=0 (if we had a probability 0 the system would not work)
2. We must make sure that we have at least one machine of each type, meaning we have one copy of each machine (if we do not have a certain machine, like in point 1 the system would not work). In addition, by having already a copy of machines from m\_1,...,m\_n, the total cost of this machines would be sum(i=1,n)=c\_i. This means that from the total budget B we need to subtract this cost, and get the extra budget for the redundant machines. B\_extra= B-sum(i=1,n)=c\_i
3. To find the redundant number of machines we just need to model the problem as knapsack. Subproblem: K(c) -\>maximum probability that a system works correctly. Recursive relationship:

for c=1 to B\_extra K(c) = max{K(c-c\_i)\*(1-(1-r\_i)^(m\_i)):c\_i\<=c}

Now, the points where I am stuck and need help are:

1. The way I am defining the problem, is it correct or am I missing any special case? I think that the recursive relationship should work fine; any reason why it shouldn't?
2. How should I keep track of the number of m\_i machines. I know that the initial value for each m\_i is one (from point 2 we need at least one copy of each machine). Should I just keep track of another variable in the problem K(c, m) and every time increase m\_i++?

# Answer
the maximum sucesss probability would be the minimum failed probability, and each machine should be at least 1, so we can reduce the original package B into B'= B-sum(c\_i), and each machine's dp\[i\]\[0\] should be initialized as fail probability (1 - r\_i).

so, we can find the dp state transition based on the modified knapsack(size is B') problem as above:

```
dp[i][c]    = min(dp[i-1][c], dp[i-1][c-cost[n]]*(1-r_i))
    0<= c <=B' , 1<=i<=n, B' = B-sum(c_i)

```

intitial of the dp array would be like this:

```
dp[0][0~B'] = 1
dp[i][0]    = 1-r_i, 1<=i<=n

```

so the pseudocode would be like :

```
 for(int i = 1 ; i<=n;++i)
  for(int c = cost[i] ; c<=B';++c)
     dp[i][c] = min(dp[i-1][c], dp[i-1][c-cost[n]]*(1-r_i)))

```
> 0 votes

# Answer
R(b,j): the max reliability for constructing the system with stage 1....j with budget b

```
 for j=1 to n
    Pr(0,j)=0
 for b=1 to B
    Pr(b,1)=r_1

 for b=1 to B
    for j=1 to n
       for k=1 to b/c_j
          Pr(b,j)=max{Pr(b-c_j*k, j-1)*(1-(1-r_j)^k}
          Red[B][j]=k
 print(Red[ ][ ])

```
> 0 votes

---
Tags: dynamic-programming
---


# Question
Title: What is a good binary encoding for $\phi$-based balanced ternary arithmetic algorithms?
I've been looking for a way to represent the golden ratio ($\phi$) base more efficiently in binary. The standard binary golden ratio notation works but is horribly space inefficient. The Balanced Ternary Tau System (BTTS) is the best I've found but is quite obscure. The paper describing it in detail is A. Stakhov, Brousentsov's Ternary Principle, Bergman's Number System and Ternary Mirror-symmetrical Arithmetic, 2002. It is covered in less depth by this blog post.

BTTS is a balanced ternary representation that uses $\phi^2 = \phi + 1$ as a base and 3 values of $\bar 1$ ($-1$), $0$, and $1$ to represent addition or subtraction of powers of $\phi^2$. The table on page 6 of the paper lists integer values from 0 up to 10, and it can represent any $\phi$-based number as well.

BTTS has some fascinating properties, but being ternary, I didn't think I'd be able to find a compact bit representation for it.

Then I noticed that because of the arithmetic rules, the pattern $\bar 1 \bar 1$ never occurs as long as you only allow numbers $\ge 0$. This means that the nine possible combinations for each pair of trits ($3^2$) only ever has 8 values, so we can encode 2 trits with 3 bits ($2^3$, a.k.a octal). Also note that the left-most bit (and also right-most for integers because of the mirror-symmetric property) will only ever be $0$ or $1$ (again for positive numbers only), which lets us encode the left-most trit with only 1 bit.

So a $2^n$-bit number can store $\lfloor 2^n/3\rfloor * 2 + 1$ balanced trits, possibly with a bit left over (maybe a good candidate for a sign bit). For example, we can represent $10 + 1 = 11$ balanced trits with $15 + 1 = 16$ bits, or $20 + 1 = 21$ balanced trits with $30 + 1 = 31$ bits, with 1 left over (32-bit). This has much better space density than ordinary golden ratio base binary encoding.

So my question is, what would be a good octal (3-bit) encoding of trit pairs such that we can implement the addition and other arithmetic rules of the BTTS with as little difficulty as possible. One of the tricky aspects of this system is that carries happen in both directions, i.e.
$1 + 1 = 1 \bar 1 .1$ and $\bar 1 + \bar 1 = \bar 1 1.\bar 1$.

This is my first post here, so please let me know if I need to fix or clarify anything.

--**Edit**--

ex0du5 asked for some clarification of what I need from a binary representation:

1. I want to be able to represent positive values of both integers and powers of $\phi$. The range of representable values need not be as good as binary, but it should be better than phinary per bit. I want to represent the largest possible set of phinary numbers in the smallest amount of space possible. Space takes priority over operation count for arithmetic operations.
2. I need addition to function such that carries happen in both directions. Addition will be the most common operation for my application. Consequently it should require as few operations as possible. If a shorter sequence of operations are possible using a longer bit representation (conflicting with goal 1), then goal 1 takes priority. Space is more important than speed.
3. Multiplication only needs to handle integers \> 0 multiplied to a phinary number, not arbitrary phinary number multiplication, and so can technically be emulated with a series of additions, though a faster algorithm would be helpful.
4. I'm ignoring division and subtraction for now, but having algorithms for them would be a bonus.
5. I need to eventually convert a phinary number to a binary floating point approximation of it's value, but this will happen only just prior to output. There will be no converting back and forth.

# Answer
I'm going to try to answer this myself, in the hope that my answer will give others a better idea of what I'm after and lead to better answers than mine.

I found that framing the problem in terms of the original golden ratio base helped me to think about a binary encoding more effectively. I want to note however that there is no difference between BTTS and phinary except the length of the representation. Both number systems represent the same set of numbers, save that BTTS more easily encodes negative numbers. Just as 3 bits can theoretically represent 2 trits of BTTS, they should also be able to represent 4 bits of phinary (which is what 2 trits encode). Keep in mind that in standard base-$\phi$ all instances of $011\_\phi$ are replaced with $100\_\phi$ and $1\_\phi + 1\_\phi = 10.01\_\phi$, with a carry both one place to the left and two to the right. The following table is my best attempt thus far:

```
Phinary  |  Binary | Octal
0 0 0 0  |  0 0 0  |   0
0 0 0 1  |  0 0 1  |   1
0 0 1 0  |  0 1 0  |   2
0 1 0 0  |  0 1 1  |   3
0 1 0 1  |  1 0 0  |   4
1 0 0 0  |  1 0 1  |   5
1 0 0 1  |  1 1 0  |   6
1 0 1 0  |  1 1 1  |   7

```

There are some benefits to this encoding. One is that $0\_\phi$ and $1\_\phi$ are the same as for binary. Another is that a carry in the forward direction works as expected automatically:

$1010\_\phi + 1\_\phi = 1011\_\phi = 1100\_\phi = 1\ 0000\_\phi$, and $111\_2 + 1\_2 = 1\ 000\_2$.

Another advantage is that addition *almost* works as is:

$0101\_\phi + 0010\_\phi = 0111\_\phi = 1001\_\phi$ and $100\_2 + 010\_2 = 110\_2$.

As far as I can tell, the only places addition breaks down are for $2\_8 + 2\_8$, $5\_8 + 7\_8$ and $7\_8 + 7\_8$.

$0010\_\phi + 0010\_\phi = 0020\_\phi = 0100.1\_\phi$, not $0101\_\phi$.
$1000\_\phi + 1010\_\phi = 2010\_\phi = 1\ 0020\_\phi = 1\ 0100.1\_\phi$, not $1\ 0101\_\phi$.
$1010\_\phi + 1010\_\phi = 2020\_\phi = 2100.1\_\phi = 1\ 1000.1\_\phi$, not $1\ 1001\_\phi$.

All other additions work (excluding right carry logic).

We can handle right carries by looking at how they are produced. I'll be using octal for brevity.

* 1, 4, and 6 produce a right carry of 3 to the previous 3 bits when they are added to themselves or each other.
* 2 and 7 produce a right carry of 5 added to the previous 3 bits when added to themselves or each other.
* 4 + 3 gives a right carry of 3 and 5 + 7 gives a right carry of 5.

That's all we need to check for (I think) with the exception of also testing for 2 + 2, 5 + 7, and 7 + 7 and subtracting 1 from the result.

So basically we are taking advantage of the redundancy in a 4-bit phinary representation ($011\_\phi = 100\_\phi$) to represent the same numbers without redundant cases in 3-bits of binary.
A $2^n$ bit number can store $\lfloor 2^n / 3\rfloor * 4 + 1$ phinary bits.

I'm sure there are clever bit-hacky ways to do this better, but I'm hoping that this will clarify my intent and provide a starting point for both myself and anyone else wanting to tackle this.
> 2 votes

# Answer
The easiest way (assuming I understand your question - I was a very bored Year 10 graduate) is to go to base 2.618~ and use the following system: if initial bit = 0 then 0 if initial bit = 1 then see next bit. if next bit = 0 then 1 if next bit = 1 then 2

Advantages: uses space efficently. Uses 1.618~ bits per notation. Disadvantages: Hard to work with. (and slow).
> -1 votes

---
Tags: algorithms, data-structures, efficiency, coding-theory
---


title: Minimum weight triangulation

text:
# Question
Title: Minimum weight triangulation
I'm just curious about the pseudocode (or real source code, doesn't matter) of the recursive version of this algorithm. In almost every book chapter/paper when describing this topic, they mention that the recursive version takes exponential time and then they give the code for the dynamic programming approach. I understand how the iterative version (dynamic programming ie. memoization) works. But i just wonder about the recursive version. For the info, the key part in the iterative code is:

> $\ell$ ... left
> $r$ ... right
> $a$ ... apex
> $T$ ... triangulation
>
> $T\_{\ell,r}= \min\\{T\_{\ell,a} + \text{perimeter}\_{\ell,a,r} + T\_{a,r}\\}$

So how does the recursive function `findOT()` seem in
pseudocode or one of these languages (C#, Java, C/C++, PHP, Javascript, SML)?

# Answer
It's really hard to say, what kind recursion you mean. There are different variants I can think of. For what you have written, I guess it is something like this.

```
function findOT(int l,r)

if ((r-l)==2) return perimeter(l,l+1,r)

min= infinity
for a=(l+1)..(r-1)
    T=findOT(l,a)+perimeter(l,a,r)+findOT(a,r)
    if T<min then min=T
    endfor
return(min)

```
> 1 votes

---
Tags: algorithms, computational-geometry, recursion
---


# Question
Title: probability wheel, redistribution of probabilities
I have a contiguous ordered data structure (0 based index):

```
x= [1/3, 1/3, 1/3]

```

Let's say I selected index 1 and increased the probability by 1/3. Rest of the probabilities each decrease by 1/6 and the total probability remains P = 1.

```
x= [1/6, 2/3, 1/6]

```

Let's say I selected index 2 and increased the probability by 1/3. Rest of the probabilities in total need to decrease by 1/3 to make the total probability remain P= 1.

```
x= [1/10, 2/5, 1/2]

```

Is there a name for this kind of data structure? I'd like to research that name and use a library instead of my custom rolled code if possible.

# Answer
> 2 votes
This can be easily achieved by an array $A$ and an additional variable $m$. The entry $A\[i\]$ stores the probability of $i$ times $m$.

In your example you start with

```
A=[1,1,1], m=3

```

The you increase the probability of the second element by 1/3. This can be carried out by setting $A\[2\]=4$ and $m=6$, which gives

```
A=[1,4,1], m=6

```

In general you could set the probability of element $k$ to $p$ by solving the system $$\sum\_i A\[i\] = m \text{ and } A\[k\]=p\cdot m,$$ for the unknowns $A\[k\]$ and $m$.

So all you need to do is to set $m$ to $$ m = \frac{\sum\_{i\neq k} A\[i\]}{1-p},$$ and $A\[k\]=p\cdot m$ for the new $m$.

---
Tags: data-structures, probability-theory
---


# Question
Title: Is the codomain/range of a hash function always $\mathbb{Z}$ or $\mathbb{N}$?
From Wikipedia

> A hash function is any algorithm or subroutine that maps **large data sets of variable length**, called keys, to **smaller data sets of a fixed length**. For example, a person's name, having a variable length, could be hashed to a single **integer**. The values returned by a hash function are called hash values, hash codes, hash sums, checksums or simply hashes.

I wonder if the range/codomain of a hash function is always the set of natural numbers or integers, because their function values seem to be always used as indices to some array?

# Answer
In fact, there's an argument to be made that the 'range' of CRC-style hashes is *not* the integers (or naturals), but is in fact the field of polynomials over GF(2) modulo a primitive polynomial of degree $n$ (i.e., the field GF$(2^n)$). All of the operations are done on $n$-bit entities, but those entities are only 'numbers' in so much as that's the representation that's used for them; they don't add like numbers or multiply like numbers. While the final value returned to the user is interpreted and stored as a number, no arithmetic operations are generally performed on *that* value either; only indexing operations, which (for hopefully obvious reasons) require that the result be integer-convertible in some fashion.
> 6 votes

# Answer
Range of any hash function is a sub-set of natural numbers (this is how we think of it, exactly for access to the arrays, that could lie behind). The actual output of common hash-functions (MD5, SHAX...) is $n$ bits, where $n$ is $128$ for MD5 and $512$ for SHA2 with 80 rounds.

These bits can then be interpreted as natural numbers from interval $\[0, 2^n-1\]$. They can also be interpreted as integer from $\[-2^{n-1},2^{n-1}\]$. They can also be interpreted as "strings", although in essence they are only bits. What @Arani is talking about (I think) is probably conversion of this binary number to the hexadecimal format, and viewing it as string.
> 6 votes

# Answer
It doesn't need to be. There is nothing about the structure of the hash function in general that requires that.

However it is more convenient to use natural numbers/strings. Computation over other objects are normally defined using an encoding of those objects by finite strings or natural numbers and there is not much lost in this conversion.
> 4 votes

# Answer
It's quite commonly smaller than $\mathbb{N}$ or $\mathbb{Z}$, e.g. $\\{-2^{31},...,2^{31}-1\\}$ so as to fit in common number types.
> 3 votes

# Answer
While hash function's outputs (especially cryptographic hash function outputs) are frequently used as strings in software engineering, this is because there exists a bijection between the set of possible strings and subset of N or Z. Thus, MD5, SHA1, SHA2 and SHA3 are all widely known hash functions whose outputs are frequently taken as strings.
> 2 votes

---
Tags: terminology, hash
---


title: Reduction to Hamiltonian cycle

text:
# Question
Title: Reduction to Hamiltonian cycle
Given that the Hamiltonian cycle problem is NP-complete, I want to prove that the following problem is NP-complete:

> Given an undirected graph $G(V,E)$ and vertices $s,t\in V$, does there exist a path from $s$ to $t$ with at least $k$ edges such that all vertices in the path are distinct?

I thought of assigning a weight of $1$ to every edge and on similar grounds, but I am not able to compensate for the "at least $k$" edges part.

It would be appreciated if somebody could help me with the approach.

# Answer
> 5 votes
**Problem is in NP**

You can easily verify an answer to your problem: if a path is given, and it is goes from $s$ to $t$ and has $k$ edges with distinct vertices, then it is correct.

**Reduction from Hamiltonian Cycle Problem**

You can pick any vertex as $s$, and then for each neighbor, $(s,t\_i)\in E$, attempt your algorithm, with $k=\left|V\right|-1$ after cutting that edge. If the algorithm succeeds for any attempt with $(s,t\_i)$, then you have found a *Hamiltonian cycle*. This means *Hamiltonian path* reduces to your given problem.

Given that it is in NP, and the *Hamiltonian Cycle Problem* can be reduced to it, it is NP-complete.

**EDIT** I suppose an even simpler reduction is just to set $s = t$, and for any vertex in $V$, with $k=\left|V\right|-1$.

Though I am unsure of how one would solve this problem given $s,t,k,V,E$ in the general case. Nor do I know how to reduce this problem to the *Hamiltonian cycle* problem. A roundabout way would be to reduce this problem to 3-SAT, and then reduce the result back down to *Hamiltonian cycle*. However, as I pointed out above, you can easily see it is NP-complete, due a reduction from *Hamiltonian cycle* to this problem, in conjunction with the fact that the problem is in NP (you can verify the answer easily).

**k-Stroll** / **k-Tour**

A similar problem is named the k-Stroll problem in Approximation Algorithms for the Directed k-Tour and k-Stroll Problems:

> The input to the k-Stroll problem is a directed $n$-vertex graph with nonnegative edge lengths, an integer $k$, and two special vertices $s$ and $t$. The goal is to find a minimum-length $s$-$t$ walk, containing at least $k$ distinct vertices.

Also related is the k-Tour problem, which is the case where $s=t$.

# Answer
> 1 votes
Note, all you need to do to show something is NP-Hard is to show that an NP-Hard problem is its subproblem.

For instance, in your case, you could show that since finding a Hamilton Path is NP-Hard, then your problem is NP-Hard since a Hamilton Path is the specific case of your problem where `k = |V|-1`.

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


# Question
Title: Is there any nontrivial problem in the theory of serial algorithms with a nontrivial polynomial lower bound of $\Omega(n^2)$?
In the theory of distributed algorithms, there are problems with lower bounds, as $\Omega(n^2)$, that are "big" (I mean, bigger than $\Omega(n\log n)$), and nontrivial. I wonder if are there problems with similar bound in the theory of serial algorithm, I mean of order much greater than $\Omega(n\log n)$.

With trivial, I mean "obtained just considering that we must read the whole input" and similarly.

# Answer
> 10 votes
There are such problems by time hierarchy theorem. Just take any problem that is complete for a large complexity class. For example, take a problem that is complete for $\mathsf{ExpTime}$. Such a problem will be $\Omega(n^c)$ for all $c\in\mathbb{N}$.

However also note that for problems in $\mathsf{NP}$, there are not strong time lower-bounds in multiple-tape TM model and existence of linear time algorithms for SAT is consistent with current state of knowledge. (In single-tape TM model it is not difficult to show that many problems like palindromes require $\Omega(n^2)$ time but such lower-bounds depend essentially on the particulars of the single-tape TM model.)

# Answer
> 3 votes
Some simple problems that have lower bounds greater than the size of their inputs, are algorithms that have output sizes greater than their input sizes.

Some examples:

* The problem of listing *all solutions* to 3-SAT, or similarly, the problem of listing all *Hamiltonian cycles*. These problems both have exponential number of solutions in the worst case. Thus they have a lower bound of $\Omega (c^n),c\>1$. Interestingly however, the 3-SAT problem itself has no known super-linear (greater than $\Omega (n)$) bounds! This means we do not know if it is harder than linear!
* You can even make up new algorithms like this: "completing a graph" that is, given $G = V,E$, where $E=\varnothing$, and $n=|V|$, the algorithm will output a graph $G' = V,E'$, where $E'=\left\\{u,v|u\neq v\space\wedge\space u,v\in V \right\\}$.

Furthermore, you might be able to compose a problem that has $\Omega (n^2)$-sized outputs, with a problem that takes $\Omega (n^2)$ as input, and outputs $\Omega (n)$ or even $\Omega (1)$-sized outputs (for example, something that counts the number outputs) to obtain a problem that takes $\Omega(n)$-sized input, and outputs $\Omega (n)$-sized output, and yet has a running time greater than $\Omega (n)$. However it might be very difficult to prove (that there is no shortcut to obtain the answer in less time).

---

Another way some problems have known lower bounds, is to restrict the model of computation.

Though comparison sort's lower bound does not exceed $\Omega (n\log n)$, I think its worth discussing. Comparison sort is also a problem that has a greater lower bound than its input size, but it's lower bound does not exceed $\Omega (n\log n)$, and in . However, as I was researching this, I found this question on mathoverflow: Super-linear time complexity lower bounds for any natural problem in NP. Further examples listed in the answer there are far below $\Omega (n\log n)$. I think the gist of it is, if you restrict the model of computation, you can get lower bounds for problems for which we otherwise do not have them. And if you do not restrict the model of computation, it is very difficult to prove lower bounds on problems.

---
Tags: algorithms, complexity-theory, lower-bounds
---


# Question
Title: Improving Time Bound of this Algorithm past $O(n^2)$
I recently came across the following interesting problem - one is given a sequence of `X`s and `Y`s such as `XXYXYXYYXYXXXYX`, and consider a sequence to be good if, as you start at the left and move right, the number of `X`s is greater than or equal to the number of `Y`s at any point except at the very end, at which the two quantities must be equal.

One must determine the number of points at which changing either a single `X` to `Y` or a single `Y` to `X` in a given sequence will yield a good sequence.

I initially considered traveling through the sequence linearly and checking if toggling the letter at that point would yield a good sequence, however that approach is on the order of $O(n\cdot n)=O(n^2)$ in the worst case where n is the length of the sequence. However, I was wondering if there was some faster method to do it.

EDIT: I made the observation that for any sequence, if the number of possible changes is greater than 0, than only one type of change will work (either changing an `X` to `Y` or `Y` to `X`) given the condition at the end that the number of `X` and `Y` must be equal.

# Answer
Here is a hint. Suppose the sequence contains $n-1$ Xs and $n+1$ Ys, so that you need to change some Y to X. You can compute for each position $k \in \[1,\ldots,2n\]$ the number of Xs minus the number of Ys; let's call that a "report". Changing a Y to an X affects the report in a certain, easy to describe, way. On the other hand, whether a sequence is good corresponds to a very simple property of the report.

Putting everything together, you should get an $O(n)$ algorithm.
> 7 votes

---
Tags: algorithms, subsequences
---


# Question
Title: Voronoi diagram with given number of vertices and sites
I want to draw a Voronoi diagram with 9 sites and with

1. no vertex,
2. 1 vertex,
3. 4 vertices, and
4. 7 vertices.

How do I approach this question. The one with no vertex is easy, it can be done by collinear points. What about the others.

A figure for each would be appreciated.

# Answer
Conceptually, it is maybe easier to construct a Delaunay triangulation tessalation. The DT is the dual to the Voronoi diagramm, so you want to limit the number of faces to $0,1,4,7$. This can be achieved by placing some of the vertices of the DT on a circle, or by picking the right number of vertices on the convex hull.

Here is a picture for the 4 vertex case (black DT, red Voronoi diagramm). Play around to get the solutions of 2. and 4. (You already solved 1.)
> 4 votes

---
Tags: computational-geometry
---


# Question
Title: How many random walks to start from each node?
Assume that we are given a real life graph, DBLP network in my case, where degree distribution of nodes follows a power law (many nodes have 1, 2 neighbors, and only a few nodes have hundreds of neighbors).

A random walk ends when it returns to the initial node or when the walk takes 3 steps. If we start random walks from each node on this graph, should we start equal number of walks from each node? If so, nodes with small degrees will often return to where they started, and we will not learn big portions of the network. This is because small degree nodes are neighbors of small degree nodes more often, so there will not be many paths to walk on.

I believe there should be a way to decide on the number of walks to minimize computational costs.

# Answer
If you consider given graph as a Markov chain, you can compute the steady-state distribution. With it, you can compute the mean-reccurence time $M\_j$ (expected time to return to the starting node). See Mean recurrence time

$\pi\_j=1/M\_j$

If for some node $n\_j$, the probability of going to each neighbour is equal to $1/out\\\_deg(n\_j)$, then you can compute $\pi\_j$ in constant time.

This does not assume, you stop after three steps (why do you actually need this?). From here you could do some experiments with damping factor $d$. Damping factor $d$ is the probability you end the walk at each step. Damping factor You can combine these two aproaches to get to your estimate.

-edit-

So here goes. Given an undirected graph $G=(V,E)$ you can find the stationary distribution of the corresponding Markov chain $M$ with transition matrix $P$ as follows:

$\pi\_i=deg(v\_i)/|E|$

where $deg(v\_i)$ is the degree of vertex $i$, $|E|$ is the number of all edges in graph $G$ and $\pi\_i$ is the $i$-th component of vector that satisfies:

$\lim\_{k-\>\infty} P^k=1\pi$

Note that $\pi$ is unique if the Markov chain is irreducible and aperiodic.

* Irreducibility essentially means, you can get from every vertex $i$ to every vertex $j$. If the graph is not connected, you can use the same approach on the connected components of the graph.
* Aperiodicity means that greatest common divisor of cylce lengths in the Markov chain. This means that if you have at least one paper which was written by three authors (in one component), the condition is trivially satisfied.

Mean recurrence time is the computed by the formula above.
> 2 votes

---
Tags: graphs, probability-theory, random-walks
---


# Question
Title: Showing a partition-like problem is NP-complete
Given a set $A=\\{a\_{1},a\_{2},a\_{3},\ldots,a\_{n}\\}$, then construct a set $P=\\{p\_{1}, p\_{2}, p\_{3}, \ldots , p\_{n}\\}$ such that

1. $|p\_{i}|=a\_{i}$, and
2. $\sum\_{i = 1,}^{n}p\_{i} = 0$.

This problem is NP-complete, which I want to prove.

How do I do it?

I am thinking of a reduction from the subset sum problem. But the problem is that because of the mod.

# Answer
I'm going to make a few guesses as to what you precisely mean, and if they're correct, we can edit the question so everything is clearer. First I'll define what I think you mean with your problem:

> **Input**: A set of positive integers $A=\\{a\_{1}, \ldots, a\_{n}\\}$.
> **Question**: Is there a set of integers $P = \\{p\_{1}, \ldots, p\_{n}\\}$ such that for each $i$ the absolute value of $p\_{i}$ equals $a\_{i}$ (*i.e.* $|p\_{i}| = a\_{i}$) and the sum of the elements of $P$ is zero (*i.e.* $\sum\_{i=1}^{n}p\_{i} = 0$)?

Clearly what we want to do is flip the sign on some of the $a\_{i}$s and make them negative (or rather $p\_{i} = -a\_{i}$). Then the question is whether this problem is NP-complete.

Of course the answer is yes, we just need to identify a suitable problem for the reduction. In this case, there's a very simple reduction from the Partition problem:

> **Partition**
> **Input**: A set of positive integers $S=\\{s\_{1},\ldots,s\_{n}\\}$.
> **Question**: Is there a partition of $S$ into two disjoint subsets $S\_{1}$ and $S\_{2}$ such that $S = S\_{1} \cup S\_{2}$ and $\sum S\_{1} = \sum S\_{2}$?

The reduction should be pretty clear from here.

Let $S$ be the input to the Partition instance, then we construct an input set $A$ for the new problem by simply setting $A := S$.

Now we just have to show that $S$ is a Yes-instance for Partition if and only if $A$ is a Yes-instance for the new problem.

Assume $S$ is a Yes-instance for Partition, then there are two sets $S\_{1}$ and $S\_{2}$ that partition $S$ as described, and importantly have the same sum, then in $P$ we can set the elements corresponding to elements of $S\_{2}$ to be negative, and we have a solution for the new problem ($P$ is really just $S$ in disguise, now with some signs flipped to negative).

Now assume $A$ is a Yes-instance for the new problem, then there exists a $P$ which is $A$, but with some elements now negative. Then there is some set $P' \subset P$ whose elements are negative and with a little thought we can see that as $\sum P = 0$ hence $\sum (P\setminus P') + \sum P' = 0$. Therefore, more precisely, $\sum\_{p \in P\setminus P'} p = \sum\_{q \in P'}|q|$. Obviously if then go back to looking at $A$ (which is just $S$ recall), we have a partition suitable for a solution to the Partition instance.

So we have that Partition $\leq\_{m}$ "the new problem", which tells us that the new problem is NP-hard. The very last bit is to show that the new problem is in NP, and hence NP-complete. This is of course simple, as all we have to do is observe that we can check a solution in polynomial-time just by:

1. Adding up $P$ and checking the sum is zero, and
2. Checking that each element $p\_{i}$ is $\pm a\_{i}$.

So, now that I've gone a bit overboard, did I guess the details correctly?
> 8 votes

---
Tags: np-complete, reductions, partitions
---


# Question
Title: Depth First Search to find Minimum spanning tree
A depth first search produces a spanning tree. If you perform DFS using all possible orderings of the adjacency list, wouldn't you find the minimum spanning tree? In other words, there is no example of a graph where a DFS won't find the minimum spanning tree regardless of how the adjacency list is ordered. Is this correct or not? I can't come up with a counter example and intuitively it seems correct...

# Answer
No you wont. Suppose you have as graph the complete graph $K\_n$ with $n\ge 4$, for simplicity we pick the $K\_4$, but this construction works for all larger $n$.

Every DFS-tree of a complete graph is a **path**, no matter how you order the edges. But clearly you can define the weights such that a non-path is the MST. See the example below (MST in red).
> 7 votes

---
Tags: algorithms, graphs, spanning-trees
---


# Question
Title: Cantor's diagonal method in simple terms?
Could anyone please explain Cantor's diagonalization principle in simple terms?

# Answer
> 7 votes
Here's the standard application explained in the simplest terms I can:

*Theorem:* There are more real numbers than there are integers.

*Lemma:* A real number has a decimal representation (that might not terminate), and all decimal representations create real numbers.

*Proof of Theorem:* Suppose there are as many integers as reals. Then we can list the reals in some order,

$r\_1 = 3.141592...$

$r\_2 = 2.718281...$

$r\_3 = 1.000000...$

and so on for each $r\_i$ where $i$ is an integer

There is a contradiction because I can construct a real that is not in the above list. Let $r' = 0.d\_1d\_2d\_3d\_4\ldots$ where $d\_1$ is not equal to the 1st digit after the decimal of $r\_1$, $d\_2$ is not equal to the 2nd digit after the decimal of $r\_2$, and so forth. For example, I could add 5 and take it mod 10. In the example this gives $r' = 0.665\ldots$. The contradiction is that $r'$ is not in the list, because for any $i$ I know that $r'$ and $r\_i$ differ by at least $4\*10^{-i}$ (since they differ in $d\_i$).

The fact that the reals cannot be enumerated as such shows that they are larger than the integers. But, the important result of Cantor is simply that they cannot be enumerated.

# Answer
> 4 votes
Perhaps you will find my blog post "On a proof of Cantor's theorem" illuminating. In short, the right way to prove Cantor's theorem is to first prove Lawvere's fixed point theorem, which is more computer-sciency in nature than Cantor's theorem.

Given two sets $A$ and $B$, let $B^A$ denote the set of all functions from $A$ to $B$.

> **Theorem (Lawvere):** Suppose $e : A \to B^A$ is a surjective map. Then every map $f : B \to B$ has a fixed point, i.e., $x \in B$ such that $f(x) = x$.

*Proof.* Consider the map $s:A \to B$ defined by $s(x)=f(e(x)(x))$. Because $e$ is onto, there is $y \in A$ such that $e(y)=s$. Then we have $e(y)(y)=s(y)=f(e(y)(y))$, therefore $e(y)(y)$ is a fixed point of $f$. QED.

> **Corollary (Cantor):** There is no onto map from a set $A$ onto its powerset $\mathcal{P}(A)$.

*Proof.* First note that $\mathcal{P}(A)$ is isomorphic to $2^A$ where $2 = \lbrace 0, 1 \rbrace$. That is, the subsets of $A$ correspond to their characteristic functions $A \to \lbrace 0, 1 \rbrace$. Suppose $e : A \to 2^A$ is onto. By Lawvere's theorem every map $2 \to 2$ has a fixed point. But this is not the case for the map $f(x) = 1 - x$. Therefore no such $e$ can exist. QED.

The usual proof of uncountability of reals (using decimal expansions) is of the same form too. There is a map $f : \lbrace 0, 1, \ldots, 9\rbrace \to \lbrace 0, 1, \ldots, 9\rbrace$ on the decimal digits which has no fixed point, therefore there can be no onto map $\mathbb{N} \to \lbrace 0, 1, \ldots, 9\rbrace^\mathbb{N}$.

---
Tags: complexity-theory, sets, uncountability
---


title: LR(1) - Items, Look Ahead

text:
# Question
Title: LR(1) - Items, Look Ahead
I am having diffuculties understanding the principle of lookahead in LR(1) - items. How do I compute the lookahead sets ?

Say for an example that I have the following grammar:

S -\> AB A -\> aAb | b B -\> d

Then the first state will look like this:

```
S -> .AB , {look ahead}
A -> .aAb, {look ahead}
A -> .b, {look ahead}

```

I now what look aheads are, but I don't know how to compute them. I have googled for answers but there isn't any webpage that explains this in a simple manner.

Thanks in advance

# Answer
There are two ways that lookaheads 'come into being'. The first is that the start production $S' \rightarrow S$ has lookahead $\\$$ in the initial state of the $LR(1)$ automaton. Hence, $S' \rightarrow \bullet S, \\$$ is an item in the initial state.

*Pendantry note: we therefore accept in the state containing the item $S' \rightarrow S \bullet, \\$$ on lookahead $\\$$ and we pad any input with $\\$$.*

The rest of the lookaheads are computed from lookaheads which we have already computed. If we have in some state an item $A \rightarrow \alpha \bullet X \beta, l$ (so $l$ is the lookahead and $X$ is a nonterminal) and another production $B \rightarrow \gamma$, then for every $a \in \mathsf{FIRST}(X \beta l)$ we add in the completion step for that state the item $B \rightarrow \bullet \gamma, a$.

In other words, the lookahead is some terminal that can appear as the first terminal in a string derived from $X \beta l$. As $l$ is a terminal and appears at the end of $X \beta l$, this means that $X \beta l$ does not derive the empty string (so we don't need $\mathsf{FOLLOW}$). Also note that we only ever derive items and therefore new lookaheads from items that already have lookaheads, so there is no problem there.

The precise definition of $\mathsf{FIRST}$ is: $\mathsf{FIRST}(a \alpha) = \\{a\\}$ if $a$ is a terminal, $\mathsf{FIRST}(A \alpha) = \mathsf{FIRST}(A)$ if $A$ is a nonterminal and $A$ does not derive the empty string, and $\mathsf{FIRST}(A \alpha) = \mathsf{FIRST}(A) \bigcup \mathsf{FIRST}(\alpha)$ if it does. $\mathsf{FIRST}(A)$ is the well-known relation denoting the first terminals in the strings derivable from $A$ (which is also used in $LL(1)$).
> 4 votes

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


# Question
Title: Find the longest repeated pattern in a string
I'm looking for an efficient algorithm to find the longest repeated pattern in a string.

For example, consider the following string of numbers:

`5431428571428571428571428571427623874534`.

As you can see, `142857142857` is the longest pattern which is repeated for a couple of times (at least twice) in this string.

The repeated string should not contain any re any idea rather than brute-force?

# Answer
The problem is surprisingly non-trivial. First, two brute force algorithms. A square ("repeated pattern") is given by its *length* $\ell$ and position $p$, and takes time $O(\ell)$ to verify. If we go over all $\ell$ and $p$, we obtain an $O(n^3)$ algorithm. We can improve on that by first looping over $\ell$, and then scanning the string with two running pointers at a distance of $\ell$. In this way, one can verify whether a square of length $2\ell$ exists in linear time, giving a total running time of $O(n^2)$.

Kolpakov and Kucherov developed an algorithm for finding all *maximal repeats* in a word in time $O(n)$ \[1\], and their algorithm can be used to find all maximal squares in time $O(n)$. A *repeat* is a subword of the form $w^kx$, where $k \geq 2$ and $x$ is a proper prefix of $w$. The largest square contained in that repeat is $(w^{\lfloor k/2 \rfloor})^2$. Using this formula, given all maximal repeats in a word (of which there are only $O(n)$ many), one can find the largest square.

---

\[1\] Kolpakov, R., & Kucherov, G. (1999). Finding maximal repetitions in a word in linear time. In *Foundations of Computer Science, 1999. 40th Annual Symposium on* (pp. 596-604). IEEE.
> 16 votes

---
Tags: algorithms, strings, subsequences
---


# Question
Title: What would an exponential reduction from an NP-complete problem to P signify?
Taking an NP-complete problem like vertex cover if we can find a reduction which is exponential and not polynomial and the reduction we do to a problem can be solved in polynomial time, then what would be it's implications?

Based on Yuval's answer, I wanted to throw this scenario into the place also.

If we have a problem in P which we can reduce in polynomial time to an NP-complete problem for e.g vertex cover, what happens then?

# Answer
> 6 votes
There would be no implications, and indeed I will now exhibit just such a reduction. The reduction takes an instance of vertex cover, finds the optimal value (in exponential time), and then reduces it to the language $\\{0\\} \in P$ (the language consisting of the single string $0$), by outputting $0$ if there is a vertex cover below the required threshold, $1$ otherwise.

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