Skip to main content
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