New answers tagged np-complete
0
For every integer k, take the travelling salesman problem with n > 1 cities where n is a power of k. (Picked the problem that way because all the instances are distinct, so we can say with good conscience that these are distinct problems).
1
As far as I can tell the earliest mention of the procedure you outline, later described in the literature as variable elimination by clause distribution, was in the paper "ZRes: The old Davis-Putnam procedure meets ZBDD" by Philippe Chatalic and Laurent Simon. The procedure was described again, along with other formula simplification techniques, in "...
2
Yes, such problems can be NP-complete.
Consider classical NP-complete graph problems like clique.
Clique has an $O(2^n)$ time algorithm, where $n$ is the number of vertices. However the input for clique is the adjacency matrix of the graph, which has $n^2$ bits. Therefore when the size of input is measured in bits, clique has an $O(2^\sqrt{n})$ time ...
1
If I may make an assumption, you want such a reference to be able to put it in one of your works, right ? I don't why you would wanna do that as if you have a problem A, reducting a NP Hard problem to problem A quite clearly shows that A is NP Hard. No one bothers proving it as it's such a straightforward and fundamental result. If you need to prove it for ...
0
First note that $\overline X$ is $\operatorname{co\mathcal{NP}}$-hard since $X$ is $\mathcal{NP}$-hard (try to see why).
Since 3SAT is in $\mathcal{NP}$, any problem that can be reduced to 3SAT is in NP as well. So the statement suggests that the $\operatorname{co\mathcal{NP}}$-hard language $\overline X$ is in $\mathcal{NP}$.
On the other hand, saying that ...
1
The $k$-clique problems asks whether there is a homomorphism from the $k$-clique to a given graph. Therefore in principle, given an instance $\langle G,k \rangle$ of $k$-clique, you can just output $\langle K_k, G \rangle$, which is an instance of graph homomorphism.
However, in general $\langle K_k, G \rangle$ could be much larger than $\langle G,k \rangle$...
3
Since $P \subseteq NP$, if the statement is false, it cannot become true by changing $P$ to $NP$.
What your teacher is doing here is trying to illustrate a very common fallacy amongst beginning CS-learners. He is giving one potential way to solve a problem, and he notes that this way needs more resources than we want to make available (sometimes it is ...
3
Very simple: We can sort an array without checking every possible permutation. (Many times we don’t check any permutation of the array, we just re-arrange the order of items so we can guarantee the array is sorted, without ever checking it. )
2
You had several questions in there, let's just look at a couple of them, the way I understood you.
Is $L \in \textsf{NP} \cap \textsf{coNP}$ "easier" than problems that are $\textsf{NP}$-hard?
Yes, we believe it is (but as gnasher729 points out in a comment, we don't know for sure; $\textsf{NP}$ could still be equal to $\textsf{P}$, in which case the ...
9
As written, the question is a bit trivial: if NP = NP-complete, then since P $\subseteq$ NP we get P=NP since every problem in P would be NP-complete.
I suspect what's meant, though, is the following:
Suppose there are no NP-intermediate problems; that is, that every problem in NP is either in P or is NP-complete. What does that tell us about P vs. NP?
...
1
I don't think you're likely to find any such proof. Given our current level of knowledge, as far as we know it is possible that $\textsf{P} \ne \textsf{NP}$ but $\textsf{NP} = \textsf{co-NP}$ (we cannot prove otherwise). If that were true, then we'd have $\textsf{NPC} = \textsf{co-NPC}$ (and thus $\textsf{NPC} \cap \textsf{co-NPC} \ne \emptyset$) yet $\...
5
The problem in which you must select $k$ vertices to maximize the number of vertices dominated is known as the budgeted dominating set problem. The problem or its connected variant is studied at least by Lamprou, Sigalis and Zissimopoulos [1] and Khuller, Purohit and Sarpatwar [2]. It also appears in the recent survey of Narayanaswamy and Vijayaragunathan [3]...
1
Yes, that's correct. You'll probably have to figure out the polynomial yourself. The way to find the polynomial is to look at the reduction, and from that you should be able to deduce a polynomial.
In your case, I believe there is a reduction from 3D-MATCHING to 3PARTITION, so you would analyze that reduction to find the polynomial. Given an instance of ...
Top 50 recent answers are included
