Timeline for Can someone explain why the MAX-CUT problem is in NP?
Current License: CC BY-SA 4.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 13, 2019 at 19:40 | comment | added | Juho | @anon.g The certificate has say a number 0 or 1 for each vertex, so it has length linear in the number of vertices. This is given to the verifier, which runs in time linear in the number of edges: check each edge, increment count if necessary, and at the end do the comparison against $k$. | |
| Mar 13, 2019 at 19:35 | comment | added | anon.g | Would the certifier/verifier just be a comparison of the count of number of edges and k, so something like verifier v(Count, k)? and what would the length of the certificate be? I'm thinking it would just be a number as it is the number of vertices right? | |
| Mar 13, 2019 at 19:27 | history | answered | Juho | CC BY-SA 4.0 |