Computational scientists generally accept the minimum time for an algorithm to be considered 'efficient' is that its running time is polynomial: O(n^c) where n is the size of the input….. 95% of computational scientists work in this space… They call the stuff that doesn't compute as "easily" NP-Hard… really that just means they haven't figured out a good way to solve the issue in polynomial time. 5% of computational scientists work in this space. They tend to share an office with an applied mathematician. This is where 'big money' and 'big data' meets 'big science'.
I've never bought into the theory that stuff is either Polynomial or P!=NP … My gut says it is because Turing machines are fundamentally fond of polynomials. To make P=NP it may be best to use a non
Turing architecture. The good news is that I don't publish or study computational sciences so my total lack of understanding of the space lets me not give a fuck if I'm right or wrong. My belief is that the basic binary approach of modern computer systems is what is making us scared of traveling sales men … WTF do I mean by that you ask? It means that modern computer systems think in ones and zeros and only know how to do some base operators on those ones and zeros (even CISC and vector processors are still reduced down to 1 and 0 of a transistor ...)… At the root of all computer operations is the need to calculate and store a one or a zero result in a register…. Hence why most computational sciences has a run-time if polynomial. Because at its core so is a microprocessor (pun intended). Let's put a pin in that idea.
What if we had a computational system that was not based on a Turing architecture but instead could use algorithms that didn't need intermediate resolution… what if we had an architecture to store a equation state and compare it to another equation state without ever calculating or resolving either state or even the final resolution… I hear of three options to solve P!=NP problems and #2 is 'innovative':
1) The current computer architecture scales out to the point the calculation capability overcomes the need for efficiency… an example of this would be the the latest heterogeneous HPC architecture. In these systems a relatively limitless number (think millions) of cell processors (Playstation3 volume has made them super cheap) lightly coupled via FPGA directly to an infiniband backbone. In short, the system has a relatively limitless amount of vector processing capabilities. The system can take a sloppy algorithmic approach of "dropping it's unit on the table" and just calculate the vector space around any vectorized input (NLP, etc). Rainbow table based cracking isn't cracking... it is just a form of bruit force. This is just slightly more intelligent than that... but not much.
2) What if we go way outside the box and build a new architecture that is not based on 1 or 0. Two examples would be: 1) Quantum computer, 2) Bio-Computer. In these systems rather than having a 0 or a 1 the computational system is based on two input equation states and storing a result without necessarily being able to calculate or resolve either input function. Clearly not polynomial. If one is calculating the NP-Hard problem of "cliches" one could imagine all sorts of ways to do this within biological systems.
3) Fuck… I forgot what the third option was.. it was based on extreme parallel Processor In Memory in a model that was similar to a neurological system. However the more I think about that it sounds like #1 above…
Early in my career… back when I did real work … I helped build 'big' systems (#1 above) … I started my afternoon trying to read a paper on emerging architectures in the 2nd space… but it's been a few hours and I'm on page 2…
The last few years I've been focused on how a modern understanding of reality (understand something before you believe it) has evolved into post-modern understanding that Truth is relative to the point Truth is not an answer but can have an expression based on a question…
Summary: Modern computer architecture is like modern philosophy and
emerging alternative architectures (Quantum/bio) are analogous to
post-modern philosophy and function of 'love' in emergent christianity…
Love is a state, it is no longer a 1 for the 0 to scapegoat.
No comments:
Post a Comment