email@example.com wrote: > 2) A problem is NP complete if it can be proved to have been solved. If > on the traveling salesperson you reach a position where you can show > that no operation can reduce the distance the solution is NP complete. > NP hard simply means that the effort goes up exponentially. > > 3) It just means there is a polynomial algorithm for that particular > problem. Su Doku is NP hard. I have been trying to find a polynomial > method based on group theory. (ie. find one valid Su Doku which is > transformable into all the others) and then write the group theoretic > transformations in the form of an equation. So far I have failed. I > would like to know if anyone else has thought along similar lines.
It does not sound too promising. There are billyuns and billyuns (as Carl Sagan would say) Sudokus with different number of givens, different symmetries. How could an ur-Sudoku be transformed into all the others? If I were a betting man (I am not) I would not bet on your success. However, surpises are always possible. The Rubic Cube is group-theoretically solvable.