Linked Questions

1 vote
1 answer
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$, ...
user2237160's user avatar
0 votes
1 answer
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.
Peter's user avatar
  • 1
1 vote
0 answers
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 ...
jaynp's user avatar
  • 143
0 votes
0 answers
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 ...
Jerome's user avatar
  • 109
40 votes
3 answers
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. ...
Ran G.'s user avatar
  • 20.7k
30 votes
5 answers
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. ...
Aniket Schneider's user avatar
5 votes
1 answer
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 ...
John Threepwood's user avatar
5 votes
2 answers
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 ...
John Threepwood's user avatar
3 votes
1 answer
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-...
rollotommasi's user avatar
5 votes
1 answer
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}$-...
aghost's user avatar
  • 365
2 votes
2 answers
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 ...
John Slaine's user avatar
4 votes
2 answers
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 ...
Nikunj Banka's user avatar
  • 1,545
2 votes
2 answers
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$. ...
Meliss's user avatar
  • 31
4 votes
1 answer
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 ...
seek's user avatar
  • 215
3 votes
1 answer
451 views

What is the Certificate for Set Cover?

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\}$...
Pete V.'s user avatar
  • 31

15 30 50 per page