Vinay Deolalikar appears to be set to do that very thing to a vast number of mathematicians and computer scientists, by suggesting some problems which can be verified in polynomial time can NEVER be solved in polynomial time.
Food for thought, though above my level of complexity theory education. I’d have to do a month or so of reading just to be able to make sense of his paper, let alone attempt to verify it.
Here’s hoping he nailed it! The cryptographer in me hopes he’s right.
Advertisement
0 Responses to “Upsetting the Apple-cart”