Re:Tricks That Can Outsmart Deepfake Videos for Now
by nothrabannosir on Saturday October 20, 2018 @11:31AM
(#18263700)
Well, 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.
Re:Tricks That Can Outsmart Deepfake Videos for Now
by krastanov on Saturday October 20, 2018 @10:58AM
(#18263552)
Nitpicking 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)
Re:Tricks That Can Outsmart Deepfake Videos for Now
by mygo on Saturday October 20, 2018 @11:25AM
(#18263669)
You’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.
Re:Tricks That Can Outsmart Deepfake Videos for Now
by valvar on Saturday October 20, 2018 @01:24PM
(#18264302)
It'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...
Re:Tricks That Can Outsmart Deepfake Videos for Now
by mygo on Saturday October 20, 2018 @09:40PM
(#18266367)
Publish 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.
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.