News for hackers. Stuff that matters.
Re: by nabla9 on Tuesday April 30, 2024 @04:46AM (#40208636)
Translating a new problem to any problem that has already been proven to belong to that complexity class suffices.
Re: by Daimanta on Tuesday April 30, 2024 @06:58AM (#40209574)
It's the other way around. Translating a problem with a known complexity class to the new problem(in time P) indicates the complexity class.