Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

# Questions tagged [np-complete]

Questions about the hardest problems in NP, i.e. of those that can be solved in polynomial time by nondeterministic Turing machines.

156 questions
Filter by
Sorted by
Tagged with
38 views

### Karp hardness of searching for a matching erosion

First, read the previous question: Karp hardness of searching for a matching cut As mentioned in the supposed-to-be-comment answer in that question, without the requirement of cardinality $k$, the ...
282 views

### Is selecting some of the sets such that their intersection is of size k NP-hard?

Given collection of sets S1,...,Sn and a positive number k. Is the problem of selecting some of the sets such that their intersection is of size k NP-hard? So far, I tend to believe it is so I tried ...
65 views

398 views

### Is the weighted transitive reduction problem NP-hard?

The transitive reduction problem is to find the graph with the smallest number of edges such that $G^t = (V,E^t)$ has the same reachability as $G=(V,E)$. When $E^t \subseteq E$ it is NP-complete. ...
988 views

### Decision Problem vs. Optimization Problem [duplicate]

Is the following statement correct? If a decision problem is NP-complete, the corresponding optimization problem can not be solved in polynomial time.
15k views

### Is legislation NP-complete?

I would like to know if there has been any work relating legal code to complexity. In particular, suppose we have the decision problem "Given this law book and this particular set of circumstances, is ...
19k views

### Are there NP problems, not in P and not NP Complete?

Are there any known problems in $\mathsf{NP}$ (and not in $\mathsf{P}$) that aren't $\mathsf{NP}$ Complete? My understanding is that there are no currently known problems where this is the case, but ...
8k views

### Rule of thumb to know if a problem could be NP-complete

This question was inspired by a comment on StackOverflow. Apart from knowing NP-complete problems of the Garey Johnson book, and many others; is there a rule of thumb to know if a problem looks like ...
10k views

### are NP Complete languages closed under any regular operations?

I have tried looking online, but I couldn't find any definitive statements. It would make sense to me that Union and Intersection of two NPC languages would produce a language not necessarily in NPC. ...
17k views

2k views

### Reducing directed hamiltonian cycle to graph coloring

The 3-SAT problem can be reduced to both the graph coloring and the directed hamiltonian cycle problem, but is there any chain of reductions which reduce directed hamiltonian cycle to graph coloring ...
3k views

### How are all NP Complete problems similar?

I'm reading few proofs which prove a given problem is NP complete. The proof technique has following steps. Prove that current problem is NP, i.e., given a certificate, prove that it can be verified ...
6k views

### Reduction from set cover problem to vertex cover problem

Although the reduction from vertex cover problem to set cover problem is quite simple, I did not find anywhere the reduction in the opposite direction. From the similarity in the type of problems, I ...
607 views

4k views

### What is practical difference between NP and PSPACE-complete?

Here's something that has puzzled me lately, and perhaps someone can explain what I'm missing. Problems in NP are those that can be solved on a NDTM in polynomial time. Now assuming P$\,\neq\,$NP, ...
419 views

### Time complexity of a problem inspired by palindromes

This was inspired by Bradshaw's question originally posted on Math.SatckExchange. EVEN PALINDROME: Input: Given a list of strings $[v_1, v_2, ... ,v_n]$ where $\Sigma |v_i|$ is even number. ...
1k views

### Why we can't have FPTAS for strong NP complete problems

I understood that we can apply FPTAS to the weak NP problems like 0-1 knapsack. But why we cant apply the same principle to the strong NP problems like bin packing? I also checked wiki page about the ...
2k views