Linked Questions

27 votes
5 answers
18k views

What is meant by "solvable by non deterministic algorithm in polynomial time" [duplicate]

In many textbooks NP problems are defined as: Set of all decision problems solvable by non deterministic algorithms in polynomial time I couldn't understand the part "solvable by non deterministic ...
user5507's user avatar
  • 2,191
1 vote
1 answer
4k views

Why is SAT not in P? [duplicate]

I'm studing P and NP complexity classes. I like know, why is SAT not in P? Is it because I can not determine if any Boolean expression is satisfiable?
juaninf's user avatar
  • 503
0 votes
1 answer
3k views

Proof of P ⊆ NP [duplicate]

What is the proof of P ⊆ NP? I cannot happen to find a good explanation for it. I read that the verifier will just ignore the proof and accept any proof if the ...
Harshil Sharma's user avatar
2 votes
2 answers
812 views

Which NPC problems are NP Hard [duplicate]

I have read that TSP and Subset Sum problems are NPC problems which are also NP Hard. There are also problems like Halting Problem which is NP Hard, but not NP Complete And Wikipedia defines this as ...
user5507's user avatar
  • 2,191
2 votes
1 answer
4k views

Does NP mean verifiable in polynomial time or solvable in polynomial time? [duplicate]

Is NP defined as verifiable in polynomial time, or solvable in polynomial time? Verifiable meaning that the solution can be checked in polynomial time, and solvable meaning that the solution can be ...
Alecto Irene Perez's user avatar
-1 votes
1 answer
2k views

If I solve hard instance, therefore I prove NP=P? [duplicate]

If someone (off-topic) asks a question (on-topic) like this: Suppose that he claims that $\mathcal{P=NP}$. Suppose that someone else (on-topic) gives him an instance of an NP-complete problem that ...
Learning's user avatar
  • 149
1 vote
2 answers
1k views

NP hard relation with NP complete [duplicate]

If any problem P is NP complete then if there is a polynomial time reduction of P to another problem R then what can we say about R.Is it NP-hard or NP complete ? From Theory of computation of ...
TcKO's user avatar
  • 21
3 votes
2 answers
1k views

The exact relation between complexity classes and algorithm complexities [duplicate]

Are all algorithms which have polynomial time complexity belong to P class ? And P class do not have any algorithm which does have not polynomial complexity ? Are all algorithms which have non ...
avi's user avatar
  • 1,463
1 vote
1 answer
2k views

Is it immediately true that the class of P is a subset of the class NP? [duplicate]

Forgive me if this is a stupid question - it's been a while since I thought at all about complexity theory and I want to make sure that I have covered all the possible angles with regards to the ...
M Smith's user avatar
  • 467
-1 votes
1 answer
2k views

How to prove a Double CNF SAT is in NP [duplicate]

So I've been stuck trying to figure this problem out for a while. I've looked on wikis and all over stack exchange but I'm really stumped. This isn't my best subject, so any sort of explanation would ...
Mark's user avatar
  • 1
1 vote
1 answer
1k views

What is meant by problems not in NP but in NP hard? [duplicate]

If there is a proof that an NP-Hard problem which is not NP-Complete can be solved in P time, it does say that the verification time is polynomial too. Why doesn't it then mean that all NP-Hard are ...
Tarun Maganti's user avatar
3 votes
0 answers
2k views

Does NP-hard problems have to be decision problems? [duplicate]

According to the selected answer on this question NP-hard problems do NOT have to be decision problem. But by definition all NP-hard problems can be karp-reduced from any NP-problem in polynomial time;...
Ferus's user avatar
  • 143
0 votes
2 answers
774 views

Definition of NP [duplicate]

We know that NP is the class of languages recognized by a nondeterministic Turing machine (NTM) in polynomial time. I've also read that NP is the class of problems can be solved by NTM in polynomial ...
asv's user avatar
  • 345
1 vote
1 answer
1k views

How to prove membership of NP [duplicate]

My tutor often says that proving membership of NP is the easy part of proving that a problem is NP-complete, and that this should only take a minute. What I don't understand is what exactly you're ...
anon's user avatar
  • 113
0 votes
1 answer
858 views

Would a polynomial-time algorithm for an NP-hard problem implies that P=NP? [duplicate]

An NP-hard problem is not in NP. (If it was in NP, it would be an NP-complete problem not NP-hard.) So my question is: if someone can find a polynomial-time algorithm for an NP-hard problem, would ...
drzbir's user avatar
  • 990

15 30 50 per page
1
2 3 4 5
10