Sun Mon Tue Wed Thu Fri Sat |

It made me think about proving P versus NP. I have been thinking that if you want to proof that P equals NP, you need to provide an algorithm (Turing machine according to the official definition) that solves an NP problem in polynomial time. There are two things that you need to do: Proof that it runs in polynomial time to the size of the input and proof that it is correct.

It seems that in order to proof that an algorithm runs in polynomial time, on needs to identify a polynomial of a certain order. It also seems that the order definines the maximum number of nested 'loops', but that it not true. It is possible to think of an algorithm where the number of nested 'loops' depend on the size of the input, where each deeper loop runs in a smaller power than the surrounding loop.

To proof that an algorithm is correct, one needs to proof that with any given input it calculates the correct answer. The general way to proof that an algorithm is correct is to provide an invariant for each step in the algorithm and to show that the invariants are kept during each step of the algorithm.

There are three types of algorithms solving an NP problem. One type find a solution in case there is a solution. The second type tells for a certain choice in the solution, if there exists a solution or not. And the third type simply answers if there exists a solution at all. In a sense all three types of algorithms are equivalent. Take for example the Exact Cover problem where one has to select a number of binary vectors for a given set of vectors such that for each column there is exactly one vector that has a value true in that column. If one has a polynomial algorithm that finds a solution, when there is one or either not, one also has an algorithm that answers the question whether there is a solution at all. If one has an algorithm that for some vector can tell if it is included in a solution or not, one can use this to find a solution. If this algorithm establishes for some vector that it does not occur in any solution, one can simply remove the vector and apply the algorithm on the remaining set of vectors. If it does occur in some solution, one can select it and apply the algorithm on the reduced set of vectors. If one has an algorithm that can determine if a certain set of vectors has a solution, one can simply use it to determine if a certain vector can be included or not by applying the algorithm to the reduced problem where the vector is either included or not. If for one of the types there exists a polynomial algorithm, than one exists for each type.

- 9: Accidental Politicians: How Randomly Selected Legislators Can Improve Parliament Efficiency
- 10: Missing DNA Helps Make Us Human
- 14: One Man Jam by Filip Diarra
- 14: U of A researcher questions whether genius might be a result of hormonal influences
- 16: Ron Muech: Hyper realist sculptor

Home | February 2011 | April 2011