# Tag Info

## New answers tagged np-complete

### Can you help me find some examples of 3co-SAT for 4 variables?

CNF is only used to describe problem formally, but it's kind of hard for human to understand it. Entailment is such tool that used to write "readable" formula. You can use propositional ...
• 93
Accepted

### CNF-SAT time complexity and input processing

No. The meaning of "polynomial-time" is "polynomial in the length of an input". We can still search for an algorithm that is efficient on short inputs. For instance, suppose we ...
• 141k

### Identifying easy subsets/instances of NP-hard problems?

This is a very broad topic. Every problem is a special case of some hard problem. For instance, most problems (both hard and easy ones) can be viewed as a special case of the halting problem, but ...
• 141k
Accepted

### Is this special case of the subset-product problem $\mathsf{NP}$-complete?

Yes, your problem is NP-complete, even when we restrict to the case where $t=1$. We will focus on the case $M=2^k$. Then $\mathbb{Z}_M^*$ is isomorphic to $\mathbb{Z}_2 \times \mathbb{Z}^{2^{k-2}}$, ...
• 141k

### Are all np-complete problems also np-hard?

No (unless you find a proof for it that will make you world famous as a mathematician and computer scientist). NP-complete problems are in NP and can be used to solve any problem in NP. NP-hard ...
• 25.2k
1 vote
Accepted

### Are all np-complete problems also np-hard?

A problem is said to be NP-complete if it is in both NP and NP-hard, so yes all NP-complete problems are also NP-hard.
• 296
1 vote

### If P=NP, are all P problems NP-complete?

In order to be NP-complete, the problem has to be also NP-hard. That means, there exists a polynomial-time reduction from SAT to the given problem. The mapping has to map all satisfiable instances of ...
• 174

### If P=NP, are all P problems NP-complete?

AYun's right. I was confused by the "trivial" instances in P because there is no mapping from SAT to an all-yes problem. Here is original Answer: $NPC\subset NP$, that's your possible ...
• 93
1 vote

### How could NP-complete problems be in P?

If a problem X is NP-complete, that means "I can solve any problem in NP by converting it into an instance of X that has the same YES or NO answer in polynomial time, and solving that instance.&...
• 25.2k
$NP$-complete problems are the hardest problems in $NP$ with regard to the time required to solve them. Despite more than 50 years of research, nobody was able to design a polynomial time algorithm to ...