I only have a basic self taught understanding in this area.
Suduko is NP Complete I believe, but as the problem size (for the usual variant), it is easily solvable using recursive algorithms (which usually run worst case in exponential time) on modern computers.
Proving an algorithm is NP, is usually done by showing that the problem is the same (can be reduced to) another know NP problem. Proving it is not is more difficult. Which appears to be what you are trying to do.
In this case I think you need to determine (prove) its worst case execution time is better than exponential.
This is about my limit of knowledge, anyway, from my point of view, arguments about N!=NP without an analysis of Big O notation (i.e. worst case performance) seems to be premature.
I don't know if this helps, is relevant or even correct, regards AlanX
Discussions
Become a Hackaday.io Member
Create an account to leave a comment. Already have an account? Log In.
I only have a basic self taught understanding in this area.
Suduko is NP Complete I believe, but as the problem size (for the usual variant), it is easily solvable using recursive algorithms (which usually run worst case in exponential time) on modern computers.
Proving an algorithm is NP, is usually done by showing that the problem is the same (can be reduced to) another know NP problem. Proving it is not is more difficult. Which appears to be what you are trying to do.
In this case I think you need to determine (prove) its worst case execution time is better than exponential.
This is about my limit of knowledge, anyway, from my point of view, arguments about N!=NP without an analysis of Big O notation (i.e. worst case performance) seems to be premature.
I don't know if this helps, is relevant or even correct, regards AlanX
Are you sure? yes | no