> 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.
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.