Polynomial-time solvable
Polynomial-time solvable: there is an algorithm in $\mathcal{O}(n^k)$ (where $n$ is the input size, for some constant $k$) that can correctly solve the problem.
$\mathcal{P}$: set of polynomial-time solvable problems
Compleness definition
Let $C$ be a set of problems. A problem $\pi$ is $C$-complete if
- $\pi \in C$
- Every problem in $C$ reduces to $\pi$
$\mathcal{NP}$-complete
A problem is in $\mathcal{NP}$ if
- Solutions always have length polynomial in the input size
- porposed solutions can be verified in polynomial time
Every problem in $\mathcal{NP}$ can be solved by brute force search in exponential time
Which of the following statements cannot be true, given the current state of knowledge?
Some NP-complete problems are polynomial-time solvable, and some NP-complete problems are not polynomial-time solvable.
Let TSP1 denote the following problem: given a TSP instance in which all edge costs are positive integers, compute the value of an optimal TSP tour. Let TSP2 denote: given a TSP instance in which all edge costs are positive integers, and a positive integer T, decide whether or not there is a TSP tour with total length at most T. Let HAM1 denote: given an undirected graph, either return the edges of a Hamiltonian cycle (a cycle that visits every vertex exactly once), or correctly decide that the graph has no such cycle. Let HAM2 denote: given an undirected graph, decide whether or not the graph contains at least one Hamiltonian cycle.
If TSP2 is polynomial-time solvable, then so is TSP1. If HAM2 is polynomial-time solvable, then so is HAM1.
Assume that $P \neq NP$. Consider undirected graphs with nonnegative edge lengths. Which of the following problems can be solved in polynomial time? Hint: The Hamiltonian path problem is: given an undirected graph with $n$ vertices, decide whether or not there is a (cycle-free) path with $n−1$ edges that visits every vertex exactly once. You can use the fact that the Hamiltonian path problem is NP-complete. There are relatively simple reductions from the Hamiltonian path problem to 3 of the 4 problems below.
For a given source $s$ and destination $t$, compute the length of a shortest $t$ path that has exactly $n−1$ edges (or $+\infty$, if no such path exists). The path is not allowed to contain cycles. (Bellman-Ford)
Choose the strongest true statement.
All three of the other assertions are true.
Which of the following statements is true?
Consider a TSP instance in which every edge cost is the Euclidean distance between two points in the place (just like in Programming Assignment #5). Deleting a vertex and all of its incident edges cannot increase the cost of the optimal (i.e., minimum sum of edge lengths) tour. (Obviously, deleting one hop can only decrease the total weight).