NP-Complete
A short story invented on the eve of mid-term on Algorithms and Data Structures instead of repeating lectures.
Having checked his calculations again, Marcus could not believe his eyes. The fact that he succeeded, just had to be a mistake. In the end, thousands of scientists tried to investigate this problem and in the end did not achieve anything.
Determined to discover a flaw in his reasoning, Marcus, in a few tens of minutes, wrote an algorithm for his theoretical constructions, full of confidence. The actual application of his theory will exactly give the wrong answer. What else can shed light on his mistakes, if not a direct implementation of his method on a real computer?
After several minor errors, the compilation was successful. Forgetting everything in the world, Marcus did not dare to launch the program for a full minute. “What will happen if it works, if it gives the right answer right here and now?” He thought. Finally, convincing himself that this was simply not possible, Marcus pressed the right key and immediately, frightened, closed his eyes.
')
A minute later, having ventured to look at the monitor, he looked at the number printed by the program in the console for a long time, unseeingly. “What a vile day? Maybe I am sleeping? ”Thought Marcus, staring at the bright pixels in the dark of the night in his old monitor.
Recovering from the stupor, he immediately took up the debugger, determined to find an error in his program. In fact, it cannot be that there are no errors in his program. It is very rarely possible to write an algorithm immediately and without bugs, and even in the third hour of the night, after spending several hours without a cup of coffee.
And yet, time after time, tracking his algorithm, Marcus became increasingly convinced that he was able to find an incredible method in its significance and simplicity, which would literally turn the world upside down. He was able to prove that others had long since ceased to be regarded as an actual scientific problem.
P = NP.
In order to finally convince himself, Marcus began to write a set of tests that solved NP-complete problems for small input data using classical re-selection algorithms and its new method. At the end of the calculations, the values ​​were compared, and if at least one solution did not match, the tests were considered unsuccessful.
Running tests and knowing that the results of his car would have to wait about 10 minutes, Marcus went to the kitchen to drink more coffee: the night promised would be long. Having a hard time waiting for the kettle to boil, he brewed a drink for himself and headed back to the computer with a cup of invigorating potion.
Seeing the man in black in his chair next to the computer, Marcus was not scared: he was too excited and too exhausted to be afraid. He just asked: “Who are you? What are you doing here? ”As if strangers climbed into his apartment every day.
“I’m just the one who is entrusted with executing orders and eliminating problems.” The black figure replied. “Despite what I have to do on duty, I never cease to admire people like you. It is a pity that we have to meet in such a situation. "
While still brewing his coffee in the kitchen, Marcus felt some weakness. Then he blamed it on physical and emotional exhaustion. Now he clearly understood what caused his condition. Unable to do anything else, he was able to ask the only question that most concerned him: “Why?”. The black man sighed sadly and replied: “What do you think yourself? Investment protection. Banks. Government. What else could it be? ”
Marcus began to lose his balance. The stranger picked him up, laid him on the bed, covered him with a blanket and said: “And the grandiose discoveries again disappeared today, but the grandiose shocks also disappeared. Society only won. Believe me, I know, I saw it. ”
A few minutes later, after the death of Marcus and the destruction of the computer, the mysterious person checked with his portable organizer and said quietly: "Leonid, object code - 10543, the beginning of the monitoring phase - after 2 days."
Having checked his calculations again, Marcus could not believe his eyes. The fact that he succeeded, just had to be a mistake. In the end, thousands of scientists tried to investigate this problem and in the end did not achieve anything.
Determined to discover a flaw in his reasoning, Marcus, in a few tens of minutes, wrote an algorithm for his theoretical constructions, full of confidence. The actual application of his theory will exactly give the wrong answer. What else can shed light on his mistakes, if not a direct implementation of his method on a real computer?
After several minor errors, the compilation was successful. Forgetting everything in the world, Marcus did not dare to launch the program for a full minute. “What will happen if it works, if it gives the right answer right here and now?” He thought. Finally, convincing himself that this was simply not possible, Marcus pressed the right key and immediately, frightened, closed his eyes.
')
A minute later, having ventured to look at the monitor, he looked at the number printed by the program in the console for a long time, unseeingly. “What a vile day? Maybe I am sleeping? ”Thought Marcus, staring at the bright pixels in the dark of the night in his old monitor.
Recovering from the stupor, he immediately took up the debugger, determined to find an error in his program. In fact, it cannot be that there are no errors in his program. It is very rarely possible to write an algorithm immediately and without bugs, and even in the third hour of the night, after spending several hours without a cup of coffee.
And yet, time after time, tracking his algorithm, Marcus became increasingly convinced that he was able to find an incredible method in its significance and simplicity, which would literally turn the world upside down. He was able to prove that others had long since ceased to be regarded as an actual scientific problem.
P = NP.
In order to finally convince himself, Marcus began to write a set of tests that solved NP-complete problems for small input data using classical re-selection algorithms and its new method. At the end of the calculations, the values ​​were compared, and if at least one solution did not match, the tests were considered unsuccessful.
Running tests and knowing that the results of his car would have to wait about 10 minutes, Marcus went to the kitchen to drink more coffee: the night promised would be long. Having a hard time waiting for the kettle to boil, he brewed a drink for himself and headed back to the computer with a cup of invigorating potion.
Seeing the man in black in his chair next to the computer, Marcus was not scared: he was too excited and too exhausted to be afraid. He just asked: “Who are you? What are you doing here? ”As if strangers climbed into his apartment every day.
“I’m just the one who is entrusted with executing orders and eliminating problems.” The black figure replied. “Despite what I have to do on duty, I never cease to admire people like you. It is a pity that we have to meet in such a situation. "
While still brewing his coffee in the kitchen, Marcus felt some weakness. Then he blamed it on physical and emotional exhaustion. Now he clearly understood what caused his condition. Unable to do anything else, he was able to ask the only question that most concerned him: “Why?”. The black man sighed sadly and replied: “What do you think yourself? Investment protection. Banks. Government. What else could it be? ”
Marcus began to lose his balance. The stranger picked him up, laid him on the bed, covered him with a blanket and said: “And the grandiose discoveries again disappeared today, but the grandiose shocks also disappeared. Society only won. Believe me, I know, I saw it. ”
A few minutes later, after the death of Marcus and the destruction of the computer, the mysterious person checked with his portable organizer and said quietly: "Leonid, object code - 10543, the beginning of the monitoring phase - after 2 days."
Source: https://habr.com/ru/post/361965/
All Articles