My hit at NP-completeness?

Superficiality has been the bane of Indian educational system. Most of us are 'Jack of all, master of none' types. We know, but we dont know! It is hardly surprising that India may have the highest number of engineers in the world, even 5% of them may not be real engineers. We dont care about efficiency as long as they think it is 'effective'. One of my managers in AMD thought EDA tools were great as far as algorithms goes and maybe thought that I underestimate their 'sophistication'. I am still of the opinion that EDA tools are just 'good enough' and not always the best. I wont be surprised if some of the algorithms used are pretty naive. No wonder, I am seeing that ATPG tools have gone up in performance over the decade. Why should they become faster, when designs are becoming bigger and bigger? The algorithms employed initially were more focussed on 'brute force' methodology rather than 'efficiency'. The time to market is probably one bottleneck why these tools were not fine-tuned to begin with. I am supposed to have done Masters in Computer Applications like thousands of others over the past few decades, but I am dead sure that not even 1% would have even heard of (forget reading) Rivest, Cormen and Leiserson. I infact think that instead of having a curriculum with those ridiculous, 'SAD - System Analysis and Design' or 'Software Engineering', the entire course should have ONLY ONE subject for the entire three years (to put it simply, just this book alone) and that would have brought out more promising students, rather than these 'we know (a bit of) everything' fools. As always, I got books long after I finished the courses ;) 'Real Analysis' and now 'Introduction to Algorithms'. I have to get a new edition of 'The C Programming Language' by Kernighan and Ritchie.

P versus NP problem attracted me the first time that I was told about it. Not surprisingly, I realized that this most important open question in mathematics was prized (priced) at a million dollars. As always, stunning beauty of mathematics is its simplicity. Just like Fermat's Theorem, it is so simple to state, but impossible to prove. It is hardly surprising that relevance of mathematics in 'social sciences' was talked by 'Graph theory' expert Frank Harary. It is tougher to prove theorems in abstract terms, but to extend to social science is taking to the end of the galaxy. A simpler rendition of this NP problem is the subset-sum problem. To extend into social realm say politics, given a set of political parties, is there a non-empty alliance of parties which can win over the rest?

Let us stick with mathematics. I found the NP-complete boolean satisfiability problem resonating a lot with Sudoku. I also read an article, Anything Su Doku, I Can Do Better

Sourendu Gupta and others (http://theory.tifr.res.in/~sgupta/sudoku/expert.html) have calculated the real total to be 6,670,903,752,021,072,936,960!, where the author’s final “!” is an exclamation, not a factorial!

It was also mentioned that 17 is believed to be the minimum number of clues needed for a soluble Su Doku. I had thought about this when I was working in SAP Labs and I learnt about Sudoku from a girl who was travelling in the bus with me (of course, I dont think either of us knew the other even by name). After I started improving in Sudoku, she thought she can go one step better by starting to do crosswords. I didnt follow. I allow people to have their moments of satisfaction/happiness ;)

Coming back to Sudoku, my initial take on computation of total number of Sudokus has to start from central triad and then extend the central row towards east and west and central column towards north and south. I also knew that the numbers didnt have any value and can be substituted by anything. I finally arrived at
. The central triad can be formed in 9! ways and extension of either side would make it 9!*6!*6! ways. I dont know how but I thought this should 'uniquely' define a sudoku. This has 21 clues but I knew that (5,5),(5,6),(6,5),(6,6) are redundant and thus it comes down to 17 clues!

If my initial premise of 'uniquely' defining a sudoku is right, then 17 clues should also be right. I guess new sudokus can be just formed by moving rows and columns appropriately. 17 clues are enough to satisfy a complete sudoku. If I get time and chance, I would like to spend more towards the final 'summit'.