I have been reading about P vs NP. I wrote down my…
0 reactions
I have been reading about P vs NP. I wrote down my intuition for why I think P ≠ NP. I know this isn’t a rigorous proof, and I’m not claiming I’ve solved the problem. I’d really appreciate feedback on where my reasoning fails or what concepts I’m missing
My take for why P is not equal to NP comes from what I believe is a fundamental difference between solving a problem and verifying its solution.
Take Sudoku as an example. If someone gives me a completed puzzle I can quickly check every row column and box to make sure the rules are satisfied. That verification process is straightforward.
Now compare that with solving the same puzzle from a blank grid. There is no obvious path to the answer. I may have to test many possibilities before finding the correct one. Solving appears much more difficult than verifying.
This same pattern appears in many other problems.
If someone gives me the password to a computer I can check it in less than a second. Finding the password without knowing it may require an enormous search.
If someone gives me the correct path through a complicated maze I can follow it and confirm that it reaches the exit almost immediately. Finding that path from the beginning can take much longer.
If someone hands me a completed school timetable I can check whether every class every teacher and every room satisfies the rules. Creating that timetable from scratch is much more difficult.
Another example (which i believe is the strongest and closest to being an actual proof) is finding the shortest route between two points. If I asked someone to find the shortest possible route they would have to compare many different routes and work out which one is actually the shortest. That could take a long time depending on how many possible paths there are. Now imagine someone has already done all of that work and gives me a list of every route with its distance such as 1 km 2.7 km 4.1 km and 6.8 km. I can immediately look at the list or the map and verify that the 1 km route is the shortest. Once again verifying the answer is much easier than finding it in the first place.
Because this pattern appears so consistently I suspect there is a real separation between solving and verifying. My take is that this separation is not simply a limitation of current algorithms but a fundamental property of computation itself.
In simple words if one problem follows the idea that solving it is fundamentally harder than verifying it then P cannot equal NP because P equals NP would have to hold for every problem in NP not just some of them.
#technology
source
My take for why P is not equal to NP comes from what I believe is a fundamental difference between solving a problem and verifying its solution.
Take Sudoku as an example. If someone gives me a completed puzzle I can quickly check every row column and box to make sure the rules are satisfied. That verification process is straightforward.
Now compare that with solving the same puzzle from a blank grid. There is no obvious path to the answer. I may have to test many possibilities before finding the correct one. Solving appears much more difficult than verifying.
This same pattern appears in many other problems.
If someone gives me the password to a computer I can check it in less than a second. Finding the password without knowing it may require an enormous search.
If someone gives me the correct path through a complicated maze I can follow it and confirm that it reaches the exit almost immediately. Finding that path from the beginning can take much longer.
If someone hands me a completed school timetable I can check whether every class every teacher and every room satisfies the rules. Creating that timetable from scratch is much more difficult.
Another example (which i believe is the strongest and closest to being an actual proof) is finding the shortest route between two points. If I asked someone to find the shortest possible route they would have to compare many different routes and work out which one is actually the shortest. That could take a long time depending on how many possible paths there are. Now imagine someone has already done all of that work and gives me a list of every route with its distance such as 1 km 2.7 km 4.1 km and 6.8 km. I can immediately look at the list or the map and verify that the 1 km route is the shortest. Once again verifying the answer is much easier than finding it in the first place.
Because this pattern appears so consistently I suspect there is a real separation between solving and verifying. My take is that this separation is not simply a limitation of current algorithms but a fundamental property of computation itself.
In simple words if one problem follows the idea that solving it is fundamentally harder than verifying it then P cannot equal NP because P equals NP would have to hold for every problem in NP not just some of them.
#technology
source
| 4,000 mlx | |
| 4 | |
| 0 |