Linked Questions
137 questions linked to/from What is the definition of P, NP, NP-complete and NP-hard?
28
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 ...
- 2,211
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?
- 503
0
votes
1
answer
4k
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 ...
- 103
2
votes
2
answers
821
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
...
- 2,211
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 ...
- 564
-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 ...
- 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 ...
- 21
1
vote
1
answer
3k
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 ...
- 467
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 ...
- 1,473
-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 ...
- 1
1
vote
1
answer
2k
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 ...
- 123
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;...
- 143
0
votes
2
answers
824
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 ...
- 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 ...
- 113
0
votes
1
answer
888
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 ...
- 990