Linked Questions

5
votes
2answers
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 ...
262
votes
7answers
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 ...
26
votes
2answers
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. ...
29
votes
1answer
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, ...
1
vote
1answer
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 ...
3
votes
2answers
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 ...
2
votes
2answers
3k 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$. ...
27
votes
2answers
8k views

Optimization version of decision problems

It is known that each optimization/search problem has an equivalent decision problem. For example the shortest path problem optimization/search version: Given an undirected unweighted graph $G ...
0
votes
0answers
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 ...
-2
votes
2answers
2k views

complexity of decision problems vs computing functions [closed]

This is an area that admittedly I've always found subtle about CS and occasionally trips me up, and clearly others. recently on tcs.se a user asked an apparently innocuous question about N-Queens ...
1
vote
0answers
25 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 ...
1
vote
0answers
329 views

Does FNP-complete = NP-complete?

I can't seem to find this stated explicitly anywhere, which makes me wonder if I have it all wrong. So first, let's say we view problems in NP as degenerate problems in FNP, where the codomain of the ...
5
votes
0answers
635 views

Time complexity of finding the largest factor of a number (using a specific oracle)

My question is related to this question posted on math.SE: Given an odd number, what is the quickest (constant-time) algorithm for finding its largest factor and suppose you can call a helper ...
2
votes
0answers
133 views

Why are optimization problems always NP-hard and not NP-complete and what does this mean for other levels of the polynomial time hierarchy? [duplicate]

I have read that optimization problems cannot be $\mathcal{NP}$-complete, but are always classified as $\mathcal{NP}$-hard. When a problem is NP-complete, I know it is contained in $\mathcal{NP}$P. ...
4
votes
1answer
561 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}$-...

15 30 50 per page