Timeline for Undecidability problem by Rice Theorem
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 7 at 2:22 | comment | added | spaceisdarkgreen | @Ali.A To be more precise, if you can compute from the input an upper bound on the size (not number) of certificates that need to be checked for it, then it's decidable (if you just know "I need to check at most 50 certificates" that doesn't help you since those could be anything, as opposed to the very helpful "i need to check all certificates with length less than 50" which is an explicit set of $2^{49}$ strings to check). I don't know of a reference that explicitly says this. | |
| Jan 6 at 20:50 | comment | added | Ali.A | @spaceisdarkgreen thank you very much for your helpful answer. Just a question: Can you please provide me a link or the page number of a book or a book name to the theorem you are referring, if its possible for you. Tanks again | |
| Jan 6 at 20:17 | comment | added | spaceisdarkgreen | @Ali.A If there's some upper bound on the number of certificates that need to be checked that's computable from the input then it is decidable... yes that's a theorem. And this is the case for all NP problems. There is some polynomial $p(n)$ in the input size that bounds the time the verifier can take, so the verifier will only be able to look at the first $p(n)$ bits of the certificate, so you only need to check certificates of length $\le p(n)$ for inputs of size $n.$ | |
| Jan 6 at 20:09 | comment | added | Ali.A | @spaceisdarkgreen Thank you for your comments. Just final question: Actually I was wondering what if there are infinite number of certificates. So, is there any Theorem or such things that says there is an upper bound for the number of certificates or that is a condition that if it is the case that there would be an upper bound for number of certificates, then our NP problem is decidable. | |
| Jan 6 at 20:02 | comment | added | spaceisdarkgreen | @Ali.A (Note though this is using crucially that it is polynomial time verifiable not just verifiable, since in this former case we have an upper bound on the size of a certificate so only a finite number to check. It should make sense that this is the case for Hamiltonian path since there's only $|V-1|!$ cycle orders for the vertices we could propose. Verifiable (without any resource bounds) does not imply decidable since there are infinitely many certificates to check... it is equivalent to being semi-decidable.) | |
| Jan 6 at 14:41 | comment | added | spaceisdarkgreen | @Ali.A Worst case, you just brute force search through every possible value of the certificate and ask the verifier about each. If you find one that verifies, decide yes. If you get through all of them and it doesn't verify any, decide no. | |
| Jan 6 at 8:47 | comment | added | Ali.A | @spaceisdarkgreen Thank you for your answers. You said it in a very clear way. Now I see what you mean. Can you please tell me how I should define a TM that can decide an NP problem e.g. Hamitonian cycle problem? | |
| Jan 6 at 7:24 | comment | added | spaceisdarkgreen | @Ali.A I think you are confusing the input to the problem with the certificate. Say the problem is whether a graph has a Hamiltonian cycle. A verifier has two inputs, the problem input (a graph) and a certificate (a purported Hamiltonian cycle). The verifier, given a graph and a purported Hamiltonian cycle, verifies whether it is indeed a valid Hamiltonian cycle in this graph. We give the verifier the graph and a bunch of junk, and it says "no". Does that mean the decider should say "no", i.e. that there is no Hamiltonian cycle? | |
| Jan 6 at 6:58 | comment | added | Ali.A | @spaceisdarkgreen spaceisdarkgreen, thank you for your comment. But I still do not get what I am missing here. For Np problems, by definition, there is a verifier that can verify our answer to be correct or not. Is there a problem to use this verifier as a decider, by defining a TM that take an input and give it to verifier. Then if verifier said 'yes', we accept the answer and if it said 'no', we reject it? What is wrong here? Can you please correct it if its wrong? | |
| Jan 6 at 3:07 | comment | added | spaceisdarkgreen | @Ali.A How do we get from that to an algorithm deciding whether or not there is a correct solution? That’s the crucial missing step.(“Certificate” is just the official name for what you’re calling a “solution”.) | |
| Jan 5 at 18:34 | comment | added | Ali.A | My understanding is that provided a solution for our problem, we can check whether its correct or wrong solution in polynomial time, using an algorithm as a verifier. | |
| Jan 4 at 21:38 | comment | added | Alexey Romanov | What's your current understanding of what "verifiable in polynomial time" means? | |
| Jan 4 at 20:31 | comment | added | Ali.A | thank you for your very helpful answer. However, I do not understand what you mean by ''it needs a certificate as well'' and my argument is not sufficient in proving NP problems are decidable. Can you explain more pls? | |
| Dec 30, 2024 at 6:13 | vote | accept | Ali.A | ||
| Dec 29, 2024 at 16:18 | history | answered | Alexey Romanov | CC BY-SA 4.0 |