Skip to content

Comment on The 2-MAXSAT Problem Can Be Solved in Polynomial Timeparent

Comments

A decision problem as used to define the classes NP and P is of the form: does there exist an x such that F(x) = 1, where F is a P-time computable function.

If you can solve that problem in P-time then you can also solve the functional version (find an x for which F(x) = 1) in P-time simply by setting each bit to a value for which the decision problem is satisfiable, one by one.

AboutSource Built by g1lg1l

Hackerly is an independent reader for Hacker News, built on the public HN API. Not affiliated with Y Combinator.