Timeline for What is the computational complexity to verify a P solution with a deterministic Turing machine?
Current License: CC BY-SA 4.0
6 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Aug 27 at 14:38 | comment | added | XL _At_Here_There | Yes, there are several questions, and I have to ask about them respectively and clearly. | |
Aug 27 at 13:50 | vote | accept | XL _At_Here_There | ||
Aug 27 at 13:44 | comment | added | Emil Jeřábek | The question is unclear regardless of whether you personally have managed to guess the intended meaning. | |
Aug 27 at 1:00 | comment | added | Joel David Hamkins | I think the OP is asking what is the complexity of verifying that a given solution does in fact solve a given decision problem in P. And my answer is that this is actually very difficult, not even computably decidable. If this is indeed what the OP intends, then I suggest leaving it as is, but if not, then I agree the question is not clear enough and should be closed. | |
Aug 27 at 0:56 | comment | added | Sam Hopkins | The question is written in a very confusing way, but I think you might be misunderstanding what is being asked. To me the answer to "If we have a solution of P problems, what is the computational complexity to verify the solution with a deterministic Turing machine?" is "polynomial time complexity" simply because P is a subset of NP (which might be what the question-asker fails to see). Anyways I think the question should be closed unless it is edited to be more clear. | |
Aug 27 at 0:49 | history | answered | Joel David Hamkins | CC BY-SA 4.0 |