3k views

### Optimization problem vs decision problem - reduction

Assume we have an optimization problem with function $f$ to maximize. Then, the corresponding decision problem 'Does there exist a solution with $f\ge k$ for a given $k$?' can easily be reduced to ...
122k views

### What is the definition of P, NP, NP-complete and NP-hard?

I'm in a course about computing and complexity, and am unable to understand what these terms mean. All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea ...
7k views

### “NP-complete” optimization problems

I am slightly confused by some terminology I have encountered regarding the complexity of optimization problems. In an algorithms class, I had the large parsimony problem described as NP-complete. ...
10k views

### How hard is counting the number of simple paths between two nodes in a directed graph?

There is an easy polynomial algorithm to decide whether there is a path between two nodes in a directed graph (just do a routine graph traversal with, say, depth-first-search). However it seems that, ...
123 views

### What is the usage of a decision problem for an optimization problem like the longest path problem?

I just read this definition for the longest path problem: LONGEST PATH Input: A graph $G=(V,E)$, an integer $k$. Question: Is there a path with at least $k$ vertices in $G$ This seems a ...
500 views

### Do all algorithms aim to solve decision problems?

An algorithm is a “unambiguous specification of how to solve a class of problems... calculation, data processing and automated reasoning tasks” Are the class of problems an algorithm can solve more ...
Let's check together whether the TSP-decision problem is NP-complete. Maybe it will help me to understand things better. Question for TSP-decision problem: Given n cities and a tour from length $k$. ...