New answers tagged

2 votes

If $P=NP$, then $LCP \in P$

Given $k$ and the graph, determining whether there exists such a cycle of length $\ge k$ is a problem in NP. (Why? Because there exists a witness for yes-instances that can be checked in polynomial ...
D.W.'s user avatar
  • 159k
1 vote

How do you show that Cosmic Kite Problem is NP complete?

Hint: Reduce from Clique. To every node, connect a path of $k$ vertices.
Pål GD's user avatar
  • 16.1k
2 votes

Invertability of Karp reductions

The Berman-Hartmanis isomorphism theorem [1, p.312] says that poly-time invertible reductions exist between any two paddable NP-complete languages: If two NP-complete languages $A$ and $B$ are ...
Neal Young's user avatar
8 votes
Accepted

Why is 3-SAT used for proving NP-Completeness so often?

You can indeed use any known NP-Hard problem as a candidate for your reduction. In my opinion, it has more to do with the fact that 3-SAT (a variant of SAT) was originally proven to be NP-Hard (see ...
codeR's user avatar
  • 600
0 votes

Polynomial-Time Solvability Through NP-Completeness Reductions

Yes, that would be the case, and here is my argument. Suppose there is a polynomial time reduction problem $A$ to problem $B$. So basically, we have a mapping function $f$ that converts any input of ...
codeR's user avatar
  • 600
3 votes
Accepted

Prove "Vertex Cover OR Clique" is NP complete

You can easily reduce from clique as follows. First, notice that the clique problem remains NP-hard even if we restrict $k$ to lie in $3 \leq k \leq n$ (because outside this range the problem is ...
Tassle's user avatar
  • 2,522
2 votes

Quasi polynomial algorithm for np complete problem

Look at the definition given. Assume you have a quasi-polynomial algorithm that takes $2^{(\log n)^{1.1}}$ nanoseconds. This is less than if $n^2$ nanoseconds $ n \le 2 ^ { 2 ^ {10}} = 2^{1024}$. That ...
gnasher729's user avatar
1 vote

Quasi polynomial algorithm for np complete problem

Recall that quasi-polynomial-time algorithms have a running time upperbounded by $2^{O((\log{n})^c)}$ for some constant $c\in\mathbb{N}$. It has a separate complexity class QP. From wikipedia: The ...
codeR's user avatar
  • 600
4 votes
Accepted

Maximum Vertex Set With a Minimum Pairwise Distance Requirement in Directed Acyclic Graphs

[EDIT: updated answer to apply to directed acyclic graphs.] Lemma 1. This problem is equivalent, under approximation-preserving poly-time reductions, to Maximum Independent Set in undirected graphs. ...
Neal Young's user avatar

Top 50 recent answers are included