72k views

### What exactly is polynomial time? [duplicate]

I'm trying to understand algorithm complexity, and a lot of algorithms are classified as polynomial. I couldn't find an exact definition anywhere. I assume it is the complexity that is not exponential....
15k 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 ...
2k 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?
673 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 ...
2k 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 ...
1k 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 ...
3k 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 ...
785 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 ...
998 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 ...
1k 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 ...
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 ...
532 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 ...
691 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 ...
880 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 ...
742 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;...
491 views

### Can someone provide an introductory example of a certificate in complexity theory? [duplicate]

Just stepping into complexity theory, I am befuddled by this notion of a certificate and can't find any utility of this concept. From my understanding, a certificate is used when you are trying to ...
364 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 ...
203 views

### Can someone explain in a simple way what “reducible” mean in complexity theory? [duplicate]

I find the word "reducible" used in complexity theory not very intuitive, and too general taken on a face value. What does it exactly mean by problem A reducible to B? Does it mean that A can be ...
271 views

### How is the complexity of algorithms to solve 3CNF (decision problem) specified? [duplicate]

For k inputs, the complexity of naive algorithm is O(2^k). I understood this one. What is meant by "the size of the instance to be solved should be polynomial in k". Is it equivalent to the statement ...
150 views

### complexity theory NP [duplicate]

Ok, I really need help because I have read in so many books but still don't understand the complexity class NP. These are the books: Theoretische Informatik; Katrin Erk, Lutz Priese (german) ...
150 views

### How do we know that all NP problems reduce to NP-hard problems? [duplicate]

For example, how is it proven that any NP problem can reduce to subset sum, circuit satisfiability, etc.? Or could you link to a proof?
67 views

### P versus NP and what we are looking for [duplicate]

I was reading the other day about this problem, refreshing it, and on a couple of places over the internet I read somebody explaining something in the line of '..does not matter as long as is ...
100 views

### Does classification of a problem also require the algorithm used? [duplicate]

Just learnt that a problem in computer science can be divided into the following categories Polynomial problems NP problems NP hard problems NP complete problems ...
44 views

### Why does $L\subseteq \textbf{P} \cap \textbf{NP}$ is $\textbf{NP}$-complete imply $\textbf{NP} = \textbf{P}$? [duplicate]

If I show that a language $L$ is contained in $\textbf{P}$ and $\textbf{NP}$ and I know that the language is $\textbf{NP}$-complete, why did I proof that $\textbf{P} = \textbf{NP}$?
112 views

### The defining property of problems in NP [duplicate]

I'm coming to Computer Science from Mathematics and am familiar with the idea of building classes of objects using Propositional Logic. Namely, start with some universe of objects, define some ...
51 views

### Given an integer n, print all integers from 1 to 2^n. Why does this not prove that P!=NP? [duplicate]

I only just recently learned about the P=NP problem in introduction to algorithms class, and I'm still trying to wrap my head around it. I thought of this situation while cleaning my room today and ...
69 views

### Reducible and NP Hard [duplicate]

I have been confusing a bit about these relationship: Given A polynomial reducible to B 1/ If A is NP hard, what is the hardness of B? 2/ If B is NP hard, what is the hardness of A? 3/ If A has ...
55 views

### Why proving the solution of a problem is polynomial time is sufficient enough to say that it is a NP prolbem? [duplicate]

Why proving that we can verify the solution of a problem is polynomial time is sufficient enough to say that the problem is nondeterministic polynomial time? Please note: this is not a question on how ...
I am trying to understand the definition / meaning of reduction. Is it correct to say that the statement "Problem $A$ reduces to Problem $B$ in $x$-time" is the same as writing $A \leq_{x} B$? For ...