⬆️ ⬇️

Humor in programming: P, NP and Turing machines

What do we do most of the time? We write code - we apply mathematics to reality, we twist algebra with language constructs and create new and interesting things.



But for some reason we often forget that the laws of the relationship of numbers to each other and the algorithms studied - the world does not end and the reality is much more complicated and multifaceted. This is especially noticeable in conditions of fuzzy requirements, tight deadlines and a changing market.



We forget that while scientists have once again made noise around neural networks and are trying to teach them, we daily learn our internal recurrent neuron (brain) at speeds close to light - by debugging a program or banal fixes bugs.

')

And sometimes people invent things that are very divorced from reality - like a non - deterministic Turing machine and the question is why? :-)







Will the theory help?



Any silicon general is an experienced programmer who knows well that it is never at first clear what they are going to code. And the smarter the developer, the more he sees the ambiguities and muddy spots. And often there is more politics here than engineering, especially from the management side - to do yesterday, I don’t know what, but the client should be pleased.



And the theoretical knowledge of algorithms and their complexity, classes of problems, excellent, beloved, but ... "toy", albeit scientific ones, fade into the background. In the foreground - the premonition of the development of architecture, the choice of the necessary and reliable libraries, people, atmosphere, iron.



In the first place - to be able to stop in time, not to get carried away by code and beauty. Stop and release as soon as possible while the market is ready!



Once upon a time you admired pictures similar to this one from the theory of algorithms :



She was fascinated - progressive science! Damn, having learned how to solve an NP-complete puzzle, it will be possible to reduce other difficult tasks to it and find faster algorithms! Cool. And if “P = NP”, then you can find a polynomial algorithm for reboring and other space tasks and cryptography will collapse to hell.



However, over time, everything is understood on an intuitive level and is expressed in simple words. Why we were loaded with complex terms, if it could be easier to explain? Who else is not in the subject, I remind you that tasks can be solved in polynomial time “P” on a regular Turing machine (remember the polynomial, squares, cubes in total can be) and, sorry for “nonsense,” for a polynomial time on a non-deterministic Turing machine "NP" :-) i.e. if we are able to simultaneously sort through all the options (and no one can yet do quantum computers, either).



Recall at once that the Turing machine is a crudely good old adding machine:





And someone can naively believe in the capabilities of quantum computers - what if they can solve NP-problems better (although it is known that not everything is good there, as expected). But gradually it becomes both scary and funny from the classics. Tell the performance expert or just a highload developer about the polynom - yes, he is ready to commit a crime in one quadratic time in the code :-)





How can you take seriously the ability to perform many tasks infinitely in parallel? Yes, MapReduce has moved a little in this direction, there is Apache Storm , there is a stretch of Apache Spark - but it’s very far from the idea of ​​a non-deterministic Turing machine. This is clearly seen when these terabytes and algorithms do not work stupidly in the forehead for a reasonable time, taking the same clustering of K-means on a million entities and the cluster will not help us much.



NP-hard and looping





When brute force on a “non-existent parallel machine” does not help, the problem becomes NP-hard (this is an inaccurate definition, but intuitive). The funny thing is that, attention, the task of determining whether the program will hang or not is NP-hard .



When the first time you find out about it, it's no laughing matter. People hear? Yes, the programmer solves such problems every day when debugging code! :-) Where did science go, how did it break away from reality.



Machine learning





Yes, there is also fun. With a bearded server , logistic regression, Bayes classifier, support vector machines, more or less figured out, learned, work well, and the implementation is not particularly difficult. There are also Markov models with algorithms to boot, but they are simple and understandable like cowards for a ruble twenty. But with the neural networks, the detective story turned out ... Few people understand well how to train them correctly at a reasonable time and how they make decisions later. And they regularly become fashionable and ... unfashionable . Another fashion - DeepLearning with the hit of the season sequence of learning on LSTM . And then Google has warmed up the situation with TensorFlow , although Torch and Theano are no worse and they have been known to everyone for a long time.



I clearly think what machine learning is used for. A typical example: when, because of the complexity of the subject area, it is very difficult to analytically form a set of rules for solving a problem — an artificial robot-mathematician is created who pokes his face into the data until he learns how to work better than standard algorithms. No need to go far: half of the algorithms from Natural Language Processing are machine learning, because Well, the language of people is not described formally well, especially ours, Russian.



Yes, recurrent neurons have recently made a breakthrough and showed undeniably better results in speech recognition, images and a little in NLP , for example, in machine translation . Yes, there is a hope that we will teach neural networks to choose the right attributes for learning, because For now, look at the unscientific medieval numerological hardcore that is going on at kaggle.com without tears. It is sincerely a pity to spend time studying methods of unscientific poking using hard competitions.



Functional programming





What all went wrong with him. This is one of the convenient designs - sometimes convenient, yes. But even Scala does not abolish the good old OOP practice and presents lambdas only as a supplement.



The basis remains objects. Structuring his thoughts in essence and methods, hiding the implementation - the developer is able to reach victory, to realize his plans. And when there are many people, OOP helps not to step on its feet. If there were no tools for managing complexity and structuring, we would be confused in our own code and thoughts. Therefore - breathe deeply.



And Stroustrup is a good fellow, he was able to create a language both fast and applicable for large programs. And java is not bad. And while nobody can catch up with dynamic languages ​​in terms of flexibility.



Haskell is certainly smart, yes, but, unfortunately, from the category of higher space and non-deterministic arithmometers.



Practice





In general, it is clearly seen that in practice, the programmer almost every day has to solve hellish NP-hard tasks when debugging non-working code, fixing bugs, refining ever-changing requirements, refactoring and choosing architecture and libraries.



And managers solve even more complex algorithmic tasks - creating a creative atmosphere in a team, buying cookies and motivating employees.



While scientists are looking for ways to effectively train recurrent neural networks for pattern recognition, the programmer pumps his more complex neuron (brain) daily at speeds close to the speed of light and does not notice it.



And the theoretical knowledge of languages, algorithms, operating systems is broken about the harsh reality, where you need to know a lot from different areas, constantly weigh and evaluate risks and make the right decisions. And no one will ever give time to bring the task to perfection! Never.



What will help us in this difficult path, colleagues? Of course, a good mood, a positive team, an atmosphere of creativity and the ability to both work hard at work to the fullest, and to have a good rest. And remember, you need to be a fan of the code, to love software engineering, to live with it - and then we have every NP-hard and NP-very very hard task!



PS





And php7 is really good! And without jit cost. 1.5-2 times faster than steel and creates a load 2 times less on iron. Here is a surprise gift - thanks to the enthusiasts.



Good luck everyone! :-)

Source: https://habr.com/ru/post/281461/



All Articles