3 ms·
It sounds very much like complexity theory, where you definitely have problems that are easier to verify than solve (see NP hard). I think you mean NP. NP hard
by chongli 8y ago
It sounds very much like complexity theory, where you definitely have problems that are easier to verify than solve (see NP hard).
I think you mean NP. NP hard includes problems that are not in NP, such as the halting problem.
I'm not aware of any proof that photorealistic 3D rendering is in NP. If it is not, then verifying 3D cannot be said to be easy.
- krastanov 8y agoNitpicking on your nitpick: you mean NP-complete, not NP (for instance, any P problem is an NP problem, but NP-complete problems are probably not P)
- mygo 8y agoYou’re correct, but I’m gonna have to nitpick your nitpick and say that NP-complete problems have not been proven (or disproven) to be in P. “Probably not” is an opinion.
- valvar 8y agoIt's a well-informed opinion that is based on the fact that what we do know indicates[1] that, probably, P≠NP. [1] https://en.wikipedia.org/wiki/P_versus_NP_problem#Reasons_to_believe_P_%E2%89%A0_NP https://en.wikipedia.org/wiki/P_versus_NP_problem#Reasons_to...
- mygo 8y agoPublish a paper with the mathematical proof. “probably not” is neither here nor there. The main argument from your link is nobody has found an efficient algorithm for any of the 3,000+ studied problems after all this time. And yet it’s also true that in the same span of time, nobody has been able to prove the that it’s not, either. No matter how hard they have tried. “probably not” is just an opinion. I’ll wait for the formal proof. Till then it simply is not known whether or not.
- deleted 8y ago[deleted]
- nothrabannosir 8y agoWell, not exactly regular NP, as was pointed out. I guess NP complete would make more sense. Although the set of problems that are easier to validate than solve reaches much further than NP complete; see basically any Σ in the polynomial hierarcy. It's about the existential quantifier.