Return to Answer

Megiddo and Vishkin proved that Minimum dominating set in tournaments is in $QP$. They showed that tournament dominating set has P-time algorithm iff SAT has subexponential time algorithm. Therefore, tournament dominating set problem can not be in $P$ unless the ETH is false.

It is very interesting to note that the exponential time hypothesis simultaneously implies that tournament dominating set can not have polynomial time algorithms and it can not be $NP$-complete. In other words, ETH implies that tournament dominating set is in $NP$-intermediate.

Woeginger suggests a candidate problem solvable in quasi-polynomial time and probably does not have polynomial time algorithms: Given $n$ integers, can you select $\log n$ of them that add up to $0$?

Megiddo and Vishkin proved that Minimum dominating set in tournaments is in $QP$. They showed that tournament dominating set has P-time algorithm iff SAT has subexponential time algorithm. Therefore, tournament dominating set problem can not be in $P$ unless the ETH is false.

It is very interesting to note that the exponential time hypothesis simultaneously implies that tournament dominating set can not have polynomial time algorithms and it can not be $NP$-complete. In other words, ETH implies that tournament dominating set is in $NP$-intermediate.

Woeginger suggests a candidate problem solvable in quasi-polynomial time and probably does not have polynomial time algorithms: Given $n$ integers, can you select $\log n$ of them that add up to $0$?

Megiddo and Vishkin proved that Minimum dominating set in tournaments is in $QP$. They showed that tournament dominating set has P-time algorithm iff SAT has subexponential time algorithm. Therefore, tournament dominating set problem can not be in $P$ unless the ETH is false.

It is very interesting to note that the exponential time hypothesis simultaneously implies that tournament dominating set can not have polynomial time algorithms and it can not be $NP$-complete. In other words, ETH implies that tournament dominating set is in $NP$-intermediate.

Megiddo and Vishkin proved that Minimum dominating set in tournaments is in $QP$. They showed that tournament dominating set has P-time algorithm iff SAT has subexponential time algorithm. Therefore, tournament dominating set problem can not be in $P$ unless the ETH is false.

It is very interesting to note that the exponential time hypothesis simultaneously implies that tournament dominating set can not have polynomial time algorithms and it can not be $NP$-complete. In other words, ETH implies that tournament dominating set is in $NP$-intermediate.

Woeginger suggests a candidate problem solvable in quasi-polynomial time and probably does not have polynomial time algorithms: Given $n$ integers, can you select $\log n$ of them that add up to $0$?

Megiddo and Vishkin proved that Minimum dominating set in tournaments is in $QP$. They showed that tournament dominating set has P-time algorithm iff SAT has subexponential time algorithm. Therefore, tournament dominating set problem can not be in $P$ unless the ETH is false.

Megiddo and Vishkin proved that Minimum dominating set in tournaments is in $QP$. They showed that tournament dominating set has P-time algorithm iff SAT has subexponential time algorithm. Therefore, tournament dominating set problem can not be in $P$ unless the ETH is false.

It is very interesting to note that the exponential time hypothesis simultaneously implies that tournament dominating set can not have polynomial time algorithms and it can not be $NP$-complete. In other words, ETH implies that tournament dominating set is in $NP$-intermediate.