Timeline for Proof plan for P ≠ NP
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 20, 2021 at 15:16 | comment | added | nir shahar | No need to apologize, its good to brainstorm (even ideas you know you wont be able to solve!), and its even better to discuss your ideas with other people :) I simply tried to provide the explanation of where such an argument falls. Now its your job to figure out if you can solve this problem and how (or just ponder on why it is so difficult) | |
| May 20, 2021 at 13:39 | comment | added | Brian | Will you people puh-leeeze get it through your heads that it's just an idea. It's completely unobvious that such a formula would exist, I agree. I'm just brainstorming. I don't need someone to tell me what I have to think about first and what I have to think about second. Obviously I've come to the wrong place. This was a mistake, I apologize. | |
| May 20, 2021 at 12:03 | comment | added | nir shahar | Then you need to properly define them before you start using them. Its not obvious why such formula exist, and even less obvious (if it is even possible) to write them in some short formula | |
| May 20, 2021 at 10:54 | comment | added | Brian | We would need a new way to represent computations of M (not all computations, just some special ones). If the formula is of length n and M is bounded by n^k, then the length of the computation would be n^k in the worst case. I agree, a formula of length n can't handle something of size n^k. We couldn't just list the transitions or have a computation tableau. We would need an entirely new method. The number 2^10^10^80 has more digits than there are particles in the universe, but we can represent it in a concise way. We would have to do something similar for M. | |
| May 20, 2021 at 6:54 | comment | added | nir shahar | if $\Phi_k^n$ is of length $n$ then it represents a computation of $M$ on some extremely short input, something that is way smaller than $n$. | |
| May 19, 2021 at 23:10 | comment | added | Brian | The length of phi_k by definition is n. I'm using n to represent the length of the input. The variable n doesn't represent anything else. The idea is to represent this particular path of M in a short way. It would have to be something new. I don't know how to do it, I'm just tossing around the idea. | |
| May 18, 2021 at 22:02 | comment | added | nir shahar | Yes, the problem is that you cant have the length of the representation of $\Phi_k^n$ to be $n$, but also to contain the expression of $M(\phi)=false$ for $\phi$ of length $n$, since that expression is most likely to take up at least $n^k$. | |
| May 18, 2021 at 21:35 | comment | added | Brian | I haven't figured out how to properly format my responses yet, my apologies. First of all, this is not a proof, it's not remotely close to being a proof, it's just an idea. When I say that the length of phi_k is n, I mean that the length of the representation of phi_k is n. | |
| May 18, 2021 at 21:01 | history | answered | nir shahar | CC BY-SA 4.0 |