On: Simplicity is an advantage but sadly complexity se...

[hammock]

I saw a 2x2 matrix recently that showed how NP-hard problems require exponential time to solve but polynomial time to verify the solution. It gave examples for every other cell of the matrix besides (exponential time to solve, exponential time to verify), which it left as blank or N/A.

I think we have found something that fits that square: truly simple solutions. It's easy to come up with a simple solution that is unsatisfactory, that's not what I'm talking about.

I mean a solution that is so simple and complete, that it was HARD to come up with. It's easy to verify that such a solution is simple, sure, but it is HARD to verify that the solution is truly complete or satisfactory

[kibwen → hammock]

> It gave examples for every other cell of the matrix besides (exponential time to solve, exponential time to verify), which it left as blank or N/A.

I would be interested in seeing this matrix, because it sounds incomplete to me.

Any NP-complete problem, as in a problem that is exponential to solve but polynomial to verify, is a "decision problem" version of a "optimization problem" that is exponential to both solve and verify.

For example, the decision-problem version of the traveling salesman is, "given a graph of nodes and weighted edges, does there exist a route that visits all nodes with a total edge cost of less than N?" Solutions are hard to compute (evaluate many paths to find a good solution) but easy to verify (evaluate the given path exactly once and compare the cost to N).

Meanwhile, the optimization-problem version of the traveling salesman is "given a graph of nodes and weighted edges, what is the route that visits all edges with the least cost?" The solution is now both hard to compute and hard to verify, because to verify it you also need to consider the entire decision space to determine whether or not there's a route with a lesser cost.