New answers tagged

0 votes

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 ...
user avatar
  • 93
2 votes
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 ...
user avatar
  • 141k
3 votes

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 ...
user avatar
  • 141k
3 votes
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}}$, ...
user avatar
  • 141k
-1 votes

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 ...
user avatar
  • 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.
user avatar
  • 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 ...
user avatar
  • 174
0 votes

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 ...
user avatar
  • 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.&...
user avatar
  • 25.2k
0 votes

How could NP-complete problems be in P?

$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 ...
user avatar

Top 50 recent answers are included