P =/= NP due to symmetry breaking
!!qEeBALi+hGB No.13058694 ViewReplyOriginalReport
Quoted By: >>13058753 >>13058772 >>13058841 >>13059273 >>13060392
I think I just, no lie, no kappa, found a possible intuitive explanation of why P might not equal NP due to a sort of 'symmetry breaking' in data structures. This example will use depth first search (dfs) and breadth first search (bfs) to explain.
So, I'm sure /sci/ knows, the dfs algorithm can be written using just recursion rather elegantly (no auxillary structure used). And that kind of makes sense, because recursion is inherently a stack structure. You can also write the dfs algorithm with an explicit stack structure built into it without using recursion, and it all still works. Well, if you take that very same algorithm but swap out the stack with a queue, you get bfs! Very nice. But now, you can't really "go back" and write bfs without an explicit queue structure using recursion, because as stated before, recursion is inherently a stack and not a queue.
Somewhere along the way, interchanging a stack and a queue "broke" our ability to implement recursion. My theory is, this breaking in "recursive symmetry" results in an emergent phenomenon of time complexity.
In short: Can write dfs recursively => Can write dfs with a stack => Can write bfs with a queue => Cannot write bfs recursively because recursion is inherently a stack and not a queue => Broken "recursion symmetry" => Time complexity arises.
I realize this isn't a proof, but I hope this can be used as a starting point to intuitively understand why P =/= NP
So, I'm sure /sci/ knows, the dfs algorithm can be written using just recursion rather elegantly (no auxillary structure used). And that kind of makes sense, because recursion is inherently a stack structure. You can also write the dfs algorithm with an explicit stack structure built into it without using recursion, and it all still works. Well, if you take that very same algorithm but swap out the stack with a queue, you get bfs! Very nice. But now, you can't really "go back" and write bfs without an explicit queue structure using recursion, because as stated before, recursion is inherently a stack and not a queue.
Somewhere along the way, interchanging a stack and a queue "broke" our ability to implement recursion. My theory is, this breaking in "recursive symmetry" results in an emergent phenomenon of time complexity.
In short: Can write dfs recursively => Can write dfs with a stack => Can write bfs with a queue => Cannot write bfs recursively because recursion is inherently a stack and not a queue => Broken "recursion symmetry" => Time complexity arises.
I realize this isn't a proof, but I hope this can be used as a starting point to intuitively understand why P =/= NP
