19 questions linked to/from Optimization version of decision problems
1 vote
3k views

If the decision problem can be solved in poly time, show the optimization problem also can [duplicate]

Here is a problem I am trying to solve: The bin packing decision problem is defined as follows: given an unlimited number of bins, each of capacity equal to $1$, and $n$ objects with sizes $s_1$, ...
2k views

Decision Problem vs. Optimization Problem [duplicate]

Is the following statement correct? If a decision problem is NP-complete, the corresponding optimization problem can not be solved in polynomial time.
1 vote
30 views

Is it possible to do reductions with non-decision problems? [duplicate]

I've recently begun studying reductions in my algorithms class. All the reductions I've seen have been from decision problem $\to$ decision problem. Is it possible to do reductions with non-decision ...
• 143
11 views

Is maximising (or minimising) something enough to say that I am solving a decision problem? [duplicate]

We know that every optimisation problem has an equivalent decision problem. So say I keep going up a mountain (I.e. I am maximising my altitude) following a certain number of finite steps (similarly ...
• 109
5k views

Decision problems vs "real" problems that aren't yes-or-no

I read in many places that some problems are difficult to approximate (it is NP-hard to approximate them). But approximation is not a decision problem: the answer is a real number and not Yes or No. ...
• 20.7k
14k 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. ...
7k views

Is MAX-SAT NP-hard?

Is the MAX-SAT problem NP-hard? From the Wikipedia page: The MAX-SAT problem is NP-hard, since its solution easily leads to the solution of the boolean satisfiability problem, which is NP-complete ...
4k 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 ...
4k views

Decisional problems vs Optimization problems : NP-COMPLETE vs NP-HARD

I'm studying some of computation theory and i encounter a big question mark. I have an optimization problem and i have to proof that is NP-HARD. I know that my problem can be reduced to another np-...
• 131
681 views

NP-Hard problems which are not NP-Complete

Is it always true that a problem which is ${\sf NP}$-hard but not ${\sf NP}$-complete is an optimization problem such as Minimum-Vertex-Cover and many others. Is it always true that a ${\sf NP}$-...
• 365
2k views

Is the longest Hamiltonian cycle NP-complete?

As I understand it to prove something is NP-complete you have to show that it's NP-hard by reducing and a known NP-complete problem to your problem and also prove that it is in NP which you do showing ...
1k views

Is it necessary for NP problems to be decision problems?

Professor Tim Roughgarden from Stanford University while teaching a MOOC said that solutions to problems in the class NP must be polynomial in length. But the wikipedia article says that NP problems ...
• 1,545
6k views

TSP decision problem vs TSP optimization problem

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$. ...
• 31
279 views

Does NP-completeness require to find the solution?

In the paper "Computing Equilibria:A Computational Complexity Perspective" by Tim Roughgarden, they consider the problem: Problem 2.1 (Clique). Given a graph $G = (V, E)$ and an integer $k$: if ...
• 215
Consider the set cover problem: given a collection of sets ${\cal U}$ whose elements come from $\{1, \ldots, m\}$ find the smallest number of sets in ${\cal U}$ whose union is all of $\{1, \ldots, m\}$...